Mercurial > Algorithms__Sedgewick
view algs4-c++/src/ResizingArrayStack.cpp @ 15:63df3e6590e2
Bag and RandomBag (1.3.34) classes.
There are not really robust enough to use as they will leak memory on
destruction if you use them to store dynamically allocated objects.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Thu, 11 Jun 2015 16:30:14 -0500 |
| parents | 310618f5e32a |
| children | a149b424b4e2 |
line source
1 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp
2 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp
5 #include "ResizingArrayStack.hpp"
7 #include <cassert>
8 #include <cstddef>
10 #include <iostream>
12 template <typename T>
13 ResizingArrayStack<T>::ResizingArrayStack( void ) :
14 N (0),
15 max(1) {
16 data = new T[1];
17 }
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 }
26 template <typename T>
27 void ResizingArrayStack<T>::push( T &item ) {
28 if ( max == N )
29 resize( 2 * max );
30 data[N++] = item;
31 }
33 template <typename T>
34 T ResizingArrayStack<T>::pop( void ) {
35 assert( N > 0 );
36 T item = data[N-1];
37 N--;
39 if ( N <= max/4 )
40 resize( max/2 );
42 return item;
43 }
45 template <typename T>
46 bool ResizingArrayStack<T>::is_empty( void ) {
47 return N == 0;
48 }
50 template <typename T>
51 size_t ResizingArrayStack<T>::size( void ) {
52 return N;
53 }
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 }
66 template <typename T>
67 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
68 return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
69 }
71 template <typename T>
72 typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
73 return ResizingArrayStack<T>::iterator( data-1, data-1 );
74 }
77 ////////////////////////////////////////////////////////////////////////////////
79 template <typename T>
80 ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
81 curr (c),
82 end (e)
83 {
84 }
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 }
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 }
103 template <typename T>
104 T ResizingArrayStack<T>::iterator::operator*() {
105 return *(this->curr);
106 }
108 template <typename T>
109 bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
110 return this->curr != other.curr;
111 }
114 ////////////////////////////////////////////////////////////////////////////////
116 #ifdef RESIZINGARRAYSTACK_MAIN
118 #include <iostream>
120 int main ( int argc, char **argv ) {
122 ResizingArrayStack<long> stack;
124 long i;
125 while ( ! std::cin.eof() ) {
126 std::cin >> i;
127 if ( std::cin.good() )
128 stack.push(i);
129 }
131 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
133 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
134 std::cout << *iter << std::endl;
135 }
137 std::cout << "Popping entries..." << std::endl;
139 while ( ! stack.is_empty() ) {
140 i = stack.pop();
141 std::cout << i << std::endl;
142 }
144 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
146 }
148 #endif