Mercurial > Algorithms__Sedgewick
changeset 4:310618f5e32a
Fleshed out ResizingArrayStack with an iterator.
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Thu, 28 May 2015 23:53:46 -0500 |
parents | ca59e5f5b29e |
children | 3db1a894bbdf |
files | algs4-c++/src/ResizingArrayStack.cpp algs4-c++/src/ResizingArrayStack.hpp |
diffstat | 2 files changed, 99 insertions(+), 16 deletions(-) [+] |
line diff
1.1 --- a/algs4-c++/src/ResizingArrayStack.cpp Tue May 26 18:18:16 2015 -0500 1.2 +++ b/algs4-c++/src/ResizingArrayStack.cpp Thu May 28 23:53:46 2015 -0500 1.3 @@ -1,5 +1,5 @@ 1.4 -// g++ -std=c++0x ResizingArrayStack.cpp 1.5 -// g++ -std=c++11 ResizingArrayStack.cpp 1.6 +// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp 1.7 +// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp 1.8 1.9 1.10 #include "ResizingArrayStack.hpp" 1.11 @@ -9,28 +9,31 @@ 1.12 1.13 #include <iostream> 1.14 1.15 -template <typename T> ResizingArrayStack<T>::ResizingArrayStack( void ) : 1.16 +template <typename T> 1.17 +ResizingArrayStack<T>::ResizingArrayStack( void ) : 1.18 N (0), 1.19 max(1) { 1.20 data = new T[1]; 1.21 } 1.22 1.23 -template <typename T> ResizingArrayStack<T>::~ResizingArrayStack( void ) { 1.24 +template <typename T> 1.25 +ResizingArrayStack<T>::~ResizingArrayStack( void ) { 1.26 assert( N == 0 ); // Catch the potential memory leak. 1.27 if ( data ) 1.28 - delete data; 1.29 + delete[] data; 1.30 } 1.31 1.32 -template <typename T> void ResizingArrayStack<T>::push( T &item ) { 1.33 +template <typename T> 1.34 +void ResizingArrayStack<T>::push( T &item ) { 1.35 if ( max == N ) 1.36 resize( 2 * max ); 1.37 data[N++] = item; 1.38 } 1.39 1.40 -template <typename T> T ResizingArrayStack<T>::pop( void ) { 1.41 +template <typename T> 1.42 +T ResizingArrayStack<T>::pop( void ) { 1.43 assert( N > 0 ); 1.44 T item = data[N-1]; 1.45 - data[N-1] = NULL; 1.46 N--; 1.47 1.48 if ( N <= max/4 ) 1.49 @@ -39,24 +42,77 @@ 1.50 return item; 1.51 } 1.52 1.53 -template <typename T> bool ResizingArrayStack<T>::is_empty( void ) { 1.54 +template <typename T> 1.55 +bool ResizingArrayStack<T>::is_empty( void ) { 1.56 return N == 0; 1.57 } 1.58 1.59 -template <typename T> size_t ResizingArrayStack<T>::size( void ) { 1.60 +template <typename T> 1.61 +size_t ResizingArrayStack<T>::size( void ) { 1.62 return N; 1.63 } 1.64 1.65 -template <typename T> void ResizingArrayStack<T>::resize( size_t new_max ) { 1.66 +template <typename T> 1.67 +void ResizingArrayStack<T>::resize( size_t new_max ) { 1.68 T *new_data = new T[new_max]; 1.69 for ( size_t i = 0; i < N; ++i ) 1.70 new_data[i] = data[i]; 1.71 T *old_data = data; 1.72 data = new_data; 1.73 - delete old_data; 1.74 + delete[] old_data; 1.75 max = new_max; 1.76 } 1.77 1.78 +template <typename T> 1.79 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) { 1.80 + return ResizingArrayStack<T>::iterator( data+N-1, data-1 ); 1.81 + } 1.82 + 1.83 +template <typename T> 1.84 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) { 1.85 + return ResizingArrayStack<T>::iterator( data-1, data-1 ); 1.86 + } 1.87 + 1.88 + 1.89 +//////////////////////////////////////////////////////////////////////////////// 1.90 + 1.91 +template <typename T> 1.92 +ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) : 1.93 + curr (c), 1.94 + end (e) 1.95 + { 1.96 + } 1.97 + 1.98 +template <typename T> 1.99 +typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() { 1.100 + if ( this->curr > this->end ) { 1.101 + this->curr -= 1; 1.102 + } 1.103 + return *this; 1.104 + } 1.105 + 1.106 +template <typename T> 1.107 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) { 1.108 + auto t = ResizingArrayStack<T>::iterator( *this ); 1.109 + if ( this->curr > this->end ) { 1.110 + this->curr -= 1; 1.111 + } 1.112 + return t; 1.113 + } 1.114 + 1.115 +template <typename T> 1.116 +T ResizingArrayStack<T>::iterator::operator*() { 1.117 + return *(this->curr); 1.118 + } 1.119 + 1.120 +template <typename T> 1.121 +bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator ) { 1.122 + return this->curr != this->end; 1.123 + } 1.124 + 1.125 + 1.126 +//////////////////////////////////////////////////////////////////////////////// 1.127 + 1.128 #ifdef RESIZINGARRAYSTACK_MAIN 1.129 1.130 #include <iostream> 1.131 @@ -74,10 +130,19 @@ 1.132 1.133 std::cout << "Stack has " << stack.size() << " entries." << std::endl; 1.134 1.135 + for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) { 1.136 + std::cout << *iter << std::endl; 1.137 + } 1.138 + 1.139 + std::cout << "Popping entries..." << std::endl; 1.140 + 1.141 while ( ! stack.is_empty() ) { 1.142 i = stack.pop(); 1.143 std::cout << i << std::endl; 1.144 } 1.145 + 1.146 + std::cout << "Stack has " << stack.size() << " entries." << std::endl; 1.147 + 1.148 } 1.149 1.150 #endif
2.1 --- a/algs4-c++/src/ResizingArrayStack.hpp Tue May 26 18:18:16 2015 -0500 2.2 +++ b/algs4-c++/src/ResizingArrayStack.hpp Thu May 28 23:53:46 2015 -0500 2.3 @@ -17,10 +17,28 @@ 2.4 bool is_empty( void ); 2.5 size_t size( void ); 2.6 2.7 - // class iterator; 2.8 - // friend class iterator; 2.9 - // class iterator { 2.10 - // }; 2.11 + class iterator; 2.12 + friend class iterator; 2.13 + class iterator { 2.14 + 2.15 + public: 2.16 + 2.17 + iterator( T *c, T *e ); 2.18 + 2.19 + iterator& operator++(); 2.20 + iterator operator++(int); 2.21 + 2.22 + T operator*(); 2.23 + bool operator!=( typename ResizingArrayStack<T>::iterator ); 2.24 + 2.25 + private: 2.26 + 2.27 + T *curr; 2.28 + T *end; 2.29 + }; 2.30 + 2.31 + iterator begin( void ); 2.32 + iterator end( void ); 2.33 2.34 private: 2.35