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. 43template <typename E> // E is the element type 44class 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. 48template <typename E> // E is the element type 49class 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 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 73template <typename E> // E is the element type. 74class Queue { 75 public: 76 // Creates an empty queue. 77 Queue() : head_(NULL), last_(NULL), size_(0) {} 78 79 // D'tor. Clears the queue. 80 ~Queue() { Clear(); } 81 82 // Clears the queue. 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. 102 size_t Size() const { return size_; } 103 104 // Gets the first element of the queue, or NULL if the queue is empty. 105 QueueNode<E>* Head() { return 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. 109 QueueNode<E>* Last() { return 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. 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. 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> 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