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)
127  exint sortedInsert(const T &t, Comparator compare);
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  /// Alias of setSize(). setSize() is preferred.
483  void entries(exint newsize)
484  {
485  setSize(newsize);
486  }
487  /// Set the size, but unlike setSize(newsize), this function
488  /// will not initialize new POD elements to zero. Non-POD data types
489  /// will still have their constructors called.
490  /// This function is faster than setSize(ne) if you intend to fill in
491  /// data for all elements.
492  void setSizeNoInit(exint newsize)
493  {
494  if (newsize < 0)
495  newsize = 0;
496  if (newsize == mySize)
497  return;
498  setCapacityIfNeeded(newsize);
499  if (mySize > newsize)
500  trivialDestructRange(myData + newsize, mySize - newsize);
501  else if (!isPOD()) // newsize > mySize
502  trivialConstructRange(myData + mySize, newsize - mySize);
503  mySize = newsize;
504  }
505 
506  /// Decreases, but never expands, to the given maxsize.
507  void truncate(exint maxsize)
508  {
509  if (maxsize >= 0 && size() > maxsize)
510  setSize(maxsize);
511  }
512  /// Resets list to an empty list.
513  void clear() {
514  // Don't call setSize(0) since that would require a valid default
515  // constructor.
516  trivialDestructRange(myData, mySize);
517  mySize = 0;
518  }
519 
520  /// Assign array a to this array by copying each of a's elements with
521  /// memcpy for POD types, and with copy construction for class types.
523 
524  /// Replace the contents with those from the initializer_list ilist
525  UT_Array<T> & operator=(std::initializer_list<T> ilist);
526 
527  /// Move the contents of array a to this array.
529 
530  /// Compare two array and return true if they are equal and false otherwise.
531  /// Two elements are checked against each other using operator '==' or
532  /// compare() respectively.
533  /// NOTE: The capacities of the arrays are not checked when
534  /// determining whether they are equal.
535  bool operator==(const UT_Array<T> &a) const;
536  bool operator!=(const UT_Array<T> &a) const;
537  int isEqual(const UT_Array<T> &a, Comparator compare) const;
538 
539  /// Subscript operator
540  /// NOTE: This does NOT do any bounds checking unless paranoid
541  /// asserts are enabled.
543  {
544  UT_ASSERT_P(i >= 0 && i < mySize);
545  return myData[i];
546  }
547  /// Const subscript operator
548  /// NOTE: This does NOT do any bounds checking unless paranoid
549  /// asserts are enabled.
550  const T & operator()(exint i) const
551  {
552  UT_ASSERT_P(i >= 0 && i < mySize);
553  return myData[i];
554  }
555 
556  /// Subscript operator
557  /// NOTE: This does NOT do any bounds checking unless paranoid
558  /// asserts are enabled.
560  {
561  UT_ASSERT_P(i >= 0 && i < mySize);
562  return myData[i];
563  }
564  /// Const subscript operator
565  /// NOTE: This does NOT do any bounds checking unless paranoid
566  /// asserts are enabled.
567  const T & operator[](exint i) const
568  {
569  UT_ASSERT_P(i >= 0 && i < mySize);
570  return myData[i];
571  }
572 
573  /// forcedRef(exint) will grow the array if necessary, initializing any
574  /// new elements to zero for POD types and default constructing for
575  /// class types.
577  {
578  UT_ASSERT_P(i >= 0);
579  if (i >= mySize)
580  bumpSize(i+1);
581  return myData[i];
582  }
583 
584  /// forcedGet(exint) does NOT grow the array, and will return default
585  /// objects for out of bound array indices.
587  {
588  return (i >= 0 && i < mySize) ? myData[i] : T();
589  }
590 
591  T & last()
592  {
593  UT_ASSERT_P(mySize);
594  return myData[mySize-1];
595  }
596  const T & last() const
597  {
598  UT_ASSERT_P(mySize);
599  return myData[mySize-1];
600  }
601 
602  /// Apply a user-defined function to each element of the array
603  /// as int as the function returns zero. If applyFct returns
604  /// 1, apply() stops traversing the list and returns the current
605  /// index; otherwise, apply() returns the size.
606  exint apply(int (*applyFct)(T &t, void *d), void *d);
607 
608  template <typename BinaryOp>
609  T accumulate(const T &init_value, BinaryOp add) const;
610 
611  T * getArray() const { return myData; }
612  const T * getRawArray() const { return myData; }
613 
614  T * array() { return myData; }
615  const T * array() const { return myData; }
616 
617  T * data() { return myData; }
618  const T * data() const { return myData; }
619 
620  /// This method allows you to swap in a new raw T array, which must be
621  /// the same size as myCapacity. Use caution with this method.
622  T * aliasArray(T *newdata)
623  { T *data = myData; myData = newdata; return data; }
624 
625  template <typename IT, bool FORWARD>
626  class base_iterator :
627  public std::iterator<std::random_access_iterator_tag, T, exint>
628  {
629  public:
630  typedef IT& reference;
631  typedef IT* pointer;
632 
633  // Note: When we drop gcc 4.4 support and allow range-based for
634  // loops, we should also drop atEnd(), which means we can drop
635  // myEnd here.
636  base_iterator() : myCurrent(nullptr), myEnd(nullptr) {}
637 
638  // Allow iterator to const_iterator conversion
639  template<typename EIT>
641  : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
642 
644  { return FORWARD ? myCurrent : myCurrent - 1; }
645 
647  { return FORWARD ? *myCurrent : myCurrent[-1]; }
648 
649  reference item() const
650  { return FORWARD ? *myCurrent : myCurrent[-1]; }
651 
653  { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; }
654 
655  /// Pre-increment operator
657  {
658  if (FORWARD) ++myCurrent; else --myCurrent;
659  return *this;
660  }
661  /// Post-increment operator
663  {
664  base_iterator tmp = *this;
665  if (FORWARD) ++myCurrent; else --myCurrent;
666  return tmp;
667  }
668  /// Pre-decrement operator
670  {
671  if (FORWARD) --myCurrent; else ++myCurrent;
672  return *this;
673  }
674  /// Post-decrement operator
676  {
677  base_iterator tmp = *this;
678  if (FORWARD) --myCurrent; else ++myCurrent;
679  return tmp;
680  }
681 
683  {
684  if (FORWARD)
685  myCurrent += n;
686  else
687  myCurrent -= n;
688  return *this;
689  }
691  {
692  if (FORWARD)
693  return base_iterator(myCurrent + n, myEnd);
694  else
695  return base_iterator(myCurrent - n, myEnd);
696  }
697 
699  { return (*this) += (-n); }
701  { return (*this) + (-n); }
702 
703  bool atEnd() const { return myCurrent == myEnd; }
704  void advance() { this->operator++(); }
705 
706  // Comparators
707  template<typename ITR, bool FR>
709  { return myCurrent == r.myCurrent; }
710 
711  template<typename ITR, bool FR>
713  { return myCurrent != r.myCurrent; }
714 
715  template<typename ITR>
716  bool operator<(const base_iterator<ITR, FORWARD> &r) const
717  {
718  if (FORWARD)
719  return myCurrent < r.myCurrent;
720  else
721  return r.myCurrent < myCurrent;
722  }
723 
724  template<typename ITR>
726  {
727  if (FORWARD)
728  return myCurrent > r.myCurrent;
729  else
730  return r.myCurrent > myCurrent;
731  }
732 
733  template<typename ITR>
734  bool operator<=(const base_iterator<ITR, FORWARD> &r) const
735  {
736  if (FORWARD)
737  return myCurrent <= r.myCurrent;
738  else
739  return r.myCurrent <= myCurrent;
740  }
741 
742  template<typename ITR>
744  {
745  if (FORWARD)
746  return myCurrent >= r.myCurrent;
747  else
748  return r.myCurrent >= myCurrent;
749  }
750 
751  // Difference operator for std::distance
752  template<typename ITR>
754  {
755  if (FORWARD)
756  return exint(myCurrent - r.myCurrent);
757  else
758  return exint(r.myCurrent - myCurrent);
759  }
760 
761 
762  protected:
763  friend class UT_Array<T>;
764  base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
765  private:
766 
767  IT *myCurrent;
768  IT *myEnd;
769  };
770 
771  typedef base_iterator<T, true> iterator;
772  typedef base_iterator<const T, true> const_iterator;
773  typedef base_iterator<T, false> reverse_iterator;
774  typedef base_iterator<const T, false> const_reverse_iterator;
775  typedef const_iterator traverser; // For backward compatibility
776 
777  /// Begin iterating over the array. The contents of the array may be
778  /// modified during the traversal.
780  {
781  return iterator(myData, myData + mySize);
782  }
783  /// End iterator.
785  {
786  return iterator(myData + mySize,
787  myData + mySize);
788  }
789 
790  /// Begin iterating over the array. The array may not be modified during
791  /// the traversal.
793  {
794  return const_iterator(myData, myData + mySize);
795  }
796  /// End const iterator. Consider using it.atEnd() instead.
798  {
799  return const_iterator(myData + mySize,
800  myData + mySize);
801  }
802 
803  /// Begin iterating over the array in reverse.
805  {
806  return reverse_iterator(myData + mySize,
807  myData);
808  }
809  /// End reverse iterator.
811  {
812  return reverse_iterator(myData, myData);
813  }
814  /// Begin iterating over the array in reverse.
816  {
817  return const_reverse_iterator(myData + mySize,
818  myData);
819  }
820  /// End reverse iterator. Consider using it.atEnd() instead.
822  {
823  return const_reverse_iterator(myData, myData);
824  }
825 
827  { return UT_IteratorRange<iterator>(begin(), end()); }
829  { return UT_IteratorRange<const_iterator>(begin(), end()); }
830 
835 
836  /// Remove item specified by the reverse_iterator.
837  void removeItem(const reverse_iterator &it)
838  {
839  removeAt(&it.item() - myData);
840  }
841 
842 
843  /// Very dangerous methods to share arrays.
844  /// The array is not aware of the sharing, so ensure you clear
845  /// out the array prior a destructor or setCapacity operation.
847  {
848  myData = src.myData;
849  myCapacity = src.myCapacity;
850  mySize = src.mySize;
851  }
852  void unsafeShareData(T *src, exint srcsize)
853  {
854  myData = src;
855  myCapacity = srcsize;
856  mySize = srcsize;
857  }
859  {
860  myData = src;
861  mySize = size;
862  myCapacity = capacity;
863  }
865  {
866  myData = nullptr;
867  myCapacity = 0;
868  mySize = 0;
869  }
870 
871  /// Returns true if the data used by the array was allocated on the heap.
872  inline bool isHeapBuffer() const
873  {
874  return (myData != (T *)(((char*)this) + sizeof(*this)));
875  }
876  inline bool isHeapBuffer(T* data) const
877  {
878  return (data != (T *)(((char*)this) + sizeof(*this)));
879  }
880 
881 protected:
882  // Check whether T may have a constructor, destructor, or copy
883  // constructor. This test is conservative in that some POD types will
884  // not be recognized as POD by this function. To mark your type as POD,
885  // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
886  static constexpr SYS_FORCE_INLINE bool isPOD()
887  {
888  return SYSisPOD<T>();
889  }
890 
891  /// Implements both append(const T &) and append(T &&) via perfect
892  /// forwarding. Unlike the variadic emplace_back(), its argument may be a
893  /// reference to another element in the array.
894  template <typename S>
895  exint appendImpl(S &&s);
896 
897  /// Similar to appendImpl() but for insertion.
898  template <typename S>
899  exint insertImpl(S &&s, exint index);
900 
901  /// In debug builds, verifies that the arguments to emplace_back() will not
902  /// be invalidated when realloc() is called.
903  template <typename First, typename... Rest>
904  void validateEmplaceArgs(First &&first, Rest&&... rest) const
905  {
907  static_cast<const void *>(&first) <
908  static_cast<const void *>(myData) ||
909  static_cast<const void *>(&first) >=
910  static_cast<const void *>(myData + mySize),
911  "Argument cannot reference an existing element in the array.");
912 
913  validateEmplaceArgs(std::forward<Rest>(rest)...);
914  }
915 
916  /// Base case for validateEmplaceArgs().
917  void validateEmplaceArgs() const
918  {
919  }
920 
921  // Construct the given type
922  template <typename... S>
923  static void construct(T &dst, S&&... s)
924  {
925  new (&dst) T(std::forward<S>(s)...);
926  }
927 
928  // Copy construct the given type
929  static void copyConstruct(T &dst, const T &src)
930  {
931  if (isPOD())
932  dst = src;
933  else
934  new (&dst) T(src);
935  }
936  static void copyConstructRange(T *dst, const T *src, exint n)
937  {
938  if (isPOD())
939  {
940  if (n > 0)
941  {
942  ::memcpy((void *)dst, (const void *)src,
943  n * sizeof(T));
944  }
945  }
946  else
947  {
948  for (exint i = 0; i < n; i++)
949  new (&dst[i]) T(src[i]);
950  }
951  }
952 
953  /// Element Constructor
954  static void trivialConstruct(T &dst)
955  {
956  if (!isPOD())
957  new (&dst) T();
958  else
959  memset((void *)&dst, 0, sizeof(T));
960  }
962  {
963  if (!isPOD())
964  {
965  for (exint i = 0; i < n; i++)
966  new (&dst[i]) T();
967  }
968  else if (n == 1)
969  {
970  // Special case for n == 1. If the size parameter
971  // passed to memset is known at compile time, this
972  // function call will be inlined. This results in
973  // much faster performance than a real memset
974  // function call which is required in the case
975  // below, where n is not known until runtime.
976  // This makes calls to append() much faster.
977  memset((void *)dst, 0, sizeof(T));
978  }
979  else
980  memset((void *)dst, 0, sizeof(T) * n);
981  }
982 
983  /// Element Destructor
985  {
986  if (!isPOD())
987  dst.~T();
988  }
990  {
991  if (!isPOD())
992  {
993  for (exint i = 0; i < n; i++)
994  dst[i].~T();
995  }
996  }
997 
998 private:
999  /// Pointer to the array of elements of type T
1000  T *myData;
1001 
1002  /// The number of elements for which we have allocated memory
1003  exint myCapacity;
1004 
1005  /// The actual number of valid elements in the array
1006  exint mySize;
1007 
1008  // The guts of the remove() methods.
1009  exint removeAt(exint index);
1010 
1011  T * allocateCapacity(exint num_items);
1012 
1013  template<typename OS, typename S>
1014  friend OS &operator<<(OS &os, const UT_Array<S> &d);
1015 
1016  /// Friend specialization of std::swap() to use UT_String::swap()
1017  /// @internal This is needed because standard std::swap() implementations
1018  /// will try to copy the UT_String objects, causing hardened strings to
1019  /// become weak.
1020  friend void swap(UT_Array<T>& a, UT_Array<T>& b) { a.swap(b); }
1021 };
1022 
1023 // Assigns src to dest, using the default C++ conversion operator.
1024 template <typename T, typename S>
1025 void
1027 {
1028  exint n = src.size();
1029  dest.setCapacity(n);
1030  dest.setSize(n);
1031  for (exint i = 0; i < n; i++)
1032  dest(i) = T(src(i));
1033 }
1034 template <typename T, typename S>
1035 void
1037 {
1038  dest.setCapacity(n);
1039  dest.setSize(n);
1040  for (exint i = 0; i < n; i++)
1041  dest(i) = T(src[i]);
1042 }
1043 template <typename T, typename S>
1044 void
1046 {
1047  // We assume here that dest has enough memory for src.size()
1048  exint n = src.size();
1049  for (exint i = 0; i < n; i++)
1050  dest[i] = T(src(i));
1051 }
1052 template <typename T, typename S>
1053 void
1054 UTconvertArray(T *dest, const S *src, int64 n)
1055 {
1056  // We assume here that dest has enough memory for n elements
1057  for (int64 i = 0; i < n; i++)
1058  dest[i] = T(src[i]);
1059 }
1060 
1061 #include "UT_ArrayImpl.h"
1062 
1063 
1064 template<typename OS, typename S>
1065 inline OS &
1066 operator<<(OS &os, const UT_Array<S> &d)
1067 {
1068  os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
1069  return os;
1070 }
1071 
1072 // Overload for custom formatting of a UT_StringArray with UTformat.
1073 template <typename T> UT_API size_t
1074 format(char *buffer, size_t bufsize, const UT_Array<T> &v);
1075 
1076 /// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
1077 /// its elements
1078 template <template <typename> class ArrayT, typename T>
1079 static inline int64
1080 UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
1081 {
1082  int64 mem = inclusive ? sizeof(arr) : 0;
1083  mem += arr.getMemoryUsage(false);
1084  for (auto &&item : arr)
1085  mem += item.getMemoryUsage(false);
1086  return mem;
1087 }
1088 
1089 /// Utility to sort array using operator<
1090 template <typename T>
1091 static inline void
1092 UTsort(UT_Array<T> &arr)
1093 {
1094  arr.stdsort([](const T &a, const T &b) { return a < b; });
1095 }
1096 
1097 /// Utility to sort array using operator< and remove duplicates
1098 template <typename T>
1099 static inline void
1100 UTsortAndRemoveDuplicates(UT_Array<T> &arr)
1101 {
1102  arr.sortAndRemoveDuplicates([](const T &a, const T &b) { return a < b; });
1103 }
1104 
1105 // For UT::ArraySet.
1106 namespace UT
1107 {
1108 template <typename T>
1109 struct DefaultClearer;
1110 
1111 template <typename T>
1113 {
1114  static void clear(UT_Array<T> &v) { v.setCapacity(0); }
1115  static bool isClear(const UT_Array<T> &v) { return v.capacity() == 0; }
1116  static void clearConstruct(UT_Array<T> *p)
1117  {
1118  new ((void *)p) UT_Array<T>();
1119  }
1120  static const bool clearNeedsDestruction = false;
1121 };
1122 } // namespace UT
1123 
1124 #endif // __UT_ARRAY_H_INCLUDED__
reference operator*() const
Definition: UT_Array.h:646
base_iterator & operator++()
Pre-increment operator.
Definition: UT_Array.h:656
int isEqual(const UT_Array< T > &a, Comparator compare) const
Definition: UT_ArrayImpl.h:928
base_iterator & operator--()
Pre-decrement operator.
Definition: UT_Array.h:669
T & last()
Definition: UT_Array.h:591
exint insert(T &&t, exint i)
Definition: UT_Array.h:110
GLint first
Definition: glcorearb.h:404
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:693
const T & operator[](exint i) const
Definition: UT_Array.h:567
void validateEmplaceArgs(First &&first, Rest &&...rest) const
Definition: UT_Array.h:904
exint append(const T &t)
Definition: UT_Array.h:96
const T * data() const
Definition: UT_Array.h:618
const T * getRawArray() const
Definition: UT_Array.h:612
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:872
pointer operator->() const
Definition: UT_Array.h:643
base_iterator operator+(exint n) const
Definition: UT_Array.h:690
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1817
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:917
GLsizei GLenum const void * indices
Definition: glcorearb.h:405
void sortAndRemoveDuplicates(ComparatorBool is_less)
Definition: UT_Array.h:392
bool operator!=(const UT_Array< T > &a) const
Definition: UT_ArrayImpl.h:921
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:936
exint uniqueSortedFind(const T &item, Comparator compare) const
Definition: UT_ArrayImpl.h:338
SYS_FORCE_INLINE void removeLast()
Definition: UT_Array.h:223
void merge(const UT_Array< T > &other, int direction, bool allow_dups, ComparatorBool is_less)
Definition: UT_ArrayImpl.h:959
void unsafeShareData(T *src, exint size, exint capacity)
Definition: UT_Array.h:858
const GLdouble * v
Definition: glcorearb.h:836
UT_Array< T > & operator=(const UT_Array< T > &a)
Definition: UT_ArrayImpl.h:824
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:622
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:492
bool isValidIndex(exint index) const
Return true if given index is valid.
Definition: UT_Array.h:211
void zero()
Zeros the array if a POD type, else trivial constructs if a class type.
Definition: UT_ArrayImpl.h:683
base_iterator< const T, false > const_reverse_iterator
Definition: UT_Array.h:774
static void trivialConstruct(T &dst)
Element Constructor.
Definition: UT_Array.h:954
friend void swap(UT_Array< T > &a, UT_Array< T > &b)
Definition: UT_Array.h:1020
UT_API size_t format(char *buffer, size_t bufsize, const UT_Array< T > &v)
const_iterator begin() const
Definition: UT_Array.h:792
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
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
exint removeIndex(exint index)
Definition: UT_Array.h:219
T * array()
Definition: UT_Array.h:614
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:294
exint apply(int(*applyFct)(T &t, void *d), void *d)
Definition: UT_ArrayImpl.h:942
const_reverse_iterator rend() const
End reverse iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:821
#define UT_API
Definition: UT_API.h:13
bool isHeapBuffer(T *data) const
Definition: UT_Array.h:876
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:886
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
exint index(const T &t) const
Definition: UT_Array.h:280
bool operator>=(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:743
exint uniqueSortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:270
reference item() const
Definition: UT_Array.h:649
void bumpCapacity(exint mincapacity)
Definition: UT_Array.h:417
static bool isClear(const UT_Array< T > &v)
Definition: UT_Array.h:1115
GLuint buffer
Definition: glcorearb.h:659
void unsafeClearData()
Definition: UT_Array.h:864
png_uint_32 i
Definition: png.h:2877
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:708
static void trivialDestructRange(T *dst, exint n)
Definition: UT_Array.h:989
GLsizeiptr size
Definition: glcorearb.h:663
base_iterator operator-(exint n) const
Definition: UT_Array.h:700
void bumpSize(exint newsize)
Definition: UT_Array.h:434
bool operator>(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:725
base_iterator< T, false > reverse_iterator
Definition: UT_Array.h:773
void unsafeShareData(T *src, exint srcsize)
Definition: UT_Array.h:852
exint append(T &&t)
Definition: UT_Array.h:97
exint operator-(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:753
long long int64
Definition: SYS_Types.h:107
const_reverse_iterator rbegin() const
Begin iterating over the array in reverse.
Definition: UT_Array.h:815
exint safeIndex(const T &t) const
Definition: UT_Array.h:281
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:751
GLdouble n
Definition: glcorearb.h:2007
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:804
exint emplace_back(S &&...s)
Definition: UT_ArrayImpl.h:171
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:923
void entries(exint newsize)
Alias of setSize(). setSize() is preferred.
Definition: UT_Array.h:483
T & operator[](exint i)
Definition: UT_Array.h:559
const T & operator()(exint i) const
Definition: UT_Array.h:550
int64 exint
Definition: SYS_Types.h:116
reference operator[](exint n) const
Definition: UT_Array.h:652
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
exint insertAt(const T &t, exint index)
Definition: UT_Array.h:207
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:771
static void clearConstruct(UT_Array< T > *p)
Definition: UT_Array.h:1116
static SYS_FORCE_INLINE void trivialDestruct(T &dst)
Element Destructor.
Definition: UT_Array.h:984
exint sortedInsert(const T &t, Comparator compare)
Definition: UT_ArrayImpl.h:219
UT_IteratorRange< reverse_iterator > rrange()
Definition: UT_Array.h:831
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:640
void appendMultiple(const T &t, exint count)
Definition: UT_ArrayImpl.h:195
static void trivialConstructRange(T *dst, exint n)
Definition: UT_Array.h:961
iterator begin()
Definition: UT_Array.h:779
base_iterator(IT *c, IT *e)
Definition: UT_Array.h:764
T forcedGet(exint i) const
Definition: UT_Array.h:586
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1601
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:929
GLboolean * data
Definition: glcorearb.h:130
#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:797
base_iterator & operator-=(exint n)
Definition: UT_Array.h:698
exint sortedRemoveDuplicates()
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:846
void cycle(exint howMany)
Cyclically shifts the entire array by howMany.
Definition: UT_ArrayImpl.h:646
reverse_iterator rend()
End reverse iterator.
Definition: UT_Array.h:810
GLint GLsizei count
Definition: glcorearb.h:404
bool atEnd() const
Definition: UT_Array.h:703
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:712
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
base_iterator & operator+=(exint n)
Definition: UT_Array.h:682
void sortedSetDifference(const UT_Array< T > &other, Comparator compare)
GLenum GLenum dst
Definition: glcorearb.h:1792
void sortedUnion(const UT_Array< T > &other, Comparator compare)
T value_type
Definition: UT_Array.h:43
typedef int
Definition: png.h:1175
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:734
#define SYS_NOEXCEPT
Definition: SYS_Compiler.h:55
T * data()
Definition: UT_Array.h:617
GLuint index
Definition: glcorearb.h:785
base_iterator operator--(int)
Post-decrement operator.
Definition: UT_Array.h:675
const T & last() const
Definition: UT_Array.h:596
const T * array() const
Definition: UT_Array.h:615
static void clear(UT_Array< T > &v)
Definition: UT_Array.h:1114
int(* Comparator)(const T *, const T *)
Definition: UT_Array.h:45
void sort(Comparator compare)
Definition: UT_ArrayImpl.h:726
base_iterator< const T, true > const_iterator
Definition: UT_Array.h:772
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:507
void constant(const T &v)
Quickly set the array to a single value.
Definition: UT_ArrayImpl.h:668
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:837
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
void sortedIntersection(const UT_Array< T > &other, Comparator compare)
void UTconvertArray(UT_Array< T > &dest, const UT_Array< S > &src)
Definition: UT_Array.h:1026
Comparator class for stableSortIndices.
Definition: UT_Array.h:320
GLboolean r
Definition: glcorearb.h:1221
#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:576
void clear()
Resets list to an empty list.
Definition: UT_Array.h:513
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:826
UT_IteratorRange< const_iterator > range() const
Definition: UT_Array.h:828
const_iterator traverser
Definition: UT_Array.h:775
T & operator()(exint i)
Definition: UT_Array.h:542
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 reverse()
Reverses the array by swapping elements in mirrored locations.
Definition: UT_ArrayImpl.h:717
T * getArray() const
Definition: UT_Array.h:611
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:662
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:784
exint findAndRemove(const T &t)
Definition: UT_ArrayImpl.h:500
#define UT_ASSERT_MSG_P(ZZ, MM)
Definition: UT_Assert.h:128
UT_IteratorRange< const_reverse_iterator > rrange() const
Definition: UT_Array.h:833
GLenum src
Definition: glcorearb.h:1792
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:910