1.1 --- a/algs4-c++/src/Deque.hpp	Fri Jun 19 18:18:47 2015 -0500
     1.2 +++ b/algs4-c++/src/Deque.hpp	Sat Jun 20 19:36:11 2015 -0500
     1.3 @@ -1,10 +1,11 @@
     1.4 +// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
     1.5 +
     1.6  #ifndef DEQUE_HPP
     1.7  #define DEQUE_HPP
     1.8  
     1.9 +#include <cassert>
    1.10  #include <cstddef>
    1.11  
    1.12 -// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
    1.13 -
    1.14  template <typename T>
    1.15  class Deque {
    1.16  
    1.17 @@ -66,6 +67,158 @@
    1.18      };
    1.19  
    1.20  
    1.21 +////////////////////////////////////////////////////////////////////////////////
    1.22 +
    1.23 +template <typename T>
    1.24 +Deque<T>::Deque( void ) :
    1.25 +    N (0),
    1.26 +    first (nullptr),
    1.27 +    last (nullptr)
    1.28 +    {
    1.29 +    }
    1.30 +    
    1.31 +template <typename T>
    1.32 +Deque<T>::~Deque( void ) {
    1.33 +    assert( N == 0 );  // Catch the potential memory leak.
    1.34 +    while ( first ) {
    1.35 +        Node *next = first->next;
    1.36 +        delete first;
    1.37 +        first = next;
    1.38 +        }
    1.39 +    }
    1.40 +
    1.41 +template <typename T>
    1.42 +void Deque<T>::push_right( T &item ) {
    1.43 +    Node * node = new Node();
    1.44 +    node->item = item;
    1.45 +    node->next = nullptr;
    1.46 +    node->prev = nullptr;
    1.47 +
    1.48 +    if ( last ) {
    1.49 +        last->next = node;
    1.50 +        node->prev = last;
    1.51 +        last = node;
    1.52 +        }
    1.53 +    else {
    1.54 +        last = first = node;
    1.55 +        }
    1.56 +
    1.57 +    N++;
    1.58 +    }
    1.59 +
    1.60 +template <typename T>
    1.61 +void Deque<T>::push_left( T &item ) {
    1.62 +    Node * node = new Node();
    1.63 +    node->item = item;
    1.64 +    node->next = nullptr;
    1.65 +    node->prev = nullptr;
    1.66 +
    1.67 +    if ( first ) {
    1.68 +        node->next = first;
    1.69 +        first->prev = node;
    1.70 +        first = node;
    1.71 +        }
    1.72 +    else {
    1.73 +        last = first = node;
    1.74 +        }
    1.75 +
    1.76 +    N++;
    1.77 +    }
    1.78 +
    1.79 +template <typename T>
    1.80 +T Deque<T>::pop_left( void ) {
    1.81 +    assert( N > 0 );
    1.82 +
    1.83 +    T item = first->item;
    1.84 +
    1.85 +    Node *old = first;
    1.86 +    if ( first->next )
    1.87 +        first->next->prev = nullptr;
    1.88 +    first = first->next;
    1.89 +    delete old;
    1.90 +    N--;
    1.91 +
    1.92 +    if ( ! first )
    1.93 +        last = nullptr;
    1.94 +
    1.95 +    return item;
    1.96 +    }
    1.97 +
    1.98 +template <typename T>
    1.99 +T Deque<T>::pop_right( void ) {
   1.100 +    assert( N > 0 );
   1.101 +
   1.102 +    T item = last->item;
   1.103 +
   1.104 +    Node *old = last;
   1.105 +    if ( last->prev )
   1.106 +        last->prev->next = nullptr;
   1.107 +    last = last->prev;
   1.108 +    delete old;
   1.109 +    N--;
   1.110 +
   1.111 +    if ( ! last )
   1.112 +        first = nullptr;
   1.113 +
   1.114 +    return item;
   1.115 +    }
   1.116 +
   1.117 +template <typename T>
   1.118 +bool Deque<T>::is_empty( void ) {
   1.119 +    return N == 0;
   1.120 +    }
   1.121 +
   1.122 +template <typename T>
   1.123 +size_t Deque<T>::size( void ) {
   1.124 +    return N;
   1.125 +    }
   1.126 +
   1.127 +template <typename T>
   1.128 +typename Deque<T>::iterator Deque<T>::begin( void ) {
   1.129 +    return Deque<T>::iterator( first );
   1.130 +    }
   1.131 +
   1.132 +template <typename T>
   1.133 +typename Deque<T>::iterator Deque<T>::end( void ) {
   1.134 +    return Deque<T>::iterator( nullptr );
   1.135 +    }
   1.136 +
   1.137 +
   1.138 +////////////////////////////////////////////////////////////////////////////////
   1.139 +
   1.140 +template <typename T>
   1.141 +Deque<T>::iterator::iterator( Node *c ) :
   1.142 +    curr (c)
   1.143 +    {
   1.144 +    }
   1.145 +
   1.146 +template <typename T>
   1.147 +typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
   1.148 +    if ( this->curr != nullptr ) {
   1.149 +        this->curr = this->curr->next;
   1.150 +        }
   1.151 +    return *this;
   1.152 +    }
   1.153 +
   1.154 +template <typename T>
   1.155 +typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
   1.156 +    auto t = Deque<T>::iterator( *this );
   1.157 +
   1.158 +    if ( this->curr != nullptr ) {
   1.159 +        this->curr = this->curr->next;
   1.160 +        }
   1.161 +    return t;
   1.162 +    }
   1.163 +
   1.164 +template <typename T>
   1.165 +T Deque<T>::iterator::operator*() {
   1.166 +    return this->curr->item;
   1.167 +    }
   1.168 +
   1.169 +template <typename T>
   1.170 +bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
   1.171 +    return this->curr != other.curr;
   1.172 +    }
   1.173  
   1.174  #endif
   1.175