Mercurial > Algorithms__Sedgewick

view algs4-c++/src/ResizingArrayDeque.cpp @ 14:2f87e582d91a

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