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  /// creation of new classes or unification of distinct classes invalidate
115  /// class indices. Each time the class indices are invalidated, the first
116  /// call to classIndex takes linear time. All subsequent calls take
117  /// constant time so long as the class indices remain valid.
118  /// The root_independent parameter is passed to buildIndex() if the index
119  /// has not been previously built needs to be rebuilt. See the comments
120  /// above that method for explanation.
121 
123  exint classIndex(exint elem, bool root_independent = false)
124  {
125  if (myIndex.size() == 0)
126  buildIndex(root_independent);
127 
128  return myIndex(elem);
129  }
130 
131 
133  exint classSize(exint elem) const
134  {
135  UT_ASSERT(myTrackSizes);
136  return mySize.size() > 0 ? mySize(classRoot(elem)) : -1;
137  }
138 
139  /// Copy the whole index array.
140  void getAllClassIndices(UT_IntArray &out_array);
141 
142  /// Free up all unnecessary information except for class roots.
143  /// makeClass and unionClasses operation are ignored on a consolidated
144  /// classifier. class size and index information are also expunged (unless
145  /// keep_size or keep_index are respectively set to true) and methods
146  /// classIndex() and classSize() return -1 on all input.
147  /// Of course classRoot() very much works as usual after consolidation!
148  /// Calling reset() revives the object from the state of consolidation
149  /// but naturally resets all the classes into singletons.
150  void consolidate(bool keep_size = false,
151  bool keep_index = false);
152 
153  /// Reset all the elements to singleton classes. If new_size is
154  /// non-negative the number of classes are changed to new_size with
155  /// ticket numbers 0 to new_size - 1. Otherwise, all classes are made
156  /// singletons again.
157  void reset(exint new_size = -1);
158 
159  /// Explicit request to build the index, instead of implicitly triggering
160  /// it by calling classIndex(). If root_indepent is true, the created
161  /// index of eac class will be the relative rank of its smallest element
162  /// compared to other classes. Otherwise, it will be the relative rank
163  /// of the class root (default) which is the case if the index is build
164  /// implicitly.
165  /// If min_class_size is set to a number larger than 1, only classes
166  /// with min_class_size elements or larger are assigned a usual index
167  /// and other classes are assigned -1.
168  void buildIndex(bool root_independent = false,
169  exint min_class_size = 1);
170 
172  { return myNumIndexedClasses; }
173 
174 private:
175 
177  exint parent(exint i) const
178  { return exint(myElems(i) & PARENT_MASK); }
179 
181  exint rank(exint i) const
182  { return exint(myElems(i) & RANK_MASK); }
183 
184 
186  void parent(exint i, exint p) const
187  { myElems(i) = ((myElems(i) & RANK_MASK) | p); }
188 
190  void rank(exint i, exint r) const
191  { myElems(i) = ((myElems(i) & PARENT_MASK) | r); }
192 
193  mutable
194  UT_ExintArray myElems;
195 
196  mutable
197  UT_ExintArray mySize;
198  UT_ExintArray myIndex;
199 
200  bool myTrackSizes;
201  exint myNumClasses = 0;
202  exint myNumIndexedClasses = 0;
203 };
204 
205 
206 
207 template <typename T>
209 {
210  UT_PtrClassifier(bool track_class_sizes) :
211  myClasses(track_class_sizes) { }
212 
213  ~UT_PtrClassifier() { }
214 
215  /// create a singleton part using parameter element
216 
218  exint makeClass(const T &ref)
219  {
220  exint res = myClasses.makeClass();
221  myRef.append(ref);
222  return res;
223  }
224 
226  void unionClasses(exint a, exint b)
227  { myClasses.unionClasses(a, b); }
228 
230  exint classRoot(exint elem) const
231  { return myClasses.classRoot(elem); }
232 
234  bool areInSameClass(exint a, exint b) const
235  { return myClasses.areInSameClass(a, b); }
236 
238  exint numClasses() const
239  { return myClasses.numClasses(); }
240 
242  exint size() const
243  { return myClasses.size(); }
244 
245  void reset()
246  { myClasses.reset(); }
247 
249  exint classIndex(exint elem)
250  { return myClasses.classIndex(elem); }
251 
253  exint classSize(exint elem)
254  { return myClasses.classSize(elem); }
255 
256  /// reverse lookup the element from the ticket number
258  T &getRef(exint elem)
259  { return myRef(elem); }
260 
261  /// reverse lookup the part root element from the ticket number of any
262  /// part element
263  T &getClassRootRef(exint elem)
264  {
265  exint root = myClasses.classRoot(elem);
266  return getRef(root);
267  }
268 
269  void consolidate(bool keep_size = false,
270  bool keep_index = false)
271  {
272  myClasses.consolidate(keep_size, keep_index);
273  }
274 
275 private:
276  UT_Array<T&> myRef;
277  UT_Classifier myClasses;
278 };
279 
280 
281 exint
283 {
284  auto s = myElems.size();
285  myElems.append(0);
286  parent(s, s);
287  return s;
288 }
289 
290 
291 exint
293 {
294  auto s = myElems.size();
295  myElems.appendMultiple(0, num_classes);
296 
297  for (exint i = s, ie = myElems.size(); i < ie; i++)
298  parent(i, i);
299 
300  if (myTrackSizes)
301  mySize.appendMultiple(1, num_classes);
302 
303  myNumClasses += num_classes;
304  return myElems.size() - 1;
305 }
306 
307 
308 void
310 {
311  exint aroot = classRoot(a);
312  exint broot = classRoot(b);
313 
314  if (aroot == broot)
315  return;
316 
317  auto arootrank = rank(aroot);
318  auto brootrank = rank(broot);
319 
320  if (arootrank < brootrank)
321  {
322  parent(aroot, broot);
323  if (myTrackSizes)
324  mySize(broot) += mySize(aroot);
325  }
326  else if (brootrank < arootrank)
327  {
328  parent(broot, aroot);
329  if (myTrackSizes)
330  mySize(aroot) += mySize(broot);
331  }
332  else
333  {
334  parent(broot, aroot);
335  rank(aroot, arootrank + RANK_BUMP);
336  if (myTrackSizes)
337  mySize(aroot) += mySize(broot);
338  }
339  myNumClasses--;
340 }
341 
342 
343 exint
345 {
346  exint e = i;
347 
348  while (true)
349  {
350  auto p = parent(e);
351  if (p == e)
352  break;
353  e = p;
354  }
355 
356 
357  while (i != e)
358  {
359  auto p = parent(i);
360  parent(i, e);
361  i = p;
362  }
363 
364  return e;
365 }
366 
367 #endif
#define RANK_BUMP
Definition: UT_Classifier.h:73
SYS_FORCE_INLINE exint makeClass()
SYS_FORCE_INLINE void unionClasses(exint a, exint b)
SYS_FORCE_INLINE bool areInSameClass(exint a, exint b) const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:13
exint size() const
Return the total number of elements in all classes.
#define RANK_MASK
Definition: UT_Classifier.h:72
png_uint_32 i
Definition: png.h:2877
exint size() const
Definition: UT_Array.h:451
GLsizeiptr size
Definition: glcorearb.h:663
UT_Classifier(bool track_class_sizes=false)
Definition: UT_Classifier.h:78
exint entries() const
GLint ref
Definition: glcorearb.h:123
int64 exint
Definition: SYS_Types.h:116
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)
SYS_FORCE_INLINE exint classIndex(exint elem, bool root_independent=false)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
exint numClasses() const
Return number of distinct classes.
size_t *lastDimSize unsigned int rank
Definition: wrapArray.h:326
SYS_FORCE_INLINE exint classSize(exint elem) const
exint append(void)
Definition: UT_Array.h:95
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
GLboolean r
Definition: glcorearb.h:1221
SYS_FORCE_INLINE exint classRoot(exint elem) const