discordia@12: // g++ -D DEQUE_MAIN -std=c++0x Deque.cpp
discordia@12: // g++ -D DEQUE_MAIN -std=c++11 Deque.cpp
discordia@12: 
discordia@12: 
discordia@12: #include "Deque.hpp"
discordia@12: 
discordia@12: #include <cassert>
discordia@12: #include <cstddef>
discordia@12: 
discordia@12: #include <iostream>
discordia@12: 
discordia@12: template <typename T>
discordia@12: Deque<T>::Deque( void ) :
discordia@12:     N (0),
discordia@12:     first (nullptr),
discordia@12:     last (nullptr)
discordia@12:     {
discordia@12:     }
discordia@12:     
discordia@12: template <typename T>
discordia@12: Deque<T>::~Deque( void ) {
discordia@12:     assert( N == 0 );  // Catch the potential memory leak.
discordia@12:     while ( first ) {
discordia@12:         Node *next = first->next;
discordia@12:         delete first;
discordia@12:         first = next;
discordia@12:         }
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: void Deque<T>::push_right( T &item ) {
discordia@12:     Node * node = new Node();
discordia@12:     node->item = item;
discordia@12:     node->next = nullptr;
discordia@12:     node->prev = nullptr;
discordia@12: 
discordia@12:     if ( last ) {
discordia@12:         last->next = node;
discordia@12:         node->prev = last;
discordia@12:         last = node;
discordia@12:         }
discordia@12:     else {
discordia@12:         last = first = node;
discordia@12:         }
discordia@12: 
discordia@12:     N++;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: void Deque<T>::push_left( T &item ) {
discordia@12:     Node * node = new Node();
discordia@12:     node->item = item;
discordia@12:     node->next = nullptr;
discordia@12:     node->prev = nullptr;
discordia@12: 
discordia@12:     if ( first ) {
discordia@12:         node->next = first;
discordia@12:         first->prev = node;
discordia@12:         first = node;
discordia@12:         }
discordia@12:     else {
discordia@12:         last = first = node;
discordia@12:         }
discordia@12: 
discordia@12:     N++;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: T Deque<T>::pop_left( void ) {
discordia@12:     assert( N > 0 );
discordia@12: 
discordia@12:     T item = first->item;
discordia@12: 
discordia@12:     Node *old = first;
discordia@12:     if ( first->next )
discordia@12:         first->next->prev = nullptr;
discordia@12:     first = first->next;
discordia@12:     delete old;
discordia@12:     N--;
discordia@12: 
discordia@12:     if ( ! first )
discordia@12:         last = nullptr;
discordia@12: 
discordia@12:     return item;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: T Deque<T>::pop_right( void ) {
discordia@12:     assert( N > 0 );
discordia@12: 
discordia@12:     T item = last->item;
discordia@12: 
discordia@12:     Node *old = last;
discordia@12:     if ( last->prev )
discordia@12:         last->prev->next = nullptr;
discordia@12:     last = last->prev;
discordia@12:     delete old;
discordia@12:     N--;
discordia@12: 
discordia@12:     if ( ! last )
discordia@12:         first = nullptr;
discordia@12: 
discordia@12:     return item;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: bool Deque<T>::is_empty( void ) {
discordia@12:     return N == 0;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: size_t Deque<T>::size( void ) {
discordia@12:     return N;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: typename Deque<T>::iterator Deque<T>::begin( void ) {
discordia@12:     return Deque<T>::iterator( first );
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: typename Deque<T>::iterator Deque<T>::end( void ) {
discordia@12:     return Deque<T>::iterator( nullptr );
discordia@12:     }
discordia@12: 
discordia@12: 
discordia@12: ////////////////////////////////////////////////////////////////////////////////
discordia@12: 
discordia@12: template <typename T>
discordia@12: Deque<T>::iterator::iterator( Node *c ) :
discordia@12:     curr (c)
discordia@12:     {
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
discordia@12:     if ( this->curr != nullptr ) {
discordia@12:         this->curr = this->curr->next;
discordia@12:         }
discordia@12:     return *this;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
discordia@12:     auto t = Deque<T>::iterator( *this );
discordia@12: 
discordia@12:     if ( this->curr != nullptr ) {
discordia@12:         this->curr = this->curr->next;
discordia@12:         }
discordia@12:     return t;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: T Deque<T>::iterator::operator*() {
discordia@12:     return this->curr->item;
discordia@12:     }
discordia@12: 
discordia@12: template <typename T>
discordia@12: bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
discordia@12:     return this->curr != other.curr;
discordia@12:     }
discordia@12: 
discordia@12: 
discordia@12: ////////////////////////////////////////////////////////////////////////////////
discordia@12: 
discordia@12: #ifdef DEQUE_MAIN
discordia@12: 
discordia@12: #include <iostream>
discordia@12: 
discordia@12: int main ( int argc, char **argv ) {
discordia@12: 
discordia@12:     Deque<long> deque;
discordia@12:     bool left = true;
discordia@12: 
discordia@12:     long i;
discordia@12:     while ( ! std::cin.eof() ) {
discordia@12:         std::cin >> i;
discordia@12:         if ( std::cin.good() )  {
discordia@12:             if ( left ) {
discordia@12:                 deque.push_left( i );
discordia@12:                 left = false;
discordia@12:                 }
discordia@12:             else {
discordia@12:                 deque.push_right( i );
discordia@12:                 left = true;
discordia@12:                 }
discordia@12:             }
discordia@12:         }
discordia@12: 
discordia@12:     std::cout << "Deque has " << deque.size() << " entries." << std::endl;
discordia@12: 
discordia@12:     for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) {
discordia@12:         std::cout << *iter << std::endl;
discordia@12:         }
discordia@12: 
discordia@12:     std::cout << "Dequeuing entries..." << std::endl;
discordia@12: 
discordia@12:     left = true;
discordia@12:     while ( ! deque.is_empty() ) {
discordia@12:         if ( left ) {
discordia@12:             i = deque.pop_left();
discordia@12:             left = false;
discordia@12:             }
discordia@12:         else {
discordia@12:             i = deque.pop_right();
discordia@12:             left = true;
discordia@12:             }
discordia@12:         std::cout << i << std::endl;
discordia@12:         }
discordia@12: 
discordia@12:     std::cout << "Deque has " << deque.size() << " entries." << std::endl;
discordia@12: 
discordia@12:     }
discordia@12: 
discordia@12: #endif