Mercurial > Algorithms__Sedgewick
comparison algs4-c++/src/ResizingArrayDeque.cpp @ 27:80ca1973e3bd
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 | 2f87e582d91a |
children |
comparison
equal
deleted
inserted
replaced
0:e25073ce7e57 | 1:8830d022334a |
---|---|
1 // g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp | 1 // g++ -std=c++11 ResizingArrayDeque.cpp |
2 // g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp | |
3 | 2 |
4 | 3 |
5 #include "ResizingArrayDeque.hpp" | 4 #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 | 5 |
214 #include <iostream> | 6 #include <iostream> |
215 | 7 |
216 int main ( int argc, char **argv ) { | 8 int main ( int argc, char **argv ) { |
217 | 9 |
256 | 48 |
257 std::cout << "Deque has " << deque.size() << " entries." << std::endl; | 49 std::cout << "Deque has " << deque.size() << " entries." << std::endl; |
258 | 50 |
259 } | 51 } |
260 | 52 |
261 #endif |