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