# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1433969082 18000
# Node ID 1e3c509b6ac47abf7c910f3408f9a4014252c618
# Parent  846aeab17939fa311192aa4c027b717ae22e3d09
Added Deque (exercise 1.3.33)

diff -r 846aeab17939 -r 1e3c509b6ac4 algs4-c++/src/Deque.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/Deque.cpp	Wed Jun 10 15:44:42 2015 -0500
@@ -0,0 +1,215 @@
+// g++ -D DEQUE_MAIN -std=c++0x Deque.cpp
+// g++ -D DEQUE_MAIN -std=c++11 Deque.cpp
+
+
+#include "Deque.hpp"
+
+#include <cassert>
+#include <cstddef>
+
+#include <iostream>
+
+template <typename T>
+Deque<T>::Deque( void ) :
+    N (0),
+    first (nullptr),
+    last (nullptr)
+    {
+    }
+    
+template <typename T>
+Deque<T>::~Deque( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    while ( first ) {
+        Node *next = first->next;
+        delete first;
+        first = next;
+        }
+    }
+
+template <typename T>
+void Deque<T>::push_right( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = nullptr;
+    node->prev = nullptr;
+
+    if ( last ) {
+        last->next = node;
+        node->prev = last;
+        last = node;
+        }
+    else {
+        last = first = node;
+        }
+
+    N++;
+    }
+
+template <typename T>
+void Deque<T>::push_left( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = nullptr;
+    node->prev = nullptr;
+
+    if ( first ) {
+        node->next = first;
+        first->prev = node;
+        first = node;
+        }
+    else {
+        last = first = node;
+        }
+
+    N++;
+    }
+
+template <typename T>
+T Deque<T>::pop_left( void ) {
+    assert( N > 0 );
+
+    T item = first->item;
+
+    Node *old = first;
+    if ( first->next )
+        first->next->prev = nullptr;
+    first = first->next;
+    delete old;
+    N--;
+
+    if ( ! first )
+        last = nullptr;
+
+    return item;
+    }
+
+template <typename T>
+T Deque<T>::pop_right( void ) {
+    assert( N > 0 );
+
+    T item = last->item;
+
+    Node *old = last;
+    if ( last->prev )
+        last->prev->next = nullptr;
+    last = last->prev;
+    delete old;
+    N--;
+
+    if ( ! last )
+        first = nullptr;
+
+    return item;
+    }
+
+template <typename T>
+bool Deque<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t Deque<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::begin( void ) {
+    return Deque<T>::iterator( first );
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::end( void ) {
+    return Deque<T>::iterator( nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Deque<T>::iterator::iterator( Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
+    auto t = Deque<T>::iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+T Deque<T>::iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+#ifdef DEQUE_MAIN
+
+#include <iostream>
+
+int main ( int argc, char **argv ) {
+
+    Deque<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 << "Dequeuing 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 846aeab17939 -r 1e3c509b6ac4 algs4-c++/src/Deque.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/Deque.hpp	Wed Jun 10 15:44:42 2015 -0500
@@ -0,0 +1,71 @@
+#ifndef DEQUE_HPP
+#define DEQUE_HPP
+
+#include <cstddef>
+
+// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
+
+template <typename T>
+class Deque {
+
+private:
+
+    ////////////////////////////////////
+    class Node {
+    public:
+        T item;
+        Node *next;
+        Node *prev;
+        };
+
+public:
+
+    ////////////////////////////////////
+    class iterator;
+    friend class iterator;
+    class iterator {
+
+    public:
+
+        iterator( Node *c );
+
+        iterator& operator++();
+        iterator operator++(int);
+
+        T operator*();
+        bool operator!=( typename Deque<T>::iterator );
+
+    private:
+
+        Node *curr;
+        };
+
+    ////////////////////////////////////
+
+    Deque( void );
+    ~Deque( 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;
+    Node *first;
+    Node *last;
+
+    };
+
+
+
+#endif
+