Mercurial > Algorithms__Sedgewick

view algs4-c++/src/ResizingArrayStack.cpp @ 4:310618f5e32a

find changesets by author, revision, files, or words in the commit message
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
line source
1 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp
2 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp
3
4
5 #include "ResizingArrayStack.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 ResizingArrayStack<T>::ResizingArrayStack( void ) :
14 N (0),
15 max(1) {
16 data = new T[1];
17 }
18
19 template <typename T>
20 ResizingArrayStack<T>::~ResizingArrayStack( void ) {
21 assert( N == 0 ); // Catch the potential memory leak.
22 if ( data )
23 delete[] data;
24 }
25
26 template <typename T>
27 void ResizingArrayStack<T>::push( T &item ) {
28 if ( max == N )
29 resize( 2 * max );
30 data[N++] = item;
31 }
32
33 template <typename T>
34 T ResizingArrayStack<T>::pop( void ) {
35 assert( N > 0 );
36 T item = data[N-1];
37 N--;
38
39 if ( N <= max/4 )
40 resize( max/2 );
41
42 return item;
43 }
44
45 template <typename T>
46 bool ResizingArrayStack<T>::is_empty( void ) {
47 return N == 0;
48 }
49
50 template <typename T>
51 size_t ResizingArrayStack<T>::size( void ) {
52 return N;
53 }
54
55 template <typename T>
56 void ResizingArrayStack<T>::resize( size_t new_max ) {
57 T *new_data = new T[new_max];
58 for ( size_t i = 0; i < N; ++i )
59 new_data[i] = data[i];
60 T *old_data = data;
61 data = new_data;
62 delete[] old_data;
63 max = new_max;
64 }
65
66 template <typename T>
67 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
68 return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
69 }
70
71 template <typename T>
72 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
73 return ResizingArrayStack<T>::iterator( data-1, data-1 );
74 }
75
76
77 ////////////////////////////////////////////////////////////////////////////////
78
79 template <typename T>
80 ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
81 curr (c),
82 end (e)
83 {
84 }
85
86 template <typename T>
87 typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
88 if ( this->curr > this->end ) {
89 this->curr -= 1;
90 }
91 return *this;
92 }
93
94 template <typename T>
95 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
96 auto t = ResizingArrayStack<T>::iterator( *this );
97 if ( this->curr > this->end ) {
98 this->curr -= 1;
99 }
100 return t;
101 }
102
103 template <typename T>
104 T ResizingArrayStack<T>::iterator::operator*() {
105 return *(this->curr);
106 }
107
108 template <typename T>
109 bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator ) {
110 return this->curr != this->end;
111 }
112
113
114 ////////////////////////////////////////////////////////////////////////////////
115
116 #ifdef RESIZINGARRAYSTACK_MAIN
117
118 #include <iostream>
119
120 int main ( int argc, char **argv ) {
121
122 ResizingArrayStack<long> stack;
123
124 long i;
125 while ( ! std::cin.eof() ) {
126 std::cin >> i;
127 if ( std::cin.good() )
128 stack.push(i);
129 }
130
131 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
132
133 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
134 std::cout << *iter << std::endl;
135 }
136
137 std::cout << "Popping entries..." << std::endl;
138
139 while ( ! stack.is_empty() ) {
140 i = stack.pop();
141 std::cout << i << std::endl;
142 }
143
144 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
145
146 }
147
148 #endif