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