rev |
line source |
discordia@16
|
1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
|
discordia@16
|
2
|
discordia@8
|
3 #ifndef QUEUE_HPP
|
discordia@8
|
4 #define QUEUE_HPP
|
discordia@8
|
5
|
discordia@8
|
6 #include <cstddef>
|
discordia@16
|
7 #include <cassert>
|
discordia@24
|
8 #include <iterator>
|
discordia@25
|
9 #include <type_traits>
|
discordia@8
|
10
|
discordia@8
|
11 template <typename T>
|
discordia@8
|
12 class Queue {
|
discordia@8
|
13
|
discordia@9
|
14 private:
|
discordia@8
|
15
|
discordia@8
|
16 ////////////////////////////////////
|
discordia@8
|
17 class Node {
|
discordia@8
|
18 public:
|
discordia@8
|
19 T item;
|
discordia@8
|
20 Node *next;
|
discordia@8
|
21 };
|
discordia@8
|
22
|
discordia@9
|
23 public:
|
discordia@8
|
24
|
discordia@8
|
25 ////////////////////////////////////
|
discordia@25
|
26
|
discordia@25
|
27 template <bool is_const = true>
|
discordia@25
|
28 class generic_iterator : public std::iterator<std::forward_iterator_tag, T> {
|
discordia@25
|
29
|
discordia@25
|
30 private:
|
discordia@25
|
31 typedef typename std::conditional<is_const, const Node *, Node *>::type NodePtrType;
|
discordia@25
|
32 typedef typename std::conditional<is_const, const T, T>::type ValueType;
|
discordia@8
|
33
|
discordia@8
|
34 public:
|
discordia@8
|
35
|
discordia@25
|
36 generic_iterator( NodePtrType c ) :
|
discordia@25
|
37 curr (c)
|
discordia@25
|
38 {
|
discordia@25
|
39 }
|
discordia@8
|
40
|
discordia@25
|
41 generic_iterator & operator++() {
|
discordia@25
|
42 if ( this->curr != nullptr ) {
|
discordia@25
|
43 this->curr = this->curr->next;
|
discordia@25
|
44 }
|
discordia@25
|
45 return *this;
|
discordia@25
|
46 }
|
discordia@8
|
47
|
discordia@25
|
48 generic_iterator operator++( int ) {
|
discordia@25
|
49 auto t = generic_iterator( *this );
|
discordia@25
|
50
|
discordia@25
|
51 if ( this->curr != nullptr ) {
|
discordia@25
|
52 this->curr = this->curr->next;
|
discordia@25
|
53 }
|
discordia@25
|
54 return t;
|
discordia@25
|
55 }
|
discordia@25
|
56
|
discordia@25
|
57 ValueType operator*() {
|
discordia@25
|
58 return this->curr->item;
|
discordia@25
|
59 }
|
discordia@25
|
60
|
discordia@25
|
61 bool operator!=( generic_iterator other ) {
|
discordia@25
|
62 return this->curr != other.curr;
|
discordia@25
|
63 }
|
discordia@8
|
64
|
discordia@8
|
65 private:
|
discordia@8
|
66
|
discordia@25
|
67 NodePtrType curr;
|
discordia@8
|
68 };
|
discordia@8
|
69
|
discordia@8
|
70 ////////////////////////////////////
|
discordia@8
|
71
|
discordia@25
|
72 typedef generic_iterator<true> const_iterator;
|
discordia@25
|
73 typedef generic_iterator<false> iterator;
|
discordia@24
|
74
|
discordia@8
|
75 Queue( void );
|
discordia@8
|
76 ~Queue( void );
|
discordia@8
|
77
|
discordia@24
|
78 // 1.3.41 Copy constructor.
|
discordia@24
|
79 Queue( const Queue<T> &q );
|
discordia@24
|
80
|
discordia@8
|
81 void enqueue( T &item );
|
discordia@8
|
82 T dequeue( void );
|
discordia@8
|
83
|
discordia@8
|
84 bool is_empty( void );
|
discordia@8
|
85 size_t size( void );
|
discordia@8
|
86
|
discordia@8
|
87 iterator begin( void );
|
discordia@8
|
88 iterator end( void );
|
discordia@24
|
89 const_iterator begin( void ) const;
|
discordia@24
|
90 const_iterator end( void ) const;
|
discordia@8
|
91
|
discordia@9
|
92
|
discordia@8
|
93 private:
|
discordia@8
|
94
|
discordia@8
|
95 size_t N;
|
discordia@8
|
96 Node *first;
|
discordia@8
|
97 Node *last;
|
discordia@8
|
98
|
discordia@8
|
99 };
|
discordia@8
|
100
|
discordia@8
|
101
|
discordia@16
|
102 template <typename T>
|
discordia@16
|
103 Queue<T>::Queue( void ) :
|
discordia@16
|
104 N (0),
|
discordia@16
|
105 first (nullptr),
|
discordia@16
|
106 last (nullptr)
|
discordia@16
|
107 {
|
discordia@16
|
108 }
|
discordia@24
|
109
|
discordia@24
|
110 // 1.3.41
|
discordia@24
|
111 template <typename T>
|
discordia@24
|
112 Queue<T>::Queue( const Queue<T> &q ) :
|
discordia@24
|
113 N (0),
|
discordia@24
|
114 first (nullptr),
|
discordia@24
|
115 last (nullptr)
|
discordia@24
|
116 {
|
discordia@24
|
117 for ( auto it = q.begin(); it != q.end(); ++it ) {
|
discordia@24
|
118 T item = *it;
|
discordia@24
|
119 this->enqueue( item );
|
discordia@24
|
120 }
|
discordia@24
|
121 }
|
discordia@16
|
122
|
discordia@16
|
123 template <typename T>
|
discordia@16
|
124 Queue<T>::~Queue( void ) {
|
discordia@16
|
125 assert( N == 0 ); // Catch the potential memory leak.
|
discordia@16
|
126 while ( first ) {
|
discordia@16
|
127 Node *next = first->next;
|
discordia@16
|
128 delete first;
|
discordia@16
|
129 first = next;
|
discordia@16
|
130 }
|
discordia@16
|
131 }
|
discordia@16
|
132
|
discordia@16
|
133 template <typename T>
|
discordia@16
|
134 void Queue<T>::enqueue( T &item ) {
|
discordia@16
|
135 Node * node = new Node();
|
discordia@16
|
136 node->item = item;
|
discordia@16
|
137 node->next = nullptr;
|
discordia@16
|
138
|
discordia@16
|
139 if ( last ) {
|
discordia@16
|
140 last->next = node;
|
discordia@16
|
141 last = node;
|
discordia@16
|
142 }
|
discordia@16
|
143 else {
|
discordia@16
|
144 last = first = node;
|
discordia@16
|
145 }
|
discordia@16
|
146
|
discordia@16
|
147 N++;
|
discordia@16
|
148 }
|
discordia@16
|
149
|
discordia@16
|
150 template <typename T>
|
discordia@16
|
151 T Queue<T>::dequeue( void ) {
|
discordia@16
|
152 assert( N > 0 );
|
discordia@16
|
153
|
discordia@16
|
154 T item = first->item;
|
discordia@16
|
155
|
discordia@16
|
156 Node *old = first;
|
discordia@16
|
157 first = first->next;
|
discordia@16
|
158 delete old;
|
discordia@16
|
159 N--;
|
discordia@16
|
160
|
discordia@16
|
161 if ( ! first )
|
discordia@16
|
162 last = nullptr;
|
discordia@16
|
163
|
discordia@16
|
164 return item;
|
discordia@16
|
165 }
|
discordia@16
|
166
|
discordia@16
|
167 template <typename T>
|
discordia@16
|
168 bool Queue<T>::is_empty( void ) {
|
discordia@16
|
169 return N == 0;
|
discordia@16
|
170 }
|
discordia@16
|
171
|
discordia@16
|
172 template <typename T>
|
discordia@16
|
173 size_t Queue<T>::size( void ) {
|
discordia@16
|
174 return N;
|
discordia@16
|
175 }
|
discordia@16
|
176
|
discordia@16
|
177 template <typename T>
|
discordia@16
|
178 typename Queue<T>::iterator Queue<T>::begin( void ) {
|
discordia@16
|
179 return Queue<T>::iterator( first );
|
discordia@16
|
180 }
|
discordia@16
|
181
|
discordia@16
|
182 template <typename T>
|
discordia@16
|
183 typename Queue<T>::iterator Queue<T>::end( void ) {
|
discordia@16
|
184 return Queue<T>::iterator( nullptr );
|
discordia@16
|
185 }
|
discordia@16
|
186
|
discordia@24
|
187 template <typename T>
|
discordia@24
|
188 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
|
discordia@24
|
189 return Queue<T>::const_iterator( first );
|
discordia@24
|
190 }
|
discordia@24
|
191
|
discordia@24
|
192 template <typename T>
|
discordia@24
|
193 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
|
discordia@24
|
194 return Queue<T>::const_iterator( nullptr );
|
discordia@24
|
195 }
|
discordia@24
|
196
|
discordia@8
|
197 #endif
|
discordia@8
|
198
|