HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_ArrayImpl.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: Utility Library (C++)
7  *
8  * COMMENTS:
9  * This is meant to be included by UT_Array.h and includes
10  * the template implementations needed by external code.
11  */
12 
13 #pragma once
14 
15 #ifndef __UT_ARRAYIMPL_H_INCLUDED__
16 #define __UT_ARRAYIMPL_H_INCLUDED__
17 
18 #include "UT_ArrayHelp.h"
19 #include "UT_Assert.h"
20 #include "UT_Compare.h"
21 #include "UT_Swap.h"
22 #include <VM/VM_Math.h>
23 #include <SYS/SYS_Math.h>
24 
25 #include <algorithm>
26 #include <utility>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 
31 
32 // Implemented in UT_Array.C
33 UT_API void ut_ArrayImplFree(void *p);
34 
35 
36 template <typename T>
37 inline
39  : myCapacity(a.size()), mySize(a.size())
40 {
41  if (myCapacity)
42  {
43  myData = allocateCapacity(myCapacity);
44  copyConstructRange(myData, a.array(), mySize);
45  }
46  else
47  {
48  myData = nullptr;
49  }
50 }
51 
52 template <typename T>
53 inline
54 UT_Array<T>::UT_Array(std::initializer_list<T> init)
55  : myCapacity(init.size()), mySize(init.size())
56 {
57  if (myCapacity)
58  {
59  myData = allocateCapacity(myCapacity);
60  copyConstructRange(myData, init.begin(), mySize);
61  }
62  else
63  {
64  myData = nullptr;
65  }
66 }
67 
68 template <typename T>
69 inline
71 {
72  if (!a.isHeapBuffer())
73  {
74  myData = nullptr;
75  myCapacity = 0;
76  mySize = 0;
77  operator=(std::move(a));
78  return;
79  }
80 
81  myCapacity = a.myCapacity;
82  mySize = a.mySize;
83  myData = a.myData;
84  a.myCapacity = a.mySize = 0;
85  a.myData = nullptr;
86 }
87 
88 
89 template <typename T>
90 inline
92 {
93  // NOTE: We call setCapacity to ensure that we call trivialDestructRange,
94  // then call free on myData.
95  setCapacity(0);
96 }
97 
100 template <typename T>
101 inline T *
102 UT_Array<T>::allocateCapacity(exint capacity)
103 {
104  constexpr auto elem_size = sizeof(T); // NOLINT
105 
106  T *data = (T *)malloc(capacity * elem_size);
107  // Avoid degenerate case if we happen to be aliased the wrong way
108  if (!isHeapBuffer(data))
109  {
110  T *prev = data;
111  data = (T *)malloc(capacity * elem_size);
112  ut_ArrayImplFree(prev);
113  }
114  return data;
115 }
117 
118 template <typename T>
119 inline void
120 UT_Array<T>::swap( UT_Array<T> &other )
121 {
122  UTswap( myData, other.myData );
123  UTswap( myCapacity, other.myCapacity );
124  UTswap( mySize, other.mySize );
125 }
126 
127 
128 template <typename T>
129 inline exint
131 {
132  if (index >= mySize)
133  {
134  bumpCapacity(index + 1);
135 
136  trivialConstructRange(myData + mySize, index - mySize + 1);
137 
138  mySize = index+1;
139  return index;
140  }
141  bumpCapacity(mySize + 1);
142 
143  UT_ASSERT_P(index >= 0);
144  ::memmove((void *)&myData[index+1], (void *)&myData[index],
145  ((mySize-index)*sizeof(T))); // NOLINT
146 
147  trivialConstruct(myData[index]);
148 
149  mySize++;
150  return index;
151 }
152 
153 template <typename T>
154 template <typename S>
155 inline exint
157 {
158  if (mySize == myCapacity)
159  {
160  exint idx = safeIndex(s);
161 
162  // NOTE: UTbumpAlloc always returns a strictly larger value.
163  setCapacity(UTbumpAlloc(myCapacity));
164  if (idx >= 0)
165  construct(myData[mySize], std::forward<S>(myData[idx]));
166  else
167  construct(myData[mySize], std::forward<S>(s));
168  }
169  else
170  {
171  construct(myData[mySize], std::forward<S>(s));
172  }
173  return mySize++;
174 }
175 
176 template <typename T>
177 template <typename... S>
178 inline exint
180 {
181 #if UT_ASSERT_LEVEL >= UT_ASSERT_LEVEL_PARANOID
182  validateEmplaceArgs(std::forward<S>(s)...);
183 #endif
184 
185  if (mySize == myCapacity)
186  setCapacity(UTbumpAlloc(myCapacity));
187 
188  construct(myData[mySize], std::forward<S>(s)...);
189  return mySize++;
190 }
191 
192 template <typename T>
193 inline void
195 {
196  bumpCapacity(mySize + count);
197  copyConstructRange(myData + mySize, pt, count);
198  mySize += count;
199 }
200 
201 template <typename T>
202 inline void
204 {
205  UT_ASSERT_P(count >= 0);
206  if (count <= 0)
207  return;
208  if (mySize + count >= myCapacity)
209  {
210  exint tidx = safeIndex(t);
211 
212  bumpCapacity(mySize + count);
213 
214  for (exint i = 0; i < count; i++)
215  copyConstruct(myData[mySize+i], tidx >= 0 ? myData[tidx] : t);
216  }
217  else
218  {
219  for (exint i = 0; i < count; i++)
220  copyConstruct(myData[mySize+i], t);
221  }
222  mySize += count;
223 }
224 
225 template <typename T>
226 inline exint
227 UT_Array<T>::sortedInsert(const T &t, Comparator compare)
228 {
229  exint low, mid, high;
230 
231  low = 0;
232  high = size() - 1;
233  while (low <= high)
234  {
235  mid = (low + high) / 2;
236  if (compare(&t, &myData[mid]) < 0)
237  high = mid - 1;
238  else if (compare(&t, &myData[mid]) > 0)
239  low = mid + 1;
240  else
241  {
242  insertAt(t, mid);
243  return mid;
244  }
245  }
246  insertAt(t, low);
247  return low;
248 }
249 
250 template <typename T>
251 template <typename ComparatorBool>
252 inline exint
253 UT_Array<T>::sortedInsert(const T &t, ComparatorBool is_less)
254 {
255  exint low, mid, high;
256 
257  low = 0;
258  high = size() - 1;
259  while (low <= high)
260  {
261  mid = (low + high) / 2;
262  if (t == myData[mid])
263  {
264  insertAt(t, mid);
265  return mid;
266  }
267  else if (is_less(t, myData[mid]))
268  high = mid - 1;
269  else
270  low = mid + 1;
271  }
272  insertAt(t, low);
273  return low;
274 }
275 
276 template <typename T>
277 template <typename S>
278 inline exint
280 {
281  exint low, mid, high;
282 
283  low = 0;
284  high = size() - 1;
285  while (low <= high)
286  {
287  mid = (low + high) / 2;
288  if (compare(&s, &myData[mid]) < 0)
289  high = mid - 1;
290  else if (compare(&s, &myData[mid]) > 0)
291  low = mid + 1;
292  else
293  return (exint)mid;
294  }
295  insertImpl(std::forward<S>(s), low);
296  return low;
297 }
298 
299 template <typename T>
300 template <typename ComparatorBool>
301 inline exint
302 UT_Array<T>::uniqueSortedInsert(const T &t, ComparatorBool is_less)
303 {
304  exint low, mid, high;
305 
306  low = 0;
307  high = size() - 1;
308  while (low <= high)
309  {
310  mid = (low + high) / 2;
311  if (t == myData[mid])
312  return (exint)mid;
313  else if (is_less(t, myData[mid]))
314  high = mid - 1;
315  else
316  low = mid + 1;
317  }
318  insertAt(t, low);
319  return low;
320 }
321 
322 template <typename T>
323 template <typename ComparatorBool>
324 inline exint
325 UT_Array<T>::uniqueSortedFind(const T &item, ComparatorBool is_less) const
326 {
327  exint len = size();
328  exint idx = 0;
329 
330  while(len > 0)
331  {
332  exint h = len / 2;
333  if (is_less(myData[idx + h], item))
334  {
335  idx += h + 1;
336  len -= h + 1;
337  }
338  else
339  len = h;
340  }
341 
342  return (idx != size() && !is_less(item, myData[idx])) ? idx : -1;
343 }
344 
345 template <typename T>
346 inline exint
347 UT_Array<T>::uniqueSortedFind(const T &item, Comparator compare) const
348 {
349  exint len = size();
350  exint idx = 0;
351 
352  while(len > 0)
353  {
354  exint h = len / 2;
355  if (compare(&myData[idx + h], &item) < 0)
356  {
357  idx += h + 1;
358  len -= h + 1;
359  }
360  else
361  len = h;
362  }
363 
364  return (idx != size() && compare(&myData[idx], &item) == 0) ? idx : -1;
365 }
366 
367 template <typename T>
368 inline exint
369 UT_Array<T>::heapPush(const T &t, Comparator compare)
370 {
371  UT_ASSERT(safeIndex(t) < 0);
372  exint i = append(t);
373 
374  // walk up towards the root restoring the heap condition
375  while( i > 0 && compare(&myData[(i - 1) / 2], &t) < 0 )
376  {
377  myData[i] = myData[(i - 1) / 2];
378  i = (i - 1) / 2;
379  }
380  myData[i] = t;
381  return i;
382 }
383 
384 template <typename T>
385 inline T
387 {
388  UT_ASSERT_P(mySize > 0);
389 
390  T result = myData[0];
391  // move last item into the newly created hole
392  myData[0] = myData[mySize - 1];
393  removeAt(mySize - 1);
394  // percolate down until the heap condition is restored
395  exint idx = 0;
396  for(;;)
397  {
398  exint largest = idx;
399 
400  // test heap condition with left child
401  exint cidx = 2 * idx + 1;
402  if( cidx < mySize && compare(&myData[largest], &myData[cidx]) < 0 )
403  largest = cidx;
404  // test heap condition with right child
405  ++cidx;
406  if( cidx < mySize && compare(&myData[largest], &myData[cidx]) < 0 )
407  largest = cidx;
408  if( largest == idx )
409  {
410  // heap condition has been restored
411  break;
412  }
413 
414  UTswap(myData[idx], myData[largest]);
415  idx = largest;
416  }
417 
418  return result;
419 }
420 
421 template <typename T>
422 inline exint
424 {
425  bumpCapacity(mySize + a.mySize);
426  copyConstructRange(myData + mySize, a.myData, a.mySize);
427  mySize += a.mySize;
428 
429  return mySize;
430 }
431 
432 template <typename T>
433 inline exint
435 {
436  const exint n = a.mySize;
437  bumpCapacity(mySize + n);
438  T *src = a.myData;
439  for (exint i = 0; i < n; i++)
440  construct(myData[mySize + i], std::forward<T>(src[i]));
441 
442  mySize += a.mySize;
443  a.clear();
444 
445  return mySize;
446 }
447 
448 template <typename T>
449 inline exint
451 {
452  exint end_index = beg_index + count;
453 
454  if (beg_index >= mySize)
455  {
456  bumpCapacity(end_index);
457 
458  trivialConstructRange(myData + mySize, end_index - mySize);
459 
460  mySize = end_index;
461  return beg_index;
462  }
463  bumpCapacity(mySize+count);
464 
465  ::memmove((void *)&myData[end_index], (void *)&myData[beg_index],
466  ((mySize-beg_index)*sizeof(T))); // NOLINT
467  mySize += count;
468 
469  trivialConstructRange(myData + beg_index, count);
470 
471  return beg_index;
472 }
473 
474 template <typename T>
475 template <typename S>
476 inline exint
478 {
479  if (index == mySize)
480  {
481  // This case avoids an extraneous call to trivialConstructRange()
482  // which the compiler may not optimize out.
483  (void) appendImpl(std::forward<S>(s));
484  }
485  else if (index > mySize)
486  {
487  exint src_i = safeIndex(s);
488 
489  bumpCapacity(index + 1);
490 
491  trivialConstructRange(myData + mySize, index - mySize);
492 
493  if (src_i >= 0)
494  construct(myData[index], std::forward<S>(myData[src_i]));
495  else
496  construct(myData[index], std::forward<S>(s));
497 
498  mySize = index + 1;
499  }
500  else // (index < mySize)
501  {
502  exint src_i = safeIndex(s);
503 
504  bumpCapacity(mySize + 1);
505 
506  ::memmove((void *)&myData[index+1], (void *)&myData[index],
507  ((mySize-index)*sizeof(T))); // NOLINT
508 
509  if (src_i >= index)
510  ++src_i;
511 
512  if (src_i >= 0)
513  construct(myData[index], std::forward<S>(myData[src_i]));
514  else
515  construct(myData[index], std::forward<S>(s));
516 
517  ++mySize;
518  }
519 
520  return index;
521 }
522 
523 template <typename T>
524 inline exint
526 {
527  exint idx = find(t);
528  return (idx < 0) ? -1 : removeAt((exint)idx);
529 }
530 
531 template <typename T>
532 inline exint
534 {
535  trivialDestruct(myData[idx]);
536  if (idx != --mySize)
537  {
538  ::memmove((void *)&myData[idx], (void *)&myData[idx+1],
539  ((mySize-idx)*sizeof(T))); // NOLINT
540  }
541 
542  return idx;
543 }
544 
545 template <typename T>
546 inline void
548 {
549  UT_ASSERT(begin_i <= end_i);
550  UT_ASSERT(end_i <= size());
551  if (end_i < size())
552  {
553  trivialDestructRange(myData + begin_i, end_i - begin_i);
554  ::memmove((void *)&myData[begin_i], (void *)&myData[end_i],
555  (mySize - end_i)*sizeof(T)); // NOLINT
556  }
557  setSize(mySize - (end_i - begin_i));
558 }
559 
560 template <typename T>
561 inline void
563 {
564  UT_ASSERT_P(begin_i >= 0);
565  UT_ASSERT_P(begin_i <= end_i);
566  UT_ASSERT_P(end_i <= size());
567  UT_ASSERT(this != &dest);
568 
569  exint nelements = end_i - begin_i;
570 
571  // grow the raw array if necessary.
572  dest.setCapacityIfNeeded(nelements);
573 
574  ::memmove((void*)dest.myData, (void*)&myData[begin_i],
575  nelements * sizeof(T)); // NOLINT
576  dest.mySize = nelements;
577 
578  // we just asserted this was true, but just in case
579  if (this != &dest)
580  {
581  if (end_i < size())
582  {
583  ::memmove((void*)&myData[begin_i], (void*)&myData[end_i],
584  (mySize - end_i) * sizeof(T)); // NOLINT
585  }
586  setSize(mySize - nelements);
587  }
588 }
589 
592 template <typename T>
593 inline void
594 UT_Array<T>::move(exint src_idx, exint dst_idx, exint how_many)
595 {
596  // Make sure all the parameters are valid.
597  if (src_idx < 0)
598  src_idx = 0;
599  if (dst_idx < 0)
600  dst_idx = 0;
601  // If we are told to move a set of elements that would extend beyond the
602  // end of the current array, trim the group.
603  if (src_idx + how_many > size())
604  how_many = size() - src_idx;
605  // If the dst_idx would have us move the source beyond the end of the
606  // current array, move the dst_idx back.
607  if (dst_idx + how_many > size())
608  dst_idx = size() - how_many;
609  if (src_idx != dst_idx && how_many > 0)
610  {
611  constexpr auto elem_size = sizeof(T); // NOLINT
612  void **tmp = 0;
613  exint savelen;
614 
615  savelen = SYSabs(src_idx - dst_idx);
616  tmp = (void **)::malloc(savelen*elem_size);
617  if (src_idx > dst_idx && how_many > 0)
618  {
619  // We're moving the group backwards. Save all the stuff that
620  // we would overwrite, plus everything beyond that to the
621  // start of the source group. Then move the source group, then
622  // tack the saved data onto the end of the moved group.
623  ::memcpy(tmp, &myData[dst_idx], savelen*elem_size);
624  ::memmove(&myData[dst_idx], &myData[src_idx], how_many*elem_size);
625  ::memcpy(&myData[dst_idx+how_many], tmp, savelen*elem_size);
626  }
627  if (src_idx < dst_idx && how_many > 0)
628  {
629  // We're moving the group forwards. Save from the end of the
630  // group being moved to the end of the where the destination
631  // group will end up. Then copy the source to the destination.
632  // Then move back up to the original source location and drop
633  // in our saved data.
634  ::memcpy(tmp, &myData[src_idx+how_many], savelen*elem_size);
635  ::memmove(&myData[dst_idx], &myData[src_idx], how_many*elem_size);
636  ::memcpy(&myData[src_idx], tmp, savelen*elem_size);
637  }
638  ::free(tmp);
639  }
640 }
642 
643 template <typename T>
644 template <typename IsEqual>
645 inline exint
646 UT_Array<T>::removeIf(IsEqual is_equal)
647 {
648  // Move dst to the first element to remove.
649  exint dst;
650  for (dst = 0; dst < mySize; dst++)
651  {
652  if (is_equal(myData[dst]))
653  break;
654  }
655  // Now start looking at all the elements past the first one to remove.
656  for (exint idx = dst+1; idx < mySize; idx++)
657  {
658  if (!is_equal(myData[idx]))
659  {
660  UT_ASSERT(idx != dst);
661  myData[dst] = std::move(myData[idx]);
662  dst++;
663  }
664  // On match, ignore.
665  }
666 
667  // Don't call setSize(dst) since it supports growing the array which
668  // requires a default constructor. Avoiding it allows this to be used on
669  // types that lack a default constructor.
670  trivialDestructRange(myData + dst, mySize - dst);
671  mySize = dst;
672 
673  return mySize;
674 }
675 
676 template <typename T>
677 inline void
679 {
680  char *tempPtr;
681  exint numShift; // The number of items we shift
682  exint remaining; // mySize - numShift
683 
684  if (how_many == 0 || mySize < 1)
685  return;
686 
687  constexpr auto elem_size = sizeof(T); // NOLINT
688 
689  numShift = how_many % (exint)mySize;
690  if (numShift < 0) numShift += mySize;
691  remaining = mySize - numShift;
692  tempPtr = new char[numShift*elem_size];
693 
694  ::memmove(tempPtr, (void *)&myData[remaining], (numShift * elem_size));
695  ::memmove((void *)&myData[numShift], (void *)&myData[0],
696  (remaining * elem_size));
697  ::memmove((void *)&myData[0], tempPtr, (numShift * elem_size));
698 
699  delete [] tempPtr;
700 }
701 
702 template <typename T>
703 inline void
705 {
706  for (exint i = 0; i < mySize; i++)
707  {
708  myData[i] = value;
709  }
710 }
711 
712 // This constant() specialization needs to be declared here and implemented
713 // in UT_Array.C.
714 template <>
716 
717 template <typename T>
718 inline void
720 {
721  if (isPOD())
722  ::memset((void *)myData, 0, mySize*sizeof(T)); // NOLINT
723  else
724  trivialConstructRange(myData, mySize);
725 }
726 
727 template <typename T>
728 inline exint
729 UT_Array<T>::find(const T &t, exint s) const
730 {
731  const T *end = myData + mySize;
732  for (const T *p = myData + s; p < end; ++p)
733  if (*p == t)
734  return (p - myData);
735  return -1;
736 }
737 
738 template <typename T>
739 exint
740 UT_Array<T>::sortedFind(const T &t, Comparator compare) const
741 {
742  T *found;
743 
744  if( mySize == 0 ) return -1;
745 
746  // NOLINTNEXTLINE
747  found = (T *)::bsearch(&t, myData, mySize, sizeof(T),
748  (ut_ptr_compare_func_t)compare);
749  return found ? (found - myData) : -1;
750 }
751 
752 template <typename T>
753 inline void
755 {
756  exint n = mySize / 2;
757  for (exint i = 0; i < n; i++ )
758  UTswap(myData[i], myData[mySize-1-i]);
759 }
760 
761 template <typename T>
762 inline void
764 {
765  stdsort(UTcompareLess(compare));
766 }
767 
768 template <typename T>
769 template <typename ComparatorBool>
770 inline T
771 UT_Array<T>::selectNthLargest(exint idx, ComparatorBool is_less)
772 {
773  // The idea of returning doesn't make sense if we have
774  // an empty array.
775  UT_ASSERT(size() > 0);
776  if (size() == 0)
777  return T();
778 
779  idx = SYSclamp(idx, (exint)0, (exint)(size())-1);
780 
781  UTnth_element(myData, &myData[idx], &myData[size()], is_less);
782 
783  return myData[idx];
784 }
785 
788 template <typename T>
789 inline void
790 UT_Array<T>::setCapacity(exint capacity)
791 {
792  // Do nothing when new capacity is the same as the current
793  if (capacity == myCapacity)
794  return;
795 
796  constexpr auto elem_size = sizeof(T); // NOLINT
797 
798  // Special case for non-heap buffers
799  if (!isHeapBuffer())
800  {
801  if (capacity < mySize)
802  {
803  // Destroy the extra elements without changing myCapacity
804  trivialDestructRange(myData + capacity, mySize - capacity);
805  mySize = capacity;
806  }
807  else if (capacity > myCapacity)
808  {
809  T *prev = myData;
810  myData = (T *)malloc(elem_size * capacity);
811  // myData is safe because we're already a stack buffer
812  UT_ASSERT_P(isHeapBuffer());
813  if (mySize > 0)
814  memcpy((void *)myData, (void *)prev, elem_size * mySize);
815  myCapacity = capacity;
816  }
817  else
818  {
819  // Keep myCapacity unchanged in this case
820  UT_ASSERT_P(capacity >= mySize && capacity <= myCapacity);
821  }
822  return;
823  }
824 
825  if (capacity == 0)
826  {
827  if (myData)
828  {
829  trivialDestructRange(myData, mySize);
830  free(myData);
831  }
832  myData = nullptr;
833  myCapacity = 0;
834  mySize = 0;
835  return;
836  }
837 
838  if (capacity < mySize)
839  {
840  trivialDestructRange(myData + capacity, mySize - capacity);
841  mySize = capacity;
842  }
843 
844  if (myData)
845  myData = (T *)realloc(myData, elem_size * capacity);
846  else
847  myData = (T *)malloc(elem_size * capacity);
848 
849  // Avoid degenerate case if we happen to be aliased the wrong way
850  if (!isHeapBuffer())
851  {
852  T *prev = myData;
853  myData = (T *)malloc(elem_size * capacity);
854  if (mySize > 0)
855  memcpy((void *)myData, (void *)prev, elem_size * mySize);
856  ut_ArrayImplFree(prev);
857  }
858 
859  myCapacity = capacity;
860  UT_ASSERT(myData);
861 }
863 
864 template <typename T>
865 inline UT_Array<T> &
866 UT_Array<T>::operator=(const UT_Array<T> &a)
867 {
868  if (this == &a)
869  return *this;
870 
871  // Grow the raw array if necessary.
872  setCapacityIfNeeded(a.size());
873 
874  // Make sure destructors and constructors are called on all elements
875  // being removed/added.
876  trivialDestructRange(myData, mySize);
877  copyConstructRange(myData, a.myData, a.size());
878 
879  mySize = a.size();
880 
881  return *this;
882 }
883 
884 template <typename T>
885 inline UT_Array<T> &
886 UT_Array<T>::operator=(std::initializer_list<T> a)
887 {
888  const exint new_size = a.size();
889 
890  // Grow the raw array if necessary.
891  setCapacityIfNeeded(new_size);
892 
893  // Make sure destructors and constructors are called on all elements
894  // being removed/added.
895  trivialDestructRange(myData, mySize);
896 
897  copyConstructRange(myData, a.begin(), new_size);
898 
899  mySize = new_size;
900 
901  return *this;
902 }
903 
904 template <typename T>
905 inline UT_Array<T> &
907 {
908  if (!a.isHeapBuffer())
909  {
910  // Cannot steal from non-heap buffers
911  clear();
912  const exint n = a.size();
913  setCapacityIfNeeded(n);
914  if (isPOD())
915  {
916  if (n > 0)
917  memcpy((void*)myData, (void*)a.myData, n * sizeof(T)); //NOLINT
918  }
919  else
920  {
921  for (exint i = 0; i < n; ++i)
922  new (&myData[i]) T(std::move(a.myData[i]));
923  }
924  mySize = a.mySize;
925  a.mySize = 0;
926  return *this;
927  }
928  // else, just steal even if we're a small buffer
929 
930  // Destroy all the elements we're currently holding.
931  if (myData)
932  {
933  trivialDestructRange(myData, mySize);
934  if (isHeapBuffer())
935  ::free(myData);
936  }
937 
938  // Move the contents of the other array to us and empty the other container
939  // so that it destructs cleanly.
940  myCapacity = a.myCapacity;
941  mySize = a.mySize;
942  myData = a.myData;
943  a.myCapacity = a.mySize = 0;
944  a.myData = nullptr;
945 
946  return *this;
947 }
948 
949 
950 template <typename T>
951 inline bool
953 {
954  if (this == &a) return true;
955  if (mySize != a.size()) return false;
956  for (exint i = 0; i < mySize; i++)
957  if (!(myData[i] == a(i))) return false;
958  return true;
959 }
960 
961 template <typename T>
962 inline bool
964 {
965  return (!operator==(a));
966 }
967 
968 template <typename T>
969 inline int
970 UT_Array<T>::isEqual(const UT_Array<T> &a, Comparator compare) const
971 {
972  if (this == &a) return 1;
973  if (mySize != a.size()) return 0;
974  for (exint i = 0; i < mySize; i++)
975  {
976  T v2 = a(i);
977  if (compare(&myData[i], &v2)) return 0;
978  }
979  return 1;
980 }
981 
982 template <typename T>
983 inline exint
984 UT_Array<T>::apply(int (*apply_func)(T &t, void *d), void *d)
985 {
986  exint i;
987  for (i = 0; i < mySize; i++)
988  {
989  if (apply_func(myData[i], d))
990  break;
991  }
992  return i;
993 }
994 
995 // Merge the given array into us.
996 // If direction is -1, then it assumes us and 'other' are both already
997 // sorted in descending order. Similarly, +1 means ascending.
998 // If allow_dups is false, then it further assumes that both arrays have no
999 // duplicates and will produce a result that also has no duplicates.
1000 // More work will be needed if you want allow_dups to mean remove duplicates
1001 template <typename T>
1002 template <typename ComparatorBool>
1003 inline void
1005  const UT_Array<T> &other, int direction, bool allow_dups,
1006  ComparatorBool is_less)
1007 {
1009  exint our_idx;
1010  exint other_idx;
1011 
1012  // handle trivial cases to avoid extra work
1013  if (other.size() == 0)
1014  return;
1015  if (size() == 0)
1016  {
1017  concat(other);
1018  return;
1019  }
1020 
1021  UT_ASSERT( direction == -1 || direction == +1 );
1022  direction = (direction > 0) ? +1 : -1;
1023 
1024  our_idx = 0;
1025  other_idx = 0;
1026  while( our_idx < size() && other_idx < other.size() )
1027  {
1028  const T &our_item = (*this)(our_idx);
1029  const T &other_item = other(other_idx);
1030  exint item_dir;
1031 
1032  if (our_item == other_item)
1033  item_dir = 0;
1034  else if (is_less(our_item, other_item))
1035  item_dir = -1;
1036  else
1037  item_dir = +1;
1038 
1039  if( item_dir != 0 )
1040  {
1041  // we need to do an comparison in the next line to take care of the
1042  // fact that -INT_MIN is still less than 0.
1043  item_dir = ( (item_dir > 0) ? +1 : -1 ) * direction;
1044  }
1045 
1046  if( item_dir < 0 )
1047  {
1048  result.append( our_item );
1049  our_idx++;
1050  }
1051  else if( item_dir > 0 )
1052  {
1053  result.append( other_item );
1054  other_idx++;
1055  }
1056  else
1057  {
1058  result.append( our_item );
1059  our_idx++;
1060  if( allow_dups )
1061  result.append( other_item );
1062  other_idx++;
1063  }
1064  }
1065 
1066  UT_ASSERT( our_idx == size() || other_idx == other.size() );
1067  for( ; our_idx < size(); our_idx++ )
1068  result.append( (*this)(our_idx) );
1069  for( ; other_idx < other.size(); other_idx++ )
1070  result.append( other(other_idx) );
1071 
1072  // finally swap the result into us
1073  swap( result );
1074 }
1075 
1076 template <typename T>
1077 inline bool
1079  const UT_Array<T> &other,
1080  Comparator compare) const
1081 {
1082  return std::includes(
1083  myData, myData + mySize,
1084  other.myData, other.myData + other.mySize,
1085  UTcompareLess(compare));
1086 }
1087 
1088 template <typename T>
1089 inline void
1091 {
1092  UT_Array<T> temp;
1093  sortedUnion( other, temp, compare );
1094  swap( temp );
1095 }
1096 
1097 template <typename T>
1098 inline void
1100  UT_Array<T> &result, Comparator compare) const
1101 {
1102  T *first1 = myData;
1103  T *last1 = myData + mySize;
1104  T *first2 = other.myData;
1105  T *last2 = other.myData + other.mySize;
1106 
1107  // Can't store to either input.
1108  UT_ASSERT(&result != this && &result != &other);
1109  UT_ASSERT(result.size() == 0);
1110 
1111  while( first1 != last1 && first2 != last2 )
1112  {
1113  if( compare(first1, first2) < 0 )
1114  {
1115  result.append( *first1 );
1116  ++first1;
1117  }
1118  else if( compare(first2, first1) < 0 )
1119  {
1120  result.append( *first2 );
1121  ++first2;
1122  }
1123  else
1124  {
1125  result.append( *first1 );
1126  ++first1;
1127  ++first2;
1128  }
1129  }
1130  while( first1 != last1 )
1131  {
1132  result.append( *first1 );
1133  ++first1;
1134  }
1135  while( first2 != last2 )
1136  {
1137  result.append( *first2 );
1138  ++first2;
1139  }
1140 }
1141 
1142 template <typename T>
1143 inline void
1145 {
1146  UT_Array<T> temp;
1147  sortedIntersection( other, temp, compare );
1148  swap( temp );
1149 }
1150 
1151 template <typename T>
1152 inline void
1154  UT_Array<T> &result, Comparator compare ) const
1155 {
1156  T *first1 = myData;
1157  T *last1 = myData + mySize;
1158  T *first2 = other.myData;
1159  T *last2 = other.myData + other.mySize;
1160 
1161  while (first1 != last1 && first2 != last2)
1162  if( compare(first1, first2) < 0 )
1163  ++first1;
1164  else if( compare(first2, first1) < 0 )
1165  ++first2;
1166  else {
1167  result.append( *first1 );
1168  ++first1;
1169  ++first2;
1170  }
1171 }
1172 
1173 template <typename T>
1174 inline void
1176 {
1177  UT_Array<T> temp;
1178  sortedSetDifference(other, temp, compare);
1179  swap( temp );
1180 }
1181 
1182 template <typename T>
1183 inline void
1186  Comparator compare) const
1187 {
1188  T *first1 = myData;
1189  T *last1 = myData + mySize;
1190  T *first2 = other.myData;
1191  T *last2 = other.myData + other.mySize;
1192 
1193  while (first1 != last1 && first2 != last2)
1194  {
1195  if( compare(first1, first2) < 0 )
1196  {
1197  result.append( *first1 );
1198  ++first1;
1199  }
1200  else if( compare(first2, first1) < 0 )
1201  ++first2;
1202  else
1203  {
1204  ++first1;
1205  ++first2;
1206  }
1207  }
1208  while( first1 != last1 )
1209  {
1210  result.append( *first1 );
1211  ++first1;
1212  }
1213 }
1214 
1215 template <typename T>
1216 template <typename CompareEqual>
1217 inline exint
1218 UT_Array<T>::sortedRemoveDuplicatesIf(CompareEqual compare_equal)
1219 {
1220  exint n = size();
1221 
1222  // Trivial, no duplicates!
1223  if (n < 2)
1224  return 0;
1225 
1226  exint dst = 1;
1227  for (exint i = 1; i < n; i++)
1228  {
1229  if (!compare_equal((*this)(i), (*this)(i-1)))
1230  {
1231  if (i != dst)
1232  (*this)(dst) = (*this)(i);
1233  dst++;
1234  }
1235  }
1236 
1237  // Store the number of remaining elements.
1238  setSize(dst);
1239  return n - dst; // Return the number of elements removed
1240 }
1241 
1242 namespace {
1243  template<typename T>
1244  struct srdCompareEqual
1245  {
1246  bool operator()(const T& x, const T& y) const { return (x == y); }
1247  };
1248 }
1249 
1250 template <typename T>
1251 inline exint
1253 {
1254  srdCompareEqual<T> cmp;
1255  return sortedRemoveDuplicatesIf(cmp);
1256 }
1257 
1258 template <typename T>
1259 template <typename BinaryOp>
1260 inline T
1261 UT_Array<T>::accumulate(const T &init_value, BinaryOp add) const
1262 {
1263  T sum(init_value);
1264  for (exint i = 0; i < mySize; i++)
1265  sum = add(sum, myData[i]);
1266  return sum;
1267 }
1268 
1269 #endif // __UT_ARRAYIMPL_H_INCLUDED__
void swap(ArAssetInfo &lhs, ArAssetInfo &rhs)
Definition: assetInfo.h:61
int isEqual(const UT_Array< T > &a, Comparator compare) const
Definition: UT_ArrayImpl.h:970
int(* ut_ptr_compare_func_t)(const void *, const void *)
Definition: UT_ArrayHelp.h:23
exint find(const T &t, exint s=0) const
Definition: UT_ArrayImpl.h:729
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
Definition: UT_Permute.h:75
bool operator!=(const UT_Array< T > &a) const
Definition: UT_ArrayImpl.h:963
#define SYS_PRAGMA_PUSH_WARN()
Definition: SYS_Pragma.h:34
void UTswap(T &a, T &b)
Definition: UT_Swap.h:35
exint insertImpl(S &&s, exint index)
Similar to appendImpl() but for insertion.
Definition: UT_ArrayImpl.h:477
void
Definition: png.h:1083
static void copyConstructRange(T *dst, const T *src, exint n)
Definition: UT_Array.h:978
exint uniqueSortedFind(const T &item, Comparator compare) const
Definition: UT_ArrayImpl.h:347
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less)
UT_Array< T > & operator=(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:866
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
void extractRange(exint begin_i, exint end_i, UT_Array< T > &dest)
Definition: UT_ArrayImpl.h:562
void zero()
Zeros the array if a POD type, else trivial constructs if a class type.
Definition: UT_ArrayImpl.h:719
int64 exint
Definition: SYS_Types.h:125
void cycle(exint how_many)
Cyclically shifts the entire array by how_many.
Definition: UT_ArrayImpl.h:678
#define SYSabs(a)
Definition: SYS_Math.h:1537
T * array()
Definition: UT_Array.h:652
#define UT_API
Definition: UT_API.h:14
exint concat(const UT_Array< T > &a)
Takes another T array and concatenate it onto my end.
Definition: UT_ArrayImpl.h:423
exint uniqueSortedInsert(const T &t, Comparator compare)
Definition: UT_Array.h:135
GLenum src
Definition: glcorearb.h:1792
float fpreal32
Definition: SYS_Types.h:200
GLdouble GLdouble t
Definition: glew.h:1403
std::string OIIO_API concat(string_view s, string_view t)
exint size() const
Definition: UT_Array.h:479
GLint GLenum GLint x
Definition: glcorearb.h:408
GLsizeiptr size
Definition: glcorearb.h:663
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, ROI roi={}, int nthreads=0)
GLuint64EXT * result
Definition: glew.h:14311
exint apply(int(*apply_func)(T &t, void *d), void *d)
Definition: UT_ArrayImpl.h:984
exint emplace_back(S &&...s)
Definition: UT_ArrayImpl.h:179
exint uniqueSortedInsertImpl(S &&s, Comparator compare)
Definition: UT_ArrayImpl.h:279
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
Definition: format.h:2929
GLenum GLsizei len
Definition: glew.h:7782
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:170
T accumulate(const T &init_value, BinaryOp add) const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
GLuint GLuint end
Definition: glcorearb.h:474
UT_Vector3T< T > SYSclamp(const UT_Vector3T< T > &v, const UT_Vector3T< T > &min, const UT_Vector3T< T > &max)
Definition: UT_Vector3.h:832
exint sortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:227
exint appendImpl(S &&s)
Definition: UT_ArrayImpl.h:156
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:203
GLfloat GLfloat p
Definition: glew.h:16656
GLint GLsizei count
Definition: glcorearb.h:404
#define SYS_PRAGMA_POP_WARN()
Definition: SYS_Pragma.h:35
exint sortedRemoveDuplicates()
exint append()
Definition: UT_Array.h:95
int cmp(T a, T b)
Definition: ImathFun.h:119
exint sortedRemoveDuplicatesIf(CompareEqual compare_equal)
GLdouble n
Definition: glcorearb.h:2007
UT_API void ut_ArrayImplFree(void *p)
bool hasSortedSubset(const UT_Array< T > &other, Comparator compare) const
GLboolean * data
Definition: glcorearb.h:130
#define SYS_PRAGMA_DISABLE_ALLOC_SIZE_LARGER_THAN()
Definition: SYS_Pragma.h:169
GLuint GLfloat * val
Definition: glcorearb.h:1607
void sortedSetDifference(const UT_Array< T > &other, Comparator compare)
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2001
void sortedUnion(const UT_Array< T > &other, Comparator compare)
T selectNthLargest(exint idx, ComparatorBool is_less)
Definition: UT_ArrayImpl.h:771
UT_Compare::Less< T > UTcompareLess(UT_Compare::Ternary< T > compare)
Definition: UT_Compare.h:64
GLuint index
Definition: glcorearb.h:785
void sort(Comparator compare)
Definition: UT_ArrayImpl.h:763
GLsizei const GLfloat * value
Definition: glcorearb.h:823
void constant(const T &v)
Quickly set the array to a single value.
Definition: UT_ArrayImpl.h:704
void setCapacityIfNeeded(exint mincapacity)
Definition: UT_Array.h:436
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:171
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)
#define const
Definition: zconf.h:214
UT_Array(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:38
GLenum GLenum dst
Definition: glcorearb.h:1792
T heapPop(Comparator compare)
Definition: UT_ArrayImpl.h:386
GLdouble s
Definition: glew.h:1395
exint heapPush(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:369
void reverse()
Reverses the array by swapping elements in mirrored locations.
Definition: UT_ArrayImpl.h:754
exint multipleInsert(exint index, exint count)
Insert an element "count" times at the given index. Return the index.
Definition: UT_ArrayImpl.h:450
GLint y
Definition: glcorearb.h:102
void removeRange(exint begin_i, exint end_i)
Remove the range [begin_i,end_i) of elements from the array.
Definition: UT_ArrayImpl.h:547
exint insert(exint index)
Definition: UT_ArrayImpl.h:130
exint findAndRemove(const T &t)
Definition: UT_ArrayImpl.h:525
bool operator==(const UT_Array< T > &a) const
Definition: UT_ArrayImpl.h:952
exint sortedFind(const T &t, Comparator compare) const
Definition: UT_ArrayImpl.h:740