Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Queue.hpp @ 24:028689700a47

find changesets by author, revision, files, or words in the commit message
Updated Queue to have a const_iterator too and to support a copy constructor (problem 1.3.41
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 14:52:17 -0500
parents a149b424b4e2
children 3cdac4c29445
rev   line source
discordia@16 1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
discordia@16 2
discordia@8 3 #ifndef QUEUE_HPP
discordia@8 4 #define QUEUE_HPP
discordia@8 5
discordia@8 6 #include <cstddef>
discordia@16 7 #include <cassert>
discordia@24 8 #include <iterator>
discordia@8 9
discordia@8 10 template <typename T>
discordia@8 11 class Queue {
discordia@8 12
discordia@9 13 private:
discordia@8 14
discordia@8 15 ////////////////////////////////////
discordia@8 16 class Node {
discordia@8 17 public:
discordia@8 18 T item;
discordia@8 19 Node *next;
discordia@8 20 };
discordia@8 21
discordia@9 22 public:
discordia@8 23
discordia@8 24 ////////////////////////////////////
discordia@24 25 class iterator : public std::iterator<std::forward_iterator_tag, T> {
discordia@8 26
discordia@8 27 public:
discordia@8 28
discordia@8 29 iterator( Node *c );
discordia@8 30
discordia@8 31 iterator& operator++();
discordia@8 32 iterator operator++(int);
discordia@8 33
discordia@8 34 T operator*();
discordia@8 35 bool operator!=( typename Queue<T>::iterator );
discordia@8 36
discordia@8 37 private:
discordia@8 38
discordia@8 39 Node *curr;
discordia@8 40 };
discordia@8 41
discordia@8 42 ////////////////////////////////////
discordia@8 43
discordia@24 44 class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
discordia@24 45
discordia@24 46 public:
discordia@24 47
discordia@24 48 const_iterator( const Node *c );
discordia@24 49
discordia@24 50 const_iterator& operator++();
discordia@24 51 const_iterator operator++(int);
discordia@24 52
discordia@24 53 const T operator*();
discordia@24 54 bool operator!=( typename Queue<T>::const_iterator );
discordia@24 55
discordia@24 56 private:
discordia@24 57
discordia@24 58 const Node *curr;
discordia@24 59 };
discordia@24 60
discordia@24 61 ////////////////////////////////////
discordia@24 62
discordia@8 63 Queue( void );
discordia@8 64 ~Queue( void );
discordia@8 65
discordia@24 66 // 1.3.41 Copy constructor.
discordia@24 67 Queue( const Queue<T> &q );
discordia@24 68
discordia@8 69 void enqueue( T &item );
discordia@8 70 T dequeue( void );
discordia@8 71
discordia@8 72 bool is_empty( void );
discordia@8 73 size_t size( void );
discordia@8 74
discordia@8 75 iterator begin( void );
discordia@8 76 iterator end( void );
discordia@24 77 const_iterator begin( void ) const;
discordia@24 78 const_iterator end( void ) const;
discordia@8 79
discordia@9 80
discordia@8 81 private:
discordia@8 82
discordia@8 83 size_t N;
discordia@8 84 Node *first;
discordia@8 85 Node *last;
discordia@8 86
discordia@8 87 };
discordia@8 88
discordia@8 89
discordia@16 90 template <typename T>
discordia@16 91 Queue<T>::Queue( void ) :
discordia@16 92 N (0),
discordia@16 93 first (nullptr),
discordia@16 94 last (nullptr)
discordia@16 95 {
discordia@16 96 }
discordia@24 97
discordia@24 98 // 1.3.41
discordia@24 99 template <typename T>
discordia@24 100 Queue<T>::Queue( const Queue<T> &q ) :
discordia@24 101 N (0),
discordia@24 102 first (nullptr),
discordia@24 103 last (nullptr)
discordia@24 104 {
discordia@24 105 for ( auto it = q.begin(); it != q.end(); ++it ) {
discordia@24 106 T item = *it;
discordia@24 107 this->enqueue( item );
discordia@24 108 }
discordia@24 109 }
discordia@16 110
discordia@16 111 template <typename T>
discordia@16 112 Queue<T>::~Queue( void ) {
discordia@16 113 assert( N == 0 ); // Catch the potential memory leak.
discordia@16 114 while ( first ) {
discordia@16 115 Node *next = first->next;
discordia@16 116 delete first;
discordia@16 117 first = next;
discordia@16 118 }
discordia@16 119 }
discordia@16 120
discordia@16 121 template <typename T>
discordia@16 122 void Queue<T>::enqueue( T &item ) {
discordia@16 123 Node * node = new Node();
discordia@16 124 node->item = item;
discordia@16 125 node->next = nullptr;
discordia@16 126
discordia@16 127 if ( last ) {
discordia@16 128 last->next = node;
discordia@16 129 last = node;
discordia@16 130 }
discordia@16 131 else {
discordia@16 132 last = first = node;
discordia@16 133 }
discordia@16 134
discordia@16 135 N++;
discordia@16 136 }
discordia@16 137
discordia@16 138 template <typename T>
discordia@16 139 T Queue<T>::dequeue( void ) {
discordia@16 140 assert( N > 0 );
discordia@16 141
discordia@16 142 T item = first->item;
discordia@16 143
discordia@16 144 Node *old = first;
discordia@16 145 first = first->next;
discordia@16 146 delete old;
discordia@16 147 N--;
discordia@16 148
discordia@16 149 if ( ! first )
discordia@16 150 last = nullptr;
discordia@16 151
discordia@16 152 return item;
discordia@16 153 }
discordia@16 154
discordia@16 155 template <typename T>
discordia@16 156 bool Queue<T>::is_empty( void ) {
discordia@16 157 return N == 0;
discordia@16 158 }
discordia@16 159
discordia@16 160 template <typename T>
discordia@16 161 size_t Queue<T>::size( void ) {
discordia@16 162 return N;
discordia@16 163 }
discordia@16 164
discordia@16 165 template <typename T>
discordia@16 166 typename Queue<T>::iterator Queue<T>::begin( void ) {
discordia@16 167 return Queue<T>::iterator( first );
discordia@16 168 }
discordia@16 169
discordia@16 170 template <typename T>
discordia@16 171 typename Queue<T>::iterator Queue<T>::end( void ) {
discordia@16 172 return Queue<T>::iterator( nullptr );
discordia@16 173 }
discordia@16 174
discordia@24 175 template <typename T>
discordia@24 176 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
discordia@24 177 return Queue<T>::const_iterator( first );
discordia@24 178 }
discordia@24 179
discordia@24 180 template <typename T>
discordia@24 181 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
discordia@24 182 return Queue<T>::const_iterator( nullptr );
discordia@24 183 }
discordia@24 184
discordia@16 185
discordia@16 186 ////////////////////////////////////////////////////////////////////////////////
discordia@16 187
discordia@16 188 template <typename T>
discordia@16 189 Queue<T>::iterator::iterator( Node *c ) :
discordia@16 190 curr (c)
discordia@16 191 {
discordia@16 192 }
discordia@16 193
discordia@16 194 template <typename T>
discordia@16 195 typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
discordia@16 196 if ( this->curr != nullptr ) {
discordia@16 197 this->curr = this->curr->next;
discordia@16 198 }
discordia@16 199 return *this;
discordia@16 200 }
discordia@16 201
discordia@16 202 template <typename T>
discordia@16 203 typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
discordia@16 204 auto t = Queue<T>::iterator( *this );
discordia@16 205
discordia@16 206 if ( this->curr != nullptr ) {
discordia@16 207 this->curr = this->curr->next;
discordia@16 208 }
discordia@16 209 return t;
discordia@16 210 }
discordia@16 211
discordia@16 212 template <typename T>
discordia@16 213 T Queue<T>::iterator::operator*() {
discordia@16 214 return this->curr->item;
discordia@16 215 }
discordia@16 216
discordia@16 217 template <typename T>
discordia@16 218 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
discordia@16 219 return this->curr != other.curr;
discordia@16 220 }
discordia@16 221
discordia@24 222 ////////////////////////////////////////////////////////////////////////////////
discordia@24 223
discordia@24 224 template <typename T>
discordia@24 225 Queue<T>::const_iterator::const_iterator( const Node *c ) :
discordia@24 226 curr (c)
discordia@24 227 {
discordia@24 228 }
discordia@24 229
discordia@24 230 template <typename T>
discordia@24 231 typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() {
discordia@24 232 if ( this->curr != nullptr ) {
discordia@24 233 this->curr = this->curr->next;
discordia@24 234 }
discordia@24 235 return *this;
discordia@24 236 }
discordia@24 237
discordia@24 238 template <typename T>
discordia@24 239 typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) {
discordia@24 240 auto t = Queue<T>::const_iterator( *this );
discordia@24 241
discordia@24 242 if ( this->curr != nullptr ) {
discordia@24 243 this->curr = this->curr->next;
discordia@24 244 }
discordia@24 245 return t;
discordia@24 246 }
discordia@24 247
discordia@24 248 template <typename T>
discordia@24 249 const T Queue<T>::const_iterator::operator*() {
discordia@24 250 return this->curr->item;
discordia@24 251 }
discordia@24 252
discordia@24 253 template <typename T>
discordia@24 254 bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) {
discordia@24 255 return this->curr != other.curr;
discordia@24 256 }
discordia@24 257
discordia@8 258
discordia@8 259 #endif
discordia@8 260