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 +