discordia@18: // Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
discordia@18: 
discordia@12: #ifndef DEQUE_HPP
discordia@12: #define DEQUE_HPP
discordia@12: 
discordia@18: #include <cassert>
discordia@12: #include <cstddef>
discordia@12: 
discordia@12: template <typename T>
discordia@12: class Deque {
discordia@12: 
discordia@12: private:
discordia@12: 
discordia@12:     ////////////////////////////////////
discordia@12:     class Node {
discordia@12:     public:
discordia@12:         T item;
discordia@12:         Node *next;
discordia@12:         Node *prev;
discordia@12:         };
discordia@12: 
discordia@12: public:
discordia@12: 
discordia@12:     ////////////////////////////////////
discordia@12:     class iterator;
discordia@12:     friend class iterator;
discordia@12:     class iterator {
discordia@12: 
discordia@12:     public:
discordia@12: 
discordia@12:         iterator( Node *c );
discordia@12: 
discordia@12:         iterator& operator++();
discordia@12:         iterator operator++(int);
discordia@12: 
discordia@12:         T operator*();
discordia@12:         bool operator!=( typename Deque<T>::iterator );
discordia@12: 
discordia@12:     private:
discordia@12: 
discordia@12:         Node *curr;
discordia@12:         };
discordia@12: 
discordia@12:     ////////////////////////////////////
discordia@12: 
discordia@12:     Deque( void );
discordia@12:     ~Deque( void );
discordia@12: 
discordia@12:     void push_left( T &item );
discordia@12:     void push_right( T &item );
discordia@12:     T pop_left( void );
discordia@12:     T pop_right( void );
discordia@12: 
discordia@12:     bool is_empty( void );
discordia@12:     size_t size( void );
discordia@12: 
discordia@12:     iterator begin( void );
discordia@12:     iterator end( void );
discordia@12: 
discordia@12: 
discordia@12: private:
discordia@12: 
discordia@12:     size_t N;
discordia@12:     Node *first;
discordia@12:     Node *last;
discordia@12: 
discordia@12:     };
discordia@12: 
discordia@12: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: Deque<T>::Deque( void ) :
discordia@18:     N (0),
discordia@18:     first (nullptr),
discordia@18:     last (nullptr)
discordia@18:     {
discordia@18:     }
discordia@18:     
discordia@18: template <typename T>
discordia@18: Deque<T>::~Deque( void ) {
discordia@18:     assert( N == 0 );  // Catch the potential memory leak.
discordia@18:     while ( first ) {
discordia@18:         Node *next = first->next;
discordia@18:         delete first;
discordia@18:         first = next;
discordia@18:         }
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void Deque<T>::push_right( T &item ) {
discordia@18:     Node * node = new Node();
discordia@18:     node->item = item;
discordia@18:     node->next = nullptr;
discordia@18:     node->prev = nullptr;
discordia@18: 
discordia@18:     if ( last ) {
discordia@18:         last->next = node;
discordia@18:         node->prev = last;
discordia@18:         last = node;
discordia@18:         }
discordia@18:     else {
discordia@18:         last = first = node;
discordia@18:         }
discordia@18: 
discordia@18:     N++;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void Deque<T>::push_left( T &item ) {
discordia@18:     Node * node = new Node();
discordia@18:     node->item = item;
discordia@18:     node->next = nullptr;
discordia@18:     node->prev = nullptr;
discordia@18: 
discordia@18:     if ( first ) {
discordia@18:         node->next = first;
discordia@18:         first->prev = node;
discordia@18:         first = node;
discordia@18:         }
discordia@18:     else {
discordia@18:         last = first = node;
discordia@18:         }
discordia@18: 
discordia@18:     N++;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Deque<T>::pop_left( void ) {
discordia@18:     assert( N > 0 );
discordia@18: 
discordia@18:     T item = first->item;
discordia@18: 
discordia@18:     Node *old = first;
discordia@18:     if ( first->next )
discordia@18:         first->next->prev = nullptr;
discordia@18:     first = first->next;
discordia@18:     delete old;
discordia@18:     N--;
discordia@18: 
discordia@18:     if ( ! first )
discordia@18:         last = nullptr;
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Deque<T>::pop_right( void ) {
discordia@18:     assert( N > 0 );
discordia@18: 
discordia@18:     T item = last->item;
discordia@18: 
discordia@18:     Node *old = last;
discordia@18:     if ( last->prev )
discordia@18:         last->prev->next = nullptr;
discordia@18:     last = last->prev;
discordia@18:     delete old;
discordia@18:     N--;
discordia@18: 
discordia@18:     if ( ! last )
discordia@18:         first = nullptr;
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Deque<T>::is_empty( void ) {
discordia@18:     return N == 0;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: size_t Deque<T>::size( void ) {
discordia@18:     return N;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Deque<T>::iterator Deque<T>::begin( void ) {
discordia@18:     return Deque<T>::iterator( first );
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Deque<T>::iterator Deque<T>::end( void ) {
discordia@18:     return Deque<T>::iterator( nullptr );
discordia@18:     }
discordia@18: 
discordia@18: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: Deque<T>::iterator::iterator( Node *c ) :
discordia@18:     curr (c)
discordia@18:     {
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
discordia@18:     if ( this->curr != nullptr ) {
discordia@18:         this->curr = this->curr->next;
discordia@18:         }
discordia@18:     return *this;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
discordia@18:     auto t = Deque<T>::iterator( *this );
discordia@18: 
discordia@18:     if ( this->curr != nullptr ) {
discordia@18:         this->curr = this->curr->next;
discordia@18:         }
discordia@18:     return t;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Deque<T>::iterator::operator*() {
discordia@18:     return this->curr->item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
discordia@18:     return this->curr != other.curr;
discordia@18:     }
discordia@12: 
discordia@12: #endif
discordia@12: