discordia@18: // Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
discordia@18: 
discordia@11: #ifndef STEQUE_HPP
discordia@11: #define STEQUE_HPP
discordia@11: 
discordia@18: #include <cassert>
discordia@11: #include <cstddef>
discordia@11: 
discordia@11: template <typename T>
discordia@11: class Steque {
discordia@11: 
discordia@11: private:
discordia@11: 
discordia@11:     ////////////////////////////////////
discordia@11:     class Node {
discordia@11:     public:
discordia@11:         T item;
discordia@11:         Node *next;
discordia@11:         };
discordia@11: 
discordia@11: 
discordia@11: public:
discordia@11: 
discordia@11:     ////////////////////////////////////
discordia@11:     class iterator;
discordia@11:     friend class iterator;
discordia@11:     class iterator {
discordia@11: 
discordia@11:     public:
discordia@11: 
discordia@11:         iterator( Node *c );
discordia@11: 
discordia@11:         iterator& operator++();
discordia@11:         iterator operator++(int);
discordia@11: 
discordia@11:         T operator*();
discordia@11:         bool operator!=( typename Steque<T>::iterator );
discordia@11: 
discordia@11:     private:
discordia@11: 
discordia@11:         Node *curr;
discordia@11:         };
discordia@11: 
discordia@11:     ////////////////////////////////////
discordia@11: 
discordia@11:     Steque( void );
discordia@11:     ~Steque( void );
discordia@11: 
discordia@11:     void push( T &item );
discordia@11:     T pop( void );
discordia@11:     void enqueue( T &item );
discordia@11: 
discordia@11:     bool is_empty( void );
discordia@11:     size_t size( void );
discordia@11: 
discordia@11:     iterator begin( void );
discordia@11:     iterator end( void );
discordia@11: 
discordia@11: private:
discordia@11: 
discordia@11:     size_t N;
discordia@11:     Node *list;
discordia@11: 
discordia@11:     };
discordia@11: 
discordia@11: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: Steque<T>::Steque( void ) :
discordia@18:     N (0),
discordia@18:     list (nullptr)
discordia@18:     {
discordia@18:     }
discordia@18:     
discordia@18: template <typename T>
discordia@18: Steque<T>::~Steque( void ) {
discordia@18:     assert( N == 0 );  // Catch the potential memory leak.
discordia@18:     while ( list ) {
discordia@18:         Node * next = list->next;
discordia@18:         delete list;
discordia@18:         list = next;
discordia@18:         }
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void Steque<T>::push( T &item ) {
discordia@18:     Node * node = new Node();
discordia@18:     node->item = item;
discordia@18:     node->next = list;
discordia@18:     list = node;
discordia@18:     N++;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Steque<T>::pop( void ) {
discordia@18:     assert( N > 0 );
discordia@18: 
discordia@18:     T item = list->item;
discordia@18: 
discordia@18:     Node *old = list;
discordia@18:     list = list->next;
discordia@18:     delete old;
discordia@18:     N--;
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void Steque<T>::enqueue( T &item ) {
discordia@18:     Node *curr = list;
discordia@18: 
discordia@18:     Node *node = new Node();
discordia@18:     node->item = item;
discordia@18:     node->next = nullptr;
discordia@18: 
discordia@18:     if ( ! curr ) {
discordia@18:         list = node;
discordia@18:         N++;
discordia@18:         return;
discordia@18:         }
discordia@18: 
discordia@18:     while ( curr->next ) {
discordia@18:         curr = curr->next;
discordia@18:         }
discordia@18: 
discordia@18:     curr->next = node;
discordia@18:     N++;
discordia@18: 
discordia@18:     return;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Steque<T>::is_empty( void ) {
discordia@18:     return N == 0;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: size_t Steque<T>::size( void ) {
discordia@18:     return N;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Steque<T>::iterator Steque<T>::begin( void ) {
discordia@18:     return Steque<T>::iterator( list );
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Steque<T>::iterator Steque<T>::end( void ) {
discordia@18:     return Steque<T>::iterator( nullptr );
discordia@18:     }
discordia@18: 
discordia@18: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: Steque<T>::iterator::iterator( Node *c ) :
discordia@18:     curr (c)
discordia@18:     {
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Steque<T>::iterator & Steque<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 Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
discordia@18:     auto t = Steque<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 Steque<T>::iterator::operator*() {
discordia@18:     return this->curr->item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
discordia@18:     return this->curr != other.curr;
discordia@18:     }
discordia@18: 
discordia@11: 
discordia@11: #endif
discordia@11: