HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_Algorithm.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_Algorithm.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  * this is supposed to be like STL's algorithm header -- put stuff in here
10  * that doesn't really belong in any other header.
11  */
12 
13 #ifndef __UT_Algorithm__
14 #define __UT_Algorithm__
15 
16 #include "UT_Assert.h"
17 
18 #include "UT_IteratorRange.h"
19 
20 #include <SYS/SYS_Types.h>
21 
22 #include <algorithm>
23 #include <iterator>
24 #include <limits>
25 #include <type_traits>
26 
27 #include <stddef.h>
28 
29 
30 /// A generic cycle detector that takes constant space and will detect cycles
31 /// using at most O(N) extra calls to detect() for a cycle of length N (if it
32 /// exists) using O(1) space.
33 ///
34 /// NOTE: In general, this won't detect cycles immediately and so your loop
35 /// must be able to support extra iterations.
36 ///
37 /// You might have as many as 3 times the number of iterations as your
38 /// total path length.
39 ///
40 /// Example:
41 ///
42 /// T walk;
43 /// UT_CycleDetect<T> cycle;
44 /// for (walk = first; walk && !cycle.detect(walk); walk = walk->next)
45 /// {
46 /// .... do stuff with walk ....
47 /// }
48 ///
49 /// @internal
50 /// This is an implementation of (Richard P.) Brent's cycle detection
51 /// algorithm. For an alternate cycle detector, there is also Floyd's cycle
52 /// detection algorithm but that one needs to be given 2 iterators.
53 /// @endinternal
54 template <typename T>
56 {
57 public:
58 
59  ///
60  /// Helper class for automatically saving and restoring the state of the
61  /// cycle detection within a scope block.
62  ///
63  /// Example:
64  ///
65  /// T walk;
66  /// UT_CycleDetect<T> cycle;
67  /// .....
68  /// {
69  /// UT_CycleDetect<T>::AutoScope cycle_detect_scope(cycle);
70  /// if (!cycle.detect(<some_object>))
71  /// {
72  /// ... do some work that may recursively update the cycle ...
73  /// }
74  /// else
75  /// {
76  /// ... cycle detected. Do work to report/handle cycle ...
77  ///
78  /// cycle_detect_scope.reset();
79  /// }
80  /// }
81  ///
82  class AutoScope
83  {
84  public:
86  : myCycle(cycle)
87  , myShouldReset(false)
88  {
89  mySavedHead = myCycle->myHead;
90  mySavedCount = myCycle->myCount;
91  mySavedStartCount = myCycle->myStartCount;
92  }
93 
95  {
96  if (myShouldReset)
97  {
98  myCycle->reset();
99  }
100  else
101  {
102  myCycle->myHead = mySavedHead;
103  myCycle->myCount = mySavedCount;
104  myCycle->myStartCount = mySavedStartCount;
105  }
106  }
107 
108  void reset()
109  {
110  myShouldReset = true;
111  }
112  private:
113  UT_CycleDetect<T> *myCycle;
114  T mySavedHead;
115  int64 mySavedCount;
116  int64 mySavedStartCount;
117  bool myShouldReset;
118  };
119 
121  {
122  reset();
123  }
124 
125  void reset()
126  {
127  myCount = 2; // must be a power of 2
128  myCycleDetected = false;
129  }
130 
131  bool detect(const T &tail)
132  {
133  if (myCycleDetected)
134  return true;
135 
136  // Reset before detection so that for loop idiom works.
137  // The if test is one iteration of the standard Brian Kernighan
138  // bit count algorithm. We use this to check if myCount is a power
139  // of 2 (ie. at most 1 bit set).
140  if ((myCount & (myCount - 1)) == 0)
141  {
142  myHead = tail;
143  myStartCount = myCount;
144  }
145  else if (myHead == tail)
146  {
147  myCycleDetected = true;
148  return true;
149  }
150 
151  myCount++;
152  return false;
153  }
154 
155  exint length() const
156  {
157  return myCount - myStartCount;
158  }
159 
160 private:
161  T myHead;
162  int64 myCount;
163  int64 myStartCount;
164  bool myCycleDetected;
165 };
166 /// A version of UT_CycleDetect that additionally supports querying of the
167 /// cycle length and detection of cycles with a minimum length.
168 /// @note Does not support cycle lengths larger than an exint
169 template <typename T>
171 {
172 public:
174  {
175  reset();
176  }
177 
178  inline void reset()
179  {
180  // Initialize myCount to the smallest value such that myHead is
181  // assigned on first but not the second call to detect().
182  myCount = 1;
183  myStartCount = myCount;
184  myCycleDetected = false;
185  }
186 
187  inline exint length() const
188  {
189  return myCount - myStartCount;
190  }
191 
192  inline bool detect(const T &tail, exint min_length = 2)
193  {
194  UT_ASSERT_P(min_length >= 2);
195 
196  if (myCycleDetected)
197  return true;
198 
199  ++myCount;
200 
201  // Reset before detection so that for loop idiom works.
202  // The if test is one iteration of the standard Brian Kernighan
203  // bit count algorithm. We use this to check if myCount is a power
204  // of 2 (ie. at most 1 bit set).
205  if ((myCount & (myCount - 1)) == 0)
206  {
207  myHead = tail;
208  myStartCount = myCount - 1;
209  }
210  else if (myHead == tail && length() >= min_length)
211  {
212  myCycleDetected = true;
213  return true;
214  }
215  return false;
216  }
217 
218  /// The algorithm guarantees that will detect a cycle with no more than
219  /// MAX_CYCLE_FACTOR*min_length calls to detect()
220  enum { MAX_CYCLE_FACTOR = 3 };
221 
222 private:
223  T myHead;
224  exint myCount;
225  exint myStartCount;
226  bool myCycleDetected;
227 };
228 
229 /// Delete all items in the range using the @c delete operator. The item type
230 /// must be a pointer type.
231 template<typename ForwardIt>
232 void UTdeleteAll(ForwardIt begin, ForwardIt end)
233 {
235  "The element type of the iterator must be a pointer." );
236  while (begin != end)
237  {
238  delete *begin;
239  *begin = nullptr;
240  ++begin;
241  }
242 }
243 
244 template<typename ForwardIt>
246 {
247  UTdeleteAll(range.begin(), range.end());
248 }
249 
250 
251 /// Deletes all items from a container. The container item type must be a
252 /// pointer type.
253 template<typename T>
254 void UTdeleteAll(T &container)
255 {
257  "The element type of the container must be a pointer." );
258  UTdeleteAll(container.begin(), container.end());
259 }
260 
261 /// Get the min/max values of an array.
262 template<typename InputIt>
263 inline void
264 UTgetArrayMinMax(InputIt begin,
265  InputIt end,
268 {
269  typedef typename std::iterator_traits<InputIt>::value_type input_t;
270 
271  std::for_each(begin, end,
272  [&min, &max](const input_t &v)
273  {
274  min = SYSmin(min, v);
275  max = SYSmax(max, v);
276  });
277 }
278 
279 /// Normalize an array.
280 template<typename InputIt, typename OutputIt>
281 inline void
282 UTnormalizeArray(InputIt begin,
283  InputIt end,
284  OutputIt d_begin)
285 {
286  typedef typename std::iterator_traits<InputIt>::value_type input_t;
289  UTgetArrayMinMax(begin, end, min, max);
290  std::transform(begin, end, d_begin,
291  [&min, &max](const input_t &v)
292  {
293  return (v-min) / (max-min);
294  });
295 }
296 
297 /// Selects between arguments 'src1/src2' based on the lower of 'a/b'.
298 template<typename T>
299 inline size_t UTfastSelectLow(T a, T b, size_t src1, size_t src2)
300 {
301 #if defined(__clang__) && defined(__x86_64)
302  size_t res = src1;
303  asm("cmpq %1, %2; cmovaeq %4, %0"
304  :
305  "=q" (res)
306  :
307  "q" (a),
308  "q" (b),
309  "q" (src1),
310  "q" (src2),
311  "0" (res)
312  :
313  "cc");
314  return res;
315 #else
316  return b >= a ? src2 : src1;
317 #endif
318 }
319 
320 /// Fast upper bound search.
321 /// Adapted from "How We Beat C++ STL Binary Search"
322 /// Reference: https://realm.io/news/how-we-beat-cpp-stl-binary-search/
323 template<typename ForwardIt, typename T>
324 inline ForwardIt UTfastUpperBound(ForwardIt first, ForwardIt last, const T &value)
325 {
326  size_t size = last - first;
327  size_t low = 0;
328 
329  while (size >= 8)
330  {
331  size_t half = size / 2;
332  size_t other_half = size - half;
333  size_t probe = low + half;
334  size_t other_low = low + other_half;
335  size = half;
336  low = UTfastSelectLow(*(first+probe), value, low, other_low);
337 
338  half = size / 2;
339  other_half = size - half;
340  probe = low + half;
341  other_low = low + other_half;
342  size = half;
343  low = UTfastSelectLow(*(first+probe), value, low, other_low);
344 
345  half = size / 2;
346  other_half = size - half;
347  probe = low + half;
348  other_low = low + other_half;
349  size = half;
350  low = UTfastSelectLow(*(first+probe), value, low, other_low);
351  }
352 
353  while (size > 0)
354  {
355  size_t half = size / 2;
356  size_t other_half = size - half;
357  size_t probe = low + half;
358  size_t other_low = low + other_half;
359  size = half;
360  low = UTfastSelectLow(*(first+probe), value, low, other_low);
361  }
362 
363  return first + low;
364 }
365 
366 #endif
367 
#define SYSmax(a, b)
Definition: SYS_Math.h:1365
GLint first
Definition: glcorearb.h:404
GLenum GLint * range
Definition: glcorearb.h:1924
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128
const GLdouble * v
Definition: glcorearb.h:836
bool detect(const T &tail)
Definition: UT_Algorithm.h:131
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
uint64 value_type
Definition: GA_PrimCompat.h:29
GLsizeiptr size
Definition: glcorearb.h:663
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
long long int64
Definition: SYS_Types.h:106
AutoScope(UT_CycleDetect< T > *cycle)
Definition: UT_Algorithm.h:85
IterT begin() const
void UTdeleteAll(ForwardIt begin, ForwardIt end)
Definition: UT_Algorithm.h:232
bool detect(const T &tail, exint min_length=2)
Definition: UT_Algorithm.h:192
IterT end() const
void UTgetArrayMinMax(InputIt begin, InputIt end, typename std::iterator_traits< InputIt >::value_type &min, typename std::iterator_traits< InputIt >::value_type &max)
Get the min/max values of an array.
Definition: UT_Algorithm.h:264
int64 exint
Definition: SYS_Types.h:115
GLuint GLuint end
Definition: glcorearb.h:474
exint length() const
Definition: UT_Algorithm.h:187
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
GA_API const UT_StringHolder transform
GLsizei const GLfloat * value
Definition: glcorearb.h:823
void UTnormalizeArray(InputIt begin, InputIt end, OutputIt d_begin)
Normalize an array.
Definition: UT_Algorithm.h:282
size_t UTfastSelectLow(T a, T b, size_t src1, size_t src2)
Selects between arguments 'src1/src2' based on the lower of 'a/b'.
Definition: UT_Algorithm.h:299
exint length() const
Definition: UT_Algorithm.h:155
#define SYSmin(a, b)
Definition: SYS_Math.h:1366
ForwardIt UTfastUpperBound(ForwardIt first, ForwardIt last, const T &value)
Definition: UT_Algorithm.h:324
Definition: half.h:91