]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
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. | |
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 | 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 | ||
73 | template <typename E> // E is the element type. | |
74 | class 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_ |