1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
// FILE: bag2.cxx
// CLASS implemented: bag (see bag2.h for documentation)
// INVARIANT for the bag class:
// 1. The number of items in the bag is in the member variable used;
// 2. The actual items of the bag are stored in a partially filled array.
// The array is a dynamic array, pointed to by the member variable data;
// 3. The size of the dynamic array is in the member variable capacity.
#include <algorithm> // Provides copy function
#include <cassert> // Provides assert function
#include "bag2.h"
using namespace std;
namespace main_savitch_4
{
const bag::size_type bag::DEFAULT_CAPACITY;
bag::bag(size_type initial_capacity)
{
data = new value_type[initial_capacity];
capacity = initial_capacity;
used = 0;
}
bag::bag(const bag& source) // bag b2(b1);
// Library facilities used: algorithm
{
data = new value_type[source.capacity];
capacity = source.capacity;
used = source.used;
copy(source.data, source.data + used, data);
}
bag::~bag( )
{
delete [ ] data;
}
void bag::reserve(size_type new_capacity)
// Library facilities used: algorithm
{
value_type *larger_array;
if (new_capacity == capacity)
return; // The allocated memory is already the right size.
if (new_capacity < used)
new_capacity = used; // Can�t allocate less than we are using.
larger_array = new value_type[new_capacity];
copy(data, data + used, larger_array);
delete [ ] data;
data = larger_array;
capacity = new_capacity;
}
bag::size_type bag::erase(const value_type& target)
{
size_type index = 0;
size_type many_removed = 0;
while (index < used)
{
if (data[index] == target)
{
--used;
data[index] = data[used];
++many_removed;
}
else
++index;
}
return many_removed;
}
bool bag::erase_one(const value_type& target)
{
size_type index; // The location of target in the data array
index = 0;
while ((index < used) && (data[index] != target))
++index;
if (index == used) // target isn't in the bag, so no work to do
return false;
// When execution reaches here, target is in the bag at data[index].
// So, reduce used by 1 and copy the last item onto data[index].
--used;
data[index] = data[used];
return true;
}
void bag::insert(const value_type& entry)
{
if (used == capacity)
reserve(used+1);
data[used] = entry;
++used;
}
void bag::operator +=(const bag& addend)
// Library facilities used: algorithm
{
if (used + addend.used > capacity)
reserve(used + addend.used);
copy(addend.data, addend.data + addend.used, data + used);
used += addend.used;
}
void bag::operator =(const bag& source)
// Library facilities used: algorithm
{
value_type *new_data;
// Check for possible self-assignment:
if (this == &source)
return;
// If needed, allocate an array with a different size:
if (capacity != source.capacity)
{
new_data = new value_type[source.capacity];
delete [ ] data;
data = new_data;
capacity = source.capacity;
}
// Copy the data from the source array:
used = source.used;
copy(source.data, source.data + used, data);
}
bag::size_type bag::count(const value_type& target) const
{
size_type answer;
size_type i;
answer = 0;
for (i = 0; i < used; ++i)
if (target == data[i])
++answer;
return answer;
}
bag operator +(const bag& b1, const bag& b2)
{
bag answer(b1.size( ) + b2.size( ));
answer += b1;
answer += b2;
return answer;
}
}
|