HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 #ifdef 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
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
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
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
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
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
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.
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();
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
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 template <typename T>
951 void
952 UT_Array<T>::fromStdVector(const std::vector<T> &vec)
953 {
954  setSize(0);
955  for (exint i=0; i<vec.size(); ++i)
956  append(vec[i]);
957 }
958 
959 template <typename T>
960 void
961 UT_Array<T>::toStdVector(std::vector<T> &vec) const
962 {
963  vec.clear();
964  for (exint i=0; i < size(); ++i)
965  vec.push_back((*this)(i));
966 }
967 
968 // Merge the given array into us.
969 // If direction is -1, then it assumes us and 'other' are both already
970 // sorted in descending order. Similarly, +1 means ascending.
971 // If allow_dups is false, then it further assumes that both arrays have no
972 // duplicates and will produce a result that also has no duplicates.
973 // More work will be needed if you want allow_dups to mean remove duplicates
974 template <typename T>
975 template <typename ComparatorBool>
976 void
978  const UT_Array<T> &other, int direction, bool allow_dups,
979  ComparatorBool is_less)
980 {
981  UT_Array<T> result;
982  exint our_idx;
983  exint other_idx;
984 
985  // handle trivial cases to avoid extra work
986  if (other.size() == 0)
987  return;
988  if (size() == 0)
989  {
990  concat(other);
991  return;
992  }
993 
994  UT_ASSERT( direction == -1 || direction == +1 );
995  direction = (direction > 0) ? +1 : -1;
996 
997  our_idx = 0;
998  other_idx = 0;
999  while( our_idx < size() && other_idx < other.size() )
1000  {
1001  const T &our_item = (*this)(our_idx);
1002  const T &other_item = other(other_idx);
1003  exint item_dir;
1004 
1005  if (our_item == other_item)
1006  item_dir = 0;
1007  else if (is_less(our_item, other_item))
1008  item_dir = -1;
1009  else
1010  item_dir = +1;
1011 
1012  if( item_dir != 0 )
1013  {
1014  // we need to do an comparison in the next line to take care of the
1015  // fact that -INT_MIN is still less than 0.
1016  item_dir = ( (item_dir > 0) ? +1 : -1 ) * direction;
1017  }
1018 
1019  if( item_dir < 0 )
1020  {
1021  result.append( our_item );
1022  our_idx++;
1023  }
1024  else if( item_dir > 0 )
1025  {
1026  result.append( other_item );
1027  other_idx++;
1028  }
1029  else
1030  {
1031  result.append( our_item );
1032  our_idx++;
1033  if( allow_dups )
1034  result.append( other_item );
1035  other_idx++;
1036  }
1037  }
1038 
1039  UT_ASSERT( our_idx == size() || other_idx == other.size() );
1040  for( ; our_idx < size(); our_idx++ )
1041  result.append( (*this)(our_idx) );
1042  for( ; other_idx < other.size(); other_idx++ )
1043  result.append( other(other_idx) );
1044 
1045  // finally swap the result into us
1046  swap( result );
1047 }
1048 
1049 template <typename T>
1050 bool
1052  const UT_Array<T> &other,
1053  Comparator compare) const
1054 {
1055  return std::includes(
1056  myData, myData + mySize,
1057  other.myData, other.myData + other.mySize,
1058  UTcompareLess(compare));
1059 }
1060 
1061 template <typename T>
1062 void
1064 {
1065  UT_Array<T> temp;
1066  sortedUnion( other, temp, compare );
1067  swap( temp );
1068 }
1069 
1070 template <typename T>
1071 void
1073  UT_Array<T> &result, Comparator compare) const
1074 {
1075  T *first1 = myData;
1076  T *last1 = myData + mySize;
1077  T *first2 = other.myData;
1078  T *last2 = other.myData + other.mySize;
1079 
1080  // Can't store to either input.
1081  UT_ASSERT(&result != this && &result != &other);
1082  UT_ASSERT(result.size() == 0);
1083 
1084  while( first1 != last1 && first2 != last2 )
1085  {
1086  if( compare(first1, first2) < 0 )
1087  {
1088  result.append( *first1 );
1089  ++first1;
1090  }
1091  else if( compare(first2, first1) < 0 )
1092  {
1093  result.append( *first2 );
1094  ++first2;
1095  }
1096  else
1097  {
1098  result.append( *first1 );
1099  ++first1;
1100  ++first2;
1101  }
1102  }
1103  while( first1 != last1 )
1104  {
1105  result.append( *first1 );
1106  ++first1;
1107  }
1108  while( first2 != last2 )
1109  {
1110  result.append( *first2 );
1111  ++first2;
1112  }
1113 }
1114 
1115 template <typename T>
1116 void
1118 {
1119  UT_Array<T> temp;
1120  sortedIntersection( other, temp, compare );
1121  swap( temp );
1122 }
1123 
1124 template <typename T>
1125 void
1127  UT_Array<T> &result, Comparator compare ) const
1128 {
1129  T *first1 = myData;
1130  T *last1 = myData + mySize;
1131  T *first2 = other.myData;
1132  T *last2 = other.myData + other.mySize;
1133 
1134  while (first1 != last1 && first2 != last2)
1135  if( compare(first1, first2) < 0 )
1136  ++first1;
1137  else if( compare(first2, first1) < 0 )
1138  ++first2;
1139  else {
1140  result.append( *first1 );
1141  ++first1;
1142  ++first2;
1143  }
1144 }
1145 
1146 template <typename T>
1147 void
1149 {
1150  UT_Array<T> temp;
1151  sortedSetDifference(other, temp, compare);
1152  swap( temp );
1153 }
1154 
1155 template <typename T>
1156 void
1158  UT_Array<T> &result,
1159  Comparator compare) const
1160 {
1161  T *first1 = myData;
1162  T *last1 = myData + mySize;
1163  T *first2 = other.myData;
1164  T *last2 = other.myData + other.mySize;
1165 
1166  while (first1 != last1 && first2 != last2)
1167  {
1168  if( compare(first1, first2) < 0 )
1169  {
1170  result.append( *first1 );
1171  ++first1;
1172  }
1173  else if( compare(first2, first1) < 0 )
1174  ++first2;
1175  else
1176  {
1177  ++first1;
1178  ++first2;
1179  }
1180  }
1181  while( first1 != last1 )
1182  {
1183  result.append( *first1 );
1184  ++first1;
1185  }
1186 }
1187 
1188 template <typename T>
1189 template <typename CompareEqual>
1190 exint
1191 UT_Array<T>::sortedRemoveDuplicatesIf(CompareEqual compare_equal)
1192 {
1193  exint n = size();
1194 
1195  // Trivial, no duplicates!
1196  if (n < 2)
1197  return 0;
1198 
1199  exint dst = 1;
1200  for (exint i = 1; i < n; i++)
1201  {
1202  if (!compare_equal((*this)(i), (*this)(i-1)))
1203  {
1204  if (i != dst)
1205  (*this)(dst) = (*this)(i);
1206  dst++;
1207  }
1208  }
1209 
1210  // Store the number of remaining elements.
1211  setSize(dst);
1212  return n - dst; // Return the number of elements removed
1213 }
1214 
1215 namespace {
1216  template<typename T>
1217  struct srdCompareEqual
1218  {
1219  bool operator()(const T& x, const T& y) const { return (x == y); }
1220  };
1221 }
1222 
1223 template <typename T>
1224 exint
1226 {
1227  srdCompareEqual<T> cmp;
1228  return sortedRemoveDuplicatesIf(cmp);
1229 }
1230 
1231 template <typename T>
1232 template <typename BinaryOp>
1233 T
1234 UT_Array<T>::accumulate(const T &init_value, BinaryOp add) const
1235 {
1236  T sum(init_value);
1237  for (exint i = 0; i < mySize; i++)
1238  sum = add(sum, myData[i]);
1239  return sum;
1240 }
1241 
1242 #endif // __UT_ARRAYIMPL_H_INCLUDED__
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
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:865
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:910
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:929
exint uniqueSortedFind(const T &item, Comparator compare) const
Definition: UT_ArrayImpl.h:338
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1561
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less)
Definition: UT_ArrayImpl.h:977
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
static void trivialConstruct(T &dst)
Element Constructor.
Definition: UT_Array.h:947
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define SYSabs(a)
Definition: SYS_Math.h:1367
T * array()
Definition: UT_Array.h:607
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:296
exint apply(int(*applyFct)(T &t, void *d), void *d)
Definition: UT_ArrayImpl.h:942
#define UT_API
Definition: UT_API.h:12
GLint y
Definition: glcorearb.h:102
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:879
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
void bumpCapacity(exint mincapacity)
Definition: UT_Array.h:410
png_uint_32 i
Definition: png.h:2877
exint size() const
Definition: UT_Array.h:444
void setSize(exint newsize)
Definition: UT_Array.h:462
static void trivialDestructRange(T *dst, exint n)
Definition: UT_Array.h:982
GLsizeiptr size
Definition: glcorearb.h:663
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
exint safeIndex(const T &t) const
Definition: UT_Array.h:283
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
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:916
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
int64 exint
Definition: SYS_Types.h:115
static void trivialDestruct(T &dst)
Element Destructor.
Definition: UT_Array.h:977
exint insertAt(const T &t, exint index)
Definition: UT_Array.h:213
void toStdVector(std::vector< T > &vec) const
Convert to an std::vector.
Definition: UT_ArrayImpl.h:961
T accumulate(const T &init_value, BinaryOp add) const
GLuint GLuint end
Definition: glcorearb.h:474
exint capacity() const
Definition: UT_Array.h:441
void fromStdVector(const std::vector< T > &vec)
Convert from an std::vector.
Definition: UT_ArrayImpl.h:952
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
static void trivialConstructRange(T *dst, exint n)
Definition: UT_Array.h:954
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:922
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:49
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
int(* Comparator)(const T *, const T *)
Definition: UT_Array.h:45
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:401
void sortedIntersection(const UT_Array< T > &other, Comparator compare)
UT_Array(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:38
void clear()
Resets list to an empty list.
Definition: UT_Array.h:506
void move(exint srcIdx, exint destIdx, exint howMany)
Definition: UT_ArrayImpl.h:567
T & operator()(exint i)
Definition: UT_Array.h:535
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:190
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