Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Queue.hpp @ 27:80ca1973e3bd

find changesets by author, revision, files, or words in the commit message
Fleshed out Queue::generic_iterator a bit more to make it a more or less complete example of implmenting an iterator.
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 17:14:09 -0500
parents 2cbfacd2a3e9
children
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 #include <type_traits>
10
11 template <typename T>
12 class Queue {
13
14 private:
15
16 ////////////////////////////////////
17 class Node {
18 public:
19 T item;
20 Node *next;
21 };
22
23 public:
24
25 ////////////////////////////////////
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 ValueReferenceType;
33
34 public:
35
36 generic_iterator( NodePtrType c ) :
37 curr (c)
38 {
39 }
40
41 generic_iterator( const generic_iterator<false>& other ) :
42 curr (other.curr)
43 {
44 }
45
46 generic_iterator & operator++() {
47 if ( this->curr != nullptr ) {
48 this->curr = this->curr->next;
49 }
50 return *this;
51 }
52
53 generic_iterator operator++( int ) {
54 auto t = generic_iterator( *this );
55
56 if ( this->curr != nullptr ) {
57 this->curr = this->curr->next;
58 }
59 return t;
60 }
61
62 ValueReferenceType operator*() {
63 return this->curr->item;
64 }
65
66 bool operator==( generic_iterator rhs ) {
67 return this->curr == rhs.curr;
68 }
69
70 bool operator!=( generic_iterator rhs ) {
71 return this->curr != rhs.curr;
72 }
73
74 private:
75
76 NodePtrType curr;
77 };
78
79 ////////////////////////////////////
80
81 typedef generic_iterator<true> const_iterator;
82 typedef generic_iterator<false> iterator;
83 typedef std::iterator_traits< generic_iterator<> > iterator_traits;
84
85 Queue( void );
86 ~Queue( void );
87
88 // 1.3.41 Copy constructor.
89 Queue( const Queue<T> &q );
90
91 void enqueue( T &item );
92 T dequeue( void );
93
94 bool is_empty( void );
95 size_t size( void );
96
97 iterator begin( void );
98 iterator end( void );
99 const_iterator begin( void ) const;
100 const_iterator end( void ) const;
101
102
103 private:
104
105 size_t N;
106 Node *first;
107 Node *last;
108
109 };
110
111
112 template <typename T>
113 Queue<T>::Queue( void ) :
114 N (0),
115 first (nullptr),
116 last (nullptr)
117 {
118 }
119
120 // 1.3.41
121 template <typename T>
122 Queue<T>::Queue( const Queue<T> &q ) :
123 N (0),
124 first (nullptr),
125 last (nullptr)
126 {
127 for ( auto it = q.begin(); it != q.end(); ++it ) {
128 T item = *it;
129 this->enqueue( item );
130 }
131 }
132
133 template <typename T>
134 Queue<T>::~Queue( void ) {
135 assert( N == 0 ); // Catch the potential memory leak.
136 while ( first ) {
137 Node *next = first->next;
138 delete first;
139 first = next;
140 }
141 }
142
143 template <typename T>
144 void Queue<T>::enqueue( T &item ) {
145 Node * node = new Node();
146 node->item = item;
147 node->next = nullptr;
148
149 if ( last ) {
150 last->next = node;
151 last = node;
152 }
153 else {
154 last = first = node;
155 }
156
157 N++;
158 }
159
160 template <typename T>
161 T Queue<T>::dequeue( void ) {
162 assert( N > 0 );
163
164 T item = first->item;
165
166 Node *old = first;
167 first = first->next;
168 delete old;
169 N--;
170
171 if ( ! first )
172 last = nullptr;
173
174 return item;
175 }
176
177 template <typename T>
178 bool Queue<T>::is_empty( void ) {
179 return N == 0;
180 }
181
182 template <typename T>
183 size_t Queue<T>::size( void ) {
184 return N;
185 }
186
187 template <typename T>
188 typename Queue<T>::iterator Queue<T>::begin( void ) {
189 return Queue<T>::iterator( first );
190 }
191
192 template <typename T>
193 typename Queue<T>::iterator Queue<T>::end( void ) {
194 return Queue<T>::iterator( nullptr );
195 }
196
197 template <typename T>
198 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
199 return Queue<T>::const_iterator( first );
200 }
201
202 template <typename T>
203 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
204 return Queue<T>::const_iterator( nullptr );
205 }
206
207 #endif
208