Mercurial > Algorithms__Sedgewick
comparison algs4-c++/src/ResizingArrayStack.cpp @ 27:80ca1973e3bd
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 | 3db1a894bbdf |
children |
comparison
equal
deleted
inserted
replaced
2:3f2ae724436f | 3:e465726a8ac6 |
---|---|
1 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp | 1 // g++ -std=c++11 ResizingArrayStack.cpp |
2 // g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp | |
3 | 2 |
4 | 3 |
5 #include "ResizingArrayStack.hpp" | 4 #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 other ) { | |
110 return this->curr != other.curr; | |
111 } | |
112 | |
113 | |
114 //////////////////////////////////////////////////////////////////////////////// | |
115 | |
116 #ifdef RESIZINGARRAYSTACK_MAIN | |
117 | 5 |
118 #include <iostream> | 6 #include <iostream> |
119 | 7 |
120 int main ( int argc, char **argv ) { | 8 int main ( int argc, char **argv ) { |
121 | 9 |
143 | 31 |
144 std::cout << "Stack has " << stack.size() << " entries." << std::endl; | 32 std::cout << "Stack has " << stack.size() << " entries." << std::endl; |
145 | 33 |
146 } | 34 } |
147 | 35 |
148 #endif |