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 #ifndef GOOGLETEST_SAMPLES_SAMPLE3_INL_H_ 33 #define GOOGLETEST_SAMPLES_SAMPLE3_INL_H_ 34 35 #include <stddef.h> 36 37 38 // Queue is a simple queue implemented as a singled-linked list. 39 // 40 // The element type must support copy constructor. 41 template <typename E> // E is the element type 42 class Queue; 43 44 // QueueNode is a node in a Queue, which consists of an element of 45 // type E and a pointer to the next node. 46 template <typename E> // E is the element type 47 class QueueNode { 48 friend class Queue<E>; 49 50 public: 51 // Gets the element in this node. element()52 const E& element() const { return element_; } 53 54 // Gets the next node in the queue. next()55 QueueNode* next() { return next_; } next()56 const QueueNode* next() const { return next_; } 57 58 private: 59 // Creates a node with a given element value. The next pointer is 60 // set to NULL. QueueNode(const E & an_element)61 explicit QueueNode(const E& an_element) 62 : element_(an_element), next_(nullptr) {} 63 64 // We disable the default assignment operator and copy c'tor. 65 const QueueNode& operator = (const QueueNode&); 66 QueueNode(const QueueNode&); 67 68 E element_; 69 QueueNode* next_; 70 }; 71 72 template <typename E> // E is the element type. 73 class Queue { 74 public: 75 // Creates an empty queue. Queue()76 Queue() : head_(nullptr), last_(nullptr), size_(0) {} 77 78 // D'tor. Clears the queue. ~Queue()79 ~Queue() { Clear(); } 80 81 // Clears the queue. Clear()82 void Clear() { 83 if (size_ > 0) { 84 // 1. Deletes every node. 85 QueueNode<E>* node = head_; 86 QueueNode<E>* next = node->next(); 87 for (; ;) { 88 delete node; 89 node = next; 90 if (node == nullptr) break; 91 next = node->next(); 92 } 93 94 // 2. Resets the member variables. 95 head_ = last_ = nullptr; 96 size_ = 0; 97 } 98 } 99 100 // Gets the number of elements. Size()101 size_t Size() const { return size_; } 102 103 // Gets the first element of the queue, or NULL if the queue is empty. Head()104 QueueNode<E>* Head() { return head_; } Head()105 const QueueNode<E>* Head() const { return head_; } 106 107 // Gets the last element of the queue, or NULL if the queue is empty. Last()108 QueueNode<E>* Last() { return last_; } Last()109 const QueueNode<E>* Last() const { return last_; } 110 111 // Adds an element to the end of the queue. A copy of the element is 112 // created using the copy constructor, and then stored in the queue. 113 // Changes made to the element in the queue doesn't affect the source 114 // object, and vice versa. Enqueue(const E & element)115 void Enqueue(const E& element) { 116 QueueNode<E>* new_node = new QueueNode<E>(element); 117 118 if (size_ == 0) { 119 head_ = last_ = new_node; 120 size_ = 1; 121 } else { 122 last_->next_ = new_node; 123 last_ = new_node; 124 size_++; 125 } 126 } 127 128 // Removes the head of the queue and returns it. Returns NULL if 129 // the queue is empty. Dequeue()130 E* Dequeue() { 131 if (size_ == 0) { 132 return nullptr; 133 } 134 135 const QueueNode<E>* const old_head = head_; 136 head_ = head_->next_; 137 size_--; 138 if (size_ == 0) { 139 last_ = nullptr; 140 } 141 142 E* element = new E(old_head->element()); 143 delete old_head; 144 145 return element; 146 } 147 148 // Applies a function/functor on each element of the queue, and 149 // returns the result in a new queue. The original queue is not 150 // affected. 151 template <typename F> Map(F function)152 Queue* Map(F function) const { 153 Queue* new_queue = new Queue(); 154 for (const QueueNode<E>* node = head_; node != nullptr; 155 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 // GOOGLETEST_SAMPLES_SAMPLE3_INL_H_ 173