Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/Deque.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 1e3c509b6ac4
children
comparison
equal deleted inserted replaced
0:58225eb10c33 1:c38d6d294de6
1 // Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
2
1 #ifndef DEQUE_HPP 3 #ifndef DEQUE_HPP
2 #define DEQUE_HPP 4 #define DEQUE_HPP
3 5
6 #include <cassert>
4 #include <cstddef> 7 #include <cstddef>
5
6 // Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
7 8
8 template <typename T> 9 template <typename T>
9 class Deque { 10 class Deque {
10 11
11 private: 12 private:
64 Node *last; 65 Node *last;
65 66
66 }; 67 };
67 68
68 69
70 ////////////////////////////////////////////////////////////////////////////////
71
72 template <typename T>
73 Deque<T>::Deque( void ) :
74 N (0),
75 first (nullptr),
76 last (nullptr)
77 {
78 }
79
80 template <typename T>
81 Deque<T>::~Deque( void ) {
82 assert( N == 0 ); // Catch the potential memory leak.
83 while ( first ) {
84 Node *next = first->next;
85 delete first;
86 first = next;
87 }
88 }
89
90 template <typename T>
91 void Deque<T>::push_right( T &item ) {
92 Node * node = new Node();
93 node->item = item;
94 node->next = nullptr;
95 node->prev = nullptr;
96
97 if ( last ) {
98 last->next = node;
99 node->prev = last;
100 last = node;
101 }
102 else {
103 last = first = node;
104 }
105
106 N++;
107 }
108
109 template <typename T>
110 void Deque<T>::push_left( T &item ) {
111 Node * node = new Node();
112 node->item = item;
113 node->next = nullptr;
114 node->prev = nullptr;
115
116 if ( first ) {
117 node->next = first;
118 first->prev = node;
119 first = node;
120 }
121 else {
122 last = first = node;
123 }
124
125 N++;
126 }
127
128 template <typename T>
129 T Deque<T>::pop_left( void ) {
130 assert( N > 0 );
131
132 T item = first->item;
133
134 Node *old = first;
135 if ( first->next )
136 first->next->prev = nullptr;
137 first = first->next;
138 delete old;
139 N--;
140
141 if ( ! first )
142 last = nullptr;
143
144 return item;
145 }
146
147 template <typename T>
148 T Deque<T>::pop_right( void ) {
149 assert( N > 0 );
150
151 T item = last->item;
152
153 Node *old = last;
154 if ( last->prev )
155 last->prev->next = nullptr;
156 last = last->prev;
157 delete old;
158 N--;
159
160 if ( ! last )
161 first = nullptr;
162
163 return item;
164 }
165
166 template <typename T>
167 bool Deque<T>::is_empty( void ) {
168 return N == 0;
169 }
170
171 template <typename T>
172 size_t Deque<T>::size( void ) {
173 return N;
174 }
175
176 template <typename T>
177 typename Deque<T>::iterator Deque<T>::begin( void ) {
178 return Deque<T>::iterator( first );
179 }
180
181 template <typename T>
182 typename Deque<T>::iterator Deque<T>::end( void ) {
183 return Deque<T>::iterator( nullptr );
184 }
185
186
187 ////////////////////////////////////////////////////////////////////////////////
188
189 template <typename T>
190 Deque<T>::iterator::iterator( Node *c ) :
191 curr (c)
192 {
193 }
194
195 template <typename T>
196 typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
197 if ( this->curr != nullptr ) {
198 this->curr = this->curr->next;
199 }
200 return *this;
201 }
202
203 template <typename T>
204 typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
205 auto t = Deque<T>::iterator( *this );
206
207 if ( this->curr != nullptr ) {
208 this->curr = this->curr->next;
209 }
210 return t;
211 }
212
213 template <typename T>
214 T Deque<T>::iterator::operator*() {
215 return this->curr->item;
216 }
217
218 template <typename T>
219 bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
220 return this->curr != other.curr;
221 }
69 222
70 #endif 223 #endif
71 224