15 #ifndef __UT_ARRAYIMPL_H_INCLUDED__
16 #define __UT_ARRAYIMPL_H_INCLUDED__
38 : myCapacity(a.
size()), mySize(a.
size())
42 myData = allocateCapacity(myCapacity);
53 : myCapacity(init.
size()), mySize(init.
size())
57 myData = allocateCapacity(myCapacity);
69 if (!
a.isHeapBuffer())
74 operator=(std::move(
a));
78 myCapacity =
a.myCapacity;
81 a.myCapacity =
a.mySize = 0;
98 constexpr
auto elem_size =
sizeof(
T);
100 T *
data = (
T *)malloc(capacity * elem_size);
102 if (!isHeapBuffer(data))
105 data = (
T *)malloc(capacity * elem_size);
111 template <
typename T>
115 UTswap( myData, other.myData );
116 UTswap( myCapacity, other.myCapacity );
117 UTswap( mySize, other.mySize );
121 template <
typename T>
127 bumpCapacity(index + 1);
129 trivialConstructRange(myData + mySize, index - mySize + 1);
134 bumpCapacity(mySize + 1);
137 ::memmove((
void *)&myData[index+1], (
void *)&myData[index],
138 ((mySize-index)*
sizeof(
T)));
140 trivialConstruct(myData[index]);
146 template <
typename T>
147 template <
typename S>
151 if (mySize == myCapacity)
156 setCapacity(UTbumpAlloc(myCapacity));
158 construct(myData[mySize], std::forward<S>(myData[idx]));
160 construct(myData[mySize], std::forward<S>(
s));
164 construct(myData[mySize], std::forward<S>(
s));
169 template <
typename T>
170 template <
typename...
S>
174 #if UT_ASSERT_LEVEL >= UT_ASSERT_LEVEL_PARANOID
175 validateEmplaceArgs(std::forward<S>(
s)...);
178 if (mySize == myCapacity)
179 setCapacity(UTbumpAlloc(myCapacity));
181 construct(myData[mySize], std::forward<S>(
s)...);
185 template <
typename T>
189 bumpCapacity(mySize + count);
190 copyConstructRange(myData + mySize, pt, count);
194 template <
typename T>
201 if (mySize + count >= myCapacity)
203 exint tidx = safeIndex(t);
205 bumpCapacity(mySize + count);
208 copyConstruct(myData[mySize+i], tidx >= 0 ? myData[tidx] : t);
213 copyConstruct(myData[mySize+i], t);
218 template <
typename T>
222 exint low, mid, high;
228 mid = (low + high) / 2;
229 if (
compare(&t, &myData[mid]) < 0)
231 else if (
compare(&t, &myData[mid]) > 0)
243 template <
typename T>
244 template <
typename ComparatorBool>
248 exint low, mid, high;
254 mid = (low + high) / 2;
255 if (t == myData[mid])
260 else if (is_less(t, myData[mid]))
269 template <
typename T>
273 exint low, mid, high;
279 mid = (low + high) / 2;
280 if (
compare(&t, &myData[mid]) < 0)
282 else if (
compare(&t, &myData[mid]) > 0)
291 template <
typename T>
292 template <
typename ComparatorBool>
296 exint low, mid, high;
302 mid = (low + high) / 2;
303 if (t == myData[mid])
305 else if (is_less(t, myData[mid]))
314 template <
typename T>
315 template <
typename ComparatorBool>
325 if (is_less(myData[idx + h], item))
334 return (idx !=
size() && !is_less(item, myData[idx])) ? idx : -1;
337 template <
typename T>
347 if (
compare(&myData[idx + h], &item) < 0)
356 return (idx !=
size() &&
compare(&myData[idx], &item) == 0) ? idx : -1;
359 template <
typename T>
367 while( i > 0 &&
compare(&myData[(i - 1) / 2], &t) < 0 )
369 myData[i] = myData[(i - 1) / 2];
376 template <
typename T>
384 myData[0] = myData[mySize - 1];
385 removeAt(mySize - 1);
393 exint cidx = 2 * idx + 1;
394 if( cidx < mySize &&
compare(&myData[largest], &myData[cidx]) < 0 )
398 if( cidx < mySize &&
compare(&myData[largest], &myData[cidx]) < 0 )
406 UTswap(myData[idx], myData[largest]);
413 template <
typename T>
417 bumpCapacity(mySize + a.mySize);
418 copyConstructRange(myData + mySize, a.myData, a.mySize);
424 template <
typename T>
429 bumpCapacity(mySize + n);
431 for (
exint i = 0; i <
n; i++)
432 construct(myData[mySize + i], std::forward<T>(src[i]));
440 template <
typename T>
446 if (beg_index >= mySize)
448 bumpCapacity(end_index);
450 trivialConstructRange(myData + mySize, end_index - mySize);
455 bumpCapacity(mySize+count);
457 ::memmove((
void *)&myData[end_index], (
void *)&myData[beg_index],
458 ((mySize-beg_index)*
sizeof(
T)));
461 trivialConstructRange(myData + beg_index, count);
466 template <
typename T>
467 template <
typename S>
475 (
void) appendImpl(std::forward<S>(
s));
477 else if (index > mySize)
479 exint src_i = safeIndex(
s);
481 bumpCapacity(index + 1);
483 trivialConstructRange(myData + mySize, index - mySize);
486 construct(myData[index], std::forward<S>(myData[src_i]));
488 construct(myData[index], std::forward<S>(
s));
494 exint src_i = safeIndex(
s);
496 bumpCapacity(mySize + 1);
498 ::memmove((
void *)&myData[index+1], (
void *)&myData[index],
499 ((mySize-index)*
sizeof(
T)));
505 construct(myData[index], std::forward<S>(myData[src_i]));
507 construct(myData[index], std::forward<S>(
s));
515 template <
typename T>
520 return (idx < 0) ? -1 : removeAt((
exint)idx);
523 template <
typename T>
527 trivialDestruct(myData[idx]);
530 ::memmove((
void *)&myData[idx], (
void *)&myData[idx+1],
531 ((mySize-idx)*
sizeof(T)));
537 template <
typename T>
545 trivialDestructRange(myData + begin_i, end_i - begin_i);
546 ::memmove((
void *)&myData[begin_i], (
void *)&myData[end_i],
547 (mySize - end_i)*
sizeof(
T));
549 setSize(mySize - (end_i - begin_i));
552 template <
typename T>
561 exint nelements = end_i - begin_i;
566 ::memmove((
void*)dest.myData, (
void*)&myData[begin_i],
567 nelements *
sizeof(
T));
568 dest.mySize = nelements;
575 ::memmove((
void*)&myData[begin_i], (
void*)&myData[end_i],
576 (mySize - end_i) *
sizeof(
T));
578 setSize(mySize - nelements);
582 template <
typename T>
593 if (src_idx + how_many >
size())
594 how_many =
size() - src_idx;
597 if (dst_idx + how_many >
size())
598 dst_idx =
size() - how_many;
599 if (src_idx != dst_idx && how_many > 0)
601 constexpr
auto elem_size =
sizeof(
T);
605 savelen =
SYSabs(src_idx - dst_idx);
606 tmp = (
void **)::malloc(savelen*elem_size);
607 if (src_idx > dst_idx && how_many > 0)
613 ::memcpy(tmp, &myData[dst_idx], savelen*elem_size);
614 ::memmove(&myData[dst_idx], &myData[src_idx], how_many*elem_size);
615 ::memcpy(&myData[dst_idx+how_many], tmp, savelen*elem_size);
617 if (src_idx < dst_idx && how_many > 0)
624 ::memcpy(tmp, &myData[src_idx+how_many], savelen*elem_size);
625 ::memmove(&myData[dst_idx], &myData[src_idx], how_many*elem_size);
626 ::memcpy(&myData[src_idx], tmp, savelen*elem_size);
632 template <
typename T>
633 template <
typename IsEqual>
639 for (dst = 0; dst < mySize; dst++)
641 if (is_equal(myData[dst]))
645 for (
exint idx = dst+1; idx < mySize; idx++)
647 if (!is_equal(myData[idx]))
650 myData[
dst] = std::move(myData[idx]);
659 trivialDestructRange(myData + dst, mySize - dst);
665 template <
typename T>
673 if (how_many == 0 || mySize < 1)
676 constexpr
auto elem_size =
sizeof(
T);
678 numShift = how_many % (
exint)mySize;
679 if (numShift < 0) numShift += mySize;
680 remaining = mySize - numShift;
681 tempPtr =
new char[numShift*elem_size];
683 ::memmove(tempPtr, (
void *)&myData[remaining], (numShift * elem_size));
684 ::memmove((
void *)&myData[numShift], (
void *)&myData[0],
685 (remaining * elem_size));
686 ::memmove((
void *)&myData[0], tempPtr, (numShift * elem_size));
691 template <
typename T>
695 for (
exint i = 0; i < mySize; i++)
706 template <
typename T>
711 ::memset((
void *)myData, 0, mySize*
sizeof(
T));
713 trivialConstructRange(myData, mySize);
716 template <
typename T>
720 const T *
end = myData + mySize;
721 for (
const T *
p = myData + s;
p <
end; ++
p)
727 template <
typename T>
733 if( mySize == 0 )
return -1;
736 found = (
T *)::bsearch(&t, myData, mySize,
sizeof(
T),
738 return found ? (found - myData) : -1;
741 template <
typename T>
746 for (
exint i = 0; i <
n; i++ )
747 UTswap(myData[i], myData[mySize-1-i]);
750 template <
typename T>
757 template <
typename T>
758 template <
typename ComparatorBool>
775 template <
typename T>
780 if (capacity == myCapacity)
783 constexpr
auto elem_size =
sizeof(
T);
788 if (capacity < mySize)
791 trivialDestructRange(myData + capacity, mySize - capacity);
794 else if (capacity > myCapacity)
797 myData = (
T *)malloc(elem_size * capacity);
801 memcpy((
void *)myData, (
void *)prev, elem_size * mySize);
802 myCapacity = capacity;
807 UT_ASSERT_P(capacity >= mySize && capacity <= myCapacity);
816 trivialDestructRange(myData, mySize);
825 if (capacity < mySize)
827 trivialDestructRange(myData + capacity, mySize - capacity);
832 myData = (
T *)realloc(myData, elem_size * capacity);
834 myData = (
T *)malloc(elem_size * capacity);
840 myData = (
T *)malloc(elem_size * capacity);
842 memcpy((
void *)myData, (
void *)prev, elem_size * mySize);
846 myCapacity = capacity;
850 template <
typename T>
858 setCapacityIfNeeded(a.
size());
862 trivialDestructRange(myData, mySize);
863 copyConstructRange(myData, a.myData, a.
size());
870 template <
typename T>
874 const exint new_size = a.size();
877 setCapacityIfNeeded(new_size);
881 trivialDestructRange(myData, mySize);
883 copyConstructRange(myData, a.begin(), new_size);
890 template <
typename T>
894 if (!
a.isHeapBuffer())
899 setCapacityIfNeeded(n);
903 memcpy((
void*)myData, (
void*)
a.myData, n *
sizeof(
T));
907 for (
exint i = 0; i <
n; ++i)
908 new (&myData[i])
T(std::move(
a.myData[i]));
919 trivialDestructRange(myData, mySize);
926 myCapacity =
a.myCapacity;
929 a.myCapacity =
a.mySize = 0;
936 template <
typename T>
940 if (
this == &a)
return true;
941 if (mySize != a.
size())
return false;
942 for (
exint i = 0; i < mySize; i++)
943 if (!(myData[i] ==
a(i)))
return false;
947 template <
typename T>
951 return (!
operator==(a));
954 template <
typename T>
958 if (
this == &a)
return 1;
959 if (mySize != a.
size())
return 0;
960 for (
exint i = 0; i < mySize; i++)
963 if (
compare(&myData[i], &v2))
return 0;
968 template <
typename T>
973 for (i = 0; i < mySize; i++)
975 if (apply_func(myData[i], d))
987 template <
typename T>
988 template <
typename ComparatorBool>
992 ComparatorBool is_less)
999 if (other.
size() == 0)
1007 UT_ASSERT( direction == -1 || direction == +1 );
1008 direction = (direction > 0) ? +1 : -1;
1012 while( our_idx <
size() && other_idx < other.
size() )
1014 const T &our_item = (*this)(our_idx);
1015 const T &other_item = other(other_idx);
1018 if (our_item == other_item)
1020 else if (is_less(our_item, other_item))
1029 item_dir = ( (item_dir > 0) ? +1 : -1 ) *
direction;
1034 result.
append( our_item );
1037 else if( item_dir > 0 )
1039 result.
append( other_item );
1044 result.
append( our_item );
1047 result.
append( other_item );
1053 for( ; our_idx <
size(); our_idx++ )
1054 result.
append( (*
this)(our_idx) );
1055 for( ; other_idx < other.
size(); other_idx++ )
1056 result.
append( other(other_idx) );
1062 template <
typename T>
1068 return std::includes(
1069 myData, myData + mySize,
1070 other.myData, other.myData + other.mySize,
1074 template <
typename T>
1079 sortedUnion( other, temp, compare );
1083 template <
typename T>
1089 T *last1 = myData + mySize;
1090 T *first2 = other.myData;
1091 T *last2 = other.myData + other.mySize;
1094 UT_ASSERT(&result !=
this && &result != &other);
1097 while( first1 != last1 && first2 != last2 )
1099 if(
compare(first1, first2) < 0 )
1101 result.
append( *first1 );
1104 else if(
compare(first2, first1) < 0 )
1106 result.
append( *first2 );
1111 result.
append( *first1 );
1116 while( first1 != last1 )
1118 result.
append( *first1 );
1121 while( first2 != last2 )
1123 result.
append( *first2 );
1128 template <
typename T>
1133 sortedIntersection( other, temp, compare );
1137 template <
typename T>
1143 T *last1 = myData + mySize;
1144 T *first2 = other.myData;
1145 T *last2 = other.myData + other.mySize;
1147 while (first1 != last1 && first2 != last2)
1148 if(
compare(first1, first2) < 0 )
1150 else if(
compare(first2, first1) < 0 )
1153 result.
append( *first1 );
1159 template <
typename T>
1164 sortedSetDifference(other, temp, compare);
1168 template <
typename T>
1175 T *last1 = myData + mySize;
1176 T *first2 = other.myData;
1177 T *last2 = other.myData + other.mySize;
1179 while (first1 != last1 && first2 != last2)
1181 if(
compare(first1, first2) < 0 )
1183 result.
append( *first1 );
1186 else if(
compare(first2, first1) < 0 )
1194 while( first1 != last1 )
1196 result.
append( *first1 );
1201 template <
typename T>
1202 template <
typename CompareEqual>
1213 for (
exint i = 1; i <
n; i++)
1215 if (!compare_equal((*
this)(i), (*
this)(i-1)))
1218 (*this)(
dst) = (*
this)(i);
1229 template<
typename T>
1230 struct srdCompareEqual
1232 bool operator()(
const T&
x,
const T&
y)
const {
return (x == y); }
1236 template <
typename T>
1240 srdCompareEqual<T>
cmp;
1241 return sortedRemoveDuplicatesIf(cmp);
1244 template <
typename T>
1245 template <
typename BinaryOp>
1250 for (
exint i = 0; i < mySize; i++)
1251 sum =
add(sum, myData[i]);
1255 #endif // __UT_ARRAYIMPL_H_INCLUDED__
void swap(ArAssetInfo &lhs, ArAssetInfo &rhs)
int isEqual(const UT_Array< T > &a, Comparator compare) const
int(* ut_ptr_compare_func_t)(const void *, const void *)
exint find(const T &t, exint s=0) const
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
bool operator!=(const UT_Array< T > &a) const
exint insertImpl(S &&s, exint index)
Similar to appendImpl() but for insertion.
static void copyConstructRange(T *dst, const T *src, exint n)
exint uniqueSortedFind(const T &item, Comparator compare) const
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less)
UT_Array< T > & operator=(const UT_Array< T > &a)
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
GLuint const GLfloat * val
void extractRange(exint begin_i, exint end_i, UT_Array< T > &dest)
GLboolean GLboolean GLboolean GLboolean a
void zero()
Zeros the array if a POD type, else trivial constructs if a class type.
void move(exint src_idx, exint dst_idx, exint how_many)
void cycle(exint how_many)
Cyclically shifts the entire array by how_many.
exint concat(const UT_Array< T > &a)
Takes another T array and concatenate it onto my end.
exint uniqueSortedInsert(const T &t, Comparator compare)
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, ROI roi={}, int nthreads=0)
GLfloat GLfloat GLfloat v2
void setCapacity(exint newcapacity)
exint apply(int(*apply_func)(T &t, void *d), void *d)
exint emplace_back(S &&...s)
GLint GLint GLint GLint GLint x
GLint GLint GLint GLint GLint GLint y
GLint GLenum GLsizei GLint GLsizei const void * data
T accumulate(const T &init_value, BinaryOp add) const
UT_Vector3T< T > SYSclamp(const UT_Vector3T< T > &v, const UT_Vector3T< T > &min, const UT_Vector3T< T > &max)
exint sortedInsert(const T &t, Comparator compare)
void appendMultiple(const T &t, exint count)
GLfloat GLfloat GLfloat GLfloat h
exint removeIf(IsEqual is_equal)
exint sortedRemoveDuplicates()
exint sortedRemoveDuplicatesIf(CompareEqual compare_equal)
UT_API void ut_ArrayImplFree(void *p)
bool hasSortedSubset(const UT_Array< T > &other, Comparator compare) const
void sortedSetDifference(const UT_Array< T > &other, Comparator compare)
void sortedUnion(const UT_Array< T > &other, Comparator compare)
T selectNthLargest(exint idx, ComparatorBool is_less)
UT_Compare::Less< T > UTcompareLess(UT_Compare::Ternary< T > compare)
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
GLuint GLuint GLsizei count
void sort(Comparator compare)
void constant(const T &v)
Quickly set the array to a single value.
void setCapacityIfNeeded(exint mincapacity)
void sortedIntersection(const UT_Array< T > &other, Comparator compare)
ImageBuf OIIO_API add(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
UT_Array(const UT_Array< T > &a)
T heapPop(Comparator compare)
exint heapPush(const T &t, Comparator compare)
GLsizei const GLfloat * value
void reverse()
Reverses the array by swapping elements in mirrored locations.
exint multipleInsert(exint index, exint count)
Insert an element "count" times at the given index. Return the index.
void removeRange(exint begin_i, exint end_i)
Remove the range [begin_i,end_i) of elements from the array.
void swap(UT_Array< T > &other)
exint insert(exint index)
exint findAndRemove(const T &t)
bool operator==(const UT_Array< T > &a) const
exint sortedFind(const T &t, Comparator compare) const