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