]>
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. | |
31f18b77 FG |
31 | |
32 | #ifndef GTEST_SAMPLES_SAMPLE3_INL_H_ | |
33 | #define GTEST_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. | |
1e59de90 TL |
61 | explicit QueueNode(const E& an_element) |
62 | : element_(an_element), next_(nullptr) {} | |
31f18b77 FG |
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. | |
1e59de90 | 76 | Queue() : head_(nullptr), last_(nullptr), size_(0) {} |
31f18b77 FG |
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; | |
1e59de90 | 90 | if (node == nullptr) break; |
31f18b77 FG |
91 | next = node->next(); |
92 | } | |
93 | ||
94 | // 2. Resets the member variables. | |
1e59de90 | 95 | head_ = last_ = nullptr; |
31f18b77 FG |
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) { | |
1e59de90 | 132 | return nullptr; |
31f18b77 FG |
133 | } |
134 | ||
135 | const QueueNode<E>* const old_head = head_; | |
136 | head_ = head_->next_; | |
137 | size_--; | |
138 | if (size_ == 0) { | |
1e59de90 | 139 | last_ = nullptr; |
31f18b77 FG |
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(); | |
1e59de90 TL |
154 | for (const QueueNode<E>* node = head_; node != nullptr; |
155 | node = node->next_) { | |
31f18b77 FG |
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_ |