Mercurial > Algorithms__Sedgewick

comparison 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
comparison
equal deleted inserted replaced
1:0c63edef9e94 2:83ad747ec03a
1 // Stack built on a resizing array.
2
1 #ifndef RESIZINGARRAYSTACK_HPP 3 #ifndef RESIZINGARRAYSTACK_HPP
2 #define RESIZINGARRAYSTACK_HPP 4 #define RESIZINGARRAYSTACK_HPP
3 5
6 #include <cassert>
4 #include <cstddef> 7 #include <cstddef>
5 8
6 template <typename T> 9 template <typename T>
7 class ResizingArrayStack { 10 class ResizingArrayStack {
8 11
47 T *data; 50 T *data;
48 51
49 void resize( size_t new_max ); 52 void resize( size_t new_max );
50 }; 53 };
51 54
55 ////////////////////////////////////////////////////////////////////////////////
56
57 template <typename T>
58 ResizingArrayStack<T>::ResizingArrayStack( void ) :
59 N (0),
60 max(1) {
61 data = new T[1];
62 }
63
64 template <typename T>
65 ResizingArrayStack<T>::~ResizingArrayStack( void ) {
66 assert( N == 0 ); // Catch the potential memory leak.
67 if ( data )
68 delete[] data;
69 }
70
71 template <typename T>
72 void ResizingArrayStack<T>::push( T &item ) {
73 if ( max == N )
74 resize( 2 * max );
75 data[N++] = item;
76 }
77
78 template <typename T>
79 T ResizingArrayStack<T>::pop( void ) {
80 assert( N > 0 );
81 T item = data[N-1];
82 N--;
83
84 if ( N <= max/4 )
85 resize( max/2 );
86
87 return item;
88 }
89
90 template <typename T>
91 bool ResizingArrayStack<T>::is_empty( void ) {
92 return N == 0;
93 }
94
95 template <typename T>
96 size_t ResizingArrayStack<T>::size( void ) {
97 return N;
98 }
99
100 template <typename T>
101 void ResizingArrayStack<T>::resize( size_t new_max ) {
102 T *new_data = new T[new_max];
103 for ( size_t i = 0; i < N; ++i )
104 new_data[i] = data[i];
105 T *old_data = data;
106 data = new_data;
107 delete[] old_data;
108 max = new_max;
109 }
110
111 template <typename T>
112 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
113 return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
114 }
115
116 template <typename T>
117 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
118 return ResizingArrayStack<T>::iterator( data-1, data-1 );
119 }
120
121
122 ////////////////////////////////////////////////////////////////////////////////
123
124 template <typename T>
125 ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
126 curr (c),
127 end (e)
128 {
129 }
130
131 template <typename T>
132 typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
133 if ( this->curr > this->end ) {
134 this->curr -= 1;
135 }
136 return *this;
137 }
138
139 template <typename T>
140 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
141 auto t = ResizingArrayStack<T>::iterator( *this );
142 if ( this->curr > this->end ) {
143 this->curr -= 1;
144 }
145 return t;
146 }
147
148 template <typename T>
149 T ResizingArrayStack<T>::iterator::operator*() {
150 return *(this->curr);
151 }
152
153 template <typename T>
154 bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
155 return this->curr != other.curr;
156 }
157
52 158
53 159
54 #endif 160 #endif
55 161