Mercurial > Algorithms__Sedgewick
changeset 14:2f87e582d91a
ResizingArrayDeque (exercise 1.3.33)
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Wed, 10 Jun 2015 18:12:59 -0500 |
parents | 5b5b5a337763 |
children | 63df3e6590e2 |
files | algs4-c++/1.3.33-2 algs4-c++/src/ResizingArrayDeque.cpp algs4-c++/src/ResizingArrayDeque.hpp |
diffstat | 3 files changed, 322 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/1.3.33-2 Wed Jun 10 18:12:59 2015 -0500 1.3 @@ -0,0 +1,1 @@ 1.4 +src/ResizingArrayDeque.hpp 1.5 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/ResizingArrayDeque.cpp Wed Jun 10 18:12:59 2015 -0500 2.3 @@ -0,0 +1,261 @@ 2.4 +// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp 2.5 +// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp 2.6 + 2.7 + 2.8 +#include "ResizingArrayDeque.hpp" 2.9 + 2.10 +#include <cassert> 2.11 +#include <cstddef> 2.12 + 2.13 +#include <iostream> 2.14 + 2.15 +template <typename T> 2.16 +ResizingArrayDeque<T>::ResizingArrayDeque( void ) : 2.17 + N (0), 2.18 + max(1), 2.19 + first(nullptr), 2.20 + last(nullptr) { 2.21 + data = new T[2]; 2.22 + } 2.23 + 2.24 +template <typename T> 2.25 +ResizingArrayDeque<T>::~ResizingArrayDeque( void ) { 2.26 + assert( N == 0 ); // Catch the potential memory leak. 2.27 + if ( data ) 2.28 + delete[] data; 2.29 + } 2.30 + 2.31 +template <typename T> 2.32 +void ResizingArrayDeque<T>::push_right( T &item ) { 2.33 + if ( N == max ) 2.34 + resize( 2 * max ); 2.35 + 2.36 + if ( last ) { 2.37 + if ( last == data ) 2.38 + last = data + max - 1; 2.39 + else 2.40 + ++last; 2.41 + } 2.42 + else { 2.43 + first = last = data; 2.44 + } 2.45 + 2.46 + *last = item; 2.47 + ++N; 2.48 + } 2.49 + 2.50 +template <typename T> 2.51 +void ResizingArrayDeque<T>::push_left( T &item ) { 2.52 + if ( N == max ) 2.53 + resize( 2 * max ); 2.54 + 2.55 + if ( first ) { 2.56 + if ( first == data ) 2.57 + first = data + max - 1; 2.58 + else 2.59 + --first; 2.60 + } 2.61 + else { 2.62 + first = last = data; 2.63 + } 2.64 + 2.65 + *first = item; 2.66 + ++N; 2.67 + } 2.68 + 2.69 +template <typename T> 2.70 +T ResizingArrayDeque<T>::pop_right( void ) { 2.71 + assert( N > 0 ); 2.72 + 2.73 + T item = *last; 2.74 + N--; 2.75 + 2.76 + if ( last == data ) { 2.77 + last = data + max - 1; 2.78 + } 2.79 + else { 2.80 + --last; 2.81 + } 2.82 + 2.83 + if ( N == 0 ) 2.84 + first = last = nullptr; 2.85 + 2.86 + // if ( N <= max/4 ) 2.87 + // resize( max/2 ); 2.88 + 2.89 + return item; 2.90 + } 2.91 + 2.92 +template <typename T> 2.93 +T ResizingArrayDeque<T>::pop_left( void ) { 2.94 + assert( N > 0 ); 2.95 + 2.96 + T item = *first; 2.97 + N--; 2.98 + 2.99 + if ( first == data + max - 1 ) { 2.100 + first = data; 2.101 + } 2.102 + else { 2.103 + ++first; 2.104 + } 2.105 + 2.106 + if ( N == 0 ) 2.107 + first = last = nullptr; 2.108 + 2.109 + // if ( N <= max/4 ) 2.110 + // resize( max/2 ); 2.111 + 2.112 + return item; 2.113 + } 2.114 + 2.115 +template <typename T> 2.116 +bool ResizingArrayDeque<T>::is_empty( void ) { 2.117 + return N == 0; 2.118 + } 2.119 + 2.120 +template <typename T> 2.121 +size_t ResizingArrayDeque<T>::size( void ) { 2.122 + return N; 2.123 + } 2.124 + 2.125 +template <typename T> 2.126 +void ResizingArrayDeque<T>::resize( size_t new_max ) { 2.127 + T *new_data = new T[new_max]; 2.128 + 2.129 + if ( N ) { 2.130 + size_t i = 0; 2.131 + T *curr = first; 2.132 + while ( i < N ) { 2.133 + new_data[i] = *curr; 2.134 + ++curr; 2.135 + if ( curr == data + max ) 2.136 + curr = data; 2.137 + ++i; 2.138 + } 2.139 + } 2.140 + first = new_data; 2.141 + last = new_data + N - 1; 2.142 + 2.143 + T *old_data = data; 2.144 + data = new_data; 2.145 + delete[] old_data; 2.146 + 2.147 + max = new_max; 2.148 + } 2.149 + 2.150 +template <typename T> 2.151 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) { 2.152 + return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 ); 2.153 + } 2.154 + 2.155 +template <typename T> 2.156 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) { 2.157 + return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr ); 2.158 + } 2.159 + 2.160 + 2.161 +//////////////////////////////////////////////////////////////////////////////// 2.162 + 2.163 +template <typename T> 2.164 +ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) : 2.165 + curr (c), 2.166 + last (l), 2.167 + begin (b), 2.168 + max (m) 2.169 + { 2.170 + } 2.171 + 2.172 +template <typename T> 2.173 +typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() { 2.174 + if ( this->curr == this->last ) { 2.175 + this->curr = nullptr; 2.176 + } 2.177 + else { 2.178 + this->curr += 1; 2.179 + if ( this->curr > this->max ) 2.180 + this->curr = this->begin; 2.181 + } 2.182 + 2.183 + return *this; 2.184 + } 2.185 + 2.186 +template <typename T> 2.187 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) { 2.188 + auto t = ResizingArrayDeque<T>::iterator( *this ); 2.189 + 2.190 + if ( this->curr == this->last ) { 2.191 + this->curr = nullptr; 2.192 + } 2.193 + else { 2.194 + this->curr += 1; 2.195 + if ( this->curr > this->max ) 2.196 + this->curr = this->begin; 2.197 + } 2.198 + 2.199 + return t; 2.200 + } 2.201 + 2.202 +template <typename T> 2.203 +T ResizingArrayDeque<T>::iterator::operator*() { 2.204 + return *(this->curr); 2.205 + } 2.206 + 2.207 +template <typename T> 2.208 +bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) { 2.209 + return this->curr != other.curr; 2.210 + } 2.211 + 2.212 + 2.213 +//////////////////////////////////////////////////////////////////////////////// 2.214 + 2.215 +#ifdef RESIZINGARRAYDEQUE_MAIN 2.216 + 2.217 +#include <iostream> 2.218 + 2.219 +int main ( int argc, char **argv ) { 2.220 + 2.221 + ResizingArrayDeque<long> deque; 2.222 + bool left = true; 2.223 + 2.224 + long i; 2.225 + while ( ! std::cin.eof() ) { 2.226 + std::cin >> i; 2.227 + if ( std::cin.good() ) { 2.228 + if ( left ) { 2.229 + deque.push_left(i); 2.230 + left = false; 2.231 + } 2.232 + else { 2.233 + deque.push_right(i); 2.234 + left = true; 2.235 + } 2.236 + } 2.237 + } 2.238 + 2.239 + std::cout << "Deque has " << deque.size() << " entries." << std::endl; 2.240 + 2.241 + for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) { 2.242 + std::cout << *iter << std::endl; 2.243 + } 2.244 + 2.245 + std::cout << "Popping entries..." << std::endl; 2.246 + 2.247 + left = true; 2.248 + while ( ! deque.is_empty() ) { 2.249 + if ( left ) { 2.250 + i = deque.pop_left(); 2.251 + left = false; 2.252 + } 2.253 + else { 2.254 + i = deque.pop_right(); 2.255 + left = true; 2.256 + } 2.257 + std::cout << i << std::endl; 2.258 + } 2.259 + 2.260 + std::cout << "Deque has " << deque.size() << " entries." << std::endl; 2.261 + 2.262 + } 2.263 + 2.264 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/algs4-c++/src/ResizingArrayDeque.hpp Wed Jun 10 18:12:59 2015 -0500 3.3 @@ -0,0 +1,60 @@ 3.4 +#ifndef RESIZINGARRAYDEQUE_HPP 3.5 +#define RESIZINGARRAYDEQUE_HPP 3.6 + 3.7 +#include <cstddef> 3.8 + 3.9 +template <typename T> 3.10 +class ResizingArrayDeque { 3.11 + 3.12 +public: 3.13 + 3.14 + //////////////////////////////////////// 3.15 + class iterator { 3.16 + 3.17 + public: 3.18 + 3.19 + iterator( T *c, T *l, T *b, T *m ); 3.20 + 3.21 + iterator& operator++(); 3.22 + iterator operator++(int); 3.23 + 3.24 + T operator*(); 3.25 + bool operator!=( typename ResizingArrayDeque<T>::iterator ); 3.26 + 3.27 + private: 3.28 + 3.29 + T *curr; 3.30 + T *last; 3.31 + T *begin; 3.32 + T *max; 3.33 + }; 3.34 + 3.35 + //////////////////////////////////////// 3.36 + ResizingArrayDeque( void ); 3.37 + ~ResizingArrayDeque( void ); 3.38 + 3.39 + void push_left( T &item ); 3.40 + void push_right( T &item ); 3.41 + T pop_left( void ); 3.42 + T pop_right( void ); 3.43 + 3.44 + bool is_empty( void ); 3.45 + size_t size( void ); 3.46 + 3.47 + iterator begin( void ); 3.48 + iterator end( void ); 3.49 + 3.50 +private: 3.51 + 3.52 + size_t N; 3.53 + size_t max; 3.54 + T *first, *last; 3.55 + T *data; 3.56 + 3.57 + void resize( size_t new_max ); 3.58 + }; 3.59 + 3.60 + 3.61 + 3.62 +#endif 3.63 +