discordia@18: // Stack built on a resizing array.
discordia@18: 
discordia@3: #ifndef RESIZINGARRAYSTACK_HPP
discordia@3: #define RESIZINGARRAYSTACK_HPP
discordia@3: 
discordia@18: #include <cassert>
discordia@3: #include <cstddef>
discordia@3: 
discordia@3: template <typename T>
discordia@3: class ResizingArrayStack {
discordia@3: 
discordia@3: public:
discordia@3: 
discordia@3:     ResizingArrayStack( void );
discordia@3:     ~ResizingArrayStack( void );
discordia@3: 
discordia@3:     void push( T &item );
discordia@3:     T pop( void );
discordia@3: 
discordia@3:     bool is_empty( void );
discordia@3:     size_t size( void );
discordia@3: 
discordia@4:     class iterator;
discordia@4:     friend class iterator;
discordia@4:     class iterator {
discordia@4: 
discordia@4:     public:
discordia@4: 
discordia@4:         iterator( T *c, T *e );
discordia@4: 
discordia@4:         iterator& operator++();
discordia@4:         iterator operator++(int);
discordia@4: 
discordia@4:         T operator*();
discordia@4:         bool operator!=( typename ResizingArrayStack<T>::iterator );
discordia@4: 
discordia@4:     private:
discordia@4: 
discordia@4:         T *curr;
discordia@4:         T *end;
discordia@4:         };
discordia@4: 
discordia@4:     iterator begin( void );
discordia@4:     iterator end( void );
discordia@3: 
discordia@3: private:
discordia@3: 
discordia@3:     size_t N;
discordia@3:     size_t max;
discordia@3:     T *data;
discordia@3: 
discordia@3:     void resize( size_t new_max );
discordia@3:     };
discordia@3: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: ResizingArrayStack<T>::ResizingArrayStack( void ) :
discordia@18:     N (0),
discordia@18:     max(1) {
discordia@18:     data = new T[1];
discordia@18:     }
discordia@18:     
discordia@18: template <typename T>
discordia@18: ResizingArrayStack<T>::~ResizingArrayStack( void ) {
discordia@18:     assert( N == 0 );  // Catch the potential memory leak.
discordia@18:     if ( data )
discordia@18:         delete[] data;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void ResizingArrayStack<T>::push( T &item ) {
discordia@18:     if ( max == N )
discordia@18:         resize( 2 * max );
discordia@18:     data[N++] = item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T ResizingArrayStack<T>::pop( void ) {
discordia@18:     assert( N > 0 );
discordia@18:     T item = data[N-1];
discordia@18:     N--;
discordia@18: 
discordia@18:     if ( N <= max/4 )
discordia@18:         resize( max/2 );
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool ResizingArrayStack<T>::is_empty( void ) {
discordia@18:     return N == 0;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: size_t ResizingArrayStack<T>::size( void ) {
discordia@18:     return N;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void ResizingArrayStack<T>::resize( size_t new_max ) {
discordia@18:     T *new_data = new T[new_max];
discordia@18:     for ( size_t i = 0; i < N; ++i )
discordia@18:         new_data[i] = data[i];
discordia@18:     T *old_data = data;
discordia@18:     data = new_data;
discordia@18:     delete[] old_data;
discordia@18:     max = new_max;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
discordia@18:     return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
discordia@18:     return ResizingArrayStack<T>::iterator( data-1, data-1 );
discordia@18:     }
discordia@18: 
discordia@18: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
discordia@18:     curr (c),
discordia@18:     end (e)
discordia@18:     {
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
discordia@18:     if ( this->curr > this->end ) {
discordia@18:         this->curr -= 1;
discordia@18:         }
discordia@18:     return *this;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
discordia@18:     auto t = ResizingArrayStack<T>::iterator( *this );
discordia@18:     if ( this->curr > this->end ) {
discordia@18:         this->curr -= 1;
discordia@18:         }
discordia@18:     return t;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T ResizingArrayStack<T>::iterator::operator*() {
discordia@18:     return *(this->curr);
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
discordia@18:     return this->curr != other.curr;
discordia@18:     }
discordia@18: 
discordia@3: 
discordia@3: 
discordia@3: #endif
discordia@3: