Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/Queue.hpp @ 25:3cdac4c29445

find changesets by author, revision, files, or words in the commit message
Refactored Queue's iterator and const_iterator into a template. The generic_iterator can be instatiated as either a const or non-const iterator as needed. It uses <type_traits> std::conditional<>::type create the appropriate types as needed. I learned this trick here: http://www.sj-vs.net/c-implementing-const_iterator-and-non-const-iterator-without-code-duplication/
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 15:27:26 -0500
parents 028689700a47
children 2cbfacd2a3e9
comparison
equal deleted inserted replaced
4:be6ea53dbdfa 5:89f5673d1606
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 #include <iterator>
9 #include <type_traits>
9 10
10 template <typename T> 11 template <typename T>
11 class Queue { 12 class Queue {
12 13
13 private: 14 private:
20 }; 21 };
21 22
22 public: 23 public:
23 24
24 //////////////////////////////////// 25 ////////////////////////////////////
25 class iterator : public std::iterator<std::forward_iterator_tag, T> { 26
27 template <bool is_const = true>
28 class generic_iterator : public std::iterator<std::forward_iterator_tag, T> {
29
30 private:
31 typedef typename std::conditional<is_const, const Node *, Node *>::type NodePtrType;
32 typedef typename std::conditional<is_const, const T, T>::type ValueType;
26 33
27 public: 34 public:
28 35
29 iterator( Node *c ); 36 generic_iterator( NodePtrType c ) :
37 curr (c)
38 {
39 }
30 40
31 iterator& operator++(); 41 generic_iterator & operator++() {
32 iterator operator++(int); 42 if ( this->curr != nullptr ) {
43 this->curr = this->curr->next;
44 }
45 return *this;
46 }
33 47
34 T operator*(); 48 generic_iterator operator++( int ) {
35 bool operator!=( typename Queue<T>::iterator ); 49 auto t = generic_iterator( *this );
50
51 if ( this->curr != nullptr ) {
52 this->curr = this->curr->next;
53 }
54 return t;
55 }
56
57 ValueType operator*() {
58 return this->curr->item;
59 }
60
61 bool operator!=( generic_iterator other ) {
62 return this->curr != other.curr;
63 }
36 64
37 private: 65 private:
38 66
39 Node *curr; 67 NodePtrType curr;
40 }; 68 };
41 69
42 //////////////////////////////////// 70 ////////////////////////////////////
43 71
44 class const_iterator : public std::iterator<std::forward_iterator_tag, T> { 72 typedef generic_iterator<true> const_iterator;
45 73 typedef generic_iterator<false> iterator;
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 74
63 Queue( void ); 75 Queue( void );
64 ~Queue( void ); 76 ~Queue( void );
65 77
66 // 1.3.41 Copy constructor. 78 // 1.3.41 Copy constructor.
180 template <typename T> 192 template <typename T>
181 typename Queue<T>::const_iterator Queue<T>::end( void ) const { 193 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
182 return Queue<T>::const_iterator( nullptr ); 194 return Queue<T>::const_iterator( nullptr );
183 } 195 }
184 196
185
186 ////////////////////////////////////////////////////////////////////////////////
187
188 template <typename T>
189 Queue<T>::iterator::iterator( Node *c ) :
190 curr (c)
191 {
192 }
193
194 template <typename T>
195 typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
196 if ( this->curr != nullptr ) {
197 this->curr = this->curr->next;
198 }
199 return *this;
200 }
201
202 template <typename T>
203 typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
204 auto t = Queue<T>::iterator( *this );
205
206 if ( this->curr != nullptr ) {
207 this->curr = this->curr->next;
208 }
209 return t;
210 }
211
212 template <typename T>
213 T Queue<T>::iterator::operator*() {
214 return this->curr->item;
215 }
216
217 template <typename T>
218 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
219 return this->curr != other.curr;
220 }
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
258
259 #endif 197 #endif
260 198