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