Mercurial > Algorithms__Sedgewick

view algs4-c++/src/ResizingArrayDeque.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
Bag and RandomBag (1.3.34) classes. There are not really robust enough to use as they will leak memory on destruction if you use them to store dynamically allocated objects.
author Eris Caffee <discordia@eldalin.com>
date Thu, 11 Jun 2015 16:30:14 -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