discordia@14: // g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp
discordia@14: // g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp
discordia@14: 
discordia@14: 
discordia@14: #include "ResizingArrayDeque.hpp"
discordia@14: 
discordia@14: #include <cassert>
discordia@14: #include <cstddef>
discordia@14: 
discordia@14: #include <iostream>
discordia@14: 
discordia@14: template <typename T>
discordia@14: ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
discordia@14:     N (0),
discordia@14:     max(1),
discordia@14:     first(nullptr),
discordia@14:     last(nullptr) {
discordia@14:     data = new T[2];
discordia@14:     }
discordia@14:     
discordia@14: template <typename T>
discordia@14: ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
discordia@14:     assert( N == 0 );  // Catch the potential memory leak.
discordia@14:     if ( data )
discordia@14:         delete[] data;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: void ResizingArrayDeque<T>::push_right( T &item ) {
discordia@14:     if ( N == max )
discordia@14:         resize( 2 * max );
discordia@14: 
discordia@14:     if ( last ) {
discordia@14:         if ( last == data )
discordia@14:             last = data + max - 1;
discordia@14:         else
discordia@14:             ++last;
discordia@14:         }
discordia@14:     else {
discordia@14:         first = last = data;
discordia@14:         }
discordia@14: 
discordia@14:     *last = item;
discordia@14:     ++N;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: void ResizingArrayDeque<T>::push_left( T &item ) {
discordia@14:     if ( N == max )
discordia@14:         resize( 2 * max );
discordia@14: 
discordia@14:     if ( first ) {
discordia@14:         if ( first == data )
discordia@14:             first = data + max - 1;
discordia@14:         else
discordia@14:             --first;
discordia@14:         }
discordia@14:     else {
discordia@14:         first = last = data;
discordia@14:         }
discordia@14: 
discordia@14:     *first = item;
discordia@14:     ++N;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: T ResizingArrayDeque<T>::pop_right( void ) {
discordia@14:     assert( N > 0 );
discordia@14: 
discordia@14:     T item = *last;
discordia@14:     N--;
discordia@14: 
discordia@14:     if ( last == data ) {
discordia@14:         last = data + max - 1;
discordia@14:         }
discordia@14:     else {
discordia@14:         --last;
discordia@14:         }
discordia@14: 
discordia@14:     if ( N == 0 )
discordia@14:         first = last = nullptr;
discordia@14: 
discordia@14:     // if ( N <= max/4 )
discordia@14:     //     resize( max/2 );
discordia@14: 
discordia@14:     return item;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: T ResizingArrayDeque<T>::pop_left( void ) {
discordia@14:     assert( N > 0 );
discordia@14: 
discordia@14:     T item = *first;
discordia@14:     N--;
discordia@14: 
discordia@14:     if ( first == data + max - 1 ) {
discordia@14:         first = data;
discordia@14:         }
discordia@14:     else {
discordia@14:         ++first;
discordia@14:         }
discordia@14: 
discordia@14:     if ( N == 0 )
discordia@14:         first = last = nullptr;
discordia@14: 
discordia@14:     // if ( N <= max/4 )
discordia@14:     //     resize( max/2 );
discordia@14: 
discordia@14:     return item;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: bool ResizingArrayDeque<T>::is_empty( void ) {
discordia@14:     return N == 0;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: size_t ResizingArrayDeque<T>::size( void ) {
discordia@14:     return N;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: void ResizingArrayDeque<T>::resize( size_t new_max ) {
discordia@14:     T *new_data = new T[new_max];
discordia@14: 
discordia@14:     if ( N ) {
discordia@14:         size_t i = 0;
discordia@14:         T *curr = first;
discordia@14:         while ( i < N ) {
discordia@14:             new_data[i] = *curr;
discordia@14:             ++curr;
discordia@14:             if ( curr == data + max )
discordia@14:                 curr = data;
discordia@14:             ++i;
discordia@14:             }
discordia@14:         }
discordia@14:     first = new_data;
discordia@14:     last = new_data + N - 1;
discordia@14: 
discordia@14:     T *old_data = data;
discordia@14:     data = new_data;
discordia@14:     delete[] old_data;
discordia@14: 
discordia@14:     max = new_max;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
discordia@14:     return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
discordia@14:     return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
discordia@14:     }
discordia@14: 
discordia@14: 
discordia@14: ////////////////////////////////////////////////////////////////////////////////
discordia@14: 
discordia@14: template <typename T>
discordia@14: ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
discordia@14:     curr (c),
discordia@14:     last (l),
discordia@14:     begin (b),
discordia@14:     max (m)
discordia@14:     {
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
discordia@14:     if ( this->curr == this->last ) {
discordia@14:         this->curr = nullptr;
discordia@14:         }
discordia@14:     else {
discordia@14:         this->curr += 1;
discordia@14:         if ( this->curr > this->max )
discordia@14:             this->curr = this->begin;
discordia@14:         }
discordia@14: 
discordia@14:     return *this;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
discordia@14:     auto t = ResizingArrayDeque<T>::iterator( *this );
discordia@14: 
discordia@14:     if ( this->curr == this->last ) {
discordia@14:         this->curr = nullptr;
discordia@14:         }
discordia@14:     else {
discordia@14:         this->curr += 1;
discordia@14:         if ( this->curr > this->max )
discordia@14:             this->curr = this->begin;
discordia@14:         }
discordia@14: 
discordia@14:     return t;
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: T ResizingArrayDeque<T>::iterator::operator*() {
discordia@14:     return *(this->curr);
discordia@14:     }
discordia@14: 
discordia@14: template <typename T>
discordia@14: bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
discordia@14:     return this->curr != other.curr;
discordia@14:     }
discordia@14: 
discordia@14: 
discordia@14: ////////////////////////////////////////////////////////////////////////////////
discordia@14: 
discordia@14: #ifdef RESIZINGARRAYDEQUE_MAIN
discordia@14: 
discordia@14: #include <iostream>
discordia@14: 
discordia@14: int main ( int argc, char **argv ) {
discordia@14: 
discordia@14:     ResizingArrayDeque<long> deque;
discordia@14:     bool left = true;
discordia@14: 
discordia@14:     long i;
discordia@14:     while ( ! std::cin.eof() ) {
discordia@14:         std::cin >> i;
discordia@14:         if ( std::cin.good() ) {
discordia@14:             if ( left ) {
discordia@14:                 deque.push_left(i);
discordia@14:                 left = false;
discordia@14:                 }
discordia@14:             else {
discordia@14:                 deque.push_right(i);
discordia@14:                 left = true;
discordia@14:                 }
discordia@14:             }
discordia@14:         }
discordia@14: 
discordia@14:     std::cout << "Deque has " << deque.size() << " entries." << std::endl;
discordia@14: 
discordia@14:     for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) {
discordia@14:         std::cout << *iter << std::endl;
discordia@14:         }
discordia@14: 
discordia@14:     std::cout << "Popping entries..." << std::endl;
discordia@14: 
discordia@14:     left = true;
discordia@14:     while ( ! deque.is_empty() ) {
discordia@14:         if ( left ) {
discordia@14:             i = deque.pop_left();
discordia@14:             left = false;
discordia@14:             }
discordia@14:         else {
discordia@14:             i = deque.pop_right();
discordia@14:             left = true;
discordia@14:             }
discordia@14:         std::cout << i << std::endl;
discordia@14:         }
discordia@14: 
discordia@14:     std::cout << "Deque has " << deque.size() << " entries." << std::endl;
discordia@14: 
discordia@14:     }
discordia@14: 
discordia@14: #endif