proxygen
sample3-inl.h
Go to the documentation of this file.
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 
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_
~Queue()
Definition: sample3-inl.h:80
const QueueNode & operator=(const QueueNode &)
Queue()
Definition: sample3-inl.h:77
size_t size_
Definition: sample3-inl.h:165
QueueNode< E > * head_
Definition: sample3-inl.h:163
const QueueNode * next() const
Definition: sample3-inl.h:58
QueueNode< E > * Head()
Definition: sample3-inl.h:105
QueueNode< E > * last_
Definition: sample3-inl.h:164
QueueNode< E > * Last()
Definition: sample3-inl.h:109
const E & element() const
Definition: sample3-inl.h:54
size_t Size() const
Definition: sample3-inl.h:102
void Clear()
Definition: sample3-inl.h:83
void Enqueue(const E &element)
Definition: sample3-inl.h:116
QueueNode(const E &an_element)
Definition: sample3-inl.h:63
const QueueNode< E > * Last() const
Definition: sample3-inl.h:110
QueueNode * next()
Definition: sample3-inl.h:57
QueueNode * next_
Definition: sample3-inl.h:70
const QueueNode< E > * Head() const
Definition: sample3-inl.h:106
Queue * Map(F function) const
Definition: sample3-inl.h:153
E * Dequeue()
Definition: sample3-inl.h:131