| 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. |
| 52 |
const E& element() const { return element_; } |
| 53 |
|
| 54 |
// Gets the next node in the queue. |
| 55 |
QueueNode* next() { return 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. |
| 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. |
| 76 |
Queue() : head_(nullptr), last_(nullptr), size_(0) {} |
| 77 |
|
| 78 |
// D'tor. Clears the queue. |
| 79 |
~Queue() { Clear(); } |
| 80 |
|
| 81 |
// Clears the queue. |
| 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. |
| 101 |
size_t Size() const { return size_; } |
| 102 |
|
| 103 |
// Gets the first element of the queue, or NULL if the queue is empty. |
| 104 |
QueueNode<E>* Head() { return 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. |
| 108 |
QueueNode<E>* Last() { return 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. |
| 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. |
| 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> |
| 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_ |