sample3-inl.h 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171
  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. // A sample program demonstrating using Google C++ testing framework.
  30. #ifndef GOOGLETEST_SAMPLES_SAMPLE3_INL_H_
  31. #define GOOGLETEST_SAMPLES_SAMPLE3_INL_H_
  32. #include <stddef.h>
  33. // Queue is a simple queue implemented as a singled-linked list.
  34. //
  35. // The element type must support copy constructor.
  36. template <typename E> // E is the element type
  37. class Queue;
  38. // QueueNode is a node in a Queue, which consists of an element of
  39. // type E and a pointer to the next node.
  40. template <typename E> // E is the element type
  41. class QueueNode {
  42. friend class Queue<E>;
  43. public:
  44. // Gets the element in this node.
  45. const E& element() const { return element_; }
  46. // Gets the next node in the queue.
  47. QueueNode* next() { return next_; }
  48. const QueueNode* next() const { return next_; }
  49. private:
  50. // Creates a node with a given element value. The next pointer is
  51. // set to NULL.
  52. explicit QueueNode(const E& an_element)
  53. : element_(an_element), next_(nullptr) {}
  54. // We disable the default assignment operator and copy c'tor.
  55. const QueueNode& operator=(const QueueNode&);
  56. QueueNode(const QueueNode&);
  57. E element_;
  58. QueueNode* next_;
  59. };
  60. template <typename E> // E is the element type.
  61. class Queue {
  62. public:
  63. // Creates an empty queue.
  64. Queue() : head_(nullptr), last_(nullptr), size_(0) {}
  65. // D'tor. Clears the queue.
  66. ~Queue() { Clear(); }
  67. // Clears the queue.
  68. void Clear() {
  69. if (size_ > 0) {
  70. // 1. Deletes every node.
  71. QueueNode<E>* node = head_;
  72. QueueNode<E>* next = node->next();
  73. for (;;) {
  74. delete node;
  75. node = next;
  76. if (node == nullptr) break;
  77. next = node->next();
  78. }
  79. // 2. Resets the member variables.
  80. head_ = last_ = nullptr;
  81. size_ = 0;
  82. }
  83. }
  84. // Gets the number of elements.
  85. size_t Size() const { return size_; }
  86. // Gets the first element of the queue, or NULL if the queue is empty.
  87. QueueNode<E>* Head() { return head_; }
  88. const QueueNode<E>* Head() const { return head_; }
  89. // Gets the last element of the queue, or NULL if the queue is empty.
  90. QueueNode<E>* Last() { return last_; }
  91. const QueueNode<E>* Last() const { return last_; }
  92. // Adds an element to the end of the queue. A copy of the element is
  93. // created using the copy constructor, and then stored in the queue.
  94. // Changes made to the element in the queue doesn't affect the source
  95. // object, and vice versa.
  96. void Enqueue(const E& element) {
  97. QueueNode<E>* new_node = new QueueNode<E>(element);
  98. if (size_ == 0) {
  99. head_ = last_ = new_node;
  100. size_ = 1;
  101. } else {
  102. last_->next_ = new_node;
  103. last_ = new_node;
  104. size_++;
  105. }
  106. }
  107. // Removes the head of the queue and returns it. Returns NULL if
  108. // the queue is empty.
  109. E* Dequeue() {
  110. if (size_ == 0) {
  111. return nullptr;
  112. }
  113. const QueueNode<E>* const old_head = head_;
  114. head_ = head_->next_;
  115. size_--;
  116. if (size_ == 0) {
  117. last_ = nullptr;
  118. }
  119. E* element = new E(old_head->element());
  120. delete old_head;
  121. return element;
  122. }
  123. // Applies a function/functor on each element of the queue, and
  124. // returns the result in a new queue. The original queue is not
  125. // affected.
  126. template <typename F>
  127. Queue* Map(F function) const {
  128. Queue* new_queue = new Queue();
  129. for (const QueueNode<E>* node = head_; node != nullptr;
  130. node = node->next_) {
  131. new_queue->Enqueue(function(node->element()));
  132. }
  133. return new_queue;
  134. }
  135. private:
  136. QueueNode<E>* head_; // The first node of the queue.
  137. QueueNode<E>* last_; // The last node of the queue.
  138. size_t size_; // The number of elements in the queue.
  139. // We disallow copying a queue.
  140. Queue(const Queue&);
  141. const Queue& operator=(const Queue&);
  142. };
  143. #endif // GOOGLETEST_SAMPLES_SAMPLE3_INL_H_