HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Array.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: UT_Array.h (UT Library, C++)
7  *
8  * COMMENTS: This is the array class implementation used by
9  * almost everything in the codebase.
10  * Please be careful if you need to change it!
11  */
12 
13 #pragma once
14 
15 #ifndef __UT_ARRAY_H_INCLUDED__
16 #define __UT_ARRAY_H_INCLUDED__
17 
18 #include "UT_API.h"
19 #include "UT_ArrayHelp.h"
20 #include "UT_Assert.h"
21 #include "UT_ContainerPrinter.h"
22 #include "UT_IteratorRange.h"
23 #include "UT_Permute.h"
24 
25 #include <SYS/SYS_Compiler.h>
26 #include <SYS/SYS_Deprecated.h>
27 #include <SYS/SYS_Inline.h>
28 #include <SYS/SYS_Types.h>
29 #include <SYS/SYS_TypeTraits.h>
30 
31 #include <algorithm>
32 #include <initializer_list>
33 #include <iterator>
34 #include <utility>
35 
36 #include <string.h>
37 
38 
39 template <typename T>
40 class UT_Array
41 {
42 public:
43  typedef T value_type;
44 
45  typedef int (*Comparator)(const T *, const T *);
46 
47  /// Copy constructor. It duplicates the data.
48  /// It's marked explicit so that it's not accidentally passed by value.
49  /// You can always pass by reference and then copy it, if needed.
50  /// If you have a line like:
51  /// UT_Array<int> a = otherarray;
52  /// and it really does need to copy instead of referencing,
53  /// you can rewrite it as:
54  /// UT_Array<int> a(otherarray);
55  explicit UT_Array(const UT_Array<T> &a);
56 
57  /// Move constructor. Steals the working data from the original.
58  UT_Array(UT_Array<T> &&a) noexcept;
59 
60  /// Construct based on given capacity and size
62  {
63  myData = capacity ? allocateCapacity(capacity) : nullptr;
64  if (capacity < size)
65  size = capacity;
66  mySize = size;
67  myCapacity = capacity;
68  trivialConstructRange(myData, mySize);
69  }
70 
71  /// Construct based on given capacity with a size of 0
72  explicit UT_Array(exint capacity = 0) : myCapacity(capacity), mySize(0)
73  {
74  myData = capacity ? allocateCapacity(capacity) : nullptr;
75  }
76 
77  /// Construct with the contents of an initializer list
78  explicit UT_Array(std::initializer_list<T> init);
79 
80  ~UT_Array();
81 
82  void swap(UT_Array<T> &other);
83 
84  /// Append an element to the current elements and return its index in the
85  /// array, or insert the element at a specified position; if necessary,
86  /// insert() grows the array to accommodate the element. The insert
87  /// methods use the assignment operator '=' to place the element into the
88  /// right spot; be aware that '=' works differently on objects and pointers.
89  /// The test for duplicates uses the logical equal operator '=='; as with
90  /// '=', the behaviour of the equality operator on pointers versus objects
91  /// is not the same.
92  /// Use the subscript operators instead of insert() if you are appending
93  /// to the array, or if you don't mind overwriting the element already
94  /// inserted at the given index.
95  exint append() { return insert(mySize); }
96  exint append(const T &t) { return appendImpl(t); }
97  exint append(T &&t) { return appendImpl(std::move(t)); }
98  exint append(const T &t, bool check_dup)
99  {
100  exint idx;
101  if (check_dup && ((idx = find(t)) != -1))
102  return idx;
103  return append(t);
104  }
105  void append(const T *pt, exint count);
106  void appendMultiple(const T &t, exint count);
108  exint insert(const T &t, exint i)
109  { return insertImpl(t, i); }
111  { return insertImpl(std::move(t), i); }
112 
113  /// Adds a new element to the array (resizing if necessary) and forwards
114  /// the given arguments to T's constructor.
115  /// NOTE: Unlike append(), the arguments cannot reference any existing
116  /// elements in the array. Checking for and handling such cases would
117  /// remove most of the performance gain versus append(T(...)). Debug builds
118  /// will assert that the arguments are valid.
119  template <typename... S>
120  exint emplace_back(S&&... s);
121 
122  /// Assuming the array is sorted, it inserts item t maintaining the sorted
123  /// state of the array. It returns the index of the inserted item.
124  /// @note This is O(N^2) behaviour if you call it in a loop! Do not use.
125  /// @{
126  SYS_DEPRECATED_HDK(13.0)
128 
129  template <typename ComparatorBool>
130  SYS_DEPRECATED_HDK(13.0)
131  exint sortedInsert(const T &t, ComparatorBool is_less);
132  /// @}
133 
134  SYS_DEPRECATED_HDK(13.0)
136 
137  template <typename ComparatorBool>
138  SYS_DEPRECATED_HDK(13.0)
139  exint uniqueSortedInsert(const T &t, ComparatorBool is_less);
140 
141  /// Convenience method to perform binary search of a ascending sorted array
142  /// with no duplicates. Returns the index of the specified item, -1 if not
143  /// found.
144  exint uniqueSortedFind(const T &item, Comparator compare) const;
145  template <typename ComparatorBool>
146  exint uniqueSortedFind(const T &item, ComparatorBool is_less) const;
147 
148  /// Merge the given array into us.
149  /// If direction is -1, then it assumes us and 'other' are both already
150  /// sorted in descending order. Similarly, +1 means ascending.
151  /// If allow_dups is false, then it further assumes that both arrays have no
152  /// duplicates and will produce a result that also has no duplicates.
153  /// More work will be needed if you want allow_dups to mean remove duplicates
154  template <typename ComparatorBool>
155  void merge(const UT_Array<T> &other, int direction,
156  bool allow_dups, ComparatorBool is_less);
157 
158  bool hasSortedSubset(const UT_Array<T> &other,
159  Comparator compare) const;
160 
161  void sortedUnion(
162  const UT_Array<T> &other,
163  Comparator compare);
164  void sortedUnion(
165  const UT_Array<T> &other,
166  UT_Array<T> &result,
167  Comparator compare) const;
168  void sortedIntersection(
169  const UT_Array<T> &other,
170  Comparator compare);
171  void sortedIntersection(
172  const UT_Array<T> &other,
173  UT_Array<T> &result,
174  Comparator compare) const;
175  void sortedSetDifference(
176  const UT_Array<T> &other,
177  Comparator compare);
178  void sortedSetDifference(
179  const UT_Array<T> &other,
180  UT_Array<T> &result,
181  Comparator compare) const;
182 
183  /// Assuming the array is already a heap, it inserts item t maintaining
184  /// the heap. It returns the index of the inserted item.
185  exint heapPush(const T &t, Comparator compare);
186 
187  /// Assuming the array is already a heap, extracts the top (maximum)
188  /// element from the heap and returns it.
189  T heapPop(Comparator compare);
190 
191  /// Assuming the array is already a heap, return the top (maximum)
192  /// element.
193  const T & heapMax() const
194  {
195  UT_ASSERT_P(mySize > 0);
196  return myData[0];
197  }
198 
199  /// Takes another T array and concatenate it onto my end
200  exint concat(const UT_Array<T> &a);
201  /// Takes another T array and concatenate it onto my end
202  exint concat(UT_Array<T> &&a) noexcept;
203 
204  /// Insert an element "count" times at the given index. Return the index.
206 
207  /// An alias for unique element insertion at a certain index. Also used by
208  /// the other insertion methods.
210  { return insertImpl(t, index); }
211 
212  /// Return true if given index is valid.
214  { return (index >= 0 && index < mySize); }
215 
216  /// Remove one element from the array given the element itself or its
217  /// position in the list, and fill the gap by shifting the elements down
218  /// by one position. Return the index of the element remove or -1 if
219  /// the value was not found.
220  exint findAndRemove(const T &t);
222  {
223  return isValidIndex(index) ? removeAt(index) : -1;
224  }
226  {
227  if (mySize)
228  {
229  exint idx = --mySize;
230  trivialDestruct(myData[idx]);
231  }
232  }
233 
234  /// Remove the range [begin_i,end_i) of elements from the array.
235  void removeRange(exint begin_i, exint end_i);
236 
237  /// Remove the range [begin_i, end_i) of elements from this array and place
238  /// them in the dest array, shrinking/growing the dest array as necessary.
239  void extractRange(exint begin_i, exint end_i,
240  UT_Array<T>& dest);
241 
242  /// Removes all matching elements from the list, shuffling down and changing
243  /// the size appropriately.
244  /// Returns the number of elements left.
245  template <typename IsEqual>
246  exint removeIf(IsEqual is_equal);
247 
248  /// Remove all matching elements. Also sets the capacity of the array.
249  template <typename IsEqual>
250  void collapseIf(IsEqual is_equal)
251  {
252  removeIf(is_equal);
253  setCapacity(size());
254  }
255 
256  /// Move how_many objects starting at index src_idx to dst_idx;
257  /// This method will remove the elements at [src_idx, src_idx+how_many) and
258  /// then insert them at dst_idx. This method can be used in place of
259  /// the old shift() operation.
260  void move(exint src_idx, exint dst_idx, exint how_many);
261 
262  /// Cyclically shifts the entire array by how_many
263  void cycle(exint how_many);
264 
265  /// Quickly set the array to a single value.
266  void constant(const T &v);
267  /// Zeros the array if a POD type, else trivial constructs if a class type.
268  void zero();
269 
270  /// Search for t linearly using the '==' operator, starting at index s.
271  /// @returns the index of the matching element or (exint)-1.
272  exint find(const T &t, exint s = 0) const;
273 
274  /// Search for t via binary search using the function specified in the
275  /// parameter list, assuming the array is already sorted with respect to
276  /// compare.
277  /// @returns the index of the matching element or (exint)-1.
278  exint sortedFind(const T &t, Comparator compare) const;
279 
280  /// Reverses the array by swapping elements in mirrored locations.
281  void reverse();
282 
283  /// The fastest search possible, which does pointer arithmetic to find the
284  /// index of the element. WARNING: index() does no out-of-bounds checking.
285  /// @{
286  exint index(const T &t) const { return &t - myData; }
287  exint safeIndex(const T &t) const
288  {
289  return (&t >= myData && &t < (myData + mySize))
290  ? &t - myData : -1;
291  }
292  /// @}
293 
294  /// Sort the array using a comparison function that you must provide. t1 and
295  /// t2 are pointers to Thing. The comparison function uses strcmp()
296  /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
297  void sort(Comparator compare);
298 
299  /// Sort using std::sort. The ComparatorBool uses the less-than semantics
300  template <typename ComparatorBool>
301  void stdsort(ComparatorBool is_less)
302  {
303  std::sort(myData, myData + mySize, is_less);
304  }
305 
306  /// stableSort is both stable, so keeps equal elements in the same
307  /// order (note this is very useful for compatibility between
308  /// compilers) and templated.
309  /// Either use a bool sort function or make a utility class with
310  /// bool operator()(const T a, const T b)
311  /// the utility class lets you bind data to avoid globals.
312  /// The comparator returns true if a must occur before b in the list.
313  /// For sorting ascending, this is a less than operation.
314  template<typename ComparatorBool>
315  void stableSort(ComparatorBool is_less)
316  {
317  // No-op for small/empty arrays, avoiding out of
318  // bounds assert on array()
319  if (size() < 2)
320  return;
321 
322  std::stable_sort(array(), array() + size(), is_less);
323  }
324 
325  /// Comparator class for stableSortIndices
326  template <typename I, typename V, typename ComparatorBool>
328  {
329  public:
331  const ComparatorBool &compare)
332  : myValues(values)
333  , myCompare(compare)
334  {}
335  inline bool operator()(I a, I b) const
336  { return myCompare(myValues(a), myValues(b)); }
337  private:
338  const UT_Array<V> &myValues;
339  const ComparatorBool &myCompare;
340  };
341 
342  /// Sort indices array by the values indexed into this array using a
343  /// stable sorting algorithm. To reorder the array in such a way
344  /// that it would be sorted, or another array to be reordered the
345  /// same way, include UT_Permute.h and use:
346  /// UTinversePermute(values.getArray(), indices.getArray(),
347  /// values.size());
348  /// The ComparatorBool uses the less-than semantics.
349  /// I must be an integer type.
350  template <typename I, typename ComparatorBool>
352  ComparatorBool is_less) const
353  {
354  IndexedCompare<I, T, ComparatorBool> compare(*this, is_less);
355  std::stable_sort(indices.getArray(),
356  indices.getArray() + indices.size(), compare);
357  }
358 
359  /// Create an index array from 0..n-1 into this array and sort
360  /// it with stableSortIndices.
361  /// The index array will be resized & rebuilt by this.
362  template <typename I, typename ComparatorBool>
364  ComparatorBool is_less) const
365  {
366  indices.setSizeNoInit(size());
367  for (exint i = 0; i < size(); i++)
368  indices(i) = i;
369  stableSortIndices(indices, is_less);
370  }
371 
372  /// Sorts this array by an external key array. We assume a 1:1
373  /// corespondence between our own elements and those of the key
374  /// array. The comparator should be defined on the key type.
375  template <typename K, typename ComparatorBool>
376  void stableSortByKey(const UT_Array<K> &keys, ComparatorBool is_less)
377  {
378  UT_ASSERT(keys.size() == size());
379  if (keys.size() != size())
380  return;
382  keys.stableArgSort(indices, is_less);
383  UTinversePermute(getArray(), indices.getArray(), size());
384  }
385 
386  /// Assuming this array is sorted, remove all duplicate elements.
387  /// Returns the number of elements removed.
389 
390  /// Assuming this array is sorted, remove all duplicate elements using the
391  /// given binary predicate.
392  /// Returns the number of elements removed
393  template <typename CompareEqual>
394  exint sortedRemoveDuplicatesIf(CompareEqual compare_equal);
395 
396  /// Sort remove duplicates. Requires that equal elements are adjacent after
397  /// sorting.
398  template<typename ComparatorBool>
399  void sortAndRemoveDuplicates(ComparatorBool is_less)
400  {
401  stableSort(is_less);
403  }
404 
405  /// Partitions the array into values greater than or less than
406  /// the Nth element, returns the resulting partition number.
407  /// idx == 0 will get the minimum value, idx == size()-1 the
408  /// maximum value. This does modify this array!
409  template <typename ComparatorBool>
410  T selectNthLargest(exint idx, ComparatorBool is_less);
411 
412  /// Set the capacity of the array, i.e. grow it or shrink it. The
413  /// function copies the data after reallocating space for the array.
414  void setCapacity(exint newcapacity);
415  void setCapacityIfNeeded(exint mincapacity)
416  {
417  if (capacity() < mincapacity)
418  setCapacity(mincapacity);
419  }
420  /// If the capacity is smaller than mincapacity, expand the array
421  /// to at least mincapacity and to at least a constant factor of the
422  /// array's previous capacity, to avoid having a linear number of
423  /// reallocations in a linear number of calls to bumpCapacity.
424  void bumpCapacity(exint mincapacity)
425  {
426  if (capacity() >= mincapacity)
427  return;
428  // The following 4 lines are just
429  // SYSmax(mincapacity, UTbumpAlloc(capacity())), avoiding SYSmax
430  exint bumped = UTbumpAlloc(capacity());
431  exint newcapacity = mincapacity;
432  if (bumped > mincapacity)
433  newcapacity = bumped;
434  setCapacity(newcapacity);
435  }
436 
437  /// First bumpCapacity to ensure that there's space for newsize,
438  /// expanding either not at all or by at least a constant factor
439  /// of the array's previous capacity,
440  /// then set the size to newsize.
441  void bumpSize(exint newsize)
442  {
443  bumpCapacity(newsize);
444  setSize(newsize);
445  }
446  /// NOTE: bumpEntries() will be deprecated in favour of bumpSize() in a
447  /// future version.
448  void bumpEntries(exint newsize)
449  {
450  bumpSize(newsize);
451  }
452 
453  /// Query the capacity, i.e. the allocated length of the array.
454  /// NOTE: capacity() >= size().
455  exint capacity() const { return myCapacity; }
456  /// Query the size, i.e. the number of occupied elements in the array.
457  /// NOTE: capacity() >= size().
458  exint size() const { return mySize; }
459  /// Alias of size(). size() is preferred.
460  exint entries() const { return mySize; }
461  /// Returns true iff there are no occupied elements in the array.
462  bool isEmpty() const { return mySize==0; }
463 
464  /// Returns the amount of memory used by this UT_Array.
465  /// If inclusive is false, it only counts the memory of the array.
466  /// This is often necessary to avoid double-counting, e.g. if this
467  /// UT_Array is a member variable of a class whose memory is already
468  /// being counted by the caller.
469  int64 getMemoryUsage(bool inclusive=false) const
470  {
471  return (inclusive ? sizeof(*this) : 0) + capacity()*sizeof(T); // NOLINT
472  }
473 
474  /// Set the size, the number of occupied elements in the array.
475  /// NOTE: This will not do bumpCapacity, so if you call this
476  /// n times to increase the size, it may take
477  /// n^2 time.
478  void setSize(exint newsize)
479  {
480  if (newsize < 0)
481  newsize = 0;
482  if (newsize == mySize)
483  return;
484  setCapacityIfNeeded(newsize);
485  if (mySize > newsize)
486  trivialDestructRange(myData + newsize, mySize - newsize);
487  else // newsize > mySize
488  trivialConstructRange(myData + mySize, newsize - mySize);
489  mySize = newsize;
490  }
491  void setSizeIfNeeded(exint minsize)
492  {
493  if (size() >= minsize)
494  return;
495  setSize(minsize);
496  }
497  /// Alias of setSize(). setSize() is preferred.
498  void entries(exint newsize)
499  {
500  setSize(newsize);
501  }
502  /// Set the size, but unlike setSize(newsize), this function
503  /// will not initialize new POD elements to zero. Non-POD data types
504  /// will still have their constructors called.
505  /// This function is faster than setSize(ne) if you intend to fill in
506  /// data for all elements.
507  void setSizeNoInit(exint newsize)
508  {
509  if (newsize < 0)
510  newsize = 0;
511  if (newsize == mySize)
512  return;
513  setCapacityIfNeeded(newsize);
514  if (mySize > newsize)
515  trivialDestructRange(myData + newsize, mySize - newsize);
516  else if (!isPOD()) // newsize > mySize
517  trivialConstructRange(myData + mySize, newsize - mySize);
518  mySize = newsize;
519  }
520 
521  /// Decreases, but never expands, to the given maxsize.
522  void truncate(exint maxsize)
523  {
524  if (maxsize >= 0 && size() > maxsize)
525  setSize(maxsize);
526  }
527  /// Resets list to an empty list.
528  void clear()
529  {
530  // Don't call setSize(0) since it supports growing the array
531  // which requires a default constructor. Avoiding it allows
532  // this to be used on types that lack a default constructor.
533  trivialDestructRange(myData, mySize);
534  mySize = 0;
535  }
536 
537  /// Assign array a to this array by copying each of a's elements with
538  /// memcpy for POD types, and with copy construction for class types.
540 
541  /// Replace the contents with those from the initializer_list ilist
542  UT_Array<T> & operator=(std::initializer_list<T> ilist);
543 
544  /// Move the contents of array a to this array.
546 
547  /// Compare two array and return true if they are equal and false otherwise.
548  /// Two elements are checked against each other using operator '==' or
549  /// compare() respectively.
550  /// NOTE: The capacities of the arrays are not checked when
551  /// determining whether they are equal.
552  bool operator==(const UT_Array<T> &a) const;
553  bool operator!=(const UT_Array<T> &a) const;
554  int isEqual(const UT_Array<T> &a, Comparator compare) const;
555 
556  /// Subscript operator
557  /// NOTE: This does NOT do any bounds checking unless paranoid
558  /// asserts are enabled.
560  {
561  UT_ASSERT_P(i >= 0 && i < mySize);
562  return myData[i];
563  }
564  /// Const subscript operator
565  /// NOTE: This does NOT do any bounds checking unless paranoid
566  /// asserts are enabled.
567  const T & operator()(exint i) const
568  {
569  UT_ASSERT_P(i >= 0 && i < mySize);
570  return myData[i];
571  }
572 
573  /// Subscript operator
574  /// NOTE: This does NOT do any bounds checking unless paranoid
575  /// asserts are enabled.
577  {
578  UT_ASSERT_P(i >= 0 && i < mySize);
579  return myData[i];
580  }
581  /// Const subscript operator
582  /// NOTE: This does NOT do any bounds checking unless paranoid
583  /// asserts are enabled.
584  const T & operator[](exint i) const
585  {
586  UT_ASSERT_P(i >= 0 && i < mySize);
587  return myData[i];
588  }
589 
590  /// forcedRef(exint) will grow the array if necessary, initializing any
591  /// new elements to zero for POD types and default constructing for
592  /// class types.
594  {
595  UT_ASSERT_P(i >= 0);
596  if (i >= mySize)
597  bumpSize(i+1);
598  return myData[i];
599  }
600 
601  /// forcedGet(exint) does NOT grow the array, and will return default
602  /// objects for out of bound array indices.
603  T forcedGet(exint i) const
604  {
605  return (i >= 0 && i < mySize) ? myData[i] : T();
606  }
607 
608  T & last()
609  {
610  UT_ASSERT_P(mySize);
611  return myData[mySize-1];
612  }
613  const T & last() const
614  {
615  UT_ASSERT_P(mySize);
616  return myData[mySize-1];
617  }
618 
619  /// Apply a user-defined function to each element of the array
620  /// as int as the function returns zero. If apply_func returns
621  /// 1, apply() stops traversing the list and returns the current
622  /// index; otherwise, apply() returns the size.
623  exint apply(int (*apply_func)(T &t, void *d), void *d);
624 
625  template <typename BinaryOp>
626  T accumulate(const T &init_value, BinaryOp add) const;
627 
628  T * getArray() const { return myData; }
629  const T * getRawArray() const { return myData; }
630 
631  T * array() { return myData; }
632  const T * array() const { return myData; }
633 
634  T * data() { return myData; }
635  const T * data() const { return myData; }
636 
637  /// This method allows you to swap in a new raw T array, which must be
638  /// the same size as myCapacity. Use caution with this method.
639  T * aliasArray(T *newdata)
640  { T *data = myData; myData = newdata; return data; }
641 
642  template <typename IT, bool FORWARD>
643  class base_iterator :
644  public std::iterator<std::random_access_iterator_tag, T, exint>
645  {
646  public:
647  typedef IT& reference;
648  typedef IT* pointer;
649 
650  // Note: When we drop gcc 4.4 support and allow range-based for
651  // loops, we should also drop atEnd(), which means we can drop
652  // myEnd here.
653  base_iterator() : myCurrent(nullptr), myEnd(nullptr) {}
654 
655  // Allow iterator to const_iterator conversion
656  template<typename EIT>
658  : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
659 
661  { return FORWARD ? myCurrent : myCurrent - 1; }
662 
664  { return FORWARD ? *myCurrent : myCurrent[-1]; }
665 
666  reference item() const
667  { return FORWARD ? *myCurrent : myCurrent[-1]; }
668 
670  { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; }
671 
672  /// Pre-increment operator
674  {
675  if (FORWARD) ++myCurrent; else --myCurrent;
676  return *this;
677  }
678  /// Post-increment operator
680  {
681  base_iterator tmp = *this;
682  if (FORWARD) ++myCurrent; else --myCurrent;
683  return tmp;
684  }
685  /// Pre-decrement operator
687  {
688  if (FORWARD) --myCurrent; else ++myCurrent;
689  return *this;
690  }
691  /// Post-decrement operator
693  {
694  base_iterator tmp = *this;
695  if (FORWARD) --myCurrent; else ++myCurrent;
696  return tmp;
697  }
698 
700  {
701  if (FORWARD)
702  myCurrent += n;
703  else
704  myCurrent -= n;
705  return *this;
706  }
708  {
709  if (FORWARD)
710  return base_iterator(myCurrent + n, myEnd);
711  else
712  return base_iterator(myCurrent - n, myEnd);
713  }
714 
716  { return (*this) += (-n); }
718  { return (*this) + (-n); }
719 
720  bool atEnd() const { return myCurrent == myEnd; }
721  void advance() { this->operator++(); }
722 
723  // Comparators
724  template<typename ITR, bool FR>
726  { return myCurrent == r.myCurrent; }
727 
728  template<typename ITR, bool FR>
730  { return myCurrent != r.myCurrent; }
731 
732  template<typename ITR>
733  bool operator<(const base_iterator<ITR, FORWARD> &r) const
734  {
735  if (FORWARD)
736  return myCurrent < r.myCurrent;
737  else
738  return r.myCurrent < myCurrent;
739  }
740 
741  template<typename ITR>
743  {
744  if (FORWARD)
745  return myCurrent > r.myCurrent;
746  else
747  return r.myCurrent > myCurrent;
748  }
749 
750  template<typename ITR>
751  bool operator<=(const base_iterator<ITR, FORWARD> &r) const
752  {
753  if (FORWARD)
754  return myCurrent <= r.myCurrent;
755  else
756  return r.myCurrent <= myCurrent;
757  }
758 
759  template<typename ITR>
761  {
762  if (FORWARD)
763  return myCurrent >= r.myCurrent;
764  else
765  return r.myCurrent >= myCurrent;
766  }
767 
768  // Difference operator for std::distance
769  template<typename ITR>
771  {
772  if (FORWARD)
773  return exint(myCurrent - r.myCurrent);
774  else
775  return exint(r.myCurrent - myCurrent);
776  }
777 
778 
779  protected:
780  friend class UT_Array<T>;
781  base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
782  private:
783 
784  IT *myCurrent;
785  IT *myEnd;
786  };
787 
788  typedef base_iterator<T, true> iterator;
789  typedef base_iterator<const T, true> const_iterator;
790  typedef base_iterator<T, false> reverse_iterator;
791  typedef base_iterator<const T, false> const_reverse_iterator;
792  typedef const_iterator traverser; // For backward compatibility
793 
794  /// Begin iterating over the array. The contents of the array may be
795  /// modified during the traversal.
797  {
798  return iterator(myData, myData + mySize);
799  }
800  /// End iterator.
802  {
803  return iterator(myData + mySize,
804  myData + mySize);
805  }
806 
807  /// Begin iterating over the array. The array may not be modified during
808  /// the traversal.
810  {
811  return const_iterator(myData, myData + mySize);
812  }
813  /// End const iterator. Consider using it.atEnd() instead.
815  {
816  return const_iterator(myData + mySize,
817  myData + mySize);
818  }
819 
820  /// Begin iterating over the array in reverse.
822  {
823  return reverse_iterator(myData + mySize,
824  myData);
825  }
826  /// End reverse iterator.
828  {
829  return reverse_iterator(myData, myData);
830  }
831  /// Begin iterating over the array in reverse.
833  {
834  return const_reverse_iterator(myData + mySize,
835  myData);
836  }
837  /// End reverse iterator. Consider using it.atEnd() instead.
839  {
840  return const_reverse_iterator(myData, myData);
841  }
842 
844  { return UT_IteratorRange<iterator>(begin(), end()); }
846  { return UT_IteratorRange<const_iterator>(begin(), end()); }
847 
852 
853  /// Remove item specified by the reverse_iterator.
854  void removeItem(const reverse_iterator &it)
855  {
856  removeAt(&it.item() - myData);
857  }
858 
859 
860  /// Very dangerous methods to share arrays.
861  /// The array is not aware of the sharing, so ensure you clear
862  /// out the array prior a destructor or setCapacity operation.
864  {
865  myData = src.myData;
866  myCapacity = src.myCapacity;
867  mySize = src.mySize;
868  }
869  void unsafeShareData(T *src, exint srcsize)
870  {
871  myData = src;
872  myCapacity = srcsize;
873  mySize = srcsize;
874  }
876  {
877  myData = src;
878  mySize = size;
879  myCapacity = capacity;
880  }
882  {
883  myData = nullptr;
884  myCapacity = 0;
885  mySize = 0;
886  }
887 
888  /// Returns true if the data used by the array was allocated on the heap.
889  inline bool isHeapBuffer() const
890  {
891  return (myData != (T *)(((char*)this) + sizeof(*this)));
892  }
893  inline bool isHeapBuffer(T* data) const
894  {
895  return (data != (T *)(((char*)this) + sizeof(*this)));
896  }
897 
898 protected:
899  // Check whether T may have a constructor, destructor, or copy
900  // constructor. This test is conservative in that some POD types will
901  // not be recognized as POD by this function. To mark your type as POD,
902  // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
903  static constexpr SYS_FORCE_INLINE bool isPOD()
904  {
905  return SYSisPOD<T>();
906  }
907 
908  /// Implements both append(const T &) and append(T &&) via perfect
909  /// forwarding. Unlike the variadic emplace_back(), its argument may be a
910  /// reference to another element in the array.
911  template <typename S>
912  exint appendImpl(S &&s);
913 
914  /// Similar to appendImpl() but for insertion.
915  template <typename S>
917 
918  /// In debug builds, verifies that the arguments to emplace_back() will not
919  /// be invalidated when realloc() is called.
920  template <typename First, typename... Rest>
921  void validateEmplaceArgs(First &&first, Rest&&... rest) const
922  {
924  static_cast<const void *>(&first) <
925  static_cast<const void *>(myData) ||
926  static_cast<const void *>(&first) >=
927  static_cast<const void *>(myData + mySize),
928  "Argument cannot reference an existing element in the array.");
929 
930  validateEmplaceArgs(std::forward<Rest>(rest)...);
931  }
932 
933  /// Base case for validateEmplaceArgs().
934  void validateEmplaceArgs() const
935  {
936  }
937 
938  // Construct the given type
939  template <typename... S>
940  static void construct(T &dst, S&&... s)
941  {
942  new (&dst) T(std::forward<S>(s)...);
943  }
944 
945  // Copy construct the given type
946  static void copyConstruct(T &dst, const T &src)
947  {
948  if (isPOD())
949  dst = src;
950  else
951  new (&dst) T(src);
952  }
953  static void copyConstructRange(T *dst, const T *src, exint n)
954  {
955  if (isPOD())
956  {
957  if (n > 0)
958  {
959  ::memcpy((void *)dst, (const void *)src,
960  n * sizeof(T)); // NOLINT
961  }
962  }
963  else
964  {
965  for (exint i = 0; i < n; i++)
966  new (&dst[i]) T(src[i]);
967  }
968  }
969 
970  /// Element Constructor
971  static void trivialConstruct(T &dst)
972  {
973  if (!isPOD())
974  new (&dst) T();
975  else
976  memset((void *)&dst, 0, sizeof(T));
977  }
979  {
980  if (!isPOD())
981  {
982  for (exint i = 0; i < n; i++)
983  new (&dst[i]) T();
984  }
985  else if (n == 1)
986  {
987  // Special case for n == 1. If the size parameter
988  // passed to memset is known at compile time, this
989  // function call will be inlined. This results in
990  // much faster performance than a real memset
991  // function call which is required in the case
992  // below, where n is not known until runtime.
993  // This makes calls to append() much faster.
994  memset((void *)dst, 0, sizeof(T));
995  }
996  else
997  memset((void *)dst, 0, sizeof(T) * n);
998  }
999 
1000  /// Element Destructor
1002  {
1003  if (!isPOD())
1004  dst.~T();
1005  }
1007  {
1008  if (!isPOD())
1009  {
1010  for (exint i = 0; i < n; i++)
1011  dst[i].~T();
1012  }
1013  }
1014 
1015 private:
1016  /// Pointer to the array of elements of type T
1017  T *myData;
1018 
1019  /// The number of elements for which we have allocated memory
1020  exint myCapacity;
1021 
1022  /// The actual number of valid elements in the array
1023  exint mySize;
1024 
1025  // The guts of the remove() methods.
1026  exint removeAt(exint index);
1027 
1028  T * allocateCapacity(exint num_items);
1029 
1030  template<typename OS, typename S>
1031  friend OS &operator<<(OS &os, const UT_Array<S> &d);
1032 
1033  /// Friend specialization of std::swap() to use UT_String::swap()
1034  /// @internal This is needed because standard std::swap() implementations
1035  /// will try to copy the UT_String objects, causing hardened strings to
1036  /// become weak.
1037  friend void swap(UT_Array<T>& a, UT_Array<T>& b) { a.swap(b); }
1038 };
1039 
1040 // Assigns src to dest, using the default C++ conversion operator.
1041 template <typename T, typename S>
1042 void
1044 {
1045  exint n = src.size();
1046  dest.setCapacity(n);
1047  dest.setSize(n);
1048  for (exint i = 0; i < n; i++)
1049  dest(i) = T(src(i));
1050 }
1051 template <typename T, typename S>
1052 void
1054 {
1055  dest.setCapacity(n);
1056  dest.setSize(n);
1057  for (exint i = 0; i < n; i++)
1058  dest(i) = T(src[i]);
1059 }
1060 template <typename T, typename S>
1061 void
1063 {
1064  // We assume here that dest has enough memory for src.size()
1065  exint n = src.size();
1066  for (exint i = 0; i < n; i++)
1067  dest[i] = T(src(i));
1068 }
1069 template <typename T, typename S>
1070 void
1071 UTconvertArray(T *dest, const S *src, int64 n)
1072 {
1073  // We assume here that dest has enough memory for n elements
1074  for (int64 i = 0; i < n; i++)
1075  dest[i] = T(src[i]);
1076 }
1077 
1078 #include "UT_ArrayImpl.h"
1079 
1080 
1081 template<typename OS, typename S>
1082 inline OS &
1083 operator<<(OS &os, const UT_Array<S> &d)
1084 {
1085  os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
1086  return os;
1087 }
1088 
1089 // Overload for custom formatting of a UT_StringArray with UTformat.
1090 template <typename T> UT_API size_t
1091 format(char *buffer, size_t bufsize, const UT_Array<T> &v);
1092 
1093 /// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
1094 /// its elements
1095 template <template <typename> class ArrayT, typename T>
1096 static inline int64
1097 UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
1098 {
1099  int64 mem = inclusive ? sizeof(arr) : 0;
1100  mem += arr.getMemoryUsage(false);
1101  for (auto &&item : arr)
1102  mem += item.getMemoryUsage(false);
1103  return mem;
1104 }
1105 
1106 /// Utility to sort array using operator<
1107 template <typename T>
1108 static inline void
1109 UTsort(UT_Array<T> &arr)
1110 {
1111  arr.stdsort([](const T &a, const T &b) { return a < b; });
1112 }
1113 
1114 /// Utility to sort array using operator< and remove duplicates
1115 template <typename T>
1116 static inline void
1117 UTsortAndRemoveDuplicates(UT_Array<T> &arr)
1118 {
1119  arr.sortAndRemoveDuplicates([](const T &a, const T &b) { return a < b; });
1120 }
1121 
1122 // For UT::ArraySet.
1123 namespace UT
1124 {
1125 template <typename T>
1126 struct DefaultClearer;
1127 
1128 template <typename T>
1130 {
1131  static void clear(UT_Array<T> &v) { v.setCapacity(0); }
1132  static bool isClear(const UT_Array<T> &v) { return v.capacity() == 0; }
1134  {
1135  new ((void *)p) UT_Array<T>();
1136  }
1137  static const bool clearNeedsDestruction = false;
1138 };
1139 } // namespace UT
1140 
1141 #endif // __UT_ARRAY_H_INCLUDED__
reference operator*() const
Definition: UT_Array.h:663
GLdouble s
Definition: glew.h:1390
base_iterator & operator++()
Pre-increment operator.
Definition: UT_Array.h:673
int isEqual(const UT_Array< T > &a, Comparator compare) const
Definition: UT_ArrayImpl.h:956
base_iterator & operator--()
Pre-decrement operator.
Definition: UT_Array.h:686
T & last()
Definition: UT_Array.h:608
exint insert(T &&t, exint i)
Definition: UT_Array.h:110
IndexedCompare(const UT_Array< V > &values, const ComparatorBool &compare)
Definition: UT_Array.h:330
exint find(const T &t, exint s=0) const
Definition: UT_ArrayImpl.h:718
const T & operator[](exint i) const
Definition: UT_Array.h:584
void validateEmplaceArgs(First &&first, Rest &&...rest) const
Definition: UT_Array.h:921
exint append(const T &t)
Definition: UT_Array.h:96
const T * data() const
Definition: UT_Array.h:635
const T * getRawArray() const
Definition: UT_Array.h:629
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:889
pointer operator->() const
Definition: UT_Array.h:660
base_iterator operator+(exint n) const
Definition: UT_Array.h:707
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:934
GLsizeiptr size
Definition: glew.h:1681
GLenum src
Definition: glew.h:2410
void sortAndRemoveDuplicates(ComparatorBool is_less)
Definition: UT_Array.h:399
GLsizei bufsize
Definition: glew.h:2581
bool operator!=(const UT_Array< T > &a) const
Definition: UT_ArrayImpl.h:949
void setSizeIfNeeded(exint minsize)
Definition: UT_Array.h:491
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
SYS_FORCE_INLINE void removeLast()
Definition: UT_Array.h:225
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
void unsafeShareData(T *src, exint size, exint capacity)
Definition: UT_Array.h:875
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)
void extractRange(exint begin_i, exint end_i, UT_Array< T > &dest)
Definition: UT_ArrayImpl.h:554
void collapseIf(IsEqual is_equal)
Remove all matching elements. Also sets the capacity of the array.
Definition: UT_Array.h:250
T * aliasArray(T *newdata)
Definition: UT_Array.h:639
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:507
bool isValidIndex(exint index) const
Return true if given index is valid.
Definition: UT_Array.h:213
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
GLint GLsizei const GLuint64 * values
Definition: glew.h:3612
base_iterator< const T, false > const_reverse_iterator
Definition: UT_Array.h:791
static void trivialConstruct(T &dst)
Element Constructor.
Definition: UT_Array.h:971
friend void swap(UT_Array< T > &a, UT_Array< T > &b)
Definition: UT_Array.h:1037
UT_API size_t format(char *buffer, size_t bufsize, const UT_Array< T > &v)
int64 exint
Definition: SYS_Types.h:125
void move(exint src_idx, exint dst_idx, exint how_many)
Definition: UT_ArrayImpl.h:584
const_iterator begin() const
Definition: UT_Array.h:809
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:469
void bumpEntries(exint newsize)
Definition: UT_Array.h:448
const T & heapMax() const
Definition: UT_Array.h:193
void cycle(exint how_many)
Cyclically shifts the entire array by how_many.
Definition: UT_ArrayImpl.h:667
exint removeIndex(exint index)
Definition: UT_Array.h:221
T * array()
Definition: UT_Array.h:631
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:301
const GLint * first
Definition: glew.h:1528
const_reverse_iterator rend() const
End reverse iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:838
#define UT_API
Definition: UT_API.h:13
bool isHeapBuffer(T *data) const
Definition: UT_Array.h:893
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:903
const GLdouble * v
Definition: glew.h:1391
exint concat(const UT_Array< T > &a)
Takes another T array and concatenate it onto my end.
Definition: UT_ArrayImpl.h:415
exint append(const T &t, bool check_dup)
Definition: UT_Array.h:98
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:137
exint index(const T &t) const
Definition: UT_Array.h:286
bool operator>=(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:760
exint uniqueSortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:271
reference item() const
Definition: UT_Array.h:666
void bumpCapacity(exint mincapacity)
Definition: UT_Array.h:424
static bool isClear(const UT_Array< T > &v)
Definition: UT_Array.h:1132
void unsafeClearData()
Definition: UT_Array.h:881
exint size() const
Definition: UT_Array.h:458
void setSize(exint newsize)
Definition: UT_Array.h:478
bool operator==(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:725
static void trivialDestructRange(T *dst, exint n)
Definition: UT_Array.h:1006
base_iterator operator-(exint n) const
Definition: UT_Array.h:717
void bumpSize(exint newsize)
Definition: UT_Array.h:441
bool operator>(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:742
base_iterator< T, false > reverse_iterator
Definition: UT_Array.h:790
void unsafeShareData(T *src, exint srcsize)
Definition: UT_Array.h:869
exint append(T &&t)
Definition: UT_Array.h:97
exint operator-(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:770
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, ROI roi={}, int nthreads=0)
const_reverse_iterator rbegin() const
Begin iterating over the array in reverse.
Definition: UT_Array.h:832
exint safeIndex(const T &t) const
Definition: UT_Array.h:287
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:777
void stableSortByKey(const UT_Array< K > &keys, ComparatorBool is_less)
Definition: UT_Array.h:376
exint apply(int(*apply_func)(T &t, void *d), void *d)
Definition: UT_ArrayImpl.h:970
reverse_iterator rbegin()
Begin iterating over the array in reverse.
Definition: UT_Array.h:821
exint emplace_back(S &&...s)
Definition: UT_ArrayImpl.h:172
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:940
void entries(exint newsize)
Alias of setSize(). setSize() is preferred.
Definition: UT_Array.h:498
T & operator[](exint i)
Definition: UT_Array.h:576
const T & operator()(exint i) const
Definition: UT_Array.h:567
GLuint buffer
Definition: glew.h:1680
GLint GLenum GLsizei GLint GLsizei const void * data
Definition: glew.h:1379
reference operator[](exint n) const
Definition: UT_Array.h:669
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
exint insertAt(const T &t, exint index)
Definition: UT_Array.h:209
GLuint GLuint GLsizei GLenum const void * indices
Definition: glew.h:1253
T accumulate(const T &init_value, BinaryOp add) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
exint capacity() const
Definition: UT_Array.h:455
base_iterator< T, true > iterator
Definition: UT_Array.h:788
static void clearConstruct(UT_Array< T > *p)
Definition: UT_Array.h:1133
static SYS_FORCE_INLINE void trivialDestruct(T &dst)
Element Destructor.
Definition: UT_Array.h:1001
GLsizei n
Definition: glew.h:4040
const GLfloat * c
Definition: glew.h:16296
exint sortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:220
UT_IteratorRange< reverse_iterator > rrange()
Definition: UT_Array.h:848
GLenum GLenum dst
Definition: glew.h:2410
exint insert(const T &t, exint i)
Definition: UT_Array.h:108
exint appendImpl(S &&s)
Definition: UT_ArrayImpl.h:149
base_iterator(const base_iterator< EIT, FORWARD > &src)
Definition: UT_Array.h:657
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:196
static void trivialConstructRange(T *dst, exint n)
Definition: UT_Array.h:978
iterator begin()
Definition: UT_Array.h:796
long long int64
Definition: SYS_Types.h:116
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
base_iterator(IT *c, IT *e)
Definition: UT_Array.h:781
T forcedGet(exint i) const
Definition: UT_Array.h:603
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:946
#define SYS_DEPRECATED_HDK(__V__)
exint removeIf(IsEqual is_equal)
Definition: UT_ArrayImpl.h:635
const_iterator end() const
End const iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:814
base_iterator & operator-=(exint n)
Definition: UT_Array.h:715
exint sortedRemoveDuplicates()
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:863
reverse_iterator rend()
End reverse iterator.
Definition: UT_Array.h:827
exint append()
Definition: UT_Array.h:95
bool atEnd() const
Definition: UT_Array.h:720
bool operator()(I a, I b) const
Definition: UT_Array.h:335
bool operator!=(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:729
exint sortedRemoveDuplicatesIf(CompareEqual compare_equal)
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:460
bool hasSortedSubset(const UT_Array< T > &other, Comparator compare) const
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLfloat GLfloat p
Definition: glew.h:16321
base_iterator & operator+=(exint n)
Definition: UT_Array.h:699
void sortedSetDifference(const UT_Array< T > &other, Comparator compare)
void sortedUnion(const UT_Array< T > &other, Comparator compare)
T value_type
Definition: UT_Array.h:43
UT_Array(exint capacity=0)
Construct based on given capacity with a size of 0.
Definition: UT_Array.h:72
T selectNthLargest(exint idx, ComparatorBool is_less)
Definition: UT_ArrayImpl.h:760
T * data()
Definition: UT_Array.h:634
base_iterator operator--(int)
Post-decrement operator.
Definition: UT_Array.h:692
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
GLuint GLuint GLsizei count
Definition: glew.h:1253
const T & last() const
Definition: UT_Array.h:613
const T * array() const
Definition: UT_Array.h:632
static void clear(UT_Array< T > &v)
Definition: UT_Array.h:1131
int(* Comparator)(const T *, const T *)
Definition: UT_Array.h:45
void sort(Comparator compare)
Definition: UT_ArrayImpl.h:752
base_iterator< const T, true > const_iterator
Definition: UT_Array.h:789
void stableArgSort(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:363
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:522
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
void removeItem(const reverse_iterator &it)
Remove item specified by the reverse_iterator.
Definition: UT_Array.h:854
GLuint64EXT * result
Definition: glew.h:14007
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:135
void sortedIntersection(const UT_Array< T > &other, Comparator compare)
void UTconvertArray(UT_Array< T > &dest, const UT_Array< S > &src)
Definition: UT_Array.h:1043
Comparator class for stableSortIndices.
Definition: UT_Array.h:327
ImageBuf OIIO_API add(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
#define const
Definition: zconf.h:214
void stableSort(ComparatorBool is_less)
Definition: UT_Array.h:315
UT_Array(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:37
T & forcedRef(exint i)
Definition: UT_Array.h:593
void clear()
Resets list to an empty list.
Definition: UT_Array.h:528
void stableSortIndices(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:351
UT_IteratorRange< iterator > range()
Definition: UT_Array.h:843
UT_IteratorRange< const_iterator > range() const
Definition: UT_Array.h:845
const_iterator traverser
Definition: UT_Array.h:792
T & operator()(exint i)
Definition: UT_Array.h:559
GA_API const UT_StringHolder rest
T heapPop(Comparator compare)
Definition: UT_ArrayImpl.h:378
exint heapPush(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:361
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
void reverse()
Reverses the array by swapping elements in mirrored locations.
Definition: UT_ArrayImpl.h:743
T * getArray() const
Definition: UT_Array.h:628
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
base_iterator operator++(int)
Post-increment operator.
Definition: UT_Array.h:679
void swap(UT_Array< T > &other)
Definition: UT_ArrayImpl.h:113
exint insert(exint index)
Definition: UT_ArrayImpl.h:123
iterator end()
End iterator.
Definition: UT_Array.h:801
exint findAndRemove(const T &t)
Definition: UT_ArrayImpl.h:517
UT_IteratorRange< const_reverse_iterator > rrange() const
Definition: UT_Array.h:850
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:462
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