HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Classifier.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_Classifier.h (UT Library, C++)
7  *
8  * COMMENTS: This is a generic implementation of disjoint-set (aka union/find)
9  * data structure.
10  *
11  * We have two versions of this data structure, the unreferenced and the
12  * referenced one, respectively realized by classes UT_Classifier and
13  * UT_PtrClassifier.
14  *
15  * The referenced version essentially has the same functionality as the
16  * unreferenced one but in addition also keeps track of the elements out of
17  * which it makes the initial singleton classes and can offer reverse look up
18  * on them.
19  *
20  * Elements are turned into singleton classes using makeClass() method which
21  * returns an integer "ticket number". Each ticket number represents an element
22  * in the structure. Ticket numbers are generated consecutively starting from
23  * 0, therefore, if the objects we wish to classify happen to be indexed
24  * consecutively (as is the case with points, primitives, etc), there will be
25  * a natural mapping between ticket numbers and object indices which makes
26  * moving between ticket numbers and and actual objects trivial. Otherwise,
27  * there will be a need for mapping between ticket numbers and the objects.
28  * In this case the class UT_PtrClassifier can help by keeping back-references
29  * to the objects for which tickets are issued. Therefore, the makeClass()
30  * method takes a reference to the object for which the ticket is being issued
31  * and this reference can be later retrieved from the ticket number using the
32  * getRef() method.
33  *
34  * In contrast, UT_Classifier::makeClass does not take a reference to the
35  * object and instead allows multiple tickets to be generated at once.
36  *
37  * The unionParts operation combines the classes to which its two operands
38  * belong into a single class. Each class is identified by its "root"
39  * (sometimes called "leader" in the literature) which is one of the elements
40  * in that class. The ticket number for the root of a class can be looked up
41  * using the partRoot() method. Therefore to check to see if two elements are
42  * contained in the same class, one can compare their corresponding roots,
43  * or equivalently use the areInSameClass() shortcut. In UT_PtrClassifier one
44  * can directly lookup a reference to the root of a class using getRootRef().
45  *
46  * It is often useful to have consecutive class indices. The classIndex()
47  * method returns such a classIndex for each ticket number. Note that these
48  * indices can change every time a new class is created or two classes are
49  * merged into one.
50  *
51  * It is sometimes useful to have access to the size of each class. The
52  * optional parameter "track_class_sizes" for the constructor of UT_Classifier
53  * and UT_PtrClassifier enables tracking of class sizes. At any time, the
54  * size of the class to which an element belongs can be queried using
55  * classSize() method.
56  *
57  * Note 1: in general this data structure does not support deletion of elements.
58  *
59  * Note 2: Neither reads nor writes are thread-safe.
60  *
61  */
62 
63 
64 #ifndef __UT_Classifier__
65 #define __UT_Classifier__
66 
67 #include <SYS/SYS_Types.h>
68 #include "UT_Array.h"
69 #include "UT_ValArray.h"
70 
71 #define PARENT_MASK 0x00ffffffffffffff
72 #define RANK_MASK 0xff00000000000000
73 #define RANK_BUMP 0x0100000000000000
74 
76 {
77 public:
78  UT_Classifier(bool track_class_sizes = false) :
79  myTrackSizes(track_class_sizes) { }
80 
81  ~UT_Classifier() = default;
82 
83  /// create one or more singleton classes which get consecutive ticket
84  /// numbers returns the ticket number of that last class created
86  exint makeClass();
87 
89  exint makeClass(exint num_classes);
90 
91 
92  /// merge the classes containing elements with tickets a and b into a
93  /// single part
95  void unionClasses(exint a, exint b);
96 
97  /// Look up the ticket number for the root element of the part of the
98  /// parameter element
100  exint classRoot(exint elem) const;
101 
103  bool areInSameClass(exint a, exint b) const
104  { return classRoot(a) == classRoot(b); }
105 
106  /// Return number of distinct classes
107  exint numClasses() const { return myNumClasses; }
108 
109  /// Return the total number of elements in all classes
110  exint size() const { return myElems.size(); }
111  exint entries() const { return size(); }
112 
113  /// Returns an ordinal number between 0 and number of classes - 1.
114  /// buildIndex() *must* be called explicitly before calling classIndex().
115  /// Calling makeClasses() or unionClasses() invalidate the index and
116 
118  exint classIndex(exint elem) const
119  {
120  UT_ASSERT_P(!myIndex.isEmpty());
121  return myIndex(elem);
122  }
123 
125  exint classSize(exint elem) const
126  {
127  UT_ASSERT_P(myTrackSizes);
128  return mySize.size() > 0 ? mySize(classRoot(elem)) : -1;
129  }
130 
131  /// Copy the whole index array.
132  void getAllClassIndices(UT_IntArray &out_array);
133 
134  /// Free up all unnecessary information except for class roots.
135  /// makeClass and unionClasses operation are ignored on a consolidated
136  /// classifier. class size and index information are also expunged (unless
137  /// keep_size or keep_index are respectively set to true) and methods
138  /// classIndex() and classSize() return -1 on all input.
139  /// Of course classRoot() very much works as usual after consolidation!
140  /// Calling reset() revives the object from the state of consolidation
141  /// but naturally resets all the classes into singletons.
142  void consolidate(bool keep_size = false,
143  bool keep_index = false);
144 
145  /// Reset all the elements to singleton classes. If new_size is
146  /// non-negative the number of classes are changed to new_size with
147  /// ticket numbers 0 to new_size - 1. Otherwise, all classes are made
148  /// singletons again.
149  void reset(exint new_size = -1);
150 
151  /// Explicit request to build the index, instead of implicitly triggering
152  /// it by calling classIndex(). If root_independent is true, the created
153  /// index of each class will be the relative rank of its smallest element
154  /// compared to other classes. Otherwise, it will be the relative rank
155  /// of the class root (default) which is the case if the index is build
156  /// implicitly.
157  /// If min_class_size is set to a number larger than 1, only classes
158  /// with min_class_size elements or larger are assigned a usual index
159  /// and other classes are assigned -1.
160  void buildIndex(bool root_independent = false,
161  exint min_class_size = 1);
162 
164  { return myNumIndexedClasses; }
165 
166 private:
167 
169  exint parent(exint i) const
170  { return exint(myElems(i) & PARENT_MASK); }
171 
173  exint rank(exint i) const
174  { return exint(myElems(i) & RANK_MASK); }
175 
176 
178  void parent(exint i, exint p) const
179  { myElems(i) = ((myElems(i) & RANK_MASK) | p); }
180 
182  void rank(exint i, exint r) const
183  { myElems(i) = ((myElems(i) & PARENT_MASK) | r); }
184 
185  mutable
186  UT_ExintArray myElems;
187 
188  mutable
189  UT_ExintArray mySize;
190  UT_ExintArray myIndex;
191 
192  bool myTrackSizes;
193  exint myNumClasses = 0;
194  exint myNumIndexedClasses = 0;
195 };
196 
197 
198 
199 template <typename T>
201 {
202  UT_PtrClassifier(bool track_class_sizes) :
203  myClasses(track_class_sizes) { }
204 
205  ~UT_PtrClassifier() { }
206 
207  /// create a singleton part using parameter element
208 
210  exint makeClass(const T &ref)
211  {
212  exint res = myClasses.makeClass();
213  myRef.append(ref);
214  return res;
215  }
216 
218  void unionClasses(exint a, exint b)
219  { myClasses.unionClasses(a, b); }
220 
222  exint classRoot(exint elem) const
223  { return myClasses.classRoot(elem); }
224 
226  bool areInSameClass(exint a, exint b) const
227  { return myClasses.areInSameClass(a, b); }
228 
230  exint numClasses() const
231  { return myClasses.numClasses(); }
232 
234  exint size() const
235  { return myClasses.size(); }
236 
237  void reset()
238  { myClasses.reset(); }
239 
241  exint classIndex(exint elem)
242  { return myClasses.classIndex(elem); }
243 
245  exint classSize(exint elem)
246  { return myClasses.classSize(elem); }
247 
248  /// reverse lookup the element from the ticket number
250  T &getRef(exint elem)
251  { return myRef(elem); }
252 
253  /// reverse lookup the part root element from the ticket number of any
254  /// part element
255  T &getClassRootRef(exint elem)
256  {
257  exint root = myClasses.classRoot(elem);
258  return getRef(root);
259  }
260 
261  void consolidate(bool keep_size = false,
262  bool keep_index = false)
263  {
264  myClasses.consolidate(keep_size, keep_index);
265  }
266 
267 private:
268  UT_Array<T&> myRef;
269  UT_Classifier myClasses;
270 };
271 
272 
273 exint
275 {
276  auto s = myElems.size();
277  myElems.append(0);
278  parent(s, s);
279  return s;
280 }
281 
282 
283 exint
285 {
286  auto s = myElems.size();
287  myElems.appendMultiple(0, num_classes);
288 
289  for (exint i = s, ie = myElems.size(); i < ie; i++)
290  parent(i, i);
291 
292  if (myTrackSizes)
293  mySize.appendMultiple(1, num_classes);
294 
295  myNumClasses += num_classes;
296  return myElems.size() - 1;
297 }
298 
299 
300 void
302 {
303  exint aroot = classRoot(a);
304  exint broot = classRoot(b);
305 
306  if (aroot == broot)
307  return;
308 
309  auto arootrank = rank(aroot);
310  auto brootrank = rank(broot);
311 
312  if (arootrank < brootrank)
313  {
314  parent(aroot, broot);
315  if (myTrackSizes)
316  mySize(broot) += mySize(aroot);
317  }
318  else if (brootrank < arootrank)
319  {
320  parent(broot, aroot);
321  if (myTrackSizes)
322  mySize(aroot) += mySize(broot);
323  }
324  else
325  {
326  parent(broot, aroot);
327  rank(aroot, arootrank + RANK_BUMP);
328  if (myTrackSizes)
329  mySize(aroot) += mySize(broot);
330  }
331  myNumClasses--;
332 }
333 
334 
335 exint
337 {
338  exint e = i;
339 
340  while (true)
341  {
342  auto p = parent(e);
343  if (p == e)
344  break;
345  e = p;
346  }
347 
348 
349  while (i != e)
350  {
351  auto p = parent(i);
352  parent(i, e);
353  i = p;
354  }
355 
356  return e;
357 }
358 
359 #endif
GLdouble s
Definition: glew.h:1390
GLsizeiptr size
Definition: glew.h:1681
#define RANK_BUMP
Definition: UT_Classifier.h:73
GLenum GLint ref
Definition: glew.h:1845
SYS_FORCE_INLINE exint makeClass()
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
SYS_FORCE_INLINE void unionClasses(exint a, exint b)
SYS_FORCE_INLINE bool areInSameClass(exint a, exint b) const
#define UT_API
Definition: UT_API.h:13
exint size() const
Return the total number of elements in all classes.
GLboolean reset
Definition: glew.h:4959
#define RANK_MASK
Definition: UT_Classifier.h:72
exint size() const
Definition: UT_Array.h:451
SYS_FORCE_INLINE exint classIndex(exint elem) const
UT_Classifier(bool track_class_sizes=false)
Definition: UT_Classifier.h:78
exint entries() const
int64 exint
Definition: SYS_Types.h:120
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
void reset(exint new_size=-1)
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
exint numIndexedClasses() const
#define PARENT_MASK
Definition: UT_Classifier.h:71
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:195
void consolidate(bool keep_size=false, bool keep_index=false)
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLfloat GLfloat p
Definition: glew.h:16321
exint numClasses() const
Return number of distinct classes.
size_t *lastDimSize unsigned int rank
Definition: wrapArray.h:331
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
SYS_FORCE_INLINE exint classSize(exint elem) const
exint append(void)
Definition: UT_Array.h:95
SYS_FORCE_INLINE exint classRoot(exint elem) const
GLuint res
Definition: glew.h:11507