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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
/**
@file Set.h
Hash set
@maintainer Morgan McGuire, http://graphics.cs.williams.edu
@created 2001-12-09
@edited 2009-06-10
*/
#ifndef G3D_Set_h
#define G3D_Set_h
#include "G3D/platform.h"
#include "G3D/Table.h"
#include "G3D/MemoryManager.h"
#include <assert.h>
#include <string>
namespace G3D {
/**
An unordered data structure that has at most one of each element.
Provides O(1) time insert, remove, and member test (contains).
Set uses G3D::Table internally, which means that the template type T
must define a hashCode and operator== function. See G3D::Table for
a discussion of these functions.
*/
// There is not copy constructor or assignment operator defined because
// the default ones are correct for Set.
template<class T, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T> >
class Set {
/**
If an object is a member, it is contained in
this table.
*/
Table<T, bool, HashFunc, EqualsFunc> memberTable;
public:
void clearAndSetMemoryManager(const MemoryManager::Ref& m) {
memberTable.clearAndSetMemoryManager(m);
}
virtual ~Set() {}
int size() const {
return (int)memberTable.size();
}
bool contains(const T& member) const {
return memberTable.containsKey(member);
}
/**
Inserts into the table if not already present.
Returns true if this is the first time the element was added.
*/
bool insert(const T& member) {
bool isNew = false;
memberTable.getCreate(member, isNew) = true;
return isNew;
}
/**
Returns true if the element was present and removed. Returns false
if the element was not present.
*/
bool remove(const T& member) {
return memberTable.remove(member);
}
/** If @a member is present, sets @a removed to the element
being removed and returns true. Otherwise returns false
and does not write to @a removed. This is useful when building
efficient hashed data structures that wrap Set.
*/
bool getRemove(const T& member, T& removed) {
bool ignore;
return memberTable.getRemove(member, removed, ignore);
}
/** If a value that is EqualsFunc to @a member is present, returns a pointer to the
version stored in the data structure, otherwise returns NULL.
*/
const T* getPointer(const T& member) const {
return memberTable.getKeyPointer(member);
}
Array<T> getMembers() const {
return memberTable.getKeys();
}
void getMembers(Array<T>& keyArray) const {
memberTable.getKeys(keyArray);
}
void clear() {
memberTable.clear();
}
void deleteAll() {
getMembers().deleteAll();
clear();
}
/**
C++ STL style iterator variable. See begin().
*/
class Iterator {
private:
friend class Set<T>;
// Note: this is a Table iterator, we are currently defining
// Set iterator
typename Table<T, bool>::Iterator it;
Iterator(const typename Table<T, bool>::Iterator& it) : it(it) {}
public:
inline bool operator!=(const Iterator& other) const {
return !(*this == other);
}
bool hasMore() const {
return it.hasMore();
}
bool operator==(const Iterator& other) const {
return it == other.it;
}
/**
Pre increment.
*/
Iterator& operator++() {
++it;
return *this;
}
/**
Post increment (slower than preincrement).
*/
Iterator operator++(int) {
Iterator old = *this;
++(*this);
return old;
}
const T& operator*() const {
return it->key;
}
T* operator->() const {
return &(it->key);
}
operator T*() const {
return &(it->key);
}
};
/**
C++ STL style iterator method. Returns the first member.
Use preincrement (++entry) to get to the next element.
Do not modify the set while iterating.
*/
Iterator begin() const {
return Iterator(memberTable.begin());
}
/**
C++ STL style iterator method. Returns one after the last iterator
element.
*/
const Iterator end() const {
return Iterator(memberTable.end());
}
};
}
#endif
|
