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 
82  { *this = other; }
83 
84  ~UT_Classifier() = default;
85 
86  inline
87  UT_Classifier &operator=(const UT_Classifier &other);
88 
89  /// create one or more singleton classes which get consecutive ticket
90  /// numbers returns the ticket number of that last class created
92  exint makeClass();
93 
95  exint makeClass(exint num_classes);
96 
97 
98  /// merge the classes containing elements with tickets a and b into a
99  /// single part
101  void unionClasses(exint a, exint b);
102 
103  /// Look up the ticket number for the root element of the part of the
104  /// parameter element
106  exint classRoot(exint elem) const;
107 
109  bool areInSameClass(exint a, exint b) const
110  { return classRoot(a) == classRoot(b); }
111 
112  /// Return number of distinct classes
113  exint numClasses() const { return myNumClasses; }
114 
115  /// Return the total number of elements in all classes
116  exint size() const { return myElems.size(); }
117  exint entries() const { return size(); }
118 
119  /// Returns an ordinal number between 0 and number of classes - 1.
120  /// buildIndex() *must* be called explicitly before calling classIndex().
121  /// Calling makeClasses() or unionClasses() invalidate the index and
122 
124  exint classIndex(exint elem) const
125  {
126  UT_ASSERT_P(!myIndex.isEmpty());
127  return myIndex(elem);
128  }
129 
131  exint classSize(exint elem) const
132  {
133  UT_ASSERT_P(myTrackSizes);
134  return mySize.size() > 0 ? mySize(classRoot(elem)) : -1;
135  }
136 
137  /// Copy the whole index array.
138  void getAllClassIndices(UT_IntArray &out_array);
139 
140  /// Free up all unnecessary information except for class roots.
141  /// makeClass and unionClasses operation are ignored on a consolidated
142  /// classifier. class size and index information are also expunged (unless
143  /// keep_size or keep_index are respectively set to true) and methods
144  /// classIndex() and classSize() return -1 on all input.
145  /// Of course classRoot() very much works as usual after consolidation!
146  /// Calling reset() revives the object from the state of consolidation
147  /// but naturally resets all the classes into singletons.
148  void consolidate(bool keep_size = false,
149  bool keep_index = false);
150 
151  /// Reset all the elements to singleton classes. If new_size is
152  /// non-negative the number of classes are changed to new_size with
153  /// ticket numbers 0 to new_size - 1. Otherwise, all classes are made
154  /// singletons again.
155  void reset(exint new_size = -1);
156 
157  /// Explicit request to build the index, instead of implicitly triggering
158  /// it by calling classIndex(). If root_independent is true, the created
159  /// index of each class will be the relative rank of its smallest element
160  /// compared to other classes. Otherwise, it will be the relative rank
161  /// of the class root (default) which is the case if the index is build
162  /// implicitly.
163  /// If min_class_size is set to a number larger than 1, only classes
164  /// with min_class_size elements or larger are assigned a usual index
165  /// and other classes are assigned -1.
166  void buildIndex(bool root_independent = false,
167  exint min_class_size = 1);
168 
170  { return myNumIndexedClasses; }
171 
172 private:
173 
175  exint parent(exint i) const
176  { return exint(myElems(i) & PARENT_MASK); }
177 
179  exint rank(exint i) const
180  { return exint(myElems(i) & RANK_MASK); }
181 
182 
184  void parent(exint i, exint p) const
185  { myElems(i) = ((myElems(i) & RANK_MASK) | p); }
186 
188  void rank(exint i, exint r) const
189  { myElems(i) = ((myElems(i) & PARENT_MASK) | r); }
190 
191  mutable
192  UT_ExintArray myElems;
193 
194  mutable
195  UT_ExintArray mySize;
196  UT_ExintArray myIndex;
197 
198  bool myTrackSizes;
199  exint myNumClasses = 0;
200  exint myNumIndexedClasses = 0;
201 };
202 
203 
204 
205 template <typename T>
207 {
208  UT_PtrClassifier(bool track_class_sizes) :
209  myClasses(track_class_sizes) { }
210 
211  ~UT_PtrClassifier() { }
212 
213  /// create a singleton part using parameter element
214 
216  exint makeClass(const T &ref)
217  {
218  exint res = myClasses.makeClass();
219  myRef.append(ref);
220  return res;
221  }
222 
224  void unionClasses(exint a, exint b)
225  { myClasses.unionClasses(a, b); }
226 
228  exint classRoot(exint elem) const
229  { return myClasses.classRoot(elem); }
230 
232  bool areInSameClass(exint a, exint b) const
233  { return myClasses.areInSameClass(a, b); }
234 
236  exint numClasses() const
237  { return myClasses.numClasses(); }
238 
240  exint size() const
241  { return myClasses.size(); }
242 
243  void reset()
244  { myClasses.reset(); }
245 
247  exint classIndex(exint elem)
248  { return myClasses.classIndex(elem); }
249 
251  exint classSize(exint elem)
252  { return myClasses.classSize(elem); }
253 
254  /// reverse lookup the element from the ticket number
256  T &getRef(exint elem)
257  { return myRef(elem); }
258 
259  /// reverse lookup the part root element from the ticket number of any
260  /// part element
261  T &getClassRootRef(exint elem)
262  {
263  exint root = myClasses.classRoot(elem);
264  return getRef(root);
265  }
266 
267  void consolidate(bool keep_size = false,
268  bool keep_index = false)
269  {
270  myClasses.consolidate(keep_size, keep_index);
271  }
272 
273 private:
274  UT_Array<T&> myRef;
275  UT_Classifier myClasses;
276 };
277 
278 
279 exint
281 {
282  auto s = myElems.size();
283  myElems.append(0);
284  parent(s, s);
285  return s;
286 }
287 
288 
289 exint
291 {
292  auto s = myElems.size();
293  myElems.appendMultiple(0, num_classes);
294 
295  for (exint i = s, ie = myElems.size(); i < ie; i++)
296  parent(i, i);
297 
298  if (myTrackSizes)
299  mySize.appendMultiple(1, num_classes);
300 
301  myNumClasses += num_classes;
302  return myElems.size() - 1;
303 }
304 
305 
306 void
308 {
309  exint aroot = classRoot(a);
310  exint broot = classRoot(b);
311 
312  if (aroot == broot)
313  return;
314 
315  auto arootrank = rank(aroot);
316  auto brootrank = rank(broot);
317 
318  if (arootrank < brootrank)
319  {
320  parent(aroot, broot);
321  if (myTrackSizes)
322  mySize(broot) += mySize(aroot);
323  }
324  else if (brootrank < arootrank)
325  {
326  parent(broot, aroot);
327  if (myTrackSizes)
328  mySize(aroot) += mySize(broot);
329  }
330  else
331  {
332  parent(broot, aroot);
333  rank(aroot, arootrank + RANK_BUMP);
334  if (myTrackSizes)
335  mySize(aroot) += mySize(broot);
336  }
337  myNumClasses--;
338 }
339 
340 
341 exint
343 {
344  exint e = i;
345 
346  while (true)
347  {
348  auto p = parent(e);
349  if (p == e)
350  break;
351  e = p;
352  }
353 
354 
355  while (i != e)
356  {
357  auto p = parent(i);
358  parent(i, e);
359  i = p;
360  }
361 
362  return e;
363 }
364 
367 {
368  myElems = other.myElems;
369  mySize = other.mySize;
370  myIndex = other.myIndex;
371 
372  myTrackSizes = other.myTrackSizes;
373  myNumClasses = other.myNumClasses;
374  myNumIndexedClasses = other.myNumIndexedClasses;
375 
376  return *this;
377 }
378 
379 #endif
#define RANK_BUMP
Definition: UT_Classifier.h:73
SYS_FORCE_INLINE exint makeClass()
UT_Classifier & operator=(const UT_Classifier &other)
SYS_FORCE_INLINE void unionClasses(exint a, exint b)
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE bool areInSameClass(exint a, exint b) const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
GLdouble s
Definition: glad.h:3009
#define UT_API
Definition: UT_API.h:14
exint size() const
Return the total number of elements in all classes.
#define RANK_MASK
Definition: UT_Classifier.h:72
exint size() const
Definition: UT_Array.h:646
SYS_FORCE_INLINE exint classIndex(exint elem) const
UT_Classifier(bool track_class_sizes=false)
Definition: UT_Classifier.h:78
exint entries() const
GLboolean reset
Definition: glad.h:5138
GLint ref
Definition: glcorearb.h:124
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
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:795
void consolidate(bool keep_size=false, bool keep_index=false)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
exint append()
Definition: UT_Array.h:142
UT_Classifier(const UT_Classifier &other)
Definition: UT_Classifier.h:81
GLsizeiptr size
Definition: glcorearb.h:664
exint numClasses() const
Return number of distinct classes.
LeafData & operator=(const LeafData &)=delete
SYS_FORCE_INLINE exint classSize(exint elem) const
GLboolean r
Definition: glcorearb.h:1222
SYS_FORCE_INLINE exint classRoot(exint elem) const