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