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