Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Bag.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 63df3e6590e2
children
line source
1 // Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
2
3 #ifndef BAG_HPP
4 #define BAG_HPP
5
6 #include <cstddef>
7
8 template <typename T>
9 class Bag {
10
11 private:
12
13 ////////////////////////////////////
14 class Node {
15 public:
16 T item;
17 Node *next;
18 };
19
20
21 public:
22
23 ////////////////////////////////////
24 class iterator;
25 friend class iterator;
26 class iterator {
27
28 public:
29
30 iterator( Node *c );
31
32 iterator& operator++();
33 iterator operator++(int);
34
35 T operator*();
36 bool operator!=( typename Bag<T>::iterator );
37
38 private:
39
40 Node *curr;
41 };
42
43 ////////////////////////////////////
44
45 Bag( void );
46 ~Bag( void );
47
48 void add( T &item );
49
50 bool is_empty( void );
51 size_t size( void );
52
53 iterator begin( void );
54 iterator end( void );
55
56 #ifdef EXERCISES
57 T delete_bottom( void );
58 T remove( size_t k );
59 bool find( T key );
60 #endif
61
62 private:
63
64 size_t N;
65 Node *list;
66
67 };
68
69
70 ////////////////////////////////////////////////////////////////////////////////
71
72
73 template <typename T>
74 Bag<T>::Bag( void ) :
75 N (0),
76 list (nullptr)
77 {
78 }
79
80 template <typename T>
81 Bag<T>::~Bag( void ) {
82 // This will leak memory, won't it?
83 while ( list ) {
84 Node * next = list->next;
85 delete list;
86 list = next;
87 }
88 }
89
90 template <typename T>
91 void Bag<T>::add( T &item ) {
92 Node * node = new Node();
93 node->item = item;
94 node->next = list;
95 list = node;
96 N++;
97 }
98
99 template <typename T>
100 bool Bag<T>::is_empty( void ) {
101 return N == 0;
102 }
103
104 template <typename T>
105 size_t Bag<T>::size( void ) {
106 return N;
107 }
108
109 template <typename T>
110 typename Bag<T>::iterator Bag<T>::begin( void ) {
111 return Bag<T>::iterator( list );
112 }
113
114 template <typename T>
115 typename Bag<T>::iterator Bag<T>::end( void ) {
116 return Bag<T>::iterator( nullptr );
117 }
118
119
120 ////////////////////////////////////////////////////////////////////////////////
121
122 template <typename T>
123 Bag<T>::iterator::iterator( Node *c ) :
124 curr (c)
125 {
126 }
127
128 template <typename T>
129 typename Bag<T>::iterator & Bag<T>::iterator::operator++() {
130 if ( this->curr != nullptr ) {
131 this->curr = this->curr->next;
132 }
133 return *this;
134 }
135
136 template <typename T>
137 typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) {
138 auto t = Bag<T>::iterator( *this );
139
140 if ( this->curr != nullptr ) {
141 this->curr = this->curr->next;
142 }
143 return t;
144 }
145
146 template <typename T>
147 T Bag<T>::iterator::operator*() {
148 return this->curr->item;
149 }
150
151 template <typename T>
152 bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) {
153 return this->curr != other.curr;
154 }
155
156 ////////////////////////////////////////////////////////////////////////////////
157
158
159 #ifdef EXERCISES
160
161 // 1.3.19
162 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
163 template <typename T>
164 T Bag<T>::delete_bottom( void ) {
165 Node *prev, *curr;
166 T item;
167
168 prev = nullptr;
169 curr = list;
170 if ( curr ) {
171 while ( curr->next ) {
172 prev = curr;
173 curr = curr->next;
174 }
175
176 item = curr->item;
177 delete curr;
178 if ( prev )
179 prev->next = nullptr;
180 else
181 list = nullptr;
182
183 N--;
184 }
185
186 return item;
187 }
188
189
190 // 1.3.20
191 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
192 template <typename T>
193 T Bag<T>::remove( size_t k ) {
194 Node *prev, *curr;
195 size_t i=0;
196 T item;
197
198 prev = nullptr;
199 curr = list;
200 while ( curr && (i < k) ) {
201 prev = curr;
202 curr = curr->next;
203 ++i;
204 }
205
206 if ( curr &&( i == k) ) {
207 item = curr->item;
208 if ( prev )
209 prev->next = curr->next;
210 else
211 list = curr->next;;
212 delete curr;
213 N--;
214 }
215
216 return item;
217 }
218
219 // 1.3.21
220 // Returns true if the specified key is in the bag.
221 template <typename T>
222 bool Bag<T>::find( T key ) {
223 Node *curr = list;
224
225 while ( curr ) {
226 if ( curr->item == key )
227 return true;
228 curr = curr->next;
229 }
230
231 return false;
232 }
233
234 #endif
235
236
237 #endif
238