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