1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/algs4-c++/src/ResizingArrayDeque.cpp	Wed Jun 10 18:12:59 2015 -0500
     1.3 @@ -0,0 +1,261 @@
     1.4 +// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp
     1.5 +// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp
     1.6 +
     1.7 +
     1.8 +#include "ResizingArrayDeque.hpp"
     1.9 +
    1.10 +#include <cassert>
    1.11 +#include <cstddef>
    1.12 +
    1.13 +#include <iostream>
    1.14 +
    1.15 +template <typename T>
    1.16 +ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
    1.17 +    N (0),
    1.18 +    max(1),
    1.19 +    first(nullptr),
    1.20 +    last(nullptr) {
    1.21 +    data = new T[2];
    1.22 +    }
    1.23 +    
    1.24 +template <typename T>
    1.25 +ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
    1.26 +    assert( N == 0 );  // Catch the potential memory leak.
    1.27 +    if ( data )
    1.28 +        delete[] data;
    1.29 +    }
    1.30 +
    1.31 +template <typename T>
    1.32 +void ResizingArrayDeque<T>::push_right( T &item ) {
    1.33 +    if ( N == max )
    1.34 +        resize( 2 * max );
    1.35 +
    1.36 +    if ( last ) {
    1.37 +        if ( last == data )
    1.38 +            last = data + max - 1;
    1.39 +        else
    1.40 +            ++last;
    1.41 +        }
    1.42 +    else {
    1.43 +        first = last = data;
    1.44 +        }
    1.45 +
    1.46 +    *last = item;
    1.47 +    ++N;
    1.48 +    }
    1.49 +
    1.50 +template <typename T>
    1.51 +void ResizingArrayDeque<T>::push_left( T &item ) {
    1.52 +    if ( N == max )
    1.53 +        resize( 2 * max );
    1.54 +
    1.55 +    if ( first ) {
    1.56 +        if ( first == data )
    1.57 +            first = data + max - 1;
    1.58 +        else
    1.59 +            --first;
    1.60 +        }
    1.61 +    else {
    1.62 +        first = last = data;
    1.63 +        }
    1.64 +
    1.65 +    *first = item;
    1.66 +    ++N;
    1.67 +    }
    1.68 +
    1.69 +template <typename T>
    1.70 +T ResizingArrayDeque<T>::pop_right( void ) {
    1.71 +    assert( N > 0 );
    1.72 +
    1.73 +    T item = *last;
    1.74 +    N--;
    1.75 +
    1.76 +    if ( last == data ) {
    1.77 +        last = data + max - 1;
    1.78 +        }
    1.79 +    else {
    1.80 +        --last;
    1.81 +        }
    1.82 +
    1.83 +    if ( N == 0 )
    1.84 +        first = last = nullptr;
    1.85 +
    1.86 +    // if ( N <= max/4 )
    1.87 +    //     resize( max/2 );
    1.88 +
    1.89 +    return item;
    1.90 +    }
    1.91 +
    1.92 +template <typename T>
    1.93 +T ResizingArrayDeque<T>::pop_left( void ) {
    1.94 +    assert( N > 0 );
    1.95 +
    1.96 +    T item = *first;
    1.97 +    N--;
    1.98 +
    1.99 +    if ( first == data + max - 1 ) {
   1.100 +        first = data;
   1.101 +        }
   1.102 +    else {
   1.103 +        ++first;
   1.104 +        }
   1.105 +
   1.106 +    if ( N == 0 )
   1.107 +        first = last = nullptr;
   1.108 +
   1.109 +    // if ( N <= max/4 )
   1.110 +    //     resize( max/2 );
   1.111 +
   1.112 +    return item;
   1.113 +    }
   1.114 +
   1.115 +template <typename T>
   1.116 +bool ResizingArrayDeque<T>::is_empty( void ) {
   1.117 +    return N == 0;
   1.118 +    }
   1.119 +
   1.120 +template <typename T>
   1.121 +size_t ResizingArrayDeque<T>::size( void ) {
   1.122 +    return N;
   1.123 +    }
   1.124 +
   1.125 +template <typename T>
   1.126 +void ResizingArrayDeque<T>::resize( size_t new_max ) {
   1.127 +    T *new_data = new T[new_max];
   1.128 +
   1.129 +    if ( N ) {
   1.130 +        size_t i = 0;
   1.131 +        T *curr = first;
   1.132 +        while ( i < N ) {
   1.133 +            new_data[i] = *curr;
   1.134 +            ++curr;
   1.135 +            if ( curr == data + max )
   1.136 +                curr = data;
   1.137 +            ++i;
   1.138 +            }
   1.139 +        }
   1.140 +    first = new_data;
   1.141 +    last = new_data + N - 1;
   1.142 +
   1.143 +    T *old_data = data;
   1.144 +    data = new_data;
   1.145 +    delete[] old_data;
   1.146 +
   1.147 +    max = new_max;
   1.148 +    }
   1.149 +
   1.150 +template <typename T>
   1.151 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
   1.152 +    return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
   1.153 +    }
   1.154 +
   1.155 +template <typename T>
   1.156 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
   1.157 +    return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
   1.158 +    }
   1.159 +
   1.160 +
   1.161 +////////////////////////////////////////////////////////////////////////////////
   1.162 +
   1.163 +template <typename T>
   1.164 +ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
   1.165 +    curr (c),
   1.166 +    last (l),
   1.167 +    begin (b),
   1.168 +    max (m)
   1.169 +    {
   1.170 +    }
   1.171 +
   1.172 +template <typename T>
   1.173 +typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
   1.174 +    if ( this->curr == this->last ) {
   1.175 +        this->curr = nullptr;
   1.176 +        }
   1.177 +    else {
   1.178 +        this->curr += 1;
   1.179 +        if ( this->curr > this->max )
   1.180 +            this->curr = this->begin;
   1.181 +        }
   1.182 +
   1.183 +    return *this;
   1.184 +    }
   1.185 +
   1.186 +template <typename T>
   1.187 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
   1.188 +    auto t = ResizingArrayDeque<T>::iterator( *this );
   1.189 +
   1.190 +    if ( this->curr == this->last ) {
   1.191 +        this->curr = nullptr;
   1.192 +        }
   1.193 +    else {
   1.194 +        this->curr += 1;
   1.195 +        if ( this->curr > this->max )
   1.196 +            this->curr = this->begin;
   1.197 +        }
   1.198 +
   1.199 +    return t;
   1.200 +    }
   1.201 +
   1.202 +template <typename T>
   1.203 +T ResizingArrayDeque<T>::iterator::operator*() {
   1.204 +    return *(this->curr);
   1.205 +    }
   1.206 +
   1.207 +template <typename T>
   1.208 +bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
   1.209 +    return this->curr != other.curr;
   1.210 +    }
   1.211 +
   1.212 +
   1.213 +////////////////////////////////////////////////////////////////////////////////
   1.214 +
   1.215 +#ifdef RESIZINGARRAYDEQUE_MAIN
   1.216 +
   1.217 +#include <iostream>
   1.218 +
   1.219 +int main ( int argc, char **argv ) {
   1.220 +
   1.221 +    ResizingArrayDeque<long> deque;
   1.222 +    bool left = true;
   1.223 +
   1.224 +    long i;
   1.225 +    while ( ! std::cin.eof() ) {
   1.226 +        std::cin >> i;
   1.227 +        if ( std::cin.good() ) {
   1.228 +            if ( left ) {
   1.229 +                deque.push_left(i);
   1.230 +                left = false;
   1.231 +                }
   1.232 +            else {
   1.233 +                deque.push_right(i);
   1.234 +                left = true;
   1.235 +                }
   1.236 +            }
   1.237 +        }
   1.238 +
   1.239 +    std::cout << "Deque has " << deque.size() << " entries." << std::endl;
   1.240 +
   1.241 +    for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) {
   1.242 +        std::cout << *iter << std::endl;
   1.243 +        }
   1.244 +
   1.245 +    std::cout << "Popping entries..." << std::endl;
   1.246 +
   1.247 +    left = true;
   1.248 +    while ( ! deque.is_empty() ) {
   1.249 +        if ( left ) {
   1.250 +            i = deque.pop_left();
   1.251 +            left = false;
   1.252 +            }
   1.253 +        else {
   1.254 +            i = deque.pop_right();
   1.255 +            left = true;
   1.256 +            }
   1.257 +        std::cout << i << std::endl;
   1.258 +        }
   1.259 +
   1.260 +    std::cout << "Deque has " << deque.size() << " entries." << std::endl;
   1.261 +
   1.262 +    }
   1.263 +
   1.264 +#endif