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