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_Swap.h"
16 #include "UT_MTwister.h"
17 #include "UT_StackBuffer.h"
18 
19 #include <tbb/parallel_invoke.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 
168 namespace UT_Permute {
169 
170 template <typename T, typename INT>
171 class Partition {
172 public:
173  Partition(T *low, const INT *permute, INT mid)
174  : myLow(low)
175  , myPermute(permute)
176  , myMid(mid) {}
177  bool operator()(const T &rhs) const
178  {
179  return myPermute[&rhs-myLow] < myMid;
180  }
181 private:
182  T *myLow;
183  const INT *myPermute;
184  INT myMid;
185 };
186 
187 template<typename INT>
189 public:
190  PartitionPermute(INT mid) : myMid(mid) {}
191  bool operator()(INT rhs) const
192  {
193  return rhs < myMid;
194  }
195 private:
196  INT myMid;
197 };
198 
199 static const int theCrossover = 1024;
200 
201 template <typename T, typename INT>
202 static void
203 permuteInPlaceRHelper(T *vals, INT *permute, INT low, INT high)
204 {
205  INT size = high-low;
206  T tmp[theCrossover];
207  for (INT i = low; i < high; i++)
208  tmp[permute[i]-low] = vals[i];
209  memcpy(vals + low, tmp, size*sizeof(T));
210 }
211 
212 // Permute by parallel recursive partitioning
213 template <typename T, typename INT>
214 static void
215 permuteInPlaceR(T *vals, INT *permute, INT low, INT high)
216 {
217  INT size = high-low;
218  if (size < theCrossover)
219  {
220  permuteInPlaceRHelper(vals, permute, low, high);
221  return;
222  }
223 
224  INT mid = (low + high) / 2;
225 
226  UTpartition(vals + low,
227  vals + high,
228  Partition<T,INT>(vals + low, permute + low, mid));
229  UTpartition(permute + low,
230  permute + high,
231  PartitionPermute<INT>(mid));
232 
233  tbb::parallel_invoke(
234  [=]() { permuteInPlaceR(vals, permute, low, mid); },
235  [=]() { permuteInPlaceR(vals, permute, mid, high); }
236  );
237 }
238 
239 } // UT_Permute
240 
241 // This method will reorder vals using the given permutation int array
242 // which must contain at least size elements. T[i] is moved to
243 // T[permute[i]] for all valid indices i. The permute array is modified by
244 // this method.
245 template <typename T, typename INT>
246 static inline void
247 UTpermuteInPlace(T *vals, INT *permute, INT size)
248 {
249  UT_Permute::permuteInPlaceR(vals, permute, INT(0), size);
250 }
251 
252 // Makes a temporary copy of permute before calling UTpermuteInPlace.
253 template <typename T, typename INT>
254 static inline void
255 UTpermute(T *vals, const INT *permute, INT size)
256 {
257  UT_StackBuffer<INT> tmp_permute(size);
258  memcpy(tmp_permute, permute, size*sizeof(INT));
259 
260  UT_Permute::permuteInPlaceR(vals, tmp_permute.array(), INT(0), size);
261 }
262 
263 // This method will reorder vals using the given permutation int array
264 // which must contain at least size elements. T[permute[i]] is moved to
265 // T[i] for all valid indices i.
266 template <typename T, typename INT>
267 static inline void
268 UTinversePermute(T *vals, const INT *permute, INT size)
269 {
270  UT_StackBuffer<INT> tmp_permute(size);
271  for (INT i = 0; i < size; i++)
272  tmp_permute[permute[i]] = i;
273 
274  UT_Permute::permuteInPlaceR(vals, tmp_permute.array(), INT(0), size);
275 }
276 
277 template <typename INT>
278 static inline void
279 UTfillRandomPermutation(UT_MersenneTwister &twist, INT *permute, INT size)
280 {
281  for (int i = 0; i < size; i++)
282  permute[i] = i;
283 
284  for (int i = size; i-- > 1; )
285  {
286  int k = twist.urandom() % (i+1);
287  if (k != i)
288  std::swap(permute[k], permute[i]);
289  }
290 }
291 
292 #endif
bool operator()(INT rhs) const
Definition: UT_Permute.h:191
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
Definition: UT_Permute.h:75
IT UTpartition(IT start, IT end, PRED isbeforesplit)
Definition: UT_Permute.h:33
void UTswap(T &a, T &b)
Definition: UT_Swap.h:35
Partition(T *low, const INT *permute, INT mid)
Definition: UT_Permute.h:173
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:1519
const GLdouble * v
Definition: glcorearb.h:836
GLuint start
Definition: glcorearb.h:474
GA_API const UT_StringHolder twist
png_uint_32 i
Definition: png.h:2877
uint64 value_type
Definition: GA_PrimCompat.h:29
GLsizeiptr size
Definition: glcorearb.h:663
bool operator()(const T &rhs) const
Definition: UT_Permute.h:177
GLuint GLuint end
Definition: glcorearb.h:474
GA_API const UT_StringHolder pivot