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 (at) 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. 54 const E & element() const { return element_; } 55 56 // Gets the next node in the queue. 57 QueueNode * next() { return 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. 63 QueueNode(const E & element) : element_(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 77 // Creates an empty queue. 78 Queue() : head_(NULL), last_(NULL), size_(0) {} 79 80 // D'tor. Clears the queue. 81 ~Queue() { Clear(); } 82 83 // Clears the queue. 84 void Clear() { 85 if (size_ > 0) { 86 // 1. Deletes every node. 87 QueueNode<E> * node = head_; 88 QueueNode<E> * next = node->next(); 89 for (; ;) { 90 delete node; 91 node = next; 92 if (node == NULL) break; 93 next = node->next(); 94 } 95 96 // 2. Resets the member variables. 97 head_ = last_ = NULL; 98 size_ = 0; 99 } 100 } 101 102 // Gets the number of elements. 103 size_t Size() const { return size_; } 104 105 // Gets the first element of the queue, or NULL if the queue is empty. 106 QueueNode<E> * Head() { return head_; } 107 const QueueNode<E> * Head() const { return head_; } 108 109 // Gets the last element of the queue, or NULL if the queue is empty. 110 QueueNode<E> * Last() { return last_; } 111 const QueueNode<E> * Last() const { return last_; } 112 113 // Adds an element to the end of the queue. A copy of the element is 114 // created using the copy constructor, and then stored in the queue. 115 // Changes made to the element in the queue doesn't affect the source 116 // object, and vice versa. 117 void Enqueue(const E & element) { 118 QueueNode<E> * new_node = new QueueNode<E>(element); 119 120 if (size_ == 0) { 121 head_ = last_ = new_node; 122 size_ = 1; 123 } else { 124 last_->next_ = new_node; 125 last_ = new_node; 126 size_++; 127 } 128 } 129 130 // Removes the head of the queue and returns it. Returns NULL if 131 // the queue is empty. 132 E * Dequeue() { 133 if (size_ == 0) { 134 return NULL; 135 } 136 137 const QueueNode<E> * const old_head = head_; 138 head_ = head_->next_; 139 size_--; 140 if (size_ == 0) { 141 last_ = NULL; 142 } 143 144 E * element = new E(old_head->element()); 145 delete old_head; 146 147 return element; 148 } 149 150 // Applies a function/functor on each element of the queue, and 151 // returns the result in a new queue. The original queue is not 152 // affected. 153 template <typename F> 154 Queue * Map(F function) const { 155 Queue * new_queue = new Queue(); 156 for (const QueueNode<E> * node = head_; node != NULL; node = node->next_) { 157 new_queue->Enqueue(function(node->element())); 158 } 159 160 return new_queue; 161 } 162 163 private: 164 QueueNode<E> * head_; // The first node of the queue. 165 QueueNode<E> * last_; // The last node of the queue. 166 size_t size_; // The number of elements in the queue. 167 168 // We disallow copying a queue. 169 Queue(const Queue &); 170 const Queue & operator = (const Queue &); 171 }; 172 173 #endif // GTEST_SAMPLES_SAMPLE3_INL_H_ 174
