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