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