Mercurial > Algorithms__Sedgewick

view 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
line source
1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
2
3 #ifndef QUEUE_HPP
4 #define QUEUE_HPP
5
6 #include <cstddef>
7 #include <cassert>
8 #include <iterator>
9
10 template <typename T>
11 class Queue {
12
13 private:
14
15 ////////////////////////////////////
16 class Node {
17 public:
18 T item;
19 Node *next;
20 };
21
22 public:
23
24 ////////////////////////////////////
25 class iterator : public std::iterator<std::forward_iterator_tag, T> {
26
27 public:
28
29 iterator( Node *c );
30
31 iterator& operator++();
32 iterator operator++(int);
33
34 T operator*();
35 bool operator!=( typename Queue<T>::iterator );
36
37 private:
38
39 Node *curr;
40 };
41
42 ////////////////////////////////////
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
63 Queue( void );
64 ~Queue( void );
65
66 // 1.3.41 Copy constructor.
67 Queue( const Queue<T> &q );
68
69 void enqueue( T &item );
70 T dequeue( void );
71
72 bool is_empty( void );
73 size_t size( void );
74
75 iterator begin( void );
76 iterator end( void );
77 const_iterator begin( void ) const;
78 const_iterator end( void ) const;
79
80
81 private:
82
83 size_t N;
84 Node *first;
85 Node *last;
86
87 };
88
89
90 template <typename T>
91 Queue<T>::Queue( void ) :
92 N (0),
93 first (nullptr),
94 last (nullptr)
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 }
109 }
110
111 template <typename T>
112 Queue<T>::~Queue( void ) {
113 assert( N == 0 ); // Catch the potential memory leak.
114 while ( first ) {
115 Node *next = first->next;
116 delete first;
117 first = next;
118 }
119 }
120
121 template <typename T>
122 void Queue<T>::enqueue( T &item ) {
123 Node * node = new Node();
124 node->item = item;
125 node->next = nullptr;
126
127 if ( last ) {
128 last->next = node;
129 last = node;
130 }
131 else {
132 last = first = node;
133 }
134
135 N++;
136 }
137
138 template <typename T>
139 T Queue<T>::dequeue( void ) {
140 assert( N > 0 );
141
142 T item = first->item;
143
144 Node *old = first;
145 first = first->next;
146 delete old;
147 N--;
148
149 if ( ! first )
150 last = nullptr;
151
152 return item;
153 }
154
155 template <typename T>
156 bool Queue<T>::is_empty( void ) {
157 return N == 0;
158 }
159
160 template <typename T>
161 size_t Queue<T>::size( void ) {
162 return N;
163 }
164
165 template <typename T>
166 typename Queue<T>::iterator Queue<T>::begin( void ) {
167 return Queue<T>::iterator( first );
168 }
169
170 template <typename T>
171 typename Queue<T>::iterator Queue<T>::end( void ) {
172 return Queue<T>::iterator( nullptr );
173 }
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
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
260