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
|
// FILE: bag1.cxx
// CLASS IMPLEMENTED: bag (see bag1.h for documentation)
// INVARIANT for the bag class:
// 1. The number of items in the bag is in the member variable used;
// 2. For an empty bag, we do not care what is stored in any of data; for a
// non-empty bag the items in the bag are stored in data[0] through
// data[used-1], and we don't care what's in the rest of data.
#include "bag.h"
#include <algorithm> // Provides copy function
#include <cassert> // Provides assert function
#include <functional>
#include <iostream>
#include <limits>
using namespace std;
namespace main_savitch_3 {
const bag::size_type bag::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
// First, set index to the location of target in the data array,
// which could be as small as 0 or as large as used-1. If target is not
// in the array, then index will be set equal to used.
index = 0;
while ((index < used) && (data[index] != target))
++index;
if (index == used)
return false; // target isn't in the bag, so no work to do.
// 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)
// Library facilities used: cassert
{
assert(size() < CAPACITY);
data[used] = entry;
++used;
}
void bag::operator+=(const bag &addend)
// Library facilities used: algorithm, cassert
{
assert(size() + addend.size() <= CAPACITY);
copy(addend.data, addend.data + addend.used, data + used);
used += addend.used;
}
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::value_type bag::smallest() const {
bag::value_type smallest = this->data[0];
for (int i = 1; i < used; ++i)
if (this->data[i] < smallest)
smallest = this->data[i];
return smallest;
}
bag::value_type bag::average() const {
bag::value_type sum = 0;
for (int i = 0; i < this->used; ++i)
sum += this->data[i];
// I'll use an arithmetic average since once isn't specified. This
// self-rounds since `value_type` is `int`.
return sum / this->used;
}
void bag::sort() const {
bag bag;
for (int i = 0; i < this->size(); ++i)
bag.insert(this->data[i]);
for (int i = 0; i < bag.used - 1; ++i)
for (int j = 0; j < bag.used - i - 1; ++j)
if (bag.data[j] > bag.data[j + 1])
std::swap(bag.data[j], bag.data[j + 1]);
for (int i = 0; i < bag.size(); ++i)
std::cout << bag.data[i] << std::endl;
}
bool bag::operator==(const bag &bag_2) {
bag bag_this_sorted = *this;
bag bag_2_sorted = bag_2;
// Typically I'd make this a member function since it could be reused in
// `sort`, but it seems out of the scope of what's asked.
std::function<void(bag &)> sort_bag = [](bag &bag) {
for (int i = 0; i < bag.used - 1; ++i)
for (int j = 0; j < bag.used - i - 1; ++j)
if (bag.data[j] > bag.data[j + 1])
std::swap(bag.data[j], bag.data[j + 1]);
};
sort_bag(bag_this_sorted);
sort_bag(bag_2_sorted);
for (int i = 0; i < this->used; ++i)
if (bag_this_sorted.data[i] != bag_2_sorted.data[i])
return false;
return true;
}
bag operator+(const bag &b1, const bag &b2)
// Library facilities used: cassert
{
bag answer;
assert(b1.size() + b2.size() <= bag::CAPACITY);
answer += b1;
answer += b2;
return answer;
}
} // namespace main_savitch_3
|