Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Bag.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
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
children a149b424b4e2
line source
1 // g++ -D BAG_MAIN -std=c++0x Bag.cpp
2 // g++ -D BAG_MAIN -std=c++11 Bag.cpp
3
4
5 #include "Bag.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 Bag<T>::Bag( void ) :
14 N (0),
15 list (nullptr)
16 {
17 }
18
19 template <typename T>
20 Bag<T>::~Bag( void ) {
21 // This will leak memory, won't it?
22 while ( list ) {
23 Node * next = list->next;
24 delete list;
25 list = next;
26 }
27 }
28
29 template <typename T>
30 void Bag<T>::add( T &item ) {
31 Node * node = new Node();
32 node->item = item;
33 node->next = list;
34 list = node;
35 N++;
36 }
37
38 template <typename T>
39 bool Bag<T>::is_empty( void ) {
40 return N == 0;
41 }
42
43 template <typename T>
44 size_t Bag<T>::size( void ) {
45 return N;
46 }
47
48 template <typename T>
49 typename Bag<T>::iterator Bag<T>::begin( void ) {
50 return Bag<T>::iterator( list );
51 }
52
53 template <typename T>
54 typename Bag<T>::iterator Bag<T>::end( void ) {
55 return Bag<T>::iterator( nullptr );
56 }
57
58
59 ////////////////////////////////////////////////////////////////////////////////
60
61 template <typename T>
62 Bag<T>::iterator::iterator( Node *c ) :
63 curr (c)
64 {
65 }
66
67 template <typename T>
68 typename Bag<T>::iterator & Bag<T>::iterator::operator++() {
69 if ( this->curr != nullptr ) {
70 this->curr = this->curr->next;
71 }
72 return *this;
73 }
74
75 template <typename T>
76 typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) {
77 auto t = Bag<T>::iterator( *this );
78
79 if ( this->curr != nullptr ) {
80 this->curr = this->curr->next;
81 }
82 return t;
83 }
84
85 template <typename T>
86 T Bag<T>::iterator::operator*() {
87 return this->curr->item;
88 }
89
90 template <typename T>
91 bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) {
92 return this->curr != other.curr;
93 }
94
95 ////////////////////////////////////////////////////////////////////////////////
96
97
98 #ifdef EXERCISES
99
100 // 1.3.19
101 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
102 template <typename T>
103 T Bag<T>::delete_bottom( void ) {
104 Node *prev, *curr;
105 T item;
106
107 prev = nullptr;
108 curr = list;
109 if ( curr ) {
110 while ( curr->next ) {
111 prev = curr;
112 curr = curr->next;
113 }
114
115 item = curr->item;
116 delete curr;
117 if ( prev )
118 prev->next = nullptr;
119 else
120 list = nullptr;
121
122 N--;
123 }
124
125 return item;
126 }
127
128
129 // 1.3.20
130 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
131 template <typename T>
132 T Bag<T>::remove( size_t k ) {
133 Node *prev, *curr;
134 size_t i=0;
135 T item;
136
137 prev = nullptr;
138 curr = list;
139 while ( curr && (i < k) ) {
140 prev = curr;
141 curr = curr->next;
142 ++i;
143 }
144
145 if ( curr &&( i == k) ) {
146 item = curr->item;
147 if ( prev )
148 prev->next = curr->next;
149 else
150 list = curr->next;;
151 delete curr;
152 N--;
153 }
154
155 return item;
156 }
157
158 // 1.3.21
159 // Returns true if the specified key is in the bag.
160 template <typename T>
161 bool Bag<T>::find( T key ) {
162 Node *curr = list;
163
164 while ( curr ) {
165 if ( curr->item == key )
166 return true;
167 curr = curr->next;
168 }
169
170 return false;
171 }
172
173 #endif
174
175
176 ////////////////////////////////////////////////////////////////////////////////
177
178 #ifdef BAG_MAIN
179
180 #include <iostream>
181
182 int main ( int argc, char **argv ) {
183
184 Bag<long> bag;
185
186 long i;
187 while ( ! std::cin.eof() ) {
188 std::cin >> i;
189 if ( std::cin.good() )
190 bag.add(i);
191 }
192
193 std::cout << "Bag has " << bag.size() << " entries." << std::endl;
194
195 for ( auto iter = bag.begin(); iter != bag.end(); ++iter ) {
196 std::cout << *iter << std::endl;
197 }
198
199 }
200
201 #endif