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
|
////////////////////////////////////////////////////////////////////////////////
//
// SparseIntegerSet.hh
//
// produced: 19/03/98 jr
// last change: 24/01/99 jr
//
////////////////////////////////////////////////////////////////////////////////
#ifndef SPARSEINTEGERSET_HH
#define SPARSEINTEGERSET_HH
#include <stdlib.h>
#include "Global.hh"
#include "Array.hh"
#include "HashSet.hh"
#include "IntegerSet.hh"
typedef size_type integer_key;
typedef HashSet<integer_key> set_data;
class IntegerSet;
class SparseIntegerSet : public set_data {
public:
// constructors:
inline SparseIntegerSet(); // constructor for empty set
inline SparseIntegerSet(const SparseIntegerSet&); // copy constructor
SparseIntegerSet(const IntegerSet&); // constructor for IntegerSet
inline SparseIntegerSet(const integer_key, const integer_key); // construct set containing the given range
inline SparseIntegerSet(const integer_key elem); // constructor for one-element set
SparseIntegerSet(const Array<integer_key>&); // constructor with given Array of integers
// destructor:
inline ~SparseIntegerSet(); // destructor
// functions:
inline const integer_key card() const; // cardinality
// boolean functions:
inline const bool contains(const integer_key) const; // membership
const bool superset(const SparseIntegerSet&) const; // superset relation
const bool subset(const SparseIntegerSet&) const; // subset relation
const bool disjoint(const SparseIntegerSet&) const; // disjoint relation
// boolean operators:
const bool operator==(const SparseIntegerSet&) const; // equality
const bool operator!=(const SparseIntegerSet&) const; // non-equality
const bool operator<(const SparseIntegerSet&) const; // order on intsets
const bool operator>(const SparseIntegerSet&) const; // reversed order
// modifiers:
SparseIntegerSet& fill(const integer_key, const integer_key); // fill in elements from start to stop
// adding and deleting an element:
SparseIntegerSet& operator+=(const integer_key); // add integer
SparseIntegerSet& operator-=(const integer_key); // delete integer
SparseIntegerSet& operator^=(const integer_key); // add if not contained/delete if contained
// union, difference, and intersection with sets:
SparseIntegerSet& operator+=(const SparseIntegerSet&); // union
SparseIntegerSet& operator-=(const SparseIntegerSet&); // difference
SparseIntegerSet& operator*=(const SparseIntegerSet&); // intersection
SparseIntegerSet& operator^=(const SparseIntegerSet&); // symmetric difference
// returns the cardinalities
// 0, 1, or 2 (2 or more) of
// the intersection of several IntegerSet's:
const size_type intersection_card(const SparseIntegerSet**,
const size_type,
size_type&) const;
const size_type intersection_nonempty(const SparseIntegerSet**,
const size_type,
size_type&) const;
// the same but a new set is returned:
SparseIntegerSet operator+(const integer_key) const; // add integer
SparseIntegerSet operator-(const integer_key) const; // delete integer
SparseIntegerSet operator+(const SparseIntegerSet&) const; // union
SparseIntegerSet operator-(const SparseIntegerSet&) const; // difference
SparseIntegerSet operator*(const SparseIntegerSet&) const; // intersection
SparseIntegerSet operator^(const SparseIntegerSet&) const; // symmetric difference
// iostream:
std::istream& read(std::istream&);
std::ostream& write(std::ostream& ost) const;
// friends (have to be inlined right here):
friend std::ostream& operator<<(std::ostream& ost, const SparseIntegerSet& sis) {
return sis.write(ost);
}
friend std::istream& operator>>(std::istream& ist, SparseIntegerSet& sis) {
return sis.read(ist);
}
};
// SparseIntegerSet inlines:
// constructors:
inline SparseIntegerSet::SparseIntegerSet() : set_data() {}
inline SparseIntegerSet::SparseIntegerSet(const SparseIntegerSet& sis) : set_data(sis) {}
inline SparseIntegerSet::SparseIntegerSet(const integer_key start, const integer_key stop) : set_data() {
fill(start, stop);
}
inline SparseIntegerSet::SparseIntegerSet(const integer_key elem) : set_data() {
insert(elem);
}
// destructor:
inline SparseIntegerSet::~SparseIntegerSet() {}
// functions:
inline const integer_key SparseIntegerSet::card() const {
return set_data::card();
}
inline const bool SparseIntegerSet::contains(const integer_key elem) const {
return (member(elem));
}
#endif
// eof SparseIntegerSet.hh
|
