Mercurial > Algorithms__Sedgewick
view algs4-c++/src/Queue.hpp @ 25:3cdac4c29445
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 |
line source
1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
3 #ifndef QUEUE_HPP
4 #define QUEUE_HPP
6 #include <cstddef>
7 #include <cassert>
8 #include <iterator>
9 #include <type_traits>
11 template <typename T>
12 class Queue {
14 private:
16 ////////////////////////////////////
17 class Node {
18 public:
19 T item;
20 Node *next;
21 };
23 public:
25 ////////////////////////////////////
27 template <bool is_const = true>
28 class generic_iterator : public std::iterator<std::forward_iterator_tag, T> {
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;
34 public:
36 generic_iterator( NodePtrType c ) :
37 curr (c)
38 {
39 }
41 generic_iterator & operator++() {
42 if ( this->curr != nullptr ) {
43 this->curr = this->curr->next;
44 }
45 return *this;
46 }
48 generic_iterator operator++( int ) {
49 auto t = generic_iterator( *this );
51 if ( this->curr != nullptr ) {
52 this->curr = this->curr->next;
53 }
54 return t;
55 }
57 ValueType operator*() {
58 return this->curr->item;
59 }
61 bool operator!=( generic_iterator other ) {
62 return this->curr != other.curr;
63 }
65 private:
67 NodePtrType curr;
68 };
70 ////////////////////////////////////
72 typedef generic_iterator<true> const_iterator;
73 typedef generic_iterator<false> iterator;
75 Queue( void );
76 ~Queue( void );
78 // 1.3.41 Copy constructor.
79 Queue( const Queue<T> &q );
81 void enqueue( T &item );
82 T dequeue( void );
84 bool is_empty( void );
85 size_t size( void );
87 iterator begin( void );
88 iterator end( void );
89 const_iterator begin( void ) const;
90 const_iterator end( void ) const;
93 private:
95 size_t N;
96 Node *first;
97 Node *last;
99 };
102 template <typename T>
103 Queue<T>::Queue( void ) :
104 N (0),
105 first (nullptr),
106 last (nullptr)
107 {
108 }
110 // 1.3.41
111 template <typename T>
112 Queue<T>::Queue( const Queue<T> &q ) :
113 N (0),
114 first (nullptr),
115 last (nullptr)
116 {
117 for ( auto it = q.begin(); it != q.end(); ++it ) {
118 T item = *it;
119 this->enqueue( item );
120 }
121 }
123 template <typename T>
124 Queue<T>::~Queue( void ) {
125 assert( N == 0 ); // Catch the potential memory leak.
126 while ( first ) {
127 Node *next = first->next;
128 delete first;
129 first = next;
130 }
131 }
133 template <typename T>
134 void Queue<T>::enqueue( T &item ) {
135 Node * node = new Node();
136 node->item = item;
137 node->next = nullptr;
139 if ( last ) {
140 last->next = node;
141 last = node;
142 }
143 else {
144 last = first = node;
145 }
147 N++;
148 }
150 template <typename T>
151 T Queue<T>::dequeue( void ) {
152 assert( N > 0 );
154 T item = first->item;
156 Node *old = first;
157 first = first->next;
158 delete old;
159 N--;
161 if ( ! first )
162 last = nullptr;
164 return item;
165 }
167 template <typename T>
168 bool Queue<T>::is_empty( void ) {
169 return N == 0;
170 }
172 template <typename T>
173 size_t Queue<T>::size( void ) {
174 return N;
175 }
177 template <typename T>
178 typename Queue<T>::iterator Queue<T>::begin( void ) {
179 return Queue<T>::iterator( first );
180 }
182 template <typename T>
183 typename Queue<T>::iterator Queue<T>::end( void ) {
184 return Queue<T>::iterator( nullptr );
185 }
187 template <typename T>
188 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
189 return Queue<T>::const_iterator( first );
190 }
192 template <typename T>
193 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
194 return Queue<T>::const_iterator( nullptr );
195 }
197 #endif