11 #ifndef __UT_Permute__
12 #define __UT_Permute__
34 template<
typename IT,
typename PRED>
43 while (isbeforesplit(*start))
56 }
while(!isbeforesplit(*end));
76 template<
typename IT,
typename COMPARE>
91 auto diff = (end-
start);
92 auto hdiff = (diff>>1);
93 const IT mid = (start+hdiff);
94 const IT
last = end-1;
99 if (isAbeforeB(*last, *start))
101 if (isAbeforeB(*mid, *start))
103 if (isAbeforeB(*last, *mid))
113 if (isAbeforeB(*mid, *start))
117 if (isAbeforeB(*last, *mid))
129 {
return isAbeforeB(v, pivot); }
140 {
return !isAbeforeB(pivot, v); }
146 else if (nth < split2)
156 if (isAbeforeB(*(end-1), *start))
157 UTswap(*start, *(end-1));
164 template<
typename IT>
198 memcpy(tmp.
array(), a.
ptr(), nbytes);
199 memcpy(a.
ptr(), b.
ptr(), nbytes);
200 memcpy(b.
ptr(), tmp.
array(), nbytes);
289 namespace UT_Permute {
291 template <
typename T,
typename INT>
301 return myPermute[&rhs-myLow] < myMid;
305 const INT *myPermute;
309 template <
typename INT>
320 return myPermute[(((
char*)rhs.
ptr())-((
char*)myLow.
ptr()))/myLow.
elementBytes()] < myMid;
324 const INT *myPermute;
328 template<
typename INT>
341 static const int theCrossover = 1024;
343 template <
typename T,
typename INT>
345 permuteInPlaceRHelper(T *vals, INT *permute, INT low, INT high)
347 INT
size = high - low;
349 for (INT i = low; i < high; i++)
350 tmp[permute[i] - low] = vals[i];
358 memcpy(reinterpret_cast<void *>(vals + low), tmp, size *
sizeof(T));
362 std::move(tmp, tmp + size, vals + low);
366 template <
typename INT>
368 permuteInPlaceRHelper(
void *vals,
size_t element_bytes, INT *permute, INT low, INT high)
372 for (INT i = low; i < high; i++)
374 memcpy(tmp.array() + element_bytes*(permute[i]-low), ((
const char *)vals) + element_bytes*i, element_bytes);
376 memcpy(((
char *)vals) + element_bytes*low, tmp.array(), size*element_bytes);
380 template <typename T, typename INT>
382 permuteInPlaceR(T *vals, INT *permute, INT low, INT high)
385 if (size < theCrossover)
387 permuteInPlaceRHelper(vals, permute, low, high);
391 INT mid = (low + high) / 2;
395 Partition<T,INT>(vals + low, permute + low, mid));
398 PartitionPermute<INT>(mid));
400 tbb::parallel_invoke(
401 [=]() { permuteInPlaceR(vals, permute, low, mid); },
402 [=]() { permuteInPlaceR(vals, permute, mid, high); }
407 template <
typename INT>
412 if (size < theCrossover)
414 permuteInPlaceRHelper(vals.
ptr(), vals.
elementBytes(), permute, low, high);
418 INT mid = (low + high) / 2;
422 PartitionUnknown<INT>(vals + low, permute + low, mid));
425 PartitionPermute<INT>(mid));
427 tbb::parallel_invoke(
428 [=]() { permuteInPlaceR(vals, permute, low, mid); },
429 [=]() { permuteInPlaceR(vals, permute, mid, high); }
439 template <
typename T,
typename INT>
441 UTpermuteInPlace(T *vals, INT *permute, INT size)
443 UT_Permute::permuteInPlaceR(vals, permute,
INT(0), size);
447 template <
typename T,
typename INT>
449 UTpermute(T *vals,
const INT *permute, INT size)
452 memcpy(tmp_permute, permute, size*
sizeof(INT));
454 UT_Permute::permuteInPlaceR(vals, tmp_permute.array(),
INT(0),
size);
460 template <
typename T,
typename INT>
462 UTinversePermute(T *vals,
const INT *permute, INT size)
465 for (INT i = 0; i <
size; i++)
466 tmp_permute[permute[i]] = i;
468 UT_Permute::permuteInPlaceR(vals, tmp_permute.array(),
INT(0),
size);
475 template <
typename INT>
477 UTinversePermute(
void *vals,
size_t element_bytes,
const INT *permute, INT nelements)
480 for (INT i = 0; i < nelements; i++)
481 tmp_permute[permute[i]] = i;
483 UT_Permute::permuteInPlaceR(
UT_VariableSizePtr(vals, element_bytes), tmp_permute.array(),
INT(0), nelements);
486 template <
typename INT>
490 for (
int i = 0; i <
size; i++)
493 for (
int i = size; i-- > 1; )
495 int k = twist.
urandom() % (i+1);
bool operator()(INT rhs) const
UT_VariableSizePtr operator+(const size_t i) const
bool operator==(const UT_VariableSizePtr &that) const
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
UT_VariableSizeRef(void *p, size_t element_bytes)
IT UTpartition(IT start, IT end, PRED isbeforesplit)
bool operator!=(const UT_VariableSizePtr &that) const
Partition(T *low, const INT *permute, INT mid)
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)
UT_VariableSizeRef operator*() const
GA_API const UT_StringHolder twist
PartitionPermute(INT mid)
GLboolean GLboolean GLboolean GLboolean a
UT_VariableSizePtr & operator++()
const size_t myElementBytes
bool operator<=(const UT_VariableSizePtr &that) const
bool operator>(const UT_VariableSizePtr &that) const
UT_VariableSizeRef & operator=(const UT_VariableSizeRef &that)=delete
UT_VariableSizePtr & operator--()
bool operator()(const T &rhs) const
const size_t myElementBytes
GLboolean GLboolean GLboolean b
void operator-=(const size_t i)
__hostdev__ uint64_t last(uint32_t i) const
size_t elementBytes() const
PartitionUnknown(UT_VariableSizePtr low, const INT *permute, INT mid)
bool operator()(const UT_VariableSizeRef &rhs) const
UT_VariableSizePtr operator-(const size_t i) const
GA_API const UT_StringHolder pivot
size_t elementBytes() const
UT_VariableSizePtr(void *p, size_t element_bytes)
bool operator<(const UT_VariableSizePtr &that) const
UT_VariableSizeRef operator[](const size_t i) const
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)
bool operator>=(const UT_VariableSizePtr &that) const