# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1433977979 18000
# Node ID 2f87e582d91a18e976338d03ea0f16320e09e62f
# Parent  5b5b5a337763a58f2f228ac482eae48d19e049a3
ResizingArrayDeque (exercise 1.3.33)

diff -r 5b5b5a337763 -r 2f87e582d91a algs4-c++/1.3.33-2
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/1.3.33-2	Wed Jun 10 18:12:59 2015 -0500
@@ -0,0 +1,1 @@
+src/ResizingArrayDeque.hpp
\ No newline at end of file
diff -r 5b5b5a337763 -r 2f87e582d91a algs4-c++/src/ResizingArrayDeque.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/ResizingArrayDeque.cpp	Wed Jun 10 18:12:59 2015 -0500
@@ -0,0 +1,261 @@
+// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp
+// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp
+
+
+#include "ResizingArrayDeque.hpp"
+
+#include <cassert>
+#include <cstddef>
+
+#include <iostream>
+
+template <typename T>
+ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
+    N (0),
+    max(1),
+    first(nullptr),
+    last(nullptr) {
+    data = new T[2];
+    }
+    
+template <typename T>
+ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    if ( data )
+        delete[] data;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::push_right( T &item ) {
+    if ( N == max )
+        resize( 2 * max );
+
+    if ( last ) {
+        if ( last == data )
+            last = data + max - 1;
+        else
+            ++last;
+        }
+    else {
+        first = last = data;
+        }
+
+    *last = item;
+    ++N;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::push_left( T &item ) {
+    if ( N == max )
+        resize( 2 * max );
+
+    if ( first ) {
+        if ( first == data )
+            first = data + max - 1;
+        else
+            --first;
+        }
+    else {
+        first = last = data;
+        }
+
+    *first = item;
+    ++N;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::pop_right( void ) {
+    assert( N > 0 );
+
+    T item = *last;
+    N--;
+
+    if ( last == data ) {
+        last = data + max - 1;
+        }
+    else {
+        --last;
+        }
+
+    if ( N == 0 )
+        first = last = nullptr;
+
+    // if ( N <= max/4 )
+    //     resize( max/2 );
+
+    return item;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::pop_left( void ) {
+    assert( N > 0 );
+
+    T item = *first;
+    N--;
+
+    if ( first == data + max - 1 ) {
+        first = data;
+        }
+    else {
+        ++first;
+        }
+
+    if ( N == 0 )
+        first = last = nullptr;
+
+    // if ( N <= max/4 )
+    //     resize( max/2 );
+
+    return item;
+    }
+
+template <typename T>
+bool ResizingArrayDeque<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t ResizingArrayDeque<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::resize( size_t new_max ) {
+    T *new_data = new T[new_max];
+
+    if ( N ) {
+        size_t i = 0;
+        T *curr = first;
+        while ( i < N ) {
+            new_data[i] = *curr;
+            ++curr;
+            if ( curr == data + max )
+                curr = data;
+            ++i;
+            }
+        }
+    first = new_data;
+    last = new_data + N - 1;
+
+    T *old_data = data;
+    data = new_data;
+    delete[] old_data;
+
+    max = new_max;
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
+    return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
+    return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
+    curr (c),
+    last (l),
+    begin (b),
+    max (m)
+    {
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
+    if ( this->curr == this->last ) {
+        this->curr = nullptr;
+        }
+    else {
+        this->curr += 1;
+        if ( this->curr > this->max )
+            this->curr = this->begin;
+        }
+
+    return *this;
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
+    auto t = ResizingArrayDeque<T>::iterator( *this );
+
+    if ( this->curr == this->last ) {
+        this->curr = nullptr;
+        }
+    else {
+        this->curr += 1;
+        if ( this->curr > this->max )
+            this->curr = this->begin;
+        }
+
+    return t;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::iterator::operator*() {
+    return *(this->curr);
+    }
+
+template <typename T>
+bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+#ifdef RESIZINGARRAYDEQUE_MAIN
+
+#include <iostream>
+
+int main ( int argc, char **argv ) {
+
+    ResizingArrayDeque<long> deque;
+    bool left = true;
+
+    long i;
+    while ( ! std::cin.eof() ) {
+        std::cin >> i;
+        if ( std::cin.good() ) {
+            if ( left ) {
+                deque.push_left(i);
+                left = false;
+                }
+            else {
+                deque.push_right(i);
+                left = true;
+                }
+            }
+        }
+
+    std::cout << "Deque has " << deque.size() << " entries." << std::endl;
+
+    for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+    std::cout << "Popping entries..." << std::endl;
+
+    left = true;
+    while ( ! deque.is_empty() ) {
+        if ( left ) {
+            i = deque.pop_left();
+            left = false;
+            }
+        else {
+            i = deque.pop_right();
+            left = true;
+            }
+        std::cout << i << std::endl;
+        }
+
+    std::cout << "Deque has " << deque.size() << " entries." << std::endl;
+
+    }
+
+#endif
diff -r 5b5b5a337763 -r 2f87e582d91a algs4-c++/src/ResizingArrayDeque.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/ResizingArrayDeque.hpp	Wed Jun 10 18:12:59 2015 -0500
@@ -0,0 +1,60 @@
+#ifndef RESIZINGARRAYDEQUE_HPP
+#define RESIZINGARRAYDEQUE_HPP
+
+#include <cstddef>
+
+template <typename T>
+class ResizingArrayDeque {
+
+public:
+
+    ////////////////////////////////////////
+    class iterator {
+
+    public:
+
+        iterator( T *c, T *l, T *b, T *m );
+
+        iterator& operator++();
+        iterator operator++(int);
+
+        T operator*();
+        bool operator!=( typename ResizingArrayDeque<T>::iterator );
+
+    private:
+
+        T *curr;
+        T *last;
+        T *begin;
+        T *max;
+        };
+
+    ////////////////////////////////////////
+    ResizingArrayDeque( void );
+    ~ResizingArrayDeque( void );
+
+    void push_left( T &item );
+    void push_right( T &item );
+    T pop_left( void );
+    T pop_right( void );
+
+    bool is_empty( void );
+    size_t size( void );
+
+    iterator begin( void );
+    iterator end( void );
+
+private:
+
+    size_t N;
+    size_t max;
+    T *first, *last;
+    T *data;
+
+    void resize( size_t new_max );
+    };
+
+
+
+#endif
+