Mercurial > Algorithms__Sedgewick

comparison 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
comparison
equal deleted inserted replaced
3:bd438a3f0d9f 4:be6ea53dbdfa
3 #ifndef QUEUE_HPP 3 #ifndef QUEUE_HPP
4 #define QUEUE_HPP 4 #define QUEUE_HPP
5 5
6 #include <cstddef> 6 #include <cstddef>
7 #include <cassert> 7 #include <cassert>
8 #include <iterator>
8 9
9 template <typename T> 10 template <typename T>
10 class Queue { 11 class Queue {
11 12
12 private: 13 private:
19 }; 20 };
20 21
21 public: 22 public:
22 23
23 //////////////////////////////////// 24 ////////////////////////////////////
24 class iterator; 25 class iterator : public std::iterator<std::forward_iterator_tag, T> {
25 friend class iterator;
26 class iterator {
27 26
28 public: 27 public:
29 28
30 iterator( Node *c ); 29 iterator( Node *c );
31 30
40 Node *curr; 39 Node *curr;
41 }; 40 };
42 41
43 //////////////////////////////////// 42 ////////////////////////////////////
44 43
44 class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
45
46 public:
47
48 const_iterator( const Node *c );
49
50 const_iterator& operator++();
51 const_iterator operator++(int);
52
53 const T operator*();
54 bool operator!=( typename Queue<T>::const_iterator );
55
56 private:
57
58 const Node *curr;
59 };
60
61 ////////////////////////////////////
62
45 Queue( void ); 63 Queue( void );
46 ~Queue( void ); 64 ~Queue( void );
47 65
66 // 1.3.41 Copy constructor.
67 Queue( const Queue<T> &q );
68
48 void enqueue( T &item ); 69 void enqueue( T &item );
49 T dequeue( void ); 70 T dequeue( void );
50 71
51 bool is_empty( void ); 72 bool is_empty( void );
52 size_t size( void ); 73 size_t size( void );
53 74
54 iterator begin( void ); 75 iterator begin( void );
55 iterator end( void ); 76 iterator end( void );
77 const_iterator begin( void ) const;
78 const_iterator end( void ) const;
56 79
57 80
58 private: 81 private:
59 82
60 size_t N; 83 size_t N;
68 Queue<T>::Queue( void ) : 91 Queue<T>::Queue( void ) :
69 N (0), 92 N (0),
70 first (nullptr), 93 first (nullptr),
71 last (nullptr) 94 last (nullptr)
72 { 95 {
96 }
97
98 // 1.3.41
99 template <typename T>
100 Queue<T>::Queue( const Queue<T> &q ) :
101 N (0),
102 first (nullptr),
103 last (nullptr)
104 {
105 for ( auto it = q.begin(); it != q.end(); ++it ) {
106 T item = *it;
107 this->enqueue( item );
108 }
73 } 109 }
74 110
75 template <typename T> 111 template <typename T>
76 Queue<T>::~Queue( void ) { 112 Queue<T>::~Queue( void ) {
77 assert( N == 0 ); // Catch the potential memory leak. 113 assert( N == 0 ); // Catch the potential memory leak.
134 template <typename T> 170 template <typename T>
135 typename Queue<T>::iterator Queue<T>::end( void ) { 171 typename Queue<T>::iterator Queue<T>::end( void ) {
136 return Queue<T>::iterator( nullptr ); 172 return Queue<T>::iterator( nullptr );
137 } 173 }
138 174
175 template <typename T>
176 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
177 return Queue<T>::const_iterator( first );
178 }
179
180 template <typename T>
181 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
182 return Queue<T>::const_iterator( nullptr );
183 }
184
139 185
140 //////////////////////////////////////////////////////////////////////////////// 186 ////////////////////////////////////////////////////////////////////////////////
141 187
142 template <typename T> 188 template <typename T>
143 Queue<T>::iterator::iterator( Node *c ) : 189 Queue<T>::iterator::iterator( Node *c ) :
171 template <typename T> 217 template <typename T>
172 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) { 218 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
173 return this->curr != other.curr; 219 return this->curr != other.curr;
174 } 220 }
175 221
222 ////////////////////////////////////////////////////////////////////////////////
223
224 template <typename T>
225 Queue<T>::const_iterator::const_iterator( const Node *c ) :
226 curr (c)
227 {
228 }
229
230 template <typename T>
231 typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() {
232 if ( this->curr != nullptr ) {
233 this->curr = this->curr->next;
234 }
235 return *this;
236 }
237
238 template <typename T>
239 typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) {
240 auto t = Queue<T>::const_iterator( *this );
241
242 if ( this->curr != nullptr ) {
243 this->curr = this->curr->next;
244 }
245 return t;
246 }
247
248 template <typename T>
249 const T Queue<T>::const_iterator::operator*() {
250 return this->curr->item;
251 }
252
253 template <typename T>
254 bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) {
255 return this->curr != other.curr;
256 }
257
176 258
177 #endif 259 #endif
178 260