HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Permute.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_Permute.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_Permute__
12 #define __UT_Permute__
13 
14 #include "UT_API.h"
15 #include "UT_Assert.h"
16 #include "UT_MTwister.h"
17 #include "UT_StackBuffer.h"
18 #include "UT_Swap.h"
19 #include "UT_TBBParallelInvoke.h"
20 
21 #include <SYS/SYS_TypeTraits.h>
22 
23 #include <algorithm>
24 #include <iterator>
25 
26 #include <string.h>
27 
28 
29 /// This is a custom implementation of std::partition,
30 /// just so that we don't keep having issues of different
31 /// platforms giving different results.
32 ///
33 /// This implementation requires bidirectional iterators.
34 template<typename IT, typename PRED>
35 IT UTpartition(IT start, IT end, PRED isbeforesplit)
36 {
37  while (true)
38  {
39  if (start == end)
40  return start;
41 
42  // Skip elements at the start that belong before the split.
43  while (isbeforesplit(*start))
44  {
45  ++start;
46  if (start == end)
47  return start;
48  }
49 
50  // Skip elements at the end that belong after the split.
51  do
52  {
53  --end;
54  if (start == end)
55  return start;
56  } while(!isbeforesplit(*end));
57 
58  // start points to something that goes after the split,
59  // and end points to something that goes before the split.
60  UTswap(*start, *end);
61  ++start;
62  }
63 }
64 
65 /// This is a custom implementation of std::nth_element,
66 /// just so that we don't keep having issues of different
67 /// platforms giving different results.
68 ///
69 /// (Having a comparator that forced strict ordering wasn't
70 /// sufficient for std::nth_element, because that only guarantees
71 /// that nth is greater than everything before it and less than
72 /// everything after it. We'd have to then sort the two sections
73 /// with the comparator have consistency.)
74 ///
75 /// This implementation requires a comparator.
76 template<typename IT, typename COMPARE>
77 void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
78 {
79  if (start == end)
80  return;
81 
82  while (start+2 < end)
83  {
84  // We have at least 3 elements
85 
86  // We could do a more formal introselect that falls back
87  // to the proper median of medians algorithm that guarantees
88  // O(n) time, but for now, let's just pick a few arbitrary
89  // points and pick the median as the pivot.
90 
91  auto diff = (end-start);
92  auto hdiff = (diff>>1);
93  const IT mid = (start+hdiff);
94  const IT last = end-1;
95 
96  // This is set up so that if they're equal,
97  // pivot will be mid.
99  if (isAbeforeB(*last, *start))
100  {
101  if (isAbeforeB(*mid, *start))
102  {
103  if (isAbeforeB(*last, *mid))
104  pivot = *mid; // LMS
105  else
106  pivot = *last; // MLS
107  }
108  else
109  pivot = *start; // LSM
110  }
111  else
112  {
113  if (isAbeforeB(*mid, *start))
114  pivot = *start; // MSL
115  else
116  {
117  if (isAbeforeB(*last, *mid))
118  pivot = *last; // SLM
119  else
120  pivot = *mid; // SML
121  }
122  }
123 
124  // This partition moves everything belonging before the pivot
125  // to the beginning, i.e.:
126  // [(elements < pivot) (elements >= pivot)]
127  IT split = UTpartition(start, end,
128  [&pivot,&isAbeforeB](const typename std::iterator_traits<IT>::value_type &v)
129  { return isAbeforeB(v, pivot); }
130  );
131  // Since there may be many duplicates and pivot could be
132  // the smallest element, we must move all elements that equal
133  // pivot (i.e. (v <= pivot) && (v >= pivot), the latter of which
134  // is dealt with above) to the beginning of the split.
135  // If we don't do this, we may make no progress on some iteration
136  // and loop forever.
137  // [(elements < pivot) (elements == pivot) (elements > pivot)]
138  IT split2 = UTpartition(split, end,
139  [&pivot,&isAbeforeB](const typename std::iterator_traits<IT>::value_type &v)
140  { return !isAbeforeB(pivot, v); } // !(pivot < v) <--> (pivot >= v) <--> (v <= pivot)
141  );
142 
143  // Just "recurse" on the section containing nth.
144  if (nth < split)
145  end = split;
146  else if (nth < split2)
147  return; // Between split and split2, everything is equal to pivot.
148  else
149  start = split2;
150  }
151 
152  if (start+1 == end)
153  return;
154 
155  // 2 elements left
156  if (isAbeforeB(*(end-1), *start))
157  UTswap(*start, *(end-1));
158 }
159 
160 /// This is a custom implementation of std::nth_element,
161 /// just so that we don't keep having issues of different
162 /// platforms giving different results.
163 /// This implementation uses std::less.
164 template<typename IT>
165 void UTnth_element(IT start, IT nth, IT end)
166 {
167  UTnth_element(start, nth, end, std::less<typename std::iterator_traits<IT>::value_type>());
168 }
169 
171 {
172  UT_VariableSizeRef(void *p, size_t element_bytes)
173  : myPtr(p)
174  , myElementBytes(element_bytes)
175  {}
176 
177  UT_VariableSizeRef &operator=(const UT_VariableSizeRef &that) = delete;
178 
179  void *ptr() const
180  {
181  return myPtr;
182  }
183  size_t elementBytes() const
184  {
185  return myElementBytes;
186  }
187 
188  void *myPtr;
189  const size_t myElementBytes;
190 };
191 
192 static inline void UTswap(UT_VariableSizeRef a, UT_VariableSizeRef b)
193 {
194  // Swap the actual content, not a and b themselves.
196  size_t nbytes = a.elementBytes();
197  UT_StackBuffer<char> tmp(nbytes);
198  memcpy(tmp.array(), a.ptr(), nbytes);
199  memcpy(a.ptr(), b.ptr(), nbytes);
200  memcpy(b.ptr(), tmp.array(), nbytes);
201 }
202 
204 {
205  UT_VariableSizePtr(void *p, size_t element_bytes)
206  : myPtr(p)
207  , myElementBytes(element_bytes)
208  {}
209 
210  bool operator==(const UT_VariableSizePtr &that) const
211  {
213  return myPtr == that.myPtr;
214  }
215  bool operator!=(const UT_VariableSizePtr &that) const
216  {
218  return myPtr != that.myPtr;
219  }
220  bool operator<(const UT_VariableSizePtr &that) const
221  {
223  return myPtr < that.myPtr;
224  }
225  bool operator<=(const UT_VariableSizePtr &that) const
226  {
228  return myPtr <= that.myPtr;
229  }
230  bool operator>(const UT_VariableSizePtr &that) const
231  {
233  return myPtr > that.myPtr;
234  }
235  bool operator>=(const UT_VariableSizePtr &that) const
236  {
238  return myPtr >= that.myPtr;
239  }
240  void operator+=(const size_t i)
241  {
242  ((char *&)myPtr) += i*myElementBytes;
243  }
244  void operator-=(const size_t i)
245  {
246  ((char *&)myPtr) -= i*myElementBytes;
247  }
248  UT_VariableSizePtr operator+(const size_t i) const
249  {
250  return UT_VariableSizePtr((void *)(((char *)myPtr) + i*myElementBytes), myElementBytes);
251  }
252  UT_VariableSizePtr operator-(const size_t i) const
253  {
254  return UT_VariableSizePtr((void *)(((char *)myPtr) - i*myElementBytes), myElementBytes);
255  }
257  {
258  ((char *&)myPtr) += myElementBytes;
259  return *this;
260  }
262  {
263  ((char *&)myPtr) -= myElementBytes;
264  return *this;
265  }
267  {
269  }
270  UT_VariableSizeRef operator[](const size_t i) const
271  {
272  return UT_VariableSizeRef((void *)(((char *)myPtr) + i*myElementBytes), myElementBytes);
273  }
274 
275  void *ptr() const
276  {
277  return myPtr;
278  }
279  size_t elementBytes() const
280  {
281  return myElementBytes;
282  }
283 
284  void *myPtr;
285  const size_t myElementBytes;
286 };
287 
288 
289 namespace UT_Permute {
290 
291 template <typename T, typename INT>
293 {
294 public:
295  Partition(T *low, const INT *permute, INT mid)
296  : myLow(low)
297  , myPermute(permute)
298  , myMid(mid) {}
299  bool operator()(const T &rhs) const
300  {
301  return myPermute[&rhs-myLow] < myMid;
302  }
303 private:
304  T *myLow;
305  const INT *myPermute;
306  INT myMid;
307 };
308 
309 template <typename INT>
311 {
312 public:
313  PartitionUnknown(UT_VariableSizePtr low, const INT *permute, INT mid)
314  : myLow(low)
315  , myPermute(permute)
316  , myMid(mid)
317  {}
318  bool operator()(const UT_VariableSizeRef &rhs) const
319  {
320  return myPermute[(((char*)rhs.ptr())-((char*)myLow.ptr()))/myLow.elementBytes()] < myMid;
321  }
322 private:
323  UT_VariableSizePtr myLow;
324  const INT *myPermute;
325  INT myMid;
326 };
327 
328 template<typename INT>
330 {
331 public:
332  PartitionPermute(INT mid) : myMid(mid) {}
333  bool operator()(INT rhs) const
334  {
335  return rhs < myMid;
336  }
337 private:
338  INT myMid;
339 };
340 
341 static const int theCrossover = 1024;
342 
343 template <typename T, typename INT>
344 static inline void
345 permuteInPlaceRHelper(T *vals, INT *permute, INT low, INT high)
346 {
347  INT size = high - low;
348  T tmp[theCrossover];
349  for (INT i = low; i < high; i++)
350  tmp[permute[i] - low] = vals[i];
351 
352  // Similar to UT_Array, avoid memcpy if the type cannot be trivially
353  // relocated.
354  if constexpr (
357  {
358  memcpy(reinterpret_cast<void *>(vals + low), tmp, size * sizeof(T));
359  }
360  else
361  {
362  std::move(tmp, tmp + size, vals + low);
363  }
364 }
365 
366 template <typename INT>
367 static inline void
368 permuteInPlaceRHelper(void *vals, size_t element_bytes, INT *permute, INT low, INT high)
369 {
370  INT size = high-low;
371  UT_StackBuffer<char, 16*1024> tmp(element_bytes*size);
372  for (INT i = low; i < high; i++)
373  {
374  memcpy(tmp.array() + element_bytes*(permute[i]-low), ((const char *)vals) + element_bytes*i, element_bytes);
375  }
376  memcpy(((char *)vals) + element_bytes*low, tmp.array(), size*element_bytes);
377 }
378 
379 // Permute by parallel recursive partitioning
380 template <typename T, typename INT>
381 static inline void
382 permuteInPlaceR(T *vals, INT *permute, INT low, INT high)
383 {
384  INT size = high-low;
385  if (size < theCrossover)
386  {
387  permuteInPlaceRHelper(vals, permute, low, high);
388  return;
389  }
390 
391  INT mid = (low + high) / 2;
392 
393  UTpartition(vals + low,
394  vals + high,
395  Partition<T,INT>(vals + low, permute + low, mid));
396  UTpartition(permute + low,
397  permute + high,
398  PartitionPermute<INT>(mid));
399 
400  tbb::parallel_invoke(
401  [=]() { permuteInPlaceR(vals, permute, low, mid); },
402  [=]() { permuteInPlaceR(vals, permute, mid, high); }
403  );
404 }
405 
406 // Permute by parallel recursive partitioning
407 template <typename INT>
408 static inline void
409 permuteInPlaceR(UT_VariableSizePtr vals, INT *permute, INT low, INT high)
410 {
411  INT size = high-low;
412  if (size < theCrossover)
413  {
414  permuteInPlaceRHelper(vals.ptr(), vals.elementBytes(), permute, low, high);
415  return;
416  }
417 
418  INT mid = (low + high) / 2;
419 
420  UTpartition(vals + low,
421  vals + high,
422  PartitionUnknown<INT>(vals + low, permute + low, mid));
423  UTpartition(permute + low,
424  permute + high,
425  PartitionPermute<INT>(mid));
426 
427  tbb::parallel_invoke(
428  [=]() { permuteInPlaceR(vals, permute, low, mid); },
429  [=]() { permuteInPlaceR(vals, permute, mid, high); }
430  );
431 }
432 
433 } // UT_Permute
434 
435 // This method will reorder vals using the given permutation int array
436 // which must contain at least size elements. T[i] is moved to
437 // T[permute[i]] for all valid indices i. The permute array is modified by
438 // this method.
439 template <typename T, typename INT>
440 static inline void
441 UTpermuteInPlace(T *vals, INT *permute, INT size)
442 {
443  UT_Permute::permuteInPlaceR(vals, permute, INT(0), size);
444 }
445 
446 // Makes a temporary copy of permute before calling UTpermuteInPlace.
447 template <typename T, typename INT>
448 static inline void
449 UTpermute(T *vals, const INT *permute, INT size)
450 {
451  UT_StackBuffer<INT> tmp_permute(size);
452  memcpy(tmp_permute, permute, size*sizeof(INT));
453 
454  UT_Permute::permuteInPlaceR(vals, tmp_permute.array(), INT(0), size);
455 }
456 
457 // This method will reorder vals using the given permutation int array
458 // which must contain at least size elements. T[permute[i]] is moved to
459 // T[i] for all valid indices i.
460 template <typename T, typename INT>
461 static inline void
462 UTinversePermute(T *vals, const INT *permute, INT size)
463 {
464  UT_StackBuffer<INT> tmp_permute(size);
465  for (INT i = 0; i < size; i++)
466  tmp_permute[permute[i]] = i;
467 
468  UT_Permute::permuteInPlaceR(vals, tmp_permute.array(), INT(0), size);
469 }
470 
471 // This method will reorder vals using the given permutation int array
472 // which must contain at least nelements elements. T[permute[i]] is moved to
473 // T[i] for all valid indices i, where each array element is element_bytes
474 // in size.
475 template <typename INT>
476 static inline void
477 UTinversePermute(void *vals, size_t element_bytes, const INT *permute, INT nelements)
478 {
479  UT_StackBuffer<INT> tmp_permute(nelements);
480  for (INT i = 0; i < nelements; i++)
481  tmp_permute[permute[i]] = i;
482 
483  UT_Permute::permuteInPlaceR(UT_VariableSizePtr(vals, element_bytes), tmp_permute.array(), INT(0), nelements);
484 }
485 
486 template <typename INT>
487 static inline void
488 UTfillRandomPermutation(UT_MersenneTwister &twist, INT *permute, INT size)
489 {
490  for (int i = 0; i < size; i++)
491  permute[i] = i;
492 
493  for (int i = size; i-- > 1; )
494  {
495  int k = twist.urandom() % (i+1);
496  if (k != i)
497  std::swap(permute[k], permute[i]);
498  }
499 }
500 
501 #endif
bool operator()(INT rhs) const
Definition: UT_Permute.h:333
UT_VariableSizePtr operator+(const size_t i) const
Definition: UT_Permute.h:248
bool operator==(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:210
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
Definition: UT_Permute.h:77
UT_VariableSizeRef(void *p, size_t element_bytes)
Definition: UT_Permute.h:172
IT UTpartition(IT start, IT end, PRED isbeforesplit)
Definition: UT_Permute.h:35
bool operator!=(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:215
Partition(T *low, const INT *permute, INT mid)
Definition: UT_Permute.h:295
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:1699
UT_VariableSizeRef operator*() const
Definition: UT_Permute.h:266
const GLdouble * v
Definition: glcorearb.h:837
GLuint start
Definition: glcorearb.h:475
GA_API const UT_StringHolder twist
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
UT_VariableSizePtr & operator++()
Definition: UT_Permute.h:256
const size_t myElementBytes
Definition: UT_Permute.h:285
bool operator<=(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:225
uint64 value_type
Definition: GA_PrimCompat.h:29
bool operator>(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:230
UT_VariableSizeRef & operator=(const UT_VariableSizeRef &that)=delete
UT_VariableSizePtr & operator--()
Definition: UT_Permute.h:261
bool operator()(const T &rhs) const
Definition: UT_Permute.h:299
const size_t myElementBytes
Definition: UT_Permute.h:189
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
GLuint GLuint end
Definition: glcorearb.h:475
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
void * ptr() const
Definition: UT_Permute.h:179
void operator-=(const size_t i)
Definition: UT_Permute.h:244
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
GLsizeiptr size
Definition: glcorearb.h:664
size_t elementBytes() const
Definition: UT_Permute.h:183
PartitionUnknown(UT_VariableSizePtr low, const INT *permute, INT mid)
Definition: UT_Permute.h:313
bool operator()(const UT_VariableSizeRef &rhs) const
Definition: UT_Permute.h:318
UT_VariableSizePtr operator-(const size_t i) const
Definition: UT_Permute.h:252
GA_API const UT_StringHolder pivot
size_t elementBytes() const
Definition: UT_Permute.h:279
UT_VariableSizePtr(void *p, size_t element_bytes)
Definition: UT_Permute.h:205
bool operator<(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:220
UT_VariableSizeRef operator[](const size_t i) const
Definition: UT_Permute.h:270
void OIIO_UTIL_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
void operator+=(const size_t i)
Definition: UT_Permute.h:240
bool operator>=(const UT_VariableSizePtr &that) const
Definition: UT_Permute.h:235
void * ptr() const
Definition: UT_Permute.h:275