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
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")
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,
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.
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 t via binary search using the function specified in the
434  /// parameter list, assuming the array is already sorted with respect to
435  /// compare.
436  /// @returns the index of the matching element or (exint)-1.
437  exint sortedFind(const T &t, Comparator compare) const;
438 
439  /// Reverses the array by swapping elements in mirrored locations.
440  void reverse();
441 
442  /// The fastest search possible, which does pointer arithmetic to find the
443  /// index of the element. WARNING: index() does no out-of-bounds checking.
444  /// @{
445  exint index(const T &t) const { return &t - myData; }
446  exint safeIndex(const T &t) const
447  {
448  return (&t >= myData && &t < (myData + mySize))
449  ? &t - myData : -1;
450  }
451  /// @}
452 
453  /// Sort using std::sort with bool comparator. Defaults to operator<().
454  template <typename ComparatorBool = Less<T>,
455  typename = IsBoolComp<ComparatorBool>>
456  void sort(ComparatorBool is_less = {})
457  {
458  std::sort(myData, myData + mySize, is_less);
459  }
460 
461  /// Sort the array using a comparison function that you must provide. t1 and
462  /// t2 are pointers to Thing. The comparison function uses strcmp()
463  /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
464  SYS_DEPRECATED_HDK_REPLACE(19.5, "Use ComparatorBool variant")
466 
467  /// Sort using std::sort. The ComparatorBool uses the less-than semantics
468  template <typename ComparatorBool,
469  typename = IsBoolComp<ComparatorBool>>
470  SYS_DEPRECATED_REPLACE(19.5, "Use sort(ComparatorBool) overload")
471  void stdsort(ComparatorBool is_less)
472  {
473  std::sort(myData, myData + mySize, is_less);
474  }
475 
476  /// stableSort is both stable, so keeps equal elements in the same
477  /// order (note this is very useful for compatibility between
478  /// compilers) and templated.
479  /// Either use a bool sort function or make a utility class with
480  /// bool operator()(const T a, const T b)
481  /// the utility class lets you bind data to avoid globals.
482  /// The comparator returns true if a must occur before b in the list.
483  /// For sorting ascending, this is a less than operation.
484  template<typename ComparatorBool = Less<T>>
485  void stableSort(ComparatorBool is_less = {})
486  {
487  // No-op for small/empty arrays, avoiding out of
488  // bounds assert on array()
489  if (size() < 2)
490  return;
491 
492  std::stable_sort(array(), array() + size(), is_less);
493  }
494  /// Like stableSort, but operates on a subset of the array.
495  template<typename ComparatorBool>
496  void stableSortRange(ComparatorBool is_less,
497  exint start, exint end)
498  {
499  // No-op for small/empty arrays or ranges, avoiding out of
500  // bounds assert on array()
501  if (end < 0)
502  end = size();
503  if (start < 0)
504  start = 0;
505  if (end < start + 2)
506  return;
507 
508  std::stable_sort(array() + start, array() + end, is_less);
509  }
510 
511  /// Comparator class for stableSortIndices
512  template <typename I, typename V, typename ComparatorBool>
514  {
515  public:
517  const ComparatorBool &compare)
518  : myValues(values)
519  , myCompare(compare)
520  {}
521  inline bool operator()(I a, I b) const
522  { return myCompare(myValues(a), myValues(b)); }
523  private:
524  const UT_Array<V> &myValues;
525  const ComparatorBool &myCompare;
526  };
527 
528  /// Sort indices array by the values indexed into this array using a
529  /// stable sorting algorithm. To reorder the array in such a way
530  /// that it would be sorted, or another array to be reordered the
531  /// same way, include UT_Permute.h and use:
532  /// UTinversePermute(values.getArray(), indices.getArray(),
533  /// values.size());
534  /// The ComparatorBool uses the less-than semantics.
535  /// I must be an integer type.
536  template <typename I, typename ComparatorBool>
538  ComparatorBool is_less) const
539  {
540  IndexedCompare<I, T, ComparatorBool> compare(*this, is_less);
541  std::stable_sort(indices.getArray(),
542  indices.getArray() + indices.size(), compare);
543  }
544 
545  /// Create an index array from 0..n-1 into this array and sort
546  /// it with stableSortIndices.
547  /// The index array will be resized & rebuilt by this.
548  template <typename I, typename ComparatorBool>
550  ComparatorBool is_less) const
551  {
552  indices.setSizeNoInit(size());
553  for (exint i = 0; i < size(); i++)
554  indices(i) = i;
555  stableSortIndices(indices, is_less);
556  }
557 
558  /// Sorts this array by an external key array. We assume a 1:1
559  /// corespondence between our own elements and those of the key
560  /// array. The comparator should be defined on the key type.
561  template <typename K, typename ComparatorBool>
562  void stableSortByKey(const UT_Array<K> &keys, ComparatorBool is_less)
563  {
564  UT_ASSERT(keys.size() == size());
565  if (keys.size() != size())
566  return;
568  keys.stableArgSort(indices, is_less);
569  UTinversePermute(getArray(), indices.getArray(), size());
570  }
571 
572  /// Assuming this array is sorted, remove all duplicate elements.
573  /// Returns the number of elements removed.
575 
576  /// Assuming this array is sorted, remove all duplicate elements using the
577  /// given binary predicate.
578  /// Returns the number of elements removed
579  template <typename CompareEqual>
580  exint sortedRemoveDuplicatesIf(CompareEqual compare_equal);
581 
582  /// Sort and then remove duplicates.
583  /// By default, operator<() is used but if you supply a custom comparator,
584  /// ensure that equal elements are adjacent after sorting.
585  /// Returns the number of elements removed.
586  template<typename ComparatorBool = Less<T>>
587  exint sortAndRemoveDuplicates(ComparatorBool is_less = {})
588  {
589  stableSort(is_less);
590  return sortedRemoveDuplicates();
591  }
592 
593  /// Partitions the array into values greater than or less than
594  /// the Nth element, returns the resulting partition number.
595  /// idx == 0 will get the minimum value, idx == size()-1 the
596  /// maximum value. This does modify this array!
597  template <typename ComparatorBool = Less<T>>
598  T selectNthLargest(exint idx, ComparatorBool is_less = {});
599 
600  /// Set the capacity of the array, i.e. grow it or shrink it. The
601  /// function copies the data after reallocating space for the array.
602  void setCapacity(exint new_capacity);
603  void setCapacityIfNeeded(exint min_capacity)
604  {
605  if (capacity() < min_capacity)
606  setCapacity(min_capacity);
607  }
608  /// If the capacity is smaller than min_capacity, expand the array
609  /// to at least min_capacity and to at least a constant factor of the
610  /// array's previous capacity, to avoid having a linear number of
611  /// reallocations in a linear number of calls to bumpCapacity.
612  void bumpCapacity(exint min_capacity)
613  {
614  if (capacity() >= min_capacity)
615  return;
616  // The following 4 lines are just
617  // SYSmax(min_capacity, UTbumpAlloc(capacity())), avoiding SYSmax
618  exint bumped = UTbumpAlloc(capacity());
619  exint new_capacity = min_capacity;
620  if (bumped > min_capacity)
621  new_capacity = bumped;
622  setCapacity(new_capacity);
623  }
624 
625  /// First bumpCapacity to ensure that there's space for newsize,
626  /// expanding either not at all or by at least a constant factor
627  /// of the array's previous capacity,
628  /// then set the size to newsize.
629  void bumpSize(exint newsize)
630  {
631  bumpCapacity(newsize);
632  setSize(newsize);
633  }
634  /// NOTE: bumpEntries() will be deprecated in favour of bumpSize() in a
635  /// future version.
636  void bumpEntries(exint newsize)
637  {
638  bumpSize(newsize);
639  }
640 
641  /// Query the capacity, i.e. the allocated length of the array.
642  /// NOTE: capacity() >= size().
643  exint capacity() const;
644  /// Query the size, i.e. the number of occupied elements in the array.
645  /// NOTE: capacity() >= size().
646  exint size() const { return mySize; }
647  /// Alias of size(). size() is preferred.
648  exint entries() const { return mySize; }
649  /// Returns true iff there are no occupied elements in the array.
650  bool isEmpty() const { return mySize==0; }
651 
652  /// Returns the amount of memory used by this UT_Array.
653  /// If inclusive is false, it only counts the memory of the array.
654  /// This is often necessary to avoid double-counting, e.g. if this
655  /// UT_Array is a member variable of a class whose memory is already
656  /// being counted by the caller.
657  int64 getMemoryUsage(bool inclusive=false) const
658  {
659  return (inclusive ? sizeof(*this) : 0) + capacity()*sizeof(T); // NOLINT
660  }
661 
662  /// Set the size, the number of occupied elements in the array.
663  /// NOTE: This will not do bumpCapacity, so if you call this
664  /// n times to increase the size, it may take
665  /// n^2 time.
666  void setSize(exint newsize)
667  {
668  if (newsize < 0)
669  newsize = 0;
670  if (newsize == mySize)
671  return;
672  setCapacityIfNeeded(newsize);
673  if (mySize > newsize)
674  destroyRange(myData + newsize, mySize - newsize);
675  else // newsize > mySize
676  constructRange(myData + mySize, newsize - mySize);
677  mySize = newsize;
678  }
679  void setSizeIfNeeded(exint minsize)
680  {
681  if (size() >= minsize)
682  return;
683  setSize(minsize);
684  }
685  /// Alias of setSize(). setSize() is preferred.
686  void entries(exint newsize)
687  {
688  setSize(newsize);
689  }
690  /// Set the size, but unlike setSize(newsize), this function
691  /// will not initialize new POD elements to zero. Non-POD data types
692  /// will still have their constructors called.
693  /// This function is faster than setSize(ne) if you intend to fill in
694  /// data for all elements.
695  void setSizeNoInit(exint newsize)
696  {
697  if (newsize < 0)
698  newsize = 0;
699  if (newsize == mySize)
700  return;
701  setCapacityIfNeeded(newsize);
702  if (mySize > newsize)
703  destroyRange(myData + newsize, mySize - newsize);
704  else if (!isPOD()) // newsize > mySize
705  constructRange(myData + mySize, newsize - mySize);
706  mySize = newsize;
707  }
708 
709  /// Decreases, but never expands, to the given maxsize.
710  void truncate(exint maxsize)
711  {
712  if (maxsize >= 0 && size() > maxsize)
713  setSize(maxsize);
714  }
715  /// Resets list to an empty list.
716  void clear()
717  {
718  // Don't call setSize(0) since it supports growing the array
719  // which requires a default constructor. Avoiding it allows
720  // this to be used on types that lack a default constructor.
721  destroyRange(myData, mySize);
722  mySize = 0;
723  }
724 
725  /// Assign array a to this array by copying each of a's elements with
726  /// memcpy for POD types, and with copy construction for class types.
728 
729  /// Replace the contents with those from the initializer_list ilist
730  UT_Array<T> & operator=(std::initializer_list<T> ilist);
731 
732  /// Move the contents of array a to this array.
734 
735  /// Compare two array and return true if they are equal and false otherwise.
736  /// Two elements are checked against each other using operator '==' or
737  /// compare() respectively.
738  /// NOTE: The capacities of the arrays are not checked when
739  /// determining whether they are equal.
740  bool operator==(const UT_Array<T> &a) const;
741  bool operator!=(const UT_Array<T> &a) const;
742  int isEqual(const UT_Array<T> &a, Comparator compare) const;
743 
744  /// Subscript operator
745  /// NOTE: This does NOT do any bounds checking unless paranoid
746  /// asserts are enabled.
748  {
749  UT_ASSERT_P(i >= 0 && i < mySize);
750  return myData[i];
751  }
752  /// Const subscript operator
753  /// NOTE: This does NOT do any bounds checking unless paranoid
754  /// asserts are enabled.
755  const T & operator()(exint i) const
756  {
757  UT_ASSERT_P(i >= 0 && i < mySize);
758  return myData[i];
759  }
760 
761  /// Subscript operator
762  /// NOTE: This does NOT do any bounds checking unless paranoid
763  /// asserts are enabled.
765  {
766  UT_ASSERT_P(i >= 0 && i < mySize);
767  return myData[i];
768  }
769  /// Const subscript operator
770  /// NOTE: This does NOT do any bounds checking unless paranoid
771  /// asserts are enabled.
772  const T & operator[](exint i) const
773  {
774  UT_ASSERT_P(i >= 0 && i < mySize);
775  return myData[i];
776  }
777 
778  /// forcedRef(exint) will grow the array if necessary, initializing any
779  /// new elements to zero for POD types and default constructing for
780  /// class types.
782  {
783  UT_ASSERT_P(i >= 0);
784  if (i >= mySize)
785  bumpSize(i+1);
786  return myData[i];
787  }
788 
789  /// forcedGet(exint) does NOT grow the array, and will return default
790  /// objects for out of bound array indices.
791  T forcedGet(exint i) const
792  {
793  return (i >= 0 && i < mySize) ? myData[i] : T();
794  }
795 
796  T & last()
797  {
798  UT_ASSERT_P(mySize);
799  return myData[mySize-1];
800  }
801  const T & last() const
802  {
803  UT_ASSERT_P(mySize);
804  return myData[mySize-1];
805  }
806 
807  /// Apply a user-defined function to each element of the array
808  /// as int as the function returns zero. If apply_func returns
809  /// 1, apply() stops traversing the list and returns the current
810  /// index; otherwise, apply() returns the size.
811  exint apply(int (*apply_func)(T &t, void *d), void *d);
812 
813  template <typename BinaryOp>
814  T accumulate(const T &init_value, BinaryOp add) const;
815 
816  T * getArray() const { return myData; }
817  const T * getRawArray() const { return myData; }
818 
819  T * array() { return myData; }
820  const T * array() const { return myData; }
821 
822  T * data() { return myData; }
823  const T * data() const { return myData; }
824 
825  /// This method allows you to swap in a new raw T array, which must be
826  /// the same size as capacity(). Use caution with this method.
827  T * aliasArray(T *newdata)
828  { T *data = myData; myData = newdata; return data; }
829 
830  template <typename IT, bool FORWARD>
832  {
833  public:
834  using iterator_category = std::random_access_iterator_tag;
835  using value_type = T;
837  using pointer = IT*;
838  using reference = IT&;
839 
840  // Note: When we drop gcc 4.4 support and allow range-based for
841  // loops, we should also drop atEnd(), which means we can drop
842  // myEnd here.
843  base_iterator() : myCurrent(nullptr), myEnd(nullptr) {}
844 
845  // Allow iterator to const_iterator conversion
846  template<typename EIT>
848  : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
849 
851  { return FORWARD ? myCurrent : myCurrent - 1; }
852 
854  { return FORWARD ? *myCurrent : myCurrent[-1]; }
855 
856  reference item() const
857  { return FORWARD ? *myCurrent : myCurrent[-1]; }
858 
860  { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; }
861 
862  /// Pre-increment operator
864  {
865  if (FORWARD) ++myCurrent; else --myCurrent;
866  return *this;
867  }
868  /// Post-increment operator
870  {
871  base_iterator tmp = *this;
872  if (FORWARD) ++myCurrent; else --myCurrent;
873  return tmp;
874  }
875  /// Pre-decrement operator
877  {
878  if (FORWARD) --myCurrent; else ++myCurrent;
879  return *this;
880  }
881  /// Post-decrement operator
883  {
884  base_iterator tmp = *this;
885  if (FORWARD) --myCurrent; else ++myCurrent;
886  return tmp;
887  }
888 
890  {
891  if (FORWARD)
892  myCurrent += n;
893  else
894  myCurrent -= n;
895  return *this;
896  }
898  {
899  if (FORWARD)
900  return base_iterator(myCurrent + n, myEnd);
901  else
902  return base_iterator(myCurrent - n, myEnd);
903  }
904 
906  { return (*this) += (-n); }
908  { return (*this) + (-n); }
909 
910  bool atEnd() const { return myCurrent == myEnd; }
911  void advance() { this->operator++(); }
912 
913  // Comparators
914  template<typename ITR, bool FR>
916  { return myCurrent == r.myCurrent; }
917 
918  template<typename ITR, bool FR>
920  { return myCurrent != r.myCurrent; }
921 
922  template<typename ITR>
923  bool operator<(const base_iterator<ITR, FORWARD> &r) const
924  {
925  if (FORWARD)
926  return myCurrent < r.myCurrent;
927  else
928  return r.myCurrent < myCurrent;
929  }
930 
931  template<typename ITR>
933  {
934  if (FORWARD)
935  return myCurrent > r.myCurrent;
936  else
937  return r.myCurrent > myCurrent;
938  }
939 
940  template<typename ITR>
941  bool operator<=(const base_iterator<ITR, FORWARD> &r) const
942  {
943  if (FORWARD)
944  return myCurrent <= r.myCurrent;
945  else
946  return r.myCurrent <= myCurrent;
947  }
948 
949  template<typename ITR>
951  {
952  if (FORWARD)
953  return myCurrent >= r.myCurrent;
954  else
955  return r.myCurrent >= myCurrent;
956  }
957 
958  // Difference operator for std::distance
959  template<typename ITR>
961  {
962  if (FORWARD)
963  return exint(myCurrent - r.myCurrent);
964  else
965  return exint(r.myCurrent - myCurrent);
966  }
967 
968 
969  protected:
970  friend class UT_Array<T>;
971  base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
972  private:
973 
974  IT *myCurrent;
975  IT *myEnd;
976  };
977 
978  typedef base_iterator<T, true> iterator;
979  typedef base_iterator<const T, true> const_iterator;
980  typedef base_iterator<T, false> reverse_iterator;
981  typedef base_iterator<const T, false> const_reverse_iterator;
982  typedef const_iterator traverser; // For backward compatibility
983 
984  /// Begin iterating over the array. The contents of the array may be
985  /// modified during the traversal.
987  {
988  return iterator(myData, myData + mySize);
989  }
990  /// End iterator.
992  {
993  return iterator(myData + mySize,
994  myData + mySize);
995  }
996 
997  /// Begin iterating over the array. The array may not be modified during
998  /// the traversal.
1000  {
1001  return const_iterator(myData, myData + mySize);
1002  }
1003  /// End const iterator. Consider using it.atEnd() instead.
1005  {
1006  return const_iterator(myData + mySize,
1007  myData + mySize);
1008  }
1009 
1010  /// Begin iterating over the array in reverse.
1012  {
1013  return reverse_iterator(myData + mySize,
1014  myData);
1015  }
1016  /// End reverse iterator.
1018  {
1019  return reverse_iterator(myData, myData);
1020  }
1021  /// Begin iterating over the array in reverse.
1023  {
1024  return const_reverse_iterator(myData + mySize,
1025  myData);
1026  }
1027  /// End reverse iterator. Consider using it.atEnd() instead.
1029  {
1030  return const_reverse_iterator(myData, myData);
1031  }
1032 
1034  { return UT_IteratorRange<iterator>(begin(), end()); }
1036  { return UT_IteratorRange<const_iterator>(begin(), end()); }
1037 
1042 
1043  /// Remove item specified by the reverse_iterator.
1045  {
1046  removeAt(&it.item() - myData);
1047  }
1048 
1049 
1050  /// Very dangerous methods to share arrays.
1051  /// The array is not aware of the sharing, so ensure you clear
1052  /// out the array prior a destructor or setCapacity operation.
1054  {
1055  myData = src.myData;
1056  myCapacity = labelExternal( src.capacity() );
1057  mySize = src.mySize;
1058  }
1059  void unsafeShareData(T *src, exint srcsize)
1060  {
1061  myData = src;
1062  myCapacity = labelExternal( srcsize );
1063  mySize = srcsize;
1064  }
1066  {
1067  myData = src;
1068  mySize = size;
1069  myCapacity = labelExternal( capacity );
1070  }
1072  {
1073  myData = nullptr;
1074  myCapacity = labelExternal( 0 );
1075  mySize = 0;
1076  }
1077 
1078  /// Returns true if the data used by the array was allocated on the heap.
1079  inline bool isHeapBuffer() const
1080  {
1081  return isHeapBuffer(myData);
1082  }
1083 
1084 protected:
1085  // Check whether T may have a constructor, destructor, or copy
1086  // constructor. This test is conservative in that some POD types will
1087  // not be recognized as POD by this function. To mark your type as POD,
1088  // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
1089  static constexpr SYS_FORCE_INLINE bool isPOD()
1090  {
1091  return SYS_IsPod_v< T >;
1092  }
1093 
1094  /// Implements both append(const T &) and append(T &&) via perfect
1095  /// forwarding. Unlike the variadic emplace_back(), its argument may be a
1096  /// reference to another element in the array.
1097  template <typename S>
1098  exint appendImpl(S &&s);
1099 
1100  /// Similar to appendImpl() but for insertion.
1101  template <typename S>
1102  exint insertImpl(S &&s, exint index);
1103 
1104  template <typename S>
1105  SYS_DEPRECATED_HDK(13.0)
1107 
1108  /// In debug builds, verifies that the arguments to emplace_back() will not
1109  /// be invalidated when realloc() is called.
1110  template <typename First, typename... Rest>
1111  void validateEmplaceArgs(First &&first, Rest&&... rest) const
1112  {
1114  static_cast<const void *>(&first) <
1115  static_cast<const void *>(myData) ||
1116  static_cast<const void *>(&first) >=
1117  static_cast<const void *>(myData + mySize),
1118  "Argument cannot reference an existing element in the array.");
1119 
1120  validateEmplaceArgs(std::forward<Rest>(rest)...);
1121  }
1122 
1123  /// Base case for validateEmplaceArgs().
1124  void validateEmplaceArgs() const
1125  {
1126  }
1127 
1128  // Construct the given type
1129  template <typename... S>
1130  static void construct(T &dst, S&&... s)
1131  {
1132  new (&dst) T(std::forward<S>(s)...);
1133  }
1134 
1135  // Copy construct the given type
1136  static void copyConstruct(T &dst, const T &src)
1137  {
1138  if constexpr( SYS_IsPod_v< T > )
1139  {
1140  dst = src;
1141  }
1142  else // constexpr
1143  {
1144  new (&dst) T(src);
1145  }
1146  }
1147 
1148 private:
1149  /// Equivalent to std::back_insert_iterator, but using the append() method
1150  /// for UT_Array. This is useful for appending to an array via STL
1151  /// algorithms that have an output iterator
1152  class AppendIterator
1153  {
1154  public:
1155  using iterator_category = std::output_iterator_tag;
1156  using value_type = void;
1157  using difference_type = void;
1158  using pointer = void;
1159  using reference = void;
1160 
1161  explicit AppendIterator(UT_Array<T> &arr) : myArray(&arr) {}
1162 
1163  /// @{
1164  /// Append the value when the iterator is assigned to.
1165  AppendIterator &operator=(const T &val)
1166  {
1167  myArray->append(val);
1168  return *this;
1169  }
1170 
1171  AppendIterator &operator=(T &&val)
1172  {
1173  myArray->append(std::move(val));
1174  return *this;
1175  }
1176  /// @}
1177 
1178  /// @{
1179  /// This iterator does not move, and dereferencing just returns itself.
1180  AppendIterator &operator*() { return *this; }
1181  AppendIterator &operator++() { return *this; }
1182  AppendIterator operator++(int) { return *this; }
1183  /// @}
1184 
1185  private:
1186  UT_Array<T> *myArray;
1187  };
1188 
1189 #ifdef UT_ARRAY_STRICT_LABELED_CAPACITY
1190  using LabeledCapacity = UT_LabeledCapacity;
1191 #else
1192  using LabeledCapacity = UT_LabeledCapacityRep;
1193 #endif
1194 
1195  /// Pointer to the array of elements of type T
1196  T *myData;
1197 
1198  /// The number of elements for which we have allocated memory
1199  LabeledCapacity myCapacity;
1200 
1201  /// The actual number of valid elements in the array
1202  exint mySize;
1203 
1204  // Create a Capacity that's labeled as owned by this UT_Array
1205  static LabeledCapacity labelOwned(const exint capacity) noexcept;
1206 
1207  // Create a Capacity that's labeled as external (not owned by this UT_Array)
1208  static LabeledCapacity labelExternal(const exint capacity) noexcept;
1209 
1210  // All memory allocations, reallocations and deallocations in UT_Array's
1211  // implementation go through the three functions
1212  // allocateArray, reallocateArray, deallocateArray below.
1213  // These functions make no calls to constructors/destructors.
1214 
1215  // Return an array with given capacity for elements of type T.
1216  // PRE: capacity > 0
1217  static T *allocateArray(const exint capacity) noexcept;
1218 
1219  // Return an array with given capacity for elements of type T.
1220  // reusing the passed-in 'data' if possible.
1221  // PRE: capacity > 0
1222  static T *reallocateArray(T *data, const exint capacity) noexcept;
1223 
1224  // NOTE: This will work correctly with data == nullptr
1225  static void deallocateArray(T *data) noexcept;
1226 
1227  // Identify whether 'data' is a heap buffer.
1228  // 'data' is decided to be a heap buffer when it is not
1229  // located at the first memory location after this UT_Array object
1230  // (a trick used by UT_SmallArray).
1231  // If a call to 'allocateArray' happens to return the first memory
1232  // location after this UT_Array object, then isHeapBuffer ends up false.
1233  // To avoid this, a second allocation should then by attempted,
1234  // see 'allocateArrayHeapIdentifiable' below.
1235  bool isHeapBuffer(T* data) const;
1236 
1237  // Like allocateArray, except ensure that the returned array 'data'
1238  // is NOT located at the end of this UT_Array object, so that
1239  // isHeapBuffer( data) is true.
1240  // PRE: capacity > 0
1241  T *allocateArrayHeapIdentifiable(const exint capacity);
1242 
1243  //
1244  // Construct/destroy elements and ranges.
1245  // For POD types, construct* fills T objects with zeroes,
1246  // and destroy* does nothing.
1247  // For non-POD types, construct* calls the regular constructor
1248  // (by way of placement new), and destroy* calls the regular destructor.
1249  //
1250 
1251  static void constructElement(T &dst);
1252  static void constructRange(T *dst, exint n);
1253 
1254  static void destroyElement(T &dst) noexcept;
1255  static void destroyRange([[maybe_unused]] T *dst, exint n) noexcept;
1256 
1257  //
1258  // About relocation:
1259  // Relocating [ src, src + n ) to [ dst, dst + n ) should be equivalent
1260  // to the following:
1261  // For each i in [ 0, n ):
1262  // 1. move construct dst[ i ] from src[ i ]
1263  // 2. destroy src[ i ]
1264  //
1265  // The trivial relocation macros and traits defined in SYS_TypeDecorate.h
1266  // and SYS_TypeTraits.h can be used to indicate for which types T
1267  // bitwise copying is equivalent to the above construct and destroy steps.
1268  //
1269 
1270  // The below "standardRelocate" methods relocate
1271  // [ src, src + n ) to [ dst, dst + n ) by invoking
1272  // T's move constructor and destructor.
1273 
1274  // Relocate elements in increasing order 0, 1, ..., n - 1
1275  static void standardRelocateIncreasing(T *dst, T *src, exint n);
1276 
1277  // Relocate elements in decreasing order n - 1,, ..., 1, 0
1278  static void standardRelocateDecreasing(T *dst, T *src, exint n);
1279 
1280  // For use in cases where the source and destination ranges may overlap:
1281  // Relocate in increasing order if dst < src and
1282  // relocate in decreasing order if src < dst.
1283  static void standardRelocate(T *dst, T *src, exint n);
1284 
1285  //
1286  // The below "bitwiseRelocate" methods relocate
1287  // [ src, src + n ) to [ dst, dst +n ) using memcpy and memmove,
1288  // and do not invoke destructors afterwards.
1289  //
1290 
1291  // PRE:
1292  // * both 'dst' and 'src' are valid (not null)
1293  static void bitwiseRelocate(T *dst, const T *src, exint n) noexcept;
1294 
1295  // PRE:
1296  // * both 'dst' and 'src' are valid (not null)
1297  // * [ dst, dst + n ) and [ src, src + n ) don't overlap
1298  static void bitwiseRelocateNonoverlapping(
1299  T *dst,
1300  const T *src,
1301  exint n) noexcept;
1302 
1303  //
1304  // The below relocate, copy and swap methods decide whether to use
1305  // standard or bitwise copying at compile time, based on traits.
1306  // Only these are the versions should be called directly by
1307  // the rest of the UT_Array implementation.
1308  //
1309 
1310  // For trivially relocatable types, bitwise copy [ src, src + n )
1311  // onto [ dst, dst + n ) instead.
1312  static void relocate(T *dst, T *src, exint n);
1313 
1314  // Version of relocate with a stronger precondition that is
1315  // exploited for potentially faster computation:
1316  // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
1317  static void relocateNonoverlapping(T *dst, T *src, exint n);
1318 
1319  // PRE: dst < src
1320  static void relocateIncreasing(T *dst, T *src, exint n);
1321 
1322  // PRE: dst > src
1323  static void relocateDecreasing(T *dst, T *src, exint n);
1324 
1325  // copyNonoverlapping is similar to relocateNonoverlapping,
1326  // with the following to differences:
1327  // * Each value is copy constructed into its destination (not moved)
1328  // * The source values are not destroyed (no destructor invoked)
1329  // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
1330  static void copyNonoverlapping(T *dst, const T *src, exint n);
1331 
1332  // swapNonoverlapping is equivalent to the following:
1333  // For each i in [ 0, n ): swap dst[ i ] and src[ i ]
1334  static void swapNonoverlapping(T *dst, T *src, exint n);
1335 
1336  // The guts of the remove() methods.
1337  exint removeAt(exint index);
1338 
1339  // Convert the current object's buffer from a non-heap buffer
1340  // to a heap buffer of given capacity
1341  // PRE: *this has a non-heap buffer
1342  // 'capacity' should be at least the size
1343  // POST: *this has a heap buffer with given capacity,
1344  // and its initial size elements are the same as before the call
1345  void convertToHeapBuffer(const exint capacity);
1346 
1347  template<typename OS, typename S>
1348  friend OS &operator<<(OS &os, const UT_Array<S> &d);
1349 
1350  /// Friend specialization of std::swap() to use UT_String::swap()
1351  /// @internal This is needed because standard std::swap() implementations
1352  /// will try to copy the UT_String objects, causing hardened strings to
1353  /// become weak.
1354  friend void swap(UT_Array<T>& a, UT_Array<T>& b) { a.swap(b); }
1355 };
1356 
1357 // Suppress UT_Array<UT_StringHolder> instantations to avoid duplicate symbols
1358 // when UT_Array<UT_StringHolder> is used with UT_StringArray which derives
1359 // from it.
1360 class UT_StringHolder;
1362 
1363 // Assigns src to dest, using the default C++ conversion operator.
1364 template <typename T, typename S>
1365 void
1367 {
1368  exint n = src.size();
1369  dest.setCapacity(n);
1370  dest.setSize(n);
1371  for (exint i = 0; i < n; i++)
1372  dest(i) = T(src(i));
1373 }
1374 template <typename T, typename S>
1375 void
1377 {
1378  dest.setCapacity(n);
1379  dest.setSize(n);
1380  for (exint i = 0; i < n; i++)
1381  dest(i) = T(src[i]);
1382 }
1383 template <typename T, typename S>
1384 void
1386 {
1387  // We assume here that dest has enough memory for src.size()
1388  exint n = src.size();
1389  for (exint i = 0; i < n; i++)
1390  dest[i] = T(src(i));
1391 }
1392 template <typename T, typename S>
1393 void
1394 UTconvertArray(T *dest, const S *src, int64 n)
1395 {
1396  // We assume here that dest has enough memory for n elements
1397  for (int64 i = 0; i < n; i++)
1398  dest[i] = T(src[i]);
1399 }
1400 
1401 #include "UT_ArrayImpl.h"
1402 
1403 
1404 template<typename OS, typename S>
1405 inline OS &
1406 operator<<(OS &os, const UT_Array<S> &d)
1407 {
1408  os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
1409  return os;
1410 }
1411 
1412 // Overload for custom formatting of a UT_StringArray with UTformat.
1413 template <typename T> UT_API size_t
1414 format(char *buffer, size_t bufsize, const UT_Array<T> &v);
1415 
1416 /// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
1417 /// its elements
1418 template <template <typename> class ArrayT, typename T>
1419 static inline int64
1420 UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
1421 {
1422  int64 mem = inclusive ? sizeof(arr) : 0;
1423  mem += arr.getMemoryUsage(false);
1424  for (auto &&item : arr)
1425  mem += item.getMemoryUsage(false);
1426  return mem;
1427 }
1428 
1429 /// Utility to sort array using operator<
1430 template <typename T>
1431 static inline void
1432 UTsort(UT_Array<T> &arr)
1433 {
1434  arr.sort([](const T &a, const T &b) { return a < b; });
1435 }
1436 
1437 /// Utility to sort array using operator< and remove duplicates
1438 template <typename T>
1439 static inline void
1440 UTsortAndRemoveDuplicates(UT_Array<T> &arr)
1441 {
1442  arr.sortAndRemoveDuplicates([](const T &a, const T &b) { return a < b; });
1443 }
1444 
1445 // For UT::ArraySet.
1446 namespace UT
1447 {
1448 template <typename T>
1449 struct DefaultClearer;
1450 
1451 template <typename T>
1453 {
1454  static void clear(UT_Array<T> &v) { v.setCapacity(0); }
1455  static bool isClear(const UT_Array<T> &v) { return v.capacity() == 0; }
1456  static void clearConstruct(UT_Array<T> *p)
1457  {
1458  new ((void *)p) UT_Array<T>();
1459  }
1460  static const bool clearNeedsDestruction = false;
1461 };
1462 } // namespace UT
1463 
1464 //
1465 // Trivial relocation is not safe for UT_Array:
1466 // UT_SmallArray, which has a fixed-buffer optimization inherits from UT_Array.
1467 // At compile time, it cannot be known whether a UT_Array object is a
1468 // UT_SmallArray object.
1469 // For this reason alone, it cannot be safe to use trivial relocation on UT_Array.
1470 //
1471 // In addition to that, UT_Array is currently not safe for trivial relocation
1472 // even if UT_SmallArray didn't get used anywhere, due to the isHeapBuffer() test,
1473 // which may incorrectly return false after a UT_Array with a heap buffer gets
1474 // trivially relocated (making it adjacent in memory to its myData).
1475 //
1476 template <typename T>
1478 
1479 //
1480 // Trivial relocation is not safe for std::string since most implementations
1481 // use a small buffer optimization (aka SBO).
1482 //
1483 #if defined(MBSD) || defined(_LIBCPP_VERSION)
1484  #include <iosfwd>
1485  template <typename CharT, typename Traits, typename Allocator>
1487 #elif defined(__GLIBCXX__)
1488  #include <bits/stringfwd.h>
1489  template <typename CharT, typename Traits, typename Allocator>
1491 #else
1492  namespace std { template <class,class,class> class basic_string; }
1493  template <typename CharT, typename Traits, typename Allocator>
1495 #endif
1496 
1497 #endif // __UT_ARRAY_H_INCLUDED__
reference operator*() const
Definition: UT_Array.h:853
base_iterator & operator++()
Pre-increment operator.
Definition: UT_Array.h:863
int isEqual(const UT_Array< T > &a, Comparator compare) const
base_iterator & operator--()
Pre-decrement operator.
Definition: UT_Array.h:876
T & last()
Definition: UT_Array.h:796
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:516
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
const T & operator[](exint i) const
Definition: UT_Array.h:772
exint append(const T &t)
Definition: UT_Array.h:143
const T * data() const
Definition: UT_Array.h:823
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less={})
const T * getRawArray() const
Definition: UT_Array.h:817
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:1079
pointer operator->() const
Definition: UT_Array.h:850
base_iterator operator+(exint n) const
Definition: UT_Array.h:897
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1818
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:1124
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
std::make_unsigned_t< exint > UT_LabeledCapacityRep
bool operator!=(const UT_Array< T > &a) const
void stableSort(ComparatorBool is_less={})
Definition: UT_Array.h:485
void bumpCapacity(exint min_capacity)
Definition: UT_Array.h:612
void setSizeIfNeeded(exint minsize)
Definition: UT_Array.h:679
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:1065
exint findAndRemove(const S &s)
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:827
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:695
bool isValidIndex(exint index) const
Return true if given index is valid.
Definition: UT_Array.h:366
#define SYS_DEPRECATED_HDK_REPLACE(__V__, __R__)
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:981
GLdouble right
Definition: glad.h:2817
friend void swap(UT_Array< T > &a, UT_Array< T > &b)
Definition: UT_Array.h:1354
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:999
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:657
void bumpEntries(exint newsize)
Definition: UT_Array.h:636
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:819
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:1028
#define UT_API
Definition: UT_API.h:14
void setCapacity(exint new_capacity)
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:1089
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:613
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:158
exint index(const T &t) const
Definition: UT_Array.h:445
bool operator>=(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:950
exint uniqueSortedInsert(const T &t, Comparator compare)
Definition: UT_Array.h:233
reference item() const
Definition: UT_Array.h:856
exint find(const S &s, exint start=0) const
static bool isClear(const UT_Array< T > &v)
Definition: UT_Array.h:1455
void unsafeClearData()
Definition: UT_Array.h:1071
exint size() const
Definition: UT_Array.h:646
void setSize(exint newsize)
Definition: UT_Array.h:666
bool operator==(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:915
void sortedUnion(const UT_Array< T > &other, ComparatorBool is_less={})
base_iterator operator-(exint n) const
Definition: UT_Array.h:907
void bumpSize(exint newsize)
Definition: UT_Array.h:629
bool operator>(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:932
base_iterator< T, false > reverse_iterator
Definition: UT_Array.h:980
void unsafeShareData(T *src, exint srcsize)
Definition: UT_Array.h:1059
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:960
exint sortAndRemoveDuplicates(ComparatorBool is_less={})
Definition: UT_Array.h:587
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:1022
exint safeIndex(const T &t) const
Definition: UT_Array.h:446
GLdouble n
Definition: glcorearb.h:2008
void stableSortByKey(const UT_Array< K > &keys, ComparatorBool is_less)
Definition: UT_Array.h:562
Definition: core.h:760
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:1011
exint emplace_back(S &&...s)
Definition: UT_ArrayImpl.h:769
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:1130
void entries(exint newsize)
Alias of setSize(). setSize() is preferred.
Definition: UT_Array.h:686
exint uniqueSortedInsertImpl(S &&s, Comparator compare)
Definition: UT_ArrayImpl.h:853
T & operator[](exint i)
Definition: UT_Array.h:764
const T & operator()(exint i) const
Definition: UT_Array.h:755
void sort(ComparatorBool is_less={})
Sort using std::sort with bool comparator. Defaults to operator<().
Definition: UT_Array.h:456
reference operator[](exint n) const
Definition: UT_Array.h:859
#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:978
static void clearConstruct(UT_Array< T > *p)
Definition: UT_Array.h:1456
exint sortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:819
UT_IteratorRange< reverse_iterator > rrange()
Definition: UT_Array.h:1038
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:847
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:795
iterator begin()
Definition: UT_Array.h:986
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:971
void stableSortRange(ComparatorBool is_less, exint start, exint end)
Like stableSort, but operates on a subset of the array.
Definition: UT_Array.h:496
static constexpr struct UT_ArrayCT::ExternalCapacity EXTERNAL_CAPACITY
T forcedGet(exint i) const
Definition: UT_Array.h:791
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:1136
void setCapacityIfNeeded(exint min_capacity)
Definition: UT_Array.h:603
#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:1004
base_iterator & operator-=(exint n)
Definition: UT_Array.h:905
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:1053
reverse_iterator rend()
End reverse iterator.
Definition: UT_Array.h:1017
exint append()
Definition: UT_Array.h:142
GLdouble t
Definition: glad.h:2397
bool atEnd() const
Definition: UT_Array.h:910
bool operator()(I a, I b) const
Definition: UT_Array.h:521
bool operator!=(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:919
exint sortedRemoveDuplicatesIf(CompareEqual compare_equal)
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:648
T selectNthLargest(exint idx, ComparatorBool is_less={})
base_iterator & operator+=(exint n)
Definition: UT_Array.h:889
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:471
#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:822
GLuint index
Definition: glcorearb.h:786
base_iterator operator--(int)
Post-decrement operator.
Definition: UT_Array.h:882
const T & last() const
Definition: UT_Array.h:801
GLuint GLfloat * val
Definition: glcorearb.h:1608
const T * array() const
Definition: UT_Array.h:820
static void clear(UT_Array< T > &v)
Definition: UT_Array.h:1454
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:979
void stableArgSort(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:549
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:710
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:1044
#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:1366
Comparator class for stableSortIndices.
Definition: UT_Array.h:513
ImageBuf OIIO_API add(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLboolean r
Definition: glcorearb.h:1222
#define const
Definition: zconf.h:214
UT_Array(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:519
T & forcedRef(exint i)
Definition: UT_Array.h:781
void clear()
Resets list to an empty list.
Definition: UT_Array.h:716
void stableSortIndices(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:537
UT_IteratorRange< iterator > range()
Definition: UT_Array.h:1033
UT_IteratorRange< const_iterator > range() const
Definition: UT_Array.h:1035
const_iterator traverser
Definition: UT_Array.h:982
T & operator()(exint i)
Definition: UT_Array.h:747
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:834
exint heapPush(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:928
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
void reverse()
Reverses the array by swapping elements in mirrored locations.
T * getArray() const
Definition: UT_Array.h:816
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:869
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:895
iterator end()
End iterator.
Definition: UT_Array.h:991
UT_IteratorRange< const_reverse_iterator > rrange() const
Definition: UT_Array.h:1040
GLenum src
Definition: glcorearb.h:1793
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:650
bool operator==(const UT_Array< T > &a) const
exint sortedFind(const T &t, Comparator compare) const