Mercurial > Algorithms__Sedgewick

view algs4-c++/src/ResizingArrayStack.hpp @ 18:a149b424b4e2

find changesets by author, revision, files, or words in the commit message
Updated all template classes to have the implementaiton in the header file.
author Eris Caffee <discordia@eldalin.com>
date Sat, 20 Jun 2015 19:36:11 -0500
parents 310618f5e32a
children
line source
1 // Stack built on a resizing array.
2
3 #ifndef RESIZINGARRAYSTACK_HPP
4 #define RESIZINGARRAYSTACK_HPP
5
6 #include <cassert>
7 #include <cstddef>
8
9 template <typename T>
10 class ResizingArrayStack {
11
12 public:
13
14 ResizingArrayStack( void );
15 ~ResizingArrayStack( void );
16
17 void push( T &item );
18 T pop( void );
19
20 bool is_empty( void );
21 size_t size( void );
22
23 class iterator;
24 friend class iterator;
25 class iterator {
26
27 public:
28
29 iterator( T *c, T *e );
30
31 iterator& operator++();
32 iterator operator++(int);
33
34 T operator*();
35 bool operator!=( typename ResizingArrayStack<T>::iterator );
36
37 private:
38
39 T *curr;
40 T *end;
41 };
42
43 iterator begin( void );
44 iterator end( void );
45
46 private:
47
48 size_t N;
49 size_t max;
50 T *data;
51
52 void resize( size_t new_max );
53 };
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
158
159
160 #endif
161