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