blob: 950b1e1c76519623bc92c0f57e7411120134462a (
about) (
plain)
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
|
#ifndef IDSET_HPP
#define IDSET_HPP
#include <ostream>
#define CELL_TYPE unsigned int
#define CELL_SIZE (8 * sizeof(CELL_TYPE))
#define DIV_ROUND_UP(NUM, DEM) ((NUM + DEM - 1) / DEM)
template<typename T>
class IdSet {
public:
IdSet() : _range(0) { }
IdSet(unsigned int length)
: _range(length) { }
virtual ~IdSet() {
}
IdSet(const IdSet& other) {
_range = other._range;
_set = other._set;
}
IdSet& operator=(const IdSet& other) {
_range = other._range;
_set = other._set;
return *this;
}
void invert() {
for (unsigned int i = 0; i < _range; ++i) {
iterator it = _set.find(i);
if (it == _set.end()) {
_set.insert(i);
} else {
_set.erase(it);
}
}
}
IdSet inverse() const {
IdSet other(_range);
for (unsigned int i = 0; i < _range; ++i) {
if (_set.find(i) == _set.end()) {
other._set.insert(i);
}
}
return other;
}
bool contains(const T& obj) const {
return _set.find(obj.id()) != _set.end();
}
void insert(const T& obj) {
_set.insert(obj.id());
}
void remove(const T& obj) {
_set.erase(obj.id());
}
void clear() {
_set.clear();
}
void absorb(const IdSet& other) {
for (iterator it = other.begin(), end = other.end();
it != end;
++it) {
_set.insert(*it);
}
}
void filter(const IdSet& other) {
for (iterator it = other.begin(), end = other.end();
it != end;
++it) {
_set.erase(*it);
}
}
bool operator==(const IdSet& other) const {
return _set == other._set;
}
bool operator!=(const IdSet& other) const {
return !(*this == other);
}
typedef std::set<unsigned int>::const_iterator iterator;
iterator begin() const {
return _set.begin();
}
iterator end() const {
return _set.end();
}
unsigned int size() const {
return _set.size();
}
private:
unsigned int _range;
std::set<unsigned int> _set;
};
template<typename T>
std::ostream& operator<<(std::ostream& cout, const IdSet<T>& set) {
cout << "{";
for (typename IdSet<T>::iterator it = set.begin();
it != set.end();
++it) {
cout << *it << ", ";
}
cout << "}";
return cout;
}
#endif
|
