HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 /// Get the min/max values of an array.
230 template<typename InputIt>
231 inline void
233  InputIt end,
236 {
237  typedef typename std::iterator_traits<InputIt>::value_type input_t;
238 
239  std::for_each(begin, end,
240  [&min, &max](const input_t &v)
241  {
242  min = SYSmin(min, v);
243  max = SYSmax(max, v);
244  });
245 }
246 
247 /// Normalize an array.
248 template<typename InputIt, typename OutputIt>
249 inline void
251  InputIt end,
252  OutputIt d_begin)
253 {
254  typedef typename std::iterator_traits<InputIt>::value_type input_t;
257  UTgetArrayMinMax(begin, end, min, max);
258  std::transform(begin, end, d_begin,
259  [&min, &max](const input_t &v)
260  {
261  return (v-min) / (max-min);
262  });
263 }
264 
265 /// Selects between arguments 'src1/src2' based on the lower of 'a/b'.
266 template<typename T>
267 inline size_t UTfastSelectLow(T a, T b, size_t src1, size_t src2)
268 {
269 #if defined(__clang__) && defined(__x86_64)
270  size_t res = src1;
271  asm("cmpq %1, %2; cmovaeq %4, %0"
272  :
273  "=q" (res)
274  :
275  "q" (a),
276  "q" (b),
277  "q" (src1),
278  "q" (src2),
279  "0" (res)
280  :
281  "cc");
282  return res;
283 #else
284  return b >= a ? src2 : src1;
285 #endif
286 }
287 
288 /// Fast upper bound search.
289 /// Adapted from "How We Beat C++ STL Binary Search"
290 /// Reference: https://realm.io/news/how-we-beat-cpp-stl-binary-search/
291 template<typename ForwardIt, typename T>
292 inline ForwardIt UTfastUpperBound(ForwardIt first, ForwardIt last, const T &value)
293 {
294  size_t size = last - first;
295  size_t low = 0;
296 
297  while (size >= 8)
298  {
299  size_t half = size / 2;
300  size_t other_half = size - half;
301  size_t probe = low + half;
302  size_t other_low = low + other_half;
303  size = half;
304  low = UTfastSelectLow(*(first+probe), value, low, other_low);
305 
306  half = size / 2;
307  other_half = size - half;
308  probe = low + half;
309  other_low = low + other_half;
310  size = half;
311  low = UTfastSelectLow(*(first+probe), value, low, other_low);
312 
313  half = size / 2;
314  other_half = size - half;
315  probe = low + half;
316  other_low = low + other_half;
317  size = half;
318  low = UTfastSelectLow(*(first+probe), value, low, other_low);
319  }
320 
321  while (size > 0)
322  {
323  size_t half = size / 2;
324  size_t other_half = size - half;
325  size_t probe = low + half;
326  size_t other_low = low + other_half;
327  size = half;
328  low = UTfastSelectLow(*(first+probe), value, low, other_low);
329  }
330 
331  return first + low;
332 }
333 
334 /// Find the value associated with the key. If the key is not found in the map,
335 /// a value is created with the given callback function and then inserted into
336 /// the map before returning.
337 template <typename Map, typename Key, typename CreateValueCB>
338 const typename Map::mapped_type &
339 UTfindOrInsert(Map &map, const Key &key, CreateValueCB create_value)
340 {
341  auto it = map.find(key);
342  if (it == map.end())
343  it = map.emplace(key, create_value()).first;
344 
345  return it->second;
346 }
347 
348 /// Reorder the elements in the given range [first, last) such that
349 /// each possible permutation of those elements has equal probability
350 /// of appearance.
351 ///
352 /// This function should be used instead of std::random_shuffle() and
353 /// std::shuffle(), which may produce different results with different
354 /// standard library implementations. std::random_shuffle() was also
355 /// removed in C++17.
356 template<class RandomIt, class RandomFunc>
357 void UTshuffle(RandomIt first, RandomIt last, RandomFunc &&r)
358 {
359  //
360  // The implementation below was modeled after a possible implementation
361  // for std::random_shuffle() in the cppreference documentation.
362  //
363 
364  typename std::iterator_traits<RandomIt>::difference_type i, n;
365  n = last - first;
366  for (i = n; i --> 1; )
367  {
368  using std::swap;
369  swap(first[i], first[r(i+1)]);
370  }
371 }
372 
373 #endif
374 
void swap(ArAssetInfo &lhs, ArAssetInfo &rhs)
Definition: assetInfo.h:60
#define SYSmax(a, b)
Definition: SYS_Math.h:1526
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
GLsizeiptr size
Definition: glew.h:1681
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1629
GLuint GLenum GLenum transform
Definition: glew.h:14742
bool detect(const T &tail)
Definition: UT_Algorithm.h:131
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
int64 exint
Definition: SYS_Types.h:125
const GLint * first
Definition: glew.h:1528
const GLdouble * v
Definition: glew.h:1391
uint64 value_type
Definition: GA_PrimCompat.h:29
AutoScope(UT_CycleDetect< T > *cycle)
Definition: UT_Algorithm.h:85
bool detect(const T &tail, exint min_length=2)
Definition: UT_Algorithm.h:192
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:232
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
void UTshuffle(RandomIt first, RandomIt last, RandomFunc &&r)
Definition: UT_Algorithm.h:357
GLuint GLuint end
Definition: glew.h:1253
GLsizei n
Definition: glew.h:4040
exint length() const
Definition: UT_Algorithm.h:187
long long int64
Definition: SYS_Types.h:116
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
void UTnormalizeArray(InputIt begin, InputIt end, OutputIt d_begin)
Normalize an array.
Definition: UT_Algorithm.h:250
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:267
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
exint length() const
Definition: UT_Algorithm.h:155
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
const Map::mapped_type & UTfindOrInsert(Map &map, const Key &key, CreateValueCB create_value)
Definition: UT_Algorithm.h:339
#define SYSmin(a, b)
Definition: SYS_Math.h:1527
ForwardIt UTfastUpperBound(ForwardIt first, ForwardIt last, const T &value)
Definition: UT_Algorithm.h:292
GLsizei const GLfloat * value
Definition: glew.h:1849
Definition: half.h:91
GLuint res
Definition: glew.h:11507