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
|
// 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 <algorithm> // Provides copy function
#include <cassert> // Provides assert function
#include "bag1.h"
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 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;
}
}
|