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
|
// FILE: set.h (part of the namespace main_savitch_11)
// TEMPLATE CLASS PROVIDED: set<Item>
// (a container template class for a set of items)
//
// TYPEDEFS for the set<Item> class:
// set<Item>::value_type
// set<Item>::value_type is the data type of the items in the set. It may be
// any of the C++ built-in types (int, char, etc.), or a class with a
// default constructor, a copy constructor, an assignment operator, and a
// less-than operator forming a strict weak ordering.
//
// CONSTRUCTOR for the set<Item> class:
// set( )
// Postcondition: The set is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the set<Item> class:
// void clear( )
// Postcondition: The set is empty.
//
// bool insert(const Item& entry)
// Postcondition: If an equal entry was already in the set, the set is
// unchanged and the return value is false. Otherwise, entry was added
// to the set and the return value is true. This is slightly different than
// the C++ Standard Library set (see Appendix H).
//
// size_t erase(const Item& target)
// Postcondition: If target was in the set, then it has been removed from
// the set and the return value is 1. Otherwise the set is unchanged and the
// return value is zero.
//
// CONSTANT MEMBER FUNCTIONS for the Set<Item> class:
// size_t count(const Item& target) const
// Postcondition: Returns the number of items equal to the target
// (either 0 or 1 for a set).
//
// bool empty( ) const
// Postcondition: Returns true if the set is empty; otherwise returns false.
//
// VALUE SEMANTICS for the set<Item> class:
// Assignments and the copy constructor may be used with set<Item> objects.
//
// DYNAMIC MEMORY USAGE by the set<Item> class:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc:
// The constructors, insert, and the assignment operator.
#ifndef MAIN_SAVITCH_SET_H
#define MAIN_SAVITCH_SET_H
#include <cstdlib> // Provides size_t
namespace main_savitch_11
{
template <class Item>
class set
{
public:
// TYPEDEFS
typedef Item value_type;
// CONSTRUCTORS and DESTRUCTOR
set( );
set(const set& source);
~set( ) { clear( ); }
// MODIFICATION MEMBER FUNCTIONS
void operator =(const set& source);
void clear( );
bool insert(const Item& entry);
std::size_t erase(const Item& target);
// CONSTANT MEMBER FUNCTIONS
std::size_t count(const Item& target) const;
bool empty( ) const { return (data_count == 0); }
// SUGGESTED FUNCTION FOR DEBUGGING
void print(int indent) const;
private:
// MEMBER CONSTANTS
static const std::size_t MINIMUM = 200;
static const std::size_t MAXIMUM = 2 * MINIMUM;
// MEMBER VARIABLES
std::size_t data_count;
Item data[MAXIMUM+1];
std::size_t child_count;
set *subset[MAXIMUM+2];
// HELPER MEMBER FUNCTIONS
bool is_leaf( ) const { return (child_count == 0); }
bool loose_insert(const Item& entry);
bool loose_erase(const Item& target);
void remove_biggest(Item& removed_entry);
void fix_excess(std::size_t i);
void fix_shortage(std::size_t i);
// NOTE: The implementor may want to have additional helper functions
};
}
#include "set.template" // Include the implementation.
#endif
|