Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/ResizingArrayStack.hpp @ 27:80ca1973e3bd

find changesets by author, revision, files, or words in the commit message
Fleshed out Queue::generic_iterator a bit more to make it a more or less complete example of implmenting an iterator.
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 17:14:09 -0500
parents 310618f5e32a
children
rev   line source
discordia@18 1 // Stack built on a resizing array.
discordia@18 2
discordia@3 3 #ifndef RESIZINGARRAYSTACK_HPP
discordia@3 4 #define RESIZINGARRAYSTACK_HPP
discordia@3 5
discordia@18 6 #include <cassert>
discordia@3 7 #include <cstddef>
discordia@3 8
discordia@3 9 template <typename T>
discordia@3 10 class ResizingArrayStack {
discordia@3 11
discordia@3 12 public:
discordia@3 13
discordia@3 14 ResizingArrayStack( void );
discordia@3 15 ~ResizingArrayStack( void );
discordia@3 16
discordia@3 17 void push( T &item );
discordia@3 18 T pop( void );
discordia@3 19
discordia@3 20 bool is_empty( void );
discordia@3 21 size_t size( void );
discordia@3 22
discordia@4 23 class iterator;
discordia@4 24 friend class iterator;
discordia@4 25 class iterator {
discordia@4 26
discordia@4 27 public:
discordia@4 28
discordia@4 29 iterator( T *c, T *e );
discordia@4 30
discordia@4 31 iterator& operator++();
discordia@4 32 iterator operator++(int);
discordia@4 33
discordia@4 34 T operator*();
discordia@4 35 bool operator!=( typename ResizingArrayStack<T>::iterator );
discordia@4 36
discordia@4 37 private:
discordia@4 38
discordia@4 39 T *curr;
discordia@4 40 T *end;
discordia@4 41 };
discordia@4 42
discordia@4 43 iterator begin( void );
discordia@4 44 iterator end( void );
discordia@3 45
discordia@3 46 private:
discordia@3 47
discordia@3 48 size_t N;
discordia@3 49 size_t max;
discordia@3 50 T *data;
discordia@3 51
discordia@3 52 void resize( size_t new_max );
discordia@3 53 };
discordia@3 54
discordia@18 55 ////////////////////////////////////////////////////////////////////////////////
discordia@18 56
discordia@18 57 template <typename T>
discordia@18 58 ResizingArrayStack<T>::ResizingArrayStack( void ) :
discordia@18 59 N (0),
discordia@18 60 max(1) {
discordia@18 61 data = new T[1];
discordia@18 62 }
discordia@18 63
discordia@18 64 template <typename T>
discordia@18 65 ResizingArrayStack<T>::~ResizingArrayStack( void ) {
discordia@18 66 assert( N == 0 ); // Catch the potential memory leak.
discordia@18 67 if ( data )
discordia@18 68 delete[] data;
discordia@18 69 }
discordia@18 70
discordia@18 71 template <typename T>
discordia@18 72 void ResizingArrayStack<T>::push( T &item ) {
discordia@18 73 if ( max == N )
discordia@18 74 resize( 2 * max );
discordia@18 75 data[N++] = item;
discordia@18 76 }
discordia@18 77
discordia@18 78 template <typename T>
discordia@18 79 T ResizingArrayStack<T>::pop( void ) {
discordia@18 80 assert( N > 0 );
discordia@18 81 T item = data[N-1];
discordia@18 82 N--;
discordia@18 83
discordia@18 84 if ( N <= max/4 )
discordia@18 85 resize( max/2 );
discordia@18 86
discordia@18 87 return item;
discordia@18 88 }
discordia@18 89
discordia@18 90 template <typename T>
discordia@18 91 bool ResizingArrayStack<T>::is_empty( void ) {
discordia@18 92 return N == 0;
discordia@18 93 }
discordia@18 94
discordia@18 95 template <typename T>
discordia@18 96 size_t ResizingArrayStack<T>::size( void ) {
discordia@18 97 return N;
discordia@18 98 }
discordia@18 99
discordia@18 100 template <typename T>
discordia@18 101 void ResizingArrayStack<T>::resize( size_t new_max ) {
discordia@18 102 T *new_data = new T[new_max];
discordia@18 103 for ( size_t i = 0; i < N; ++i )
discordia@18 104 new_data[i] = data[i];
discordia@18 105 T *old_data = data;
discordia@18 106 data = new_data;
discordia@18 107 delete[] old_data;
discordia@18 108 max = new_max;
discordia@18 109 }
discordia@18 110
discordia@18 111 template <typename T>
discordia@18 112 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
discordia@18 113 return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
discordia@18 114 }
discordia@18 115
discordia@18 116 template <typename T>
discordia@18 117 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
discordia@18 118 return ResizingArrayStack<T>::iterator( data-1, data-1 );
discordia@18 119 }
discordia@18 120
discordia@18 121
discordia@18 122 ////////////////////////////////////////////////////////////////////////////////
discordia@18 123
discordia@18 124 template <typename T>
discordia@18 125 ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
discordia@18 126 curr (c),
discordia@18 127 end (e)
discordia@18 128 {
discordia@18 129 }
discordia@18 130
discordia@18 131 template <typename T>
discordia@18 132 typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
discordia@18 133 if ( this->curr > this->end ) {
discordia@18 134 this->curr -= 1;
discordia@18 135 }
discordia@18 136 return *this;
discordia@18 137 }
discordia@18 138
discordia@18 139 template <typename T>
discordia@18 140 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
discordia@18 141 auto t = ResizingArrayStack<T>::iterator( *this );
discordia@18 142 if ( this->curr > this->end ) {
discordia@18 143 this->curr -= 1;
discordia@18 144 }
discordia@18 145 return t;
discordia@18 146 }
discordia@18 147
discordia@18 148 template <typename T>
discordia@18 149 T ResizingArrayStack<T>::iterator::operator*() {
discordia@18 150 return *(this->curr);
discordia@18 151 }
discordia@18 152
discordia@18 153 template <typename T>
discordia@18 154 bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
discordia@18 155 return this->curr != other.curr;
discordia@18 156 }
discordia@18 157
discordia@3 158
discordia@3 159
discordia@3 160 #endif
discordia@3 161