1d201456903f3ecae1f7794edfab0d5678e64226shiqian// Copyright 2005, Google Inc. 2d201456903f3ecae1f7794edfab0d5678e64226shiqian// All rights reserved. 3d201456903f3ecae1f7794edfab0d5678e64226shiqian// 4d201456903f3ecae1f7794edfab0d5678e64226shiqian// Redistribution and use in source and binary forms, with or without 5d201456903f3ecae1f7794edfab0d5678e64226shiqian// modification, are permitted provided that the following conditions are 6d201456903f3ecae1f7794edfab0d5678e64226shiqian// met: 7d201456903f3ecae1f7794edfab0d5678e64226shiqian// 8d201456903f3ecae1f7794edfab0d5678e64226shiqian// * Redistributions of source code must retain the above copyright 9d201456903f3ecae1f7794edfab0d5678e64226shiqian// notice, this list of conditions and the following disclaimer. 10d201456903f3ecae1f7794edfab0d5678e64226shiqian// * Redistributions in binary form must reproduce the above 11d201456903f3ecae1f7794edfab0d5678e64226shiqian// copyright notice, this list of conditions and the following disclaimer 12d201456903f3ecae1f7794edfab0d5678e64226shiqian// in the documentation and/or other materials provided with the 13d201456903f3ecae1f7794edfab0d5678e64226shiqian// distribution. 14d201456903f3ecae1f7794edfab0d5678e64226shiqian// * Neither the name of Google Inc. nor the names of its 15d201456903f3ecae1f7794edfab0d5678e64226shiqian// contributors may be used to endorse or promote products derived from 16d201456903f3ecae1f7794edfab0d5678e64226shiqian// this software without specific prior written permission. 17d201456903f3ecae1f7794edfab0d5678e64226shiqian// 18d201456903f3ecae1f7794edfab0d5678e64226shiqian// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19d201456903f3ecae1f7794edfab0d5678e64226shiqian// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20d201456903f3ecae1f7794edfab0d5678e64226shiqian// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21d201456903f3ecae1f7794edfab0d5678e64226shiqian// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22d201456903f3ecae1f7794edfab0d5678e64226shiqian// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23d201456903f3ecae1f7794edfab0d5678e64226shiqian// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24d201456903f3ecae1f7794edfab0d5678e64226shiqian// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25d201456903f3ecae1f7794edfab0d5678e64226shiqian// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26d201456903f3ecae1f7794edfab0d5678e64226shiqian// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27d201456903f3ecae1f7794edfab0d5678e64226shiqian// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28d201456903f3ecae1f7794edfab0d5678e64226shiqian// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29d201456903f3ecae1f7794edfab0d5678e64226shiqian 30d201456903f3ecae1f7794edfab0d5678e64226shiqian// A sample program demonstrating using Google C++ testing framework. 31d201456903f3ecae1f7794edfab0d5678e64226shiqian// 32d201456903f3ecae1f7794edfab0d5678e64226shiqian// Author: wan@google.com (Zhanyong Wan) 33d201456903f3ecae1f7794edfab0d5678e64226shiqian 34d201456903f3ecae1f7794edfab0d5678e64226shiqian#ifndef GTEST_SAMPLES_SAMPLE3_INL_H_ 35d201456903f3ecae1f7794edfab0d5678e64226shiqian#define GTEST_SAMPLES_SAMPLE3_INL_H_ 36d201456903f3ecae1f7794edfab0d5678e64226shiqian 37d201456903f3ecae1f7794edfab0d5678e64226shiqian#include <stddef.h> 38d201456903f3ecae1f7794edfab0d5678e64226shiqian 39d201456903f3ecae1f7794edfab0d5678e64226shiqian 40d201456903f3ecae1f7794edfab0d5678e64226shiqian// Queue is a simple queue implemented as a singled-linked list. 41d201456903f3ecae1f7794edfab0d5678e64226shiqian// 42d201456903f3ecae1f7794edfab0d5678e64226shiqian// The element type must support copy constructor. 43d201456903f3ecae1f7794edfab0d5678e64226shiqiantemplate <typename E> // E is the element type 44d201456903f3ecae1f7794edfab0d5678e64226shiqianclass Queue; 45d201456903f3ecae1f7794edfab0d5678e64226shiqian 46d201456903f3ecae1f7794edfab0d5678e64226shiqian// QueueNode is a node in a Queue, which consists of an element of 47d201456903f3ecae1f7794edfab0d5678e64226shiqian// type E and a pointer to the next node. 48d201456903f3ecae1f7794edfab0d5678e64226shiqiantemplate <typename E> // E is the element type 49d201456903f3ecae1f7794edfab0d5678e64226shiqianclass QueueNode { 50d201456903f3ecae1f7794edfab0d5678e64226shiqian friend class Queue<E>; 51d201456903f3ecae1f7794edfab0d5678e64226shiqian 52d201456903f3ecae1f7794edfab0d5678e64226shiqian public: 53d201456903f3ecae1f7794edfab0d5678e64226shiqian // Gets the element in this node. 54fe7876095950ad3be55babb27604d138fed4ec21vladlosev const E& element() const { return element_; } 55d201456903f3ecae1f7794edfab0d5678e64226shiqian 56d201456903f3ecae1f7794edfab0d5678e64226shiqian // Gets the next node in the queue. 57fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode* next() { return next_; } 58fe7876095950ad3be55babb27604d138fed4ec21vladlosev const QueueNode* next() const { return next_; } 59d201456903f3ecae1f7794edfab0d5678e64226shiqian 60d201456903f3ecae1f7794edfab0d5678e64226shiqian private: 61d201456903f3ecae1f7794edfab0d5678e64226shiqian // Creates a node with a given element value. The next pointer is 62d201456903f3ecae1f7794edfab0d5678e64226shiqian // set to NULL. 638965a6a0d2165f32e6413594bba6367f271f51e7vladlosev explicit QueueNode(const E& an_element) : element_(an_element), next_(NULL) {} 64d201456903f3ecae1f7794edfab0d5678e64226shiqian 65d201456903f3ecae1f7794edfab0d5678e64226shiqian // We disable the default assignment operator and copy c'tor. 66fe7876095950ad3be55babb27604d138fed4ec21vladlosev const QueueNode& operator = (const QueueNode&); 67fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode(const QueueNode&); 68d201456903f3ecae1f7794edfab0d5678e64226shiqian 69d201456903f3ecae1f7794edfab0d5678e64226shiqian E element_; 70fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode* next_; 71d201456903f3ecae1f7794edfab0d5678e64226shiqian}; 72d201456903f3ecae1f7794edfab0d5678e64226shiqian 73d201456903f3ecae1f7794edfab0d5678e64226shiqiantemplate <typename E> // E is the element type. 74d201456903f3ecae1f7794edfab0d5678e64226shiqianclass Queue { 758965a6a0d2165f32e6413594bba6367f271f51e7vladlosev public: 76d201456903f3ecae1f7794edfab0d5678e64226shiqian // Creates an empty queue. 77d201456903f3ecae1f7794edfab0d5678e64226shiqian Queue() : head_(NULL), last_(NULL), size_(0) {} 78d201456903f3ecae1f7794edfab0d5678e64226shiqian 79d201456903f3ecae1f7794edfab0d5678e64226shiqian // D'tor. Clears the queue. 80d201456903f3ecae1f7794edfab0d5678e64226shiqian ~Queue() { Clear(); } 81d201456903f3ecae1f7794edfab0d5678e64226shiqian 82d201456903f3ecae1f7794edfab0d5678e64226shiqian // Clears the queue. 83d201456903f3ecae1f7794edfab0d5678e64226shiqian void Clear() { 84d201456903f3ecae1f7794edfab0d5678e64226shiqian if (size_ > 0) { 85d201456903f3ecae1f7794edfab0d5678e64226shiqian // 1. Deletes every node. 86fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* node = head_; 87fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* next = node->next(); 88d201456903f3ecae1f7794edfab0d5678e64226shiqian for (; ;) { 89d201456903f3ecae1f7794edfab0d5678e64226shiqian delete node; 90d201456903f3ecae1f7794edfab0d5678e64226shiqian node = next; 91d201456903f3ecae1f7794edfab0d5678e64226shiqian if (node == NULL) break; 92d201456903f3ecae1f7794edfab0d5678e64226shiqian next = node->next(); 93d201456903f3ecae1f7794edfab0d5678e64226shiqian } 94d201456903f3ecae1f7794edfab0d5678e64226shiqian 95d201456903f3ecae1f7794edfab0d5678e64226shiqian // 2. Resets the member variables. 96d201456903f3ecae1f7794edfab0d5678e64226shiqian head_ = last_ = NULL; 97d201456903f3ecae1f7794edfab0d5678e64226shiqian size_ = 0; 98d201456903f3ecae1f7794edfab0d5678e64226shiqian } 99d201456903f3ecae1f7794edfab0d5678e64226shiqian } 100d201456903f3ecae1f7794edfab0d5678e64226shiqian 101d201456903f3ecae1f7794edfab0d5678e64226shiqian // Gets the number of elements. 102d201456903f3ecae1f7794edfab0d5678e64226shiqian size_t Size() const { return size_; } 103d201456903f3ecae1f7794edfab0d5678e64226shiqian 104d201456903f3ecae1f7794edfab0d5678e64226shiqian // Gets the first element of the queue, or NULL if the queue is empty. 105fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* Head() { return head_; } 106fe7876095950ad3be55babb27604d138fed4ec21vladlosev const QueueNode<E>* Head() const { return head_; } 107d201456903f3ecae1f7794edfab0d5678e64226shiqian 108d201456903f3ecae1f7794edfab0d5678e64226shiqian // Gets the last element of the queue, or NULL if the queue is empty. 109fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* Last() { return last_; } 110fe7876095950ad3be55babb27604d138fed4ec21vladlosev const QueueNode<E>* Last() const { return last_; } 111d201456903f3ecae1f7794edfab0d5678e64226shiqian 112d201456903f3ecae1f7794edfab0d5678e64226shiqian // Adds an element to the end of the queue. A copy of the element is 113d201456903f3ecae1f7794edfab0d5678e64226shiqian // created using the copy constructor, and then stored in the queue. 114d201456903f3ecae1f7794edfab0d5678e64226shiqian // Changes made to the element in the queue doesn't affect the source 115d201456903f3ecae1f7794edfab0d5678e64226shiqian // object, and vice versa. 116fe7876095950ad3be55babb27604d138fed4ec21vladlosev void Enqueue(const E& element) { 117fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* new_node = new QueueNode<E>(element); 118d201456903f3ecae1f7794edfab0d5678e64226shiqian 119d201456903f3ecae1f7794edfab0d5678e64226shiqian if (size_ == 0) { 120d201456903f3ecae1f7794edfab0d5678e64226shiqian head_ = last_ = new_node; 121d201456903f3ecae1f7794edfab0d5678e64226shiqian size_ = 1; 122d201456903f3ecae1f7794edfab0d5678e64226shiqian } else { 123d201456903f3ecae1f7794edfab0d5678e64226shiqian last_->next_ = new_node; 124d201456903f3ecae1f7794edfab0d5678e64226shiqian last_ = new_node; 125d201456903f3ecae1f7794edfab0d5678e64226shiqian size_++; 126d201456903f3ecae1f7794edfab0d5678e64226shiqian } 127d201456903f3ecae1f7794edfab0d5678e64226shiqian } 128d201456903f3ecae1f7794edfab0d5678e64226shiqian 129d201456903f3ecae1f7794edfab0d5678e64226shiqian // Removes the head of the queue and returns it. Returns NULL if 130d201456903f3ecae1f7794edfab0d5678e64226shiqian // the queue is empty. 131fe7876095950ad3be55babb27604d138fed4ec21vladlosev E* Dequeue() { 132d201456903f3ecae1f7794edfab0d5678e64226shiqian if (size_ == 0) { 133d201456903f3ecae1f7794edfab0d5678e64226shiqian return NULL; 134d201456903f3ecae1f7794edfab0d5678e64226shiqian } 135d201456903f3ecae1f7794edfab0d5678e64226shiqian 136fe7876095950ad3be55babb27604d138fed4ec21vladlosev const QueueNode<E>* const old_head = head_; 137d201456903f3ecae1f7794edfab0d5678e64226shiqian head_ = head_->next_; 138d201456903f3ecae1f7794edfab0d5678e64226shiqian size_--; 139d201456903f3ecae1f7794edfab0d5678e64226shiqian if (size_ == 0) { 140d201456903f3ecae1f7794edfab0d5678e64226shiqian last_ = NULL; 141d201456903f3ecae1f7794edfab0d5678e64226shiqian } 142d201456903f3ecae1f7794edfab0d5678e64226shiqian 143fe7876095950ad3be55babb27604d138fed4ec21vladlosev E* element = new E(old_head->element()); 144d201456903f3ecae1f7794edfab0d5678e64226shiqian delete old_head; 145d201456903f3ecae1f7794edfab0d5678e64226shiqian 146d201456903f3ecae1f7794edfab0d5678e64226shiqian return element; 147d201456903f3ecae1f7794edfab0d5678e64226shiqian } 148d201456903f3ecae1f7794edfab0d5678e64226shiqian 149d201456903f3ecae1f7794edfab0d5678e64226shiqian // Applies a function/functor on each element of the queue, and 150d201456903f3ecae1f7794edfab0d5678e64226shiqian // returns the result in a new queue. The original queue is not 151d201456903f3ecae1f7794edfab0d5678e64226shiqian // affected. 152d201456903f3ecae1f7794edfab0d5678e64226shiqian template <typename F> 153fe7876095950ad3be55babb27604d138fed4ec21vladlosev Queue* Map(F function) const { 154fe7876095950ad3be55babb27604d138fed4ec21vladlosev Queue* new_queue = new Queue(); 155fe7876095950ad3be55babb27604d138fed4ec21vladlosev for (const QueueNode<E>* node = head_; node != NULL; node = node->next_) { 156d201456903f3ecae1f7794edfab0d5678e64226shiqian new_queue->Enqueue(function(node->element())); 157d201456903f3ecae1f7794edfab0d5678e64226shiqian } 158d201456903f3ecae1f7794edfab0d5678e64226shiqian 159d201456903f3ecae1f7794edfab0d5678e64226shiqian return new_queue; 160d201456903f3ecae1f7794edfab0d5678e64226shiqian } 161d201456903f3ecae1f7794edfab0d5678e64226shiqian 162d201456903f3ecae1f7794edfab0d5678e64226shiqian private: 163fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* head_; // The first node of the queue. 164fe7876095950ad3be55babb27604d138fed4ec21vladlosev QueueNode<E>* last_; // The last node of the queue. 165d201456903f3ecae1f7794edfab0d5678e64226shiqian size_t size_; // The number of elements in the queue. 166d201456903f3ecae1f7794edfab0d5678e64226shiqian 167d201456903f3ecae1f7794edfab0d5678e64226shiqian // We disallow copying a queue. 168fe7876095950ad3be55babb27604d138fed4ec21vladlosev Queue(const Queue&); 169fe7876095950ad3be55babb27604d138fed4ec21vladlosev const Queue& operator = (const Queue&); 1708965a6a0d2165f32e6413594bba6367f271f51e7vladlosev}; 171d201456903f3ecae1f7794edfab0d5678e64226shiqian 172d201456903f3ecae1f7794edfab0d5678e64226shiqian#endif // GTEST_SAMPLES_SAMPLE3_INL_H_ 173