Mercurial > Algorithms__Sedgewick

annotate 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
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