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 #include "UT_LabeledCapacity.h"
59 
60 #include <SYS/SYS_Compiler.h>
61 #include <SYS/SYS_Deprecated.h>
62 #include <SYS/SYS_Inline.h>
63 #include <SYS/SYS_Types.h>
64 #include <SYS/SYS_TypeTraits.h>
65 #include <SYS/SYS_TypeDecorate.h>
66 
67 #include <algorithm>
68 #include <initializer_list>
69 #include <iterator>
70 #include <type_traits>
71 #include <utility>
72 
73 #include <string.h>
74 
75 // Enable this to encode labeled capacity using a wrapper class rather than
76 // directly as an integer type. This allows the compiler to catch cases
77 // where the numeric value of the encoding which includes the label bit
78 // is accidentally used directly as a capacity value.
79 #undef UT_ARRAY_STRICT_LABELED_CAPACITY
80 
81 // Constructor tags for UT_Array
82 struct UT_ArrayCT
83 {
84  static constexpr struct ExternalCapacity{} EXTERNAL_CAPACITY{};
85  static constexpr struct ExternalMove{} EXTERNAL_MOVE{};
86  static constexpr struct GeneralizedMove{} GENERALIZED_MOVE{};
87 };
88 
89 template <typename T>
90 class UT_Array
91 {
92 public:
93  typedef T value_type;
94 
95  typedef int (*Comparator)(const T *, const T *);
96 
97  /// Copy constructor. It duplicates the data.
98  /// It's marked explicit so that it's not accidentally passed by value.
99  /// You can always pass by reference and then copy it, if needed.
100  /// If you have a line like:
101  /// UT_Array<int> a = otherarray;
102  /// and it really does need to copy instead of referencing,
103  /// you can rewrite it as:
104  /// UT_Array<int> a(otherarray);
105  explicit UT_Array(const UT_Array<T> &a);
106 
107  /// Move constructor. Steals the working data from the original.
108  UT_Array(UT_Array<T> &&a) noexcept;
109 
110  /// Construct based on given capacity and size
111  UT_Array(const exint capacity, const exint size);
112 
113  /// Construct based on given capacity with a size of 0
114  explicit UT_Array(const exint capacity = 0);
115 
116  /// Construct with the contents of an initializer list
117  /// If you are wondering why we mark this as explicit...
118  /// Imagine you have the following:
119  /// void foo(int i); // 1
120  /// void foo(UT_Array<int>); // 2
121  /// Without explicit you can do this
122  /// foo({1})
123  /// and function 1 will be called when you probably meant
124  /// for function 2 to be called.
125  explicit UT_Array(std::initializer_list<T> init);
126 
127  ~UT_Array();
128 
129  void swap(UT_Array<T> &other);
130 
131  /// Append an element to the current elements and return its index in the
132  /// array, or insert the element at a specified position; if necessary,
133  /// insert() grows the array to accommodate the element. The insert
134  /// methods use the assignment operator '=' to place the element into the
135  /// right spot; be aware that '=' works differently on objects and pointers.
136  /// The test for duplicates uses the logical equal operator '=='; as with
137  /// '=', the behaviour of the equality operator on pointers versus objects
138  /// is not the same.
139  /// Use the subscript operators instead of insert() if you are appending
140  /// to the array, or if you don't mind overwriting the element already
141  /// inserted at the given index.
142  exint append() { return insert(mySize); }
143  exint append(const T &t) { return appendImpl(t); }
144  exint append(T &&t) { return appendImpl(std::move(t)); }
145  exint append(const T &t, bool check_dup)
146  {
147  exint idx;
148  if (check_dup && ((idx = find(t)) != -1))
149  return idx;
150  return append(t);
151  }
152  void append(const T *pt, exint count);
153  void appendMultiple(const T &t, exint count);
155  exint insert(const T &t, exint i)
156  { return insertImpl(t, i); }
158  { return insertImpl(std::move(t), i); }
159 
160  /// Adds a new element to the array (resizing if necessary) and forwards
161  /// the given arguments to T's constructor.
162  /// NOTE: Unlike append(), the arguments cannot reference any existing
163  /// elements in the array. Checking for and handling such cases would
164  /// remove most of the performance gain versus append(T(...)). Debug builds
165  /// will assert that the arguments are valid.
166  template <typename... S>
167  exint emplace_back(S&&... s);
168 
169 protected:
170 
171  // The constructors below create a UT_Array with an external data buffer
172  // that's not allocated by UT_Array itself.
173  // This is used by UT_SmallArray to create UT_Array superclass objects
174  // that have a nonheap data buffer, created on the stack.
175 
176  explicit UT_Array(
177  const UT_ArrayCT::ExternalCapacity,
178  T *external_data,
179  const exint external_capacity
180  );
181 
182  explicit UT_Array(
183  const UT_ArrayCT::ExternalMove,
184  T *external_data,
185  const exint external_capacity,
186  UT_Array&& a
187  );
188 
189 private:
190 
191  // Move construct a UT_Array that uses (data, capacity) as its buffer.
192  // This constructor works both for an externally provided
193  // buffer (e.g., the UT_SmallArray case) and
194  // for a heap buffer that's allocated and owned by UT_Array itself.
195  explicit UT_Array(
196  const UT_ArrayCT::GeneralizedMove,
197  T *data,
198  const exint capacity,
199  UT_Array&& a
200  );
201 
202  // Equivalent to std::less without bringing in <functional>
203  template <typename Y>
204  struct Less
205  {
206  constexpr bool operator()(const Y &left, const Y &right) const noexcept
207  {
208  return left < right;
209  }
210  };
211 
212  // SFINAE constraint for bool comparators to avoid ambiguity
213  template <typename F>
214  using IsBoolComp = decltype(std::declval<F>()(std::declval<T>(),
215  std::declval<T>()),
216  void());
217 
218 public:
219  /// Assuming the array is sorted, it inserts item t maintaining the sorted
220  /// state of the array. It returns the index of the inserted item.
221  /// @note This is O(N^2) behaviour if you call it in a loop! Do not use.
222  /// @{
223  SYS_DEPRECATED_HDK(13.0)
225 
226  template <typename ComparatorBool = Less<T>,
227  typename = IsBoolComp<ComparatorBool>>
228  SYS_DEPRECATED_HDK(13.0)
229  exint sortedInsert(const T &t, ComparatorBool is_less = {});
230  /// @}
231 
232  SYS_DEPRECATED_HDK(13.0)
234  { return uniqueSortedInsertImpl(t, compare); }
235 
236  template <typename ComparatorBool = Less<T>,
237  typename = IsBoolComp<ComparatorBool>>
238  SYS_DEPRECATED_HDK(13.0)
239  exint uniqueSortedInsert(const T &t, ComparatorBool is_less = {});
240 
241  SYS_DEPRECATED_HDK(13.0)
243  { return uniqueSortedInsertImpl(std::move(t), compare); }
244 
245  /// Convenience method to perform binary search of a ascending sorted array
246  /// with no duplicates. Returns the index of the specified item, -1 if not
247  /// found.
248  template <typename ComparatorBool = Less<T>,
249  typename = IsBoolComp<ComparatorBool>>
250  exint uniqueSortedFind(const T &item,
251  ComparatorBool is_less = {}) const;
252 
253  SYS_DEPRECATED_HDK_REPLACE(19.5, "Use ComparatorBool variant")
254  exint uniqueSortedFind(const T &item, Comparator compare) const;
255 
256  /// Merge the given array into us.
257  /// If direction is -1, then it assumes us and 'other' are both already
258  /// sorted in descending order. Similarly, +1 means ascending.
259  /// If allow_dups is false, then it further assumes that both arrays have no
260  /// duplicates and will produce a result that also has no duplicates.
261  /// More work will be needed if you want allow_dups to mean remove duplicates
262  template <typename ComparatorBool = Less<T>>
263  void merge(const UT_Array<T> &other, int direction,
264  bool allow_dups, ComparatorBool is_less = {});
265 
266  template <typename ComparatorBool = Less<T>,
267  typename = IsBoolComp<ComparatorBool>>
268  bool hasSortedSubset(const UT_Array<T> &other,
269  ComparatorBool is_less = {}) const;
270 
271  template <typename ComparatorBool = Less<T>,
272  typename = IsBoolComp<ComparatorBool>>
273  void sortedUnion(
274  const UT_Array<T> &other,
275  ComparatorBool is_less = {});
276  template <typename ComparatorBool = Less<T>,
277  typename = IsBoolComp<ComparatorBool>>
278  void sortedUnion(
279  const UT_Array<T> &other,
281  ComparatorBool is_less = {}) const;
282  template <typename ComparatorBool = Less<T>,
283  typename = IsBoolComp<ComparatorBool>>
284  void sortedIntersection(
285  const UT_Array<T> &other,
286  ComparatorBool is_less = {});
287  template <typename ComparatorBool = Less<T>,
288  typename = IsBoolComp<ComparatorBool>>
289  void sortedIntersection(
290  const UT_Array<T> &other,
291  UT_Array<T> &result,
292  ComparatorBool is_less = {}) const;
293  template <typename ComparatorBool = Less<T>,
294  typename = IsBoolComp<ComparatorBool>>
295  void sortedSetDifference(
296  const UT_Array<T> &other,
297  ComparatorBool is_less = {});
298  template <typename ComparatorBool = Less<T>,
299  typename = IsBoolComp<ComparatorBool>>
300  void sortedSetDifference(
301  const UT_Array<T> &other,
302  UT_Array<T> &result,
303  ComparatorBool is_less = {}) const;
304 
305  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
306  bool hasSortedSubset(const UT_Array<T> &other,
307  Comparator compare) const;
308  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
309  void sortedUnion(
310  const UT_Array<T> &other,
312  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
313  void sortedUnion(
314  const UT_Array<T> &other,
315  UT_Array<T> &result,
316  Comparator compare) const;
317  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
318  void sortedIntersection(
319  const UT_Array<T> &other,
320  Comparator compare);
321  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
322  void sortedIntersection(
323  const UT_Array<T> &other,
324  UT_Array<T> &result,
325  Comparator compare) const;
326  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
327  void sortedSetDifference(
328  const UT_Array<T> &other,
329  Comparator compare);
330  SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
331  void sortedSetDifference(
332  const UT_Array<T> &other,
333  UT_Array<T> &result,
334  Comparator compare) const;
335 
336  /// Assuming the array is already a heap, it inserts item t maintaining
337  /// the heap. It returns the index of the inserted item.
338  exint heapPush(const T &t, Comparator compare);
339 
340  /// Assuming the array is already a heap, extracts the top (maximum)
341  /// element from the heap and returns it.
342  T heapPop(Comparator compare);
343 
344  /// Assuming the array is already a heap, return the top (maximum)
345  /// element.
346  const T & heapMax() const
347  {
348  UT_ASSERT_P(mySize > 0);
349  return myData[0];
350  }
351 
352  /// Takes another T array and concatenate it onto my end
353  exint concat(const UT_Array<T> &a);
354  /// Takes another T array and concatenate it onto my end
355  exint concat(UT_Array<T> &&a) noexcept;
356 
357  /// Insert an element "count" times at the given index. Return the index.
359 
360  /// An alias for unique element insertion at a certain index. Also used by
361  /// the other insertion methods.
362  exint insertAt(const T &t, exint index)
363  { return insertImpl(t, index); }
364 
365  /// Return true if given index is valid.
367  { return (index >= 0 && index < mySize); }
368 
369  /// Remove one element from the array given the element itself or its
370  /// position in the list, and fill the gap by shifting the elements down
371  /// by one position. Return the index of the element remove or -1 if
372  /// the value was not found.
373  template <typename S>
374  exint findAndRemove(const S &s);
376  {
377  return isValidIndex(index) ? removeAt(index) : -1;
378  }
380  {
381  if (mySize)
382  {
383  exint idx = --mySize;
384  destroyElement(myData[idx]);
385  }
386  }
387 
388  /// Remove the range [begin_i,end_i) of elements from the array.
389  /// begin_i is the start index.
390  /// end_i is the index to stop at, and isn't inclusive.
391  void removeRange(exint begin_i, exint end_i);
392 
393  /// Remove the range [begin_i, end_i) of elements from this array and place
394  /// them in the dest array, shrinking/growing the dest array as necessary.
395  /// begin_i is the start index,
396  /// end_i is index to stop at, and isn't inclusive.
397  void extractRange(exint begin_i, exint end_i,
398  UT_Array<T>& dest);
399 
400  /// Removes all matching elements from the list, shuffling down and changing
401  /// the size appropriately.
402  /// Returns the number of elements left.
403  template <typename IsEqual>
404  exint removeIf(IsEqual is_equal);
405 
406  /// Remove all matching elements. Also sets the capacity of the array.
407  template <typename IsEqual>
408  void collapseIf(IsEqual is_equal)
409  {
410  removeIf(is_equal);
411  setCapacity(size());
412  }
413 
414  /// Move how_many objects starting at index src_idx to dst_idx;
415  /// This method will remove the elements at [src_idx, src_idx+how_many) and
416  /// then insert them at dst_idx. This method can be used in place of
417  /// the old shift() operation.
418  void move(exint src_idx, exint dst_idx, exint how_many);
419 
420  /// Cyclically shifts the entire array by how_many
421  void cycle(exint how_many);
422 
423  /// Quickly set the array to a single value.
424  void constant(const T &v);
425  /// Zeros the array if a POD type, else trivial constructs if a class type.
426  void zero();
427 
428  /// Search for s linearly using the '==' operator, starting at index start.
429  /// @returns the index of the matching element or (exint)-1.
430  template <typename S>
431  exint find(const S &s, exint start = 0) const;
432 
433  /// Search for s linearly using functor, starting at index start.
434  /// @returns the index of the matching element or (exint)-1.
435  template <typename IsEqual>
436  exint findIf(IsEqual is_equal, exint start = 0) const;
437 
438  /// Search for t via binary search using the function specified in the
439  /// parameter list, assuming the array is already sorted with respect to
440  /// compare.
441  /// @returns the index of the matching element or (exint)-1.
442  exint sortedFind(const T &t, Comparator compare) const;
443 
444  /// Reverses the array by swapping elements in mirrored locations.
445  void reverse();
446 
447  /// The fastest search possible, which does pointer arithmetic to find the
448  /// index of the element. WARNING: index() does no out-of-bounds checking.
449  /// @{
450  exint index(const T &t) const
451  { return SYSaddressof(t) - myData; }
452  exint safeIndex(const T &t) const
453  {
454  return (SYSaddressof(t) >= myData &&
455  SYSaddressof(t) < (myData + mySize))
456  ? SYSaddressof(t) - myData : -1;
457  }
458  /// @}
459 
460  /// Sort using std::sort with bool comparator. Defaults to operator<().
461  template <typename ComparatorBool = Less<T>,
462  typename = IsBoolComp<ComparatorBool>>
463  void sort(ComparatorBool is_less = {})
464  {
465  std::sort(myData, myData + mySize, is_less);
466  }
467 
468  /// Sort the array using a comparison function that you must provide. t1 and
469  /// t2 are pointers to Thing. The comparison function uses strcmp()
470  /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
471  SYS_DEPRECATED_HDK_REPLACE(19.5, "Use ComparatorBool variant")
473 
474  /// Sort using std::sort. The ComparatorBool uses the less-than semantics
475  template <typename ComparatorBool,
476  typename = IsBoolComp<ComparatorBool>>
477  SYS_DEPRECATED_REPLACE(19.5, "Use sort(ComparatorBool) overload")
478  void stdsort(ComparatorBool is_less)
479  {
480  std::sort(myData, myData + mySize, is_less);
481  }
482 
483  /// stableSort is both stable, so keeps equal elements in the same
484  /// order (note this is very useful for compatibility between
485  /// compilers) and templated.
486  /// Either use a bool sort function or make a utility class with
487  /// bool operator()(const T a, const T b)
488  /// the utility class lets you bind data to avoid globals.
489  /// The comparator returns true if a must occur before b in the list.
490  /// For sorting ascending, this is a less than operation.
491  template<typename ComparatorBool = Less<T>>
492  void stableSort(ComparatorBool is_less = {})
493  {
494  // No-op for small/empty arrays, avoiding out of
495  // bounds assert on array()
496  if (size() < 2)
497  return;
498 
499  std::stable_sort(array(), array() + size(), is_less);
500  }
501  /// Like stableSort, but operates on a subset of the array.
502  template<typename ComparatorBool>
503  void stableSortRange(ComparatorBool is_less,
504  exint start, exint end)
505  {
506  // No-op for small/empty arrays or ranges, avoiding out of
507  // bounds assert on array()
508  if (end < 0)
509  end = size();
510  if (start < 0)
511  start = 0;
512  if (end < start + 2)
513  return;
514 
515  std::stable_sort(array() + start, array() + end, is_less);
516  }
517 
518  /// Comparator class for stableSortIndices
519  template <typename I, typename V, typename ComparatorBool>
521  {
522  public:
524  const ComparatorBool &compare)
525  : myValues(values)
526  , myCompare(compare)
527  {}
528  inline bool operator()(I a, I b) const
529  { return myCompare(myValues(a), myValues(b)); }
530  private:
531  const UT_Array<V> &myValues;
532  const ComparatorBool &myCompare;
533  };
534 
535  /// Sort indices array by the values indexed into this array using a
536  /// stable sorting algorithm. To reorder the array in such a way
537  /// that it would be sorted, or another array to be reordered the
538  /// same way, include UT_Permute.h and use:
539  /// UTinversePermute(values.getArray(), indices.getArray(),
540  /// values.size());
541  /// The ComparatorBool uses the less-than semantics.
542  /// I must be an integer type.
543  template <typename I, typename ComparatorBool>
545  ComparatorBool is_less) const
546  {
547  IndexedCompare<I, T, ComparatorBool> compare(*this, is_less);
548  std::stable_sort(indices.getArray(),
549  indices.getArray() + indices.size(), compare);
550  }
551 
552  /// Create an index array from 0..n-1 into this array and sort
553  /// it with stableSortIndices.
554  /// The index array will be resized & rebuilt by this.
555  template <typename I, typename ComparatorBool>
557  ComparatorBool is_less) const
558  {
559  indices.setSizeNoInit(size());
560  for (exint i = 0; i < size(); i++)
561  indices(i) = i;
562  stableSortIndices(indices, is_less);
563  }
564 
565  /// Sorts this array by an external key array. We assume a 1:1
566  /// corespondence between our own elements and those of the key
567  /// array. The comparator should be defined on the key type.
568  template <typename K, typename ComparatorBool>
569  void stableSortByKey(const UT_Array<K> &keys, ComparatorBool is_less)
570  {
571  UT_ASSERT(keys.size() == size());
572  if (keys.size() != size())
573  return;
575  keys.stableArgSort(indices, is_less);
576  UTinversePermute(getArray(), indices.getArray(), size());
577  }
578 
579  /// Assuming this array is sorted, remove all duplicate elements.
580  /// Returns the number of elements removed.
582 
583  /// Assuming this array is sorted, remove all duplicate elements using the
584  /// given binary predicate.
585  /// Returns the number of elements removed
586  template <typename CompareEqual>
587  exint sortedRemoveDuplicatesIf(CompareEqual compare_equal);
588 
589  /// Sort and then remove duplicates.
590  /// By default, operator<() is used but if you supply a custom comparator,
591  /// ensure that equal elements are adjacent after sorting.
592  /// Returns the number of elements removed.
593  template<typename ComparatorBool = Less<T>>
594  exint sortAndRemoveDuplicates(ComparatorBool is_less = {})
595  {
596  stableSort(is_less);
597  return sortedRemoveDuplicates();
598  }
599 
600  /// Partitions the array into values greater than or less than
601  /// the Nth element, returns the resulting partition number.
602  /// idx == 0 will get the minimum value, idx == size()-1 the
603  /// maximum value. This does modify this array!
604  template <typename ComparatorBool = Less<T>>
605  T selectNthLargest(exint idx, ComparatorBool is_less = {});
606 
607  /// Set the capacity of the array, i.e. grow it or shrink it. The
608  /// function copies the data after reallocating space for the array.
609  void setCapacity(exint new_capacity);
610  void setCapacityIfNeeded(exint min_capacity)
611  {
612  if (capacity() < min_capacity)
613  setCapacity(min_capacity);
614  }
615  /// If the capacity is smaller than min_capacity, expand the array
616  /// to at least min_capacity and to at least a constant factor of the
617  /// array's previous capacity, to avoid having a linear number of
618  /// reallocations in a linear number of calls to bumpCapacity.
619  void bumpCapacity(exint min_capacity)
620  {
621  if (capacity() >= min_capacity)
622  return;
623  // The following 4 lines are just
624  // SYSmax(min_capacity, UTbumpAlloc(capacity())), avoiding SYSmax
625  exint bumped = UTbumpAlloc(capacity());
626  exint new_capacity = min_capacity;
627  if (bumped > min_capacity)
628  new_capacity = bumped;
629  setCapacity(new_capacity);
630  }
631 
632  /// First bumpCapacity to ensure that there's space for newsize,
633  /// expanding either not at all or by at least a constant factor
634  /// of the array's previous capacity,
635  /// then set the size to newsize.
636  void bumpSize(exint newsize)
637  {
638  bumpCapacity(newsize);
639  setSize(newsize);
640  }
641  /// NOTE: bumpEntries() will be deprecated in favour of bumpSize() in a
642  /// future version.
643  void bumpEntries(exint newsize)
644  {
645  bumpSize(newsize);
646  }
647 
648  /// Query the capacity, i.e. the allocated length of the array.
649  /// NOTE: capacity() >= size().
650  exint capacity() const;
651  /// Query the size, i.e. the number of occupied elements in the array.
652  /// NOTE: capacity() >= size().
653  exint size() const { return mySize; }
654  /// Alias of size(). size() is preferred.
655  exint entries() const { return mySize; }
656  /// Returns true iff there are no occupied elements in the array.
657  bool isEmpty() const { return mySize==0; }
658 
659  /// Returns the amount of memory used by this UT_Array.
660  /// If inclusive is false, it only counts the memory of the array.
661  /// This is often necessary to avoid double-counting, e.g. if this
662  /// UT_Array is a member variable of a class whose memory is already
663  /// being counted by the caller.
664  int64 getMemoryUsage(bool inclusive=false) const
665  {
666  return (inclusive ? sizeof(*this) : 0) + capacity()*sizeof(T); // NOLINT
667  }
668 
669  /// Set the size, the number of occupied elements in the array.
670  /// NOTE: This will not do bumpCapacity, so if you call this
671  /// n times to increase the size, it may take
672  /// n^2 time.
673  void setSize(exint newsize)
674  {
675  if (newsize < 0)
676  newsize = 0;
677  if (newsize == mySize)
678  return;
679  setCapacityIfNeeded(newsize);
680  if (mySize > newsize)
681  destroyRange(myData + newsize, mySize - newsize);
682  else // newsize > mySize
683  constructRange(myData + mySize, newsize - mySize);
684  mySize = newsize;
685  }
686  void setSizeIfNeeded(exint minsize)
687  {
688  if (size() >= minsize)
689  return;
690  setSize(minsize);
691  }
692  /// Alias of setSize(). setSize() is preferred.
693  void entries(exint newsize)
694  {
695  setSize(newsize);
696  }
697  /// Set the size, but unlike setSize(newsize), this function
698  /// will not initialize new POD elements to zero. Non-POD data types
699  /// will still have their constructors called.
700  /// This function is faster than setSize(ne) if you intend to fill in
701  /// data for all elements.
702  void setSizeNoInit(exint newsize)
703  {
704  if (newsize < 0)
705  newsize = 0;
706  if (newsize == mySize)
707  return;
708  setCapacityIfNeeded(newsize);
709  if (mySize > newsize)
710  destroyRange(myData + newsize, mySize - newsize);
711  else if (!isPOD()) // newsize > mySize
712  constructRange(myData + mySize, newsize - mySize);
713  mySize = newsize;
714  }
715 
716  /// shrinks the capacity to the current size
717  void shrinkToFit()
718  {
719  // TODO: be more intelligent here
720  setCapacity(size());
721  }
722  /// convenience method to set size and shrink-to-fit in a single call
723  void setSizeAndShrink(exint new_size)
724  {
725  setSize(new_size);
726  shrinkToFit();
727  }
728 
729  /// Decreases, but never expands, to the given maxsize.
730  void truncate(exint maxsize)
731  {
732  if (maxsize >= 0 && size() > maxsize)
733  setSize(maxsize);
734  }
735  /// Resets list to an empty list.
736  void clear()
737  {
738  // Don't call setSize(0) since it supports growing the array
739  // which requires a default constructor. Avoiding it allows
740  // this to be used on types that lack a default constructor.
741  destroyRange(myData, mySize);
742  mySize = 0;
743  }
744 
745  /// Assign array a to this array by copying each of a's elements with
746  /// memcpy for POD types, and with copy construction for class types.
748 
749  /// Replace the contents with those from the initializer_list ilist
750  UT_Array<T> & operator=(std::initializer_list<T> ilist);
751 
752  /// Move the contents of array a to this array.
753  UT_Array<T> & operator=(UT_Array<T> &&a) noexcept;
754 
755  /// Compare two array and return true if they are equal and false otherwise.
756  /// Two elements are checked against each other using operator '==' or
757  /// compare() respectively.
758  /// NOTE: The capacities of the arrays are not checked when
759  /// determining whether they are equal.
760  bool operator==(const UT_Array<T> &a) const;
761  bool operator!=(const UT_Array<T> &a) const;
762 
763 
764  template <typename ComparatorBool,
765  typename = IsBoolComp<ComparatorBool>>
766  bool isEqual(const UT_Array<T> &a, ComparatorBool is_equal) const;
767 
768  SYS_DEPRECATED_REPLACE(20.5, "Use ComparatorBool variant")
769  int isEqual(const UT_Array<T> &a, Comparator compare) const;
770 
771  /// Subscript operator
772  /// NOTE: This does NOT do any bounds checking unless paranoid
773  /// asserts are enabled.
774  T & operator()(exint i)
775  {
776  UT_ASSERT_P(i >= 0 && i < mySize);
777  return myData[i];
778  }
779  /// Const subscript operator
780  /// NOTE: This does NOT do any bounds checking unless paranoid
781  /// asserts are enabled.
782  const T & operator()(exint i) const
783  {
784  UT_ASSERT_P(i >= 0 && i < mySize);
785  return myData[i];
786  }
787 
788  /// Subscript operator
789  /// NOTE: This does NOT do any bounds checking unless paranoid
790  /// asserts are enabled.
792  {
793  UT_ASSERT_P(i >= 0 && i < mySize);
794  return myData[i];
795  }
796  /// Const subscript operator
797  /// NOTE: This does NOT do any bounds checking unless paranoid
798  /// asserts are enabled.
799  const T & operator[](exint i) const
800  {
801  UT_ASSERT_P(i >= 0 && i < mySize);
802  return myData[i];
803  }
804 
805  /// forcedRef(exint) will grow the array if necessary, initializing any
806  /// new elements to zero for POD types and default constructing for
807  /// class types.
809  {
810  UT_ASSERT_P(i >= 0);
811  if (i >= mySize)
812  bumpSize(i+1);
813  return myData[i];
814  }
815 
816  /// forcedGet(exint) does NOT grow the array, and will return default
817  /// objects for out of bound array indices.
818  T forcedGet(exint i) const
819  {
820  return (i >= 0 && i < mySize) ? myData[i] : T();
821  }
822 
823  T & last()
824  {
825  UT_ASSERT_P(mySize);
826  return myData[mySize-1];
827  }
828  const T & last() const
829  {
830  UT_ASSERT_P(mySize);
831  return myData[mySize-1];
832  }
833 
834  /// Apply a user-defined function to each element of the array
835  /// as int as the function returns zero. If apply_func returns
836  /// 1, apply() stops traversing the list and returns the current
837  /// index; otherwise, apply() returns the size.
838  exint apply(int (*apply_func)(T &t, void *d), void *d);
839 
840  template <typename BinaryOp>
841  T accumulate(const T &init_value, BinaryOp add) const;
842 
843  T * getArray() const { return myData; }
844  const T * getRawArray() const { return myData; }
845 
846  T * array() { return myData; }
847  const T * array() const { return myData; }
848 
849  T * data() { return myData; }
850  const T * data() const { return myData; }
851 
852  /// This method allows you to swap in a new raw T array, which must be
853  /// the same size as capacity(). Use caution with this method.
854  T * aliasArray(T *newdata)
855  { T *data = myData; myData = newdata; return data; }
856 
857  template <typename IT, bool FORWARD>
859  {
860  public:
861  using iterator_category = std::random_access_iterator_tag;
862  using value_type = T;
864  using pointer = IT*;
865  using reference = IT&;
866 
867  // Note: When we drop gcc 4.4 support and allow range-based for
868  // loops, we should also drop atEnd(), which means we can drop
869  // myEnd here.
870  base_iterator() : myCurrent(nullptr), myEnd(nullptr) {}
871 
872  // Allow iterator to const_iterator conversion
873  template<typename EIT>
875  : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
876 
878  { return FORWARD ? myCurrent : myCurrent - 1; }
879 
881  { return FORWARD ? *myCurrent : myCurrent[-1]; }
882 
883  reference item() const
884  { return FORWARD ? *myCurrent : myCurrent[-1]; }
885 
887  { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; }
888 
889  /// Pre-increment operator
891  {
892  if (FORWARD) ++myCurrent; else --myCurrent;
893  return *this;
894  }
895  /// Post-increment operator
897  {
898  base_iterator tmp = *this;
899  if (FORWARD) ++myCurrent; else --myCurrent;
900  return tmp;
901  }
902  /// Pre-decrement operator
904  {
905  if (FORWARD) --myCurrent; else ++myCurrent;
906  return *this;
907  }
908  /// Post-decrement operator
910  {
911  base_iterator tmp = *this;
912  if (FORWARD) --myCurrent; else ++myCurrent;
913  return tmp;
914  }
915 
917  {
918  if (FORWARD)
919  myCurrent += n;
920  else
921  myCurrent -= n;
922  return *this;
923  }
925  {
926  if (FORWARD)
927  return base_iterator(myCurrent + n, myEnd);
928  else
929  return base_iterator(myCurrent - n, myEnd);
930  }
931 
933  { return (*this) += (-n); }
935  { return (*this) + (-n); }
936 
937  bool atEnd() const { return myCurrent == myEnd; }
938  void advance() { this->operator++(); }
939 
940  // Comparators
941  template<typename ITR, bool FR>
943  { return myCurrent == r.myCurrent; }
944 
945  template<typename ITR, bool FR>
947  { return myCurrent != r.myCurrent; }
948 
949  template<typename ITR>
950  bool operator<(const base_iterator<ITR, FORWARD> &r) const
951  {
952  if (FORWARD)
953  return myCurrent < r.myCurrent;
954  else
955  return r.myCurrent < myCurrent;
956  }
957 
958  template<typename ITR>
960  {
961  if (FORWARD)
962  return myCurrent > r.myCurrent;
963  else
964  return r.myCurrent > myCurrent;
965  }
966 
967  template<typename ITR>
968  bool operator<=(const base_iterator<ITR, FORWARD> &r) const
969  {
970  if (FORWARD)
971  return myCurrent <= r.myCurrent;
972  else
973  return r.myCurrent <= myCurrent;
974  }
975 
976  template<typename ITR>
978  {
979  if (FORWARD)
980  return myCurrent >= r.myCurrent;
981  else
982  return r.myCurrent >= myCurrent;
983  }
984 
985  // Difference operator for std::distance
986  template<typename ITR>
988  {
989  if (FORWARD)
990  return exint(myCurrent - r.myCurrent);
991  else
992  return exint(r.myCurrent - myCurrent);
993  }
994 
995 
996  protected:
997  friend class UT_Array<T>;
998  base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
999  private:
1000 
1001  IT *myCurrent;
1002  IT *myEnd;
1003  };
1004 
1005  typedef base_iterator<T, true> iterator;
1006  typedef base_iterator<const T, true> const_iterator;
1007  typedef base_iterator<T, false> reverse_iterator;
1008  typedef base_iterator<const T, false> const_reverse_iterator;
1009  typedef const_iterator traverser; // For backward compatibility
1010 
1011  /// Begin iterating over the array. The contents of the array may be
1012  /// modified during the traversal.
1014  {
1015  return iterator(myData, myData + mySize);
1016  }
1017  /// End iterator.
1019  {
1020  return iterator(myData + mySize,
1021  myData + mySize);
1022  }
1023 
1024  /// Begin iterating over the array. The array may not be modified during
1025  /// the traversal.
1027  {
1028  return const_iterator(myData, myData + mySize);
1029  }
1030  /// End const iterator. Consider using it.atEnd() instead.
1032  {
1033  return const_iterator(myData + mySize,
1034  myData + mySize);
1035  }
1036 
1037  /// Begin iterating over the array in reverse.
1039  {
1040  return reverse_iterator(myData + mySize,
1041  myData);
1042  }
1043  /// End reverse iterator.
1045  {
1046  return reverse_iterator(myData, myData);
1047  }
1048  /// Begin iterating over the array in reverse.
1050  {
1051  return const_reverse_iterator(myData + mySize,
1052  myData);
1053  }
1054  /// End reverse iterator. Consider using it.atEnd() instead.
1056  {
1057  return const_reverse_iterator(myData, myData);
1058  }
1059 
1061  { return UT_IteratorRange<iterator>(begin(), end()); }
1063  { return UT_IteratorRange<const_iterator>(begin(), end()); }
1064 
1069 
1070  /// Remove item specified by the reverse_iterator.
1072  {
1073  removeAt(&it.item() - myData);
1074  }
1075 
1076 
1077  /// Very dangerous methods to share arrays.
1078  /// The array is not aware of the sharing, so ensure you clear
1079  /// out the array prior a destructor or setCapacity operation.
1081  {
1082  myData = src.myData;
1083  myCapacity = labelExternal( src.capacity() );
1084  mySize = src.mySize;
1085  }
1086  void unsafeShareData(T *src, exint srcsize)
1087  {
1088  myData = src;
1089  myCapacity = labelExternal( srcsize );
1090  mySize = srcsize;
1091  }
1093  {
1094  myData = src;
1095  mySize = size;
1096  myCapacity = labelExternal( capacity );
1097  }
1099  {
1100  myData = nullptr;
1101  myCapacity = labelExternal( 0 );
1102  mySize = 0;
1103  }
1104 
1105  /// Returns true if the data used by the array was allocated on the heap.
1106  inline bool isHeapBuffer() const
1107  {
1108  return isHeapBuffer(myData);
1109  }
1110 
1111 protected:
1112  // Check whether T may have a constructor, destructor, or copy
1113  // constructor. This test is conservative in that some POD types will
1114  // not be recognized as POD by this function. To mark your type as POD,
1115  // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
1116  static constexpr SYS_FORCE_INLINE bool isPOD()
1117  {
1118  return SYS_IsPod_v< T >;
1119  }
1120 
1121  /// Implements both append(const T &) and append(T &&) via perfect
1122  /// forwarding. Unlike the variadic emplace_back(), its argument may be a
1123  /// reference to another element in the array.
1124  template <typename S>
1125  exint appendImpl(S &&s);
1126 
1127  /// Similar to appendImpl() but for insertion.
1128  template <typename S>
1129  exint insertImpl(S &&s, exint index);
1130 
1131  template <typename S>
1132  SYS_DEPRECATED_HDK(13.0)
1134 
1135  /// In debug builds, verifies that the arguments to emplace_back() will not
1136  /// be invalidated when realloc() is called.
1137  template <typename First, typename... Rest>
1138  void validateEmplaceArgs(First &&first, Rest&&... rest) const
1139  {
1141  static_cast<const void *>(&first) <
1142  static_cast<const void *>(myData) ||
1143  static_cast<const void *>(&first) >=
1144  static_cast<const void *>(myData + mySize),
1145  "Argument cannot reference an existing element in the array.");
1146 
1147  validateEmplaceArgs(std::forward<Rest>(rest)...);
1148  }
1149 
1150  /// Base case for validateEmplaceArgs().
1151  void validateEmplaceArgs() const
1152  {
1153  }
1154 
1155  // Construct the given type
1156  template <typename... S>
1157  static void construct(T &dst, S&&... s)
1158  {
1159  new (&dst) T(std::forward<S>(s)...);
1160  }
1161 
1162  // Copy construct the given type
1163  static void copyConstruct(T &dst, const T &src)
1164  {
1165  if constexpr( SYS_IsPod_v< T > )
1166  {
1167  dst = src;
1168  }
1169  else // constexpr
1170  {
1171  new (&dst) T(src);
1172  }
1173  }
1174 
1175 private:
1176  /// Equivalent to std::back_insert_iterator, but using the append() method
1177  /// for UT_Array. This is useful for appending to an array via STL
1178  /// algorithms that have an output iterator
1179  class AppendIterator
1180  {
1181  public:
1182  using iterator_category = std::output_iterator_tag;
1183  using value_type = void;
1184  using difference_type = void;
1185  using pointer = void;
1186  using reference = void;
1187 
1188  explicit AppendIterator(UT_Array<T> &arr) : myArray(&arr) {}
1189 
1190  /// @{
1191  /// Append the value when the iterator is assigned to.
1192  AppendIterator &operator=(const T &val)
1193  {
1194  myArray->append(val);
1195  return *this;
1196  }
1197 
1198  AppendIterator &operator=(T &&val)
1199  {
1200  myArray->append(std::move(val));
1201  return *this;
1202  }
1203  /// @}
1204 
1205  /// @{
1206  /// This iterator does not move, and dereferencing just returns itself.
1207  AppendIterator &operator*() { return *this; }
1208  AppendIterator &operator++() { return *this; }
1209  AppendIterator operator++(int) { return *this; }
1210  /// @}
1211 
1212  private:
1213  UT_Array<T> *myArray;
1214  };
1215 
1216 #ifdef UT_ARRAY_STRICT_LABELED_CAPACITY
1217  using LabeledCapacity = UT_LabeledCapacity;
1218 #else
1219  using LabeledCapacity = UT_LabeledCapacityRep;
1220 #endif
1221 
1222  /// Pointer to the array of elements of type T
1223  T *myData;
1224 
1225  /// The number of elements for which we have allocated memory
1226  LabeledCapacity myCapacity;
1227 
1228  /// The actual number of valid elements in the array
1229  exint mySize;
1230 
1231  // Create a Capacity that's labeled as owned by this UT_Array
1232  static LabeledCapacity labelOwned(const exint capacity) noexcept;
1233 
1234  // Create a Capacity that's labeled as external (not owned by this UT_Array)
1235  static LabeledCapacity labelExternal(const exint capacity) noexcept;
1236 
1237  // All memory allocations, reallocations and deallocations in UT_Array's
1238  // implementation go through the three functions
1239  // allocateArray, reallocateArray, deallocateArray below.
1240  // These functions make no calls to constructors/destructors.
1241 
1242  // Return an array with given capacity for elements of type T.
1243  // PRE: capacity > 0
1244  static T *allocateArray(const exint capacity) noexcept;
1245 
1246  // Return an array with given capacity for elements of type T.
1247  // reusing the passed-in 'data' if possible.
1248  // PRE: capacity > 0
1249  static T *reallocateArray(T *data, const exint capacity) noexcept;
1250 
1251  // NOTE: This will work correctly with data == nullptr
1252  static void deallocateArray(T *data) noexcept;
1253 
1254  // Identify whether 'data' is a heap buffer.
1255  // 'data' is decided to be a heap buffer when it is not
1256  // located at the first memory location after this UT_Array object
1257  // (a trick used by UT_SmallArray).
1258  // If a call to 'allocateArray' happens to return the first memory
1259  // location after this UT_Array object, then isHeapBuffer ends up false.
1260  // To avoid this, a second allocation should then by attempted,
1261  // see 'allocateArrayHeapIdentifiable' below.
1262  bool isHeapBuffer(T* data) const;
1263 
1264  // Like allocateArray, except ensure that the returned array 'data'
1265  // is NOT located at the end of this UT_Array object, so that
1266  // isHeapBuffer( data) is true.
1267  // PRE: capacity > 0
1268  T *allocateArrayHeapIdentifiable(const exint capacity);
1269 
1270  //
1271  // Construct/destroy elements and ranges.
1272  // For POD types, construct* fills T objects with zeroes,
1273  // and destroy* does nothing.
1274  // For non-POD types, construct* calls the regular constructor
1275  // (by way of placement new), and destroy* calls the regular destructor.
1276  //
1277 
1278  static void constructElement(T &dst);
1279  static void constructRange(T *dst, exint n);
1280 
1281  static void destroyElement(T &dst) noexcept;
1282  static void destroyRange([[maybe_unused]] T *dst, exint n) noexcept;
1283 
1284  //
1285  // About relocation:
1286  // Relocating [ src, src + n ) to [ dst, dst + n ) should be equivalent
1287  // to the following:
1288  // For each i in [ 0, n ):
1289  // 1. move construct dst[ i ] from src[ i ]
1290  // 2. destroy src[ i ]
1291  //
1292  // The trivial relocation macros and traits defined in SYS_TypeDecorate.h
1293  // and SYS_TypeTraits.h can be used to indicate for which types T
1294  // bitwise copying is equivalent to the above construct and destroy steps.
1295  //
1296 
1297  // The below "standardRelocate" methods relocate
1298  // [ src, src + n ) to [ dst, dst + n ) by invoking
1299  // T's move constructor and destructor.
1300 
1301  // Relocate elements in increasing order 0, 1, ..., n - 1
1302  static void standardRelocateIncreasing(T *dst, T *src, exint n);
1303 
1304  // Relocate elements in decreasing order n - 1,, ..., 1, 0
1305  static void standardRelocateDecreasing(T *dst, T *src, exint n);
1306 
1307  // For use in cases where the source and destination ranges may overlap:
1308  // Relocate in increasing order if dst < src and
1309  // relocate in decreasing order if src < dst.
1310  static void standardRelocate(T *dst, T *src, exint n);
1311 
1312  //
1313  // The below "bitwiseRelocate" methods relocate
1314  // [ src, src + n ) to [ dst, dst +n ) using memcpy and memmove,
1315  // and do not invoke destructors afterwards.
1316  //
1317 
1318  // PRE:
1319  // * both 'dst' and 'src' are valid (not null)
1320  static void bitwiseRelocate(T *dst, const T *src, exint n) noexcept;
1321 
1322  // PRE:
1323  // * both 'dst' and 'src' are valid (not null)
1324  // * [ dst, dst + n ) and [ src, src + n ) don't overlap
1325  static void bitwiseRelocateNonoverlapping(
1326  T *dst,
1327  const T *src,
1328  exint n) noexcept;
1329 
1330  //
1331  // The below relocate, copy and swap methods decide whether to use
1332  // standard or bitwise copying at compile time, based on traits.
1333  // Only these are the versions should be called directly by
1334  // the rest of the UT_Array implementation.
1335  //
1336 
1337  // For trivially relocatable types, bitwise copy [ src, src + n )
1338  // onto [ dst, dst + n ) instead.
1339  static void relocate(T *dst, T *src, exint n);
1340 
1341  // Version of relocate with a stronger precondition that is
1342  // exploited for potentially faster computation:
1343  // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
1344  static void relocateNonoverlapping(T *dst, T *src, exint n);
1345 
1346  // PRE: dst < src
1347  static void relocateIncreasing(T *dst, T *src, exint n);
1348 
1349  // PRE: dst > src
1350  static void relocateDecreasing(T *dst, T *src, exint n);
1351 
1352  // copyNonoverlapping is similar to relocateNonoverlapping,
1353  // with the following to differences:
1354  // * Each value is copy constructed into its destination (not moved)
1355  // * The source values are not destroyed (no destructor invoked)
1356  // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
1357  static void copyNonoverlapping(T *dst, const T *src, exint n);
1358 
1359  // swapNonoverlapping is equivalent to the following:
1360  // For each i in [ 0, n ): swap dst[ i ] and src[ i ]
1361  static void swapNonoverlapping(T *dst, T *src, exint n);
1362 
1363  // The guts of the remove() methods.
1364  exint removeAt(exint index);
1365 
1366  // Convert the current object's buffer from a non-heap buffer
1367  // to a heap buffer of given capacity
1368  // PRE: *this has a non-heap buffer
1369  // 'capacity' should be at least the size
1370  // POST: *this has a heap buffer with given capacity,
1371  // and its initial size elements are the same as before the call
1372  void convertToHeapBuffer(const exint capacity);
1373 
1374  template<typename OS, typename S>
1375  friend OS &operator<<(OS &os, const UT_Array<S> &d);
1376 
1377  /// Friend specialization of std::swap() to use UT_String::swap()
1378  /// @internal This is needed because standard std::swap() implementations
1379  /// will try to copy the UT_String objects, causing hardened strings to
1380  /// become weak.
1381  friend void swap(UT_Array<T>& a, UT_Array<T>& b) { a.swap(b); }
1382 };
1383 
1384 // Suppress UT_Array<UT_StringHolder> instantations to avoid duplicate symbols
1385 // when UT_Array<UT_StringHolder> is used with UT_StringArray which derives
1386 // from it.
1387 class UT_StringHolder;
1389 
1390 // Assigns src to dest, using the default C++ conversion operator.
1391 template <typename T, typename S>
1392 void
1394 {
1395  exint n = src.size();
1396  dest.setCapacity(n);
1397  dest.setSize(n);
1398  for (exint i = 0; i < n; i++)
1399  dest(i) = T(src(i));
1400 }
1401 template <typename T, typename S>
1402 void
1404 {
1405  dest.setCapacity(n);
1406  dest.setSize(n);
1407  for (exint i = 0; i < n; i++)
1408  dest(i) = T(src[i]);
1409 }
1410 template <typename T, typename S>
1411 void
1413 {
1414  // We assume here that dest has enough memory for src.size()
1415  exint n = src.size();
1416  for (exint i = 0; i < n; i++)
1417  dest[i] = T(src(i));
1418 }
1419 template <typename T, typename S>
1420 void
1421 UTconvertArray(T *dest, const S *src, int64 n)
1422 {
1423  // We assume here that dest has enough memory for n elements
1424  for (int64 i = 0; i < n; i++)
1425  dest[i] = T(src[i]);
1426 }
1427 
1428 #include "UT_ArrayImpl.h" // IWYU pragma: export
1429 
1430 
1431 template<typename OS, typename S>
1432 inline OS &
1433 operator<<(OS &os, const UT_Array<S> &d)
1434 {
1435  os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
1436  return os;
1437 }
1438 
1439 // Overload for custom formatting of a UT_StringArray with UTformat.
1440 template <typename T> UT_API size_t
1441 format(char *buffer, size_t bufsize, const UT_Array<T> &v);
1442 
1443 /// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
1444 /// its elements
1445 template <template <typename> class ArrayT, typename T>
1446 static inline int64
1447 UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
1448 {
1449  int64 mem = inclusive ? sizeof(arr) : 0;
1450  mem += arr.getMemoryUsage(false);
1451  for (auto &&item : arr)
1452  mem += item.getMemoryUsage(false);
1453  return mem;
1454 }
1455 
1456 /// Utility to sort array using operator<
1457 template <typename T>
1458 static inline void
1459 UTsort(UT_Array<T> &arr)
1460 {
1461  arr.sort([](const T &a, const T &b) { return a < b; });
1462 }
1463 
1464 /// Utility to sort array using operator< and remove duplicates
1465 template <typename T>
1466 static inline void
1467 UTsortAndRemoveDuplicates(UT_Array<T> &arr)
1468 {
1469  arr.sortAndRemoveDuplicates([](const T &a, const T &b) { return a < b; });
1470 }
1471 
1472 // For UT::ArraySet.
1473 namespace UT
1474 {
1475 template <typename T>
1476 struct DefaultClearer;
1477 
1478 template <typename T>
1480 {
1481  static void clear(UT_Array<T> &v) { v.setCapacity(0); }
1482  static bool isClear(const UT_Array<T> &v) { return v.capacity() == 0; }
1483  static void clearConstruct(UT_Array<T> *p)
1484  {
1485  new ((void *)p) UT_Array<T>();
1486  }
1487  static const bool clearNeedsDestruction = false;
1488 };
1489 } // namespace UT
1490 
1491 //
1492 // Trivial relocation is not safe for UT_Array:
1493 // UT_SmallArray, which has a fixed-buffer optimization inherits from UT_Array.
1494 // At compile time, it cannot be known whether a UT_Array object is a
1495 // UT_SmallArray object.
1496 // For this reason alone, it cannot be safe to use trivial relocation on UT_Array.
1497 //
1498 // In addition to that, UT_Array is currently not safe for trivial relocation
1499 // even if UT_SmallArray didn't get used anywhere, due to the isHeapBuffer() test,
1500 // which may incorrectly return false after a UT_Array with a heap buffer gets
1501 // trivially relocated (making it adjacent in memory to its myData).
1502 //
1503 template <typename T>
1505 
1506 //
1507 // Trivial relocation is not safe for std::string since most implementations
1508 // use a small buffer optimization (aka SBO).
1509 //
1510 #if defined(MBSD) || defined(_LIBCPP_VERSION)
1511  #include <iosfwd>
1512  template <typename CharT, typename Traits, typename Allocator>
1514 #elif defined(__GLIBCXX__)
1515  #include <bits/stringfwd.h>
1516  template <typename CharT, typename Traits, typename Allocator>
1518 #else
1519  namespace std { template <class,class,class> class basic_string; }
1520  template <typename CharT, typename Traits, typename Allocator>
1522 #endif
1523 
1524 #endif // __UT_ARRAY_H_INCLUDED__
reference operator*() const
Definition: UT_Array.h:880
base_iterator & operator++()
Pre-increment operator.
Definition: UT_Array.h:890
base_iterator & operator--()
Pre-decrement operator.
Definition: UT_Array.h:903
T & last()
Definition: UT_Array.h:823
exint insert(T &&t, exint i)
Definition: UT_Array.h:157
GLint first
Definition: glcorearb.h:405
IndexedCompare(const UT_Array< V > &values, const ComparatorBool &compare)
Definition: UT_Array.h:523
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
const T & operator[](exint i) const
Definition: UT_Array.h:799
exint append(const T &t)
Definition: UT_Array.h:143
const T * data() const
Definition: UT_Array.h:850
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less={})
const T * getRawArray() const
Definition: UT_Array.h:844
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:1106
pointer operator->() const
Definition: UT_Array.h:877
base_iterator operator+(exint n) const
Definition: UT_Array.h:924
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1818
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:1151
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
std::make_unsigned_t< exint > UT_LabeledCapacityRep
void stableSort(ComparatorBool is_less={})
Definition: UT_Array.h:492
void bumpCapacity(exint min_capacity)
Definition: UT_Array.h:619
void setSizeIfNeeded(exint minsize)
Definition: UT_Array.h:686
exint insertImpl(S &&s, exint index)
Similar to appendImpl() but for insertion.
void
Definition: png.h:1083
GLint left
Definition: glcorearb.h:2005
SYS_FORCE_INLINE void removeLast()
Definition: UT_Array.h:379
const GLdouble * v
Definition: glcorearb.h:837
void unsafeShareData(T *src, exint size, exint capacity)
Definition: UT_Array.h:1092
exint findAndRemove(const S &s)
void shrinkToFit()
shrinks the capacity to the current size
Definition: UT_Array.h:717
UT_Array< T > & operator=(const UT_Array< T > &a)
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)
void collapseIf(IsEqual is_equal)
Remove all matching elements. Also sets the capacity of the array.
Definition: UT_Array.h:408
T * aliasArray(T *newdata)
Definition: UT_Array.h:854
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:702
bool isValidIndex(exint index) const
Return true if given index is valid.
Definition: UT_Array.h:366
#define SYS_DEPRECATED_HDK_REPLACE(__V__, __R__)
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, float failrelative, float warnrelative, ROI roi={}, int nthreads=0)
void zero()
Zeros the array if a POD type, else trivial constructs if a class type.
base_iterator< const T, false > const_reverse_iterator
Definition: UT_Array.h:1008
GLdouble right
Definition: glad.h:2817
friend void swap(UT_Array< T > &a, UT_Array< T > &b)
Definition: UT_Array.h:1381
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:899
int64 exint
Definition: SYS_Types.h:125
void move(exint src_idx, exint dst_idx, exint how_many)
const_iterator begin() const
Definition: UT_Array.h:1026
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:664
void bumpEntries(exint newsize)
Definition: UT_Array.h:643
const T & heapMax() const
Definition: UT_Array.h:346
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
void cycle(exint how_many)
Cyclically shifts the entire array by how_many.
GLdouble s
Definition: glad.h:3009
exint removeIndex(exint index)
Definition: UT_Array.h:375
T * array()
Definition: UT_Array.h:846
static constexpr struct UT_ArrayCT::GeneralizedMove GENERALIZED_MOVE
const_reverse_iterator rend() const
End reverse iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:1055
#define UT_API
Definition: UT_API.h:14
void setCapacity(exint new_capacity)
PUGI__FN void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7550
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:1116
exint concat(const UT_Array< T > &a)
Takes another T array and concatenate it onto my end.
Definition: UT_ArrayImpl.h:982
exint append(const T &t, bool check_dup)
Definition: UT_Array.h:145
**But if you need a result
Definition: thread.h:622
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:158
exint index(const T &t) const
Definition: UT_Array.h:450
bool operator>=(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:977
exint uniqueSortedInsert(const T &t, Comparator compare)
Definition: UT_Array.h:233
reference item() const
Definition: UT_Array.h:883
exint find(const S &s, exint start=0) const
static bool isClear(const UT_Array< T > &v)
Definition: UT_Array.h:1482
GLuint buffer
Definition: glcorearb.h:660
void unsafeClearData()
Definition: UT_Array.h:1098
exint size() const
Definition: UT_Array.h:653
void setSize(exint newsize)
Definition: UT_Array.h:673
bool operator==(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:942
OutGridT const XformOp bool bool
void sortedUnion(const UT_Array< T > &other, ComparatorBool is_less={})
base_iterator operator-(exint n) const
Definition: UT_Array.h:934
void bumpSize(exint newsize)
Definition: UT_Array.h:636
bool operator>(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:959
void setSizeAndShrink(exint new_size)
convenience method to set size and shrink-to-fit in a single call
Definition: UT_Array.h:723
base_iterator< T, false > reverse_iterator
Definition: UT_Array.h:1007
void unsafeShareData(T *src, exint srcsize)
Definition: UT_Array.h:1086
exint append(T &&t)
Definition: UT_Array.h:144
#define SYS_DEPRECATED_REPLACE(__V__, __R__)
exint operator-(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:987
exint sortAndRemoveDuplicates(ComparatorBool is_less={})
Definition: UT_Array.h:594
const_reverse_iterator rbegin() const
Begin iterating over the array in reverse.
Definition: UT_Array.h:1049
exint safeIndex(const T &t) const
Definition: UT_Array.h:452
GLdouble n
Definition: glcorearb.h:2008
void stableSortByKey(const UT_Array< K > &keys, ComparatorBool is_less)
Definition: UT_Array.h:569
SYS_NO_DISCARD_RESULT SYS_FORCE_INLINE constexpr T * SYSaddressof(T &val) noexcept
exint findIf(IsEqual is_equal, exint start=0) const
exint apply(int(*apply_func)(T &t, void *d), void *d)
reverse_iterator rbegin()
Begin iterating over the array in reverse.
Definition: UT_Array.h:1038
exint emplace_back(S &&...s)
Definition: UT_ArrayImpl.h:769
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:1157
void entries(exint newsize)
Alias of setSize(). setSize() is preferred.
Definition: UT_Array.h:693
exint uniqueSortedInsertImpl(S &&s, Comparator compare)
Definition: UT_ArrayImpl.h:853
T & operator[](exint i)
Definition: UT_Array.h:791
const T & operator()(exint i) const
Definition: UT_Array.h:782
void sort(ComparatorBool is_less={})
Sort using std::sort with bool comparator. Defaults to operator<().
Definition: UT_Array.h:463
reference operator[](exint n) const
Definition: UT_Array.h:886
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
exint insertAt(const T &t, exint index)
Definition: UT_Array.h:362
T accumulate(const T &init_value, BinaryOp add) const
GLuint GLuint end
Definition: glcorearb.h:475
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
exint capacity() const
Definition: UT_ArrayImpl.h:143
base_iterator< T, true > iterator
Definition: UT_Array.h:1005
static void clearConstruct(UT_Array< T > *p)
Definition: UT_Array.h:1483
exint sortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:819
UT_IteratorRange< reverse_iterator > rrange()
Definition: UT_Array.h:1065
exint insert(const T &t, exint i)
Definition: UT_Array.h:155
exint appendImpl(S &&s)
Definition: UT_ArrayImpl.h:746
base_iterator(const base_iterator< EIT, FORWARD > &src)
Definition: UT_Array.h:874
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:795
iterator begin()
Definition: UT_Array.h:1013
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
base_iterator(IT *c, IT *e)
Definition: UT_Array.h:998
void stableSortRange(ComparatorBool is_less, exint start, exint end)
Like stableSort, but operates on a subset of the array.
Definition: UT_Array.h:503
static constexpr struct UT_ArrayCT::ExternalCapacity EXTERNAL_CAPACITY
T forcedGet(exint i) const
Definition: UT_Array.h:818
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:1163
void setCapacityIfNeeded(exint min_capacity)
Definition: UT_Array.h:610
#define SYS_DEPRECATED_HDK(__V__)
exint removeIf(IsEqual is_equal)
const_iterator end() const
End const iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:1031
base_iterator & operator-=(exint n)
Definition: UT_Array.h:932
exint sortedRemoveDuplicates()
void sortedSetDifference(const UT_Array< T > &other, ComparatorBool is_less={})
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:1080
reverse_iterator rend()
End reverse iterator.
Definition: UT_Array.h:1044
exint append()
Definition: UT_Array.h:142
GLdouble t
Definition: glad.h:2397
bool atEnd() const
Definition: UT_Array.h:937
bool operator()(I a, I b) const
Definition: UT_Array.h:528
bool operator!=(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:946
exint sortedRemoveDuplicatesIf(CompareEqual compare_equal)
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:655
T selectNthLargest(exint idx, ComparatorBool is_less={})
base_iterator & operator+=(exint n)
Definition: UT_Array.h:916
GLsizeiptr size
Definition: glcorearb.h:664
GLenum GLenum dst
Definition: glcorearb.h:1793
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:478
#define SYS_DECLARE_IS_NOT_TR_TEMPLATE(...)
Version for class template.
T value_type
Definition: UT_Array.h:93
GLenum void ** pointer
Definition: glcorearb.h:810
static constexpr struct UT_ArrayCT::ExternalMove EXTERNAL_MOVE
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1602
T * data()
Definition: UT_Array.h:849
GLuint index
Definition: glcorearb.h:786
bool isEqual(const UT_Array< T > &a, ComparatorBool is_equal) const
base_iterator operator--(int)
Post-decrement operator.
Definition: UT_Array.h:909
const T & last() const
Definition: UT_Array.h:828
GLuint GLfloat * val
Definition: glcorearb.h:1608
const T * array() const
Definition: UT_Array.h:847
static void clear(UT_Array< T > &v)
Definition: UT_Array.h:1481
int(* Comparator)(const T *, const T *)
Definition: UT_Array.h:95
UT_EXTERN_TEMPLATE(UT_Array< UT_StringHolder >)
base_iterator< const T, true > const_iterator
Definition: UT_Array.h:1006
void stableArgSort(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:556
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:730
void constant(const T &v)
Quickly set the array to a single value.
void removeItem(const reverse_iterator &it)
Remove item specified by the reverse_iterator.
Definition: UT_Array.h:1071
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
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:1393
Comparator class for stableSortIndices.
Definition: UT_Array.h:520
ImageBuf OIIO_API add(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLboolean r
Definition: glcorearb.h:1222
UT_Array(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:519
T & forcedRef(exint i)
Definition: UT_Array.h:808
void clear()
Resets list to an empty list.
Definition: UT_Array.h:736
void stableSortIndices(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:544
UT_IteratorRange< iterator > range()
Definition: UT_Array.h:1060
UT_IteratorRange< const_iterator > range() const
Definition: UT_Array.h:1062
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate and *a name There is also one special expression reference
const_iterator traverser
Definition: UT_Array.h:1009
T & operator()(exint i)
Definition: UT_Array.h:774
GA_API const UT_StringHolder rest
T heapPop(Comparator compare)
Definition: UT_ArrayImpl.h:945
std::random_access_iterator_tag iterator_category
Definition: UT_Array.h:861
exint heapPush(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:928
void reverse()
Reverses the array by swapping elements in mirrored locations.
T * getArray() const
Definition: UT_Array.h:843
exint multipleInsert(exint index, exint count)
Insert an element "count" times at the given index. Return the index.
void removeRange(exint begin_i, exint end_i)
base_iterator operator++(int)
Post-increment operator.
Definition: UT_Array.h:896
void swap(UT_Array< T > &other)
Definition: UT_ArrayImpl.h:676
exint insert(exint index)
Definition: UT_ArrayImpl.h:721
bool hasSortedSubset(const UT_Array< T > &other, ComparatorBool is_less={}) const
GLint GLsizei count
Definition: glcorearb.h:405
Definition: format.h:1821
iterator end()
End iterator.
Definition: UT_Array.h:1018
UT_IteratorRange< const_reverse_iterator > rrange() const
Definition: UT_Array.h:1067
GLenum src
Definition: glcorearb.h:1793
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:657
exint sortedFind(const T &t, Comparator compare) const