Mercurial > Algorithms__Sedgewick

view algs4-c++/src/ResizingArrayDeque.hpp @ 18:a149b424b4e2

find changesets by author, revision, files, or words in the commit message
Updated all template classes to have the implementaiton in the header file.
author Eris Caffee <discordia@eldalin.com>
date Sat, 20 Jun 2015 19:36:11 -0500
parents 2f87e582d91a
children
line source
1 // Double ended queue built on a resizing array.
2
3 #ifndef RESIZINGARRAYDEQUE_HPP
4 #define RESIZINGARRAYDEQUE_HPP
5
6 #include <cassert>
7 #include <cstddef>
8
9 template <typename T>
10 class ResizingArrayDeque {
11
12 public:
13
14 ////////////////////////////////////////
15 class iterator {
16
17 public:
18
19 iterator( T *c, T *l, T *b, T *m );
20
21 iterator& operator++();
22 iterator operator++(int);
23
24 T operator*();
25 bool operator!=( typename ResizingArrayDeque<T>::iterator );
26
27 private:
28
29 T *curr;
30 T *last;
31 T *begin;
32 T *max;
33 };
34
35 ////////////////////////////////////////
36 ResizingArrayDeque( void );
37 ~ResizingArrayDeque( void );
38
39 void push_left( T &item );
40 void push_right( T &item );
41 T pop_left( void );
42 T pop_right( void );
43
44 bool is_empty( void );
45 size_t size( void );
46
47 iterator begin( void );
48 iterator end( void );
49
50 private:
51
52 size_t N;
53 size_t max;
54 T *first, *last;
55 T *data;
56
57 void resize( size_t new_max );
58 };
59
60 ////////////////////////////////////////////////////////////////////////////////
61
62 template <typename T>
63 ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
64 N (0),
65 max(1),
66 first(nullptr),
67 last(nullptr) {
68 data = new T[2];
69 }
70
71 template <typename T>
72 ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
73 assert( N == 0 ); // Catch the potential memory leak.
74 if ( data )
75 delete[] data;
76 }
77
78 template <typename T>
79 void ResizingArrayDeque<T>::push_right( T &item ) {
80 if ( N == max )
81 resize( 2 * max );
82
83 if ( last ) {
84 if ( last == data )
85 last = data + max - 1;
86 else
87 ++last;
88 }
89 else {
90 first = last = data;
91 }
92
93 *last = item;
94 ++N;
95 }
96
97 template <typename T>
98 void ResizingArrayDeque<T>::push_left( T &item ) {
99 if ( N == max )
100 resize( 2 * max );
101
102 if ( first ) {
103 if ( first == data )
104 first = data + max - 1;
105 else
106 --first;
107 }
108 else {
109 first = last = data;
110 }
111
112 *first = item;
113 ++N;
114 }
115
116 template <typename T>
117 T ResizingArrayDeque<T>::pop_right( void ) {
118 assert( N > 0 );
119
120 T item = *last;
121 N--;
122
123 if ( last == data ) {
124 last = data + max - 1;
125 }
126 else {
127 --last;
128 }
129
130 if ( N == 0 )
131 first = last = nullptr;
132
133 // if ( N <= max/4 )
134 // resize( max/2 );
135
136 return item;
137 }
138
139 template <typename T>
140 T ResizingArrayDeque<T>::pop_left( void ) {
141 assert( N > 0 );
142
143 T item = *first;
144 N--;
145
146 if ( first == data + max - 1 ) {
147 first = data;
148 }
149 else {
150 ++first;
151 }
152
153 if ( N == 0 )
154 first = last = nullptr;
155
156 // if ( N <= max/4 )
157 // resize( max/2 );
158
159 return item;
160 }
161
162 template <typename T>
163 bool ResizingArrayDeque<T>::is_empty( void ) {
164 return N == 0;
165 }
166
167 template <typename T>
168 size_t ResizingArrayDeque<T>::size( void ) {
169 return N;
170 }
171
172 template <typename T>
173 void ResizingArrayDeque<T>::resize( size_t new_max ) {
174 T *new_data = new T[new_max];
175
176 if ( N ) {
177 size_t i = 0;
178 T *curr = first;
179 while ( i < N ) {
180 new_data[i] = *curr;
181 ++curr;
182 if ( curr == data + max )
183 curr = data;
184 ++i;
185 }
186 }
187 first = new_data;
188 last = new_data + N - 1;
189
190 T *old_data = data;
191 data = new_data;
192 delete[] old_data;
193
194 max = new_max;
195 }
196
197 template <typename T>
198 typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
199 return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
200 }
201
202 template <typename T>
203 typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
204 return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
205 }
206
207
208 ////////////////////////////////////////////////////////////////////////////////
209
210 template <typename T>
211 ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
212 curr (c),
213 last (l),
214 begin (b),
215 max (m)
216 {
217 }
218
219 template <typename T>
220 typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
221 if ( this->curr == this->last ) {
222 this->curr = nullptr;
223 }
224 else {
225 this->curr += 1;
226 if ( this->curr > this->max )
227 this->curr = this->begin;
228 }
229
230 return *this;
231 }
232
233 template <typename T>
234 typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
235 auto t = ResizingArrayDeque<T>::iterator( *this );
236
237 if ( this->curr == this->last ) {
238 this->curr = nullptr;
239 }
240 else {
241 this->curr += 1;
242 if ( this->curr > this->max )
243 this->curr = this->begin;
244 }
245
246 return t;
247 }
248
249 template <typename T>
250 T ResizingArrayDeque<T>::iterator::operator*() {
251 return *(this->curr);
252 }
253
254 template <typename T>
255 bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
256 return this->curr != other.curr;
257 }
258
259
260
261
262 #endif
263