HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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_VectorTypes.h"
24 #include "UT_Permute.h"
25 
26 #include <SYS/SYS_Deprecated.h>
27 #include <SYS/SYS_TypeTraits.h>
28 #include <SYS/SYS_Types.h>
29 
30 #include <algorithm>
31 #include <functional>
32 #include <iosfwd>
33 #include <limits>
34 #include <vector>
35 #include <stdio.h>
36 #include <string.h>
37 
38 
39 template <typename T>
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
61  UT_Array(exint capacity, exint size)
62  {
63  myData = capacity ? allocateCapacity(capacity) : NULL;
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) : NULL;
75  }
76 
77  /// Construct with the contents of an initializer list
78  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);
107  exint insert(exint index);
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)
135  exint uniqueSortedInsert(const T &t, Comparator compare);
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  /// Convert from an std::vector.
184  void fromStdVector(const std::vector<T> &vec);
185  /// Convert to an std::vector.
186  void toStdVector(std::vector<T> &vec) const;
187 
188 
189  /// Assuming the array is already a heap, it inserts item t maintaining
190  /// the heap. It returns the index of the inserted item.
191  exint heapPush(const T &t, Comparator compare);
192 
193  /// Assuming the array is already a heap, extracts the top (maximum)
194  /// element from the heap and returns it.
195  T heapPop(Comparator compare);
196 
197  /// Assuming the array is already a heap, return the top (maximum)
198  /// element.
199  const T & heapMax() const
200  {
201  UT_ASSERT_P(mySize > 0);
202  return myData[0];
203  }
204 
205  /// Takes another T array and concatenate it onto my end
206  exint concat(const UT_Array<T> &a);
207 
208  /// Insert an element "count" times at the given index. Return the index.
209  exint multipleInsert(exint index, exint count);
210 
211  /// An alias for unique element insertion at a certain index. Also used by
212  /// the other insertion methods.
214  { return insertImpl(t, index); }
215 
216  /// Return true if given index is valid.
218  { return (index >= 0 && index < mySize); }
219 
220  /// Remove one element from the array given the element itself or its
221  /// position in the list, and fill the gap by shifting the elements down
222  /// by one position. Return the index of the element remove or -1 if
223  /// the value was not found.
224  exint findAndRemove(const T &t);
226  {
227  return isValidIndex(index) ? removeAt(index) : -1;
228  }
229  void removeLast()
230  {
231  if (mySize) removeAt(mySize-1);
232  }
233 
234  /// Remove the range [begin_i,end_i) of elements from the array.
235  void removeRange(exint begin_i, exint end_i);
236 
237  /// Remove the range [begin_i, end_i) of elements from this array and place
238  /// them in the dest array, shrinking/growing the dest array as necessary.
239  void extractRange(exint begin_i, exint end_i,
240  UT_Array<T>& dest);
241 
242  /// Removes all matching elements from the list, shuffling down and changing
243  /// the size appropriately.
244  /// Returns the number of elements left.
245  template <typename IsEqual>
246  exint removeIf(IsEqual is_equal);
247 
248  /// Remove all matching elements. Also sets the capacity of the array.
249  template <typename IsEqual>
250  void collapseIf(IsEqual is_equal)
251  {
252  removeIf(is_equal);
253  setCapacity(size());
254  }
255 
256  /// Move howMany objects starting at index srcIndex to destIndex;
257  /// This method will remove the elements at [srcIdx, srcIdx+howMany) and
258  /// then insert them at destIdx. This method can be used in place of
259  /// the old shift() operation.
260  void move(exint srcIdx, exint destIdx, exint howMany);
261 
262  /// Cyclically shifts the entire array by howMany
263  void cycle(exint howMany);
264 
265  /// Quickly set the array to a single value.
266  void constant(const T &v);
267  /// Zeros the array if a POD type, else trivial constructs if a class type.
268  void zero();
269 
270  /// Search for t in one of two ways: linearly using the '==' operator, or
271  /// binary using the function specified in the parameter list respectively.
272  /// find() returns the index of the matching element or (exint)-1.
273  /// Parameter s indicates the index the search should start at.
274  exint find(const T &t, exint s = 0) const;
275  exint find(const T &t, Comparator compare) const;
276 
277  /// Reverses the array by swapping elements in mirrored locations.
278  void reverse();
279 
280  /// The fastest search possible, which does pointer arithmetic to find the
281  /// index of the element. WARNING: index() does no out-of-bounds checking.
282  exint index(const T &t) const { return &t - myData; }
283  exint safeIndex(const T &t) const
284  {
285  return (&t >= myData && &t < (myData + mySize))
286  ? &t - myData : -1;
287  }
288 
289  /// Sort the array using a comparison function that you must provide. t1 and
290  /// t2 are pointers to Thing. The comparison function uses strcmp()
291  /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
292  void sort(Comparator compare);
293 
294  /// Sort using std::sort. The ComparatorBool uses the less-than semantics
295  template <typename ComparatorBool>
296  void stdsort(ComparatorBool is_less)
297  {
298  std::sort(myData, myData + mySize, is_less);
299  }
300 
301  /// stableSort is both stable, so keeps equal elements in the same
302  /// order (note this is very useful for compatibility between
303  /// compilers) and templated.
304  /// Either use a bool sort function or make a utility class with
305  /// bool operator()(const T a, const T b)
306  /// the utility class lets you bind data to avoid globals.
307  /// The comparator returns true if a must occur before b in the list.
308  /// For sorting ascending, this is a less than operation.
309  template<typename ComparatorBool>
310  void stableSort(ComparatorBool is_less)
311  {
312  // No-op for small/empty arrays, avoiding out of
313  // bounds assert on array()
314  if (size() < 2)
315  return;
316 
317  std::stable_sort(array(), array() + size(), is_less);
318  }
319 
320  /// Comparator class for stableSortIndices
321  template <typename I, typename V, typename ComparatorBool>
323  {
324  public:
326  const ComparatorBool &compare)
327  : myValues(values)
328  , myCompare(compare)
329  {}
330  inline bool operator()(I a, I b) const
331  { return myCompare(myValues(a), myValues(b)); }
332  private:
333  const UT_Array<V> &myValues;
334  const ComparatorBool &myCompare;
335  };
336 
337  /// Sort indices array by the values indexed into this array using a
338  /// stable sorting algorithm. To reorder the array in such a way
339  /// that it would be sorted, or another array to be reordered the
340  /// same way, include UT_Permute.h and use:
341  /// UTinversePermute(values.getArray(), indices.getArray(),
342  /// values.size());
343  /// The ComparatorBool uses the less-than semantics.
344  /// I must be an integer type.
345  template <typename I, typename ComparatorBool>
347  ComparatorBool is_less) const
348  {
349  IndexedCompare<I, T, ComparatorBool> compare(*this, is_less);
350  std::stable_sort(indices.getArray(),
351  indices.getArray() + indices.size(), compare);
352  }
353 
354  /// Create an index array from 0..n-1 into this array and sort
355  /// it with stableSortIndices.
356  /// The index array will be resized & rebuilt by this.
357  template <typename I, typename ComparatorBool>
359  ComparatorBool is_less) const
360  {
361  indices.setSizeNoInit(size());
362  for (exint i = 0; i < size(); i++)
363  indices(i) = i;
364  stableSortIndices(indices, is_less);
365  }
366 
367  /// Sorts this array by an external key array. We assume a 1:1
368  /// corespondence between our own elements and those of the key
369  /// array. The comparator should be defined on the key type.
370  template <typename K, typename ComparatorBool>
371  void stableSortByKey(const UT_Array<K> &keys, ComparatorBool is_less)
372  {
373  UT_ASSERT(keys.size() == size());
374  if (keys.size() != size())
375  return;
377  keys.stableArgSort(indices, is_less);
378  UTinversePermute(getArray(), indices.getArray(), size());
379  }
380 
381  /// Assuming this array is sorted, remove all duplicate elements.
382  /// Returns the number of elements removed.
383  exint sortedRemoveDuplicates();
384 
385  /// Assuming this array is sorted, remove all duplicate elements using the
386  /// given binary predicate.
387  /// Returns the number of elements removed
388  template <typename CompareEqual>
389  exint sortedRemoveDuplicatesIf(CompareEqual compare_equal);
390 
391  /// Partitions the array into values greater than or less than
392  /// the Nth element, returns the resulting partition number.
393  /// idx == 0 will get the minimum value, idx == size()-1 the
394  /// maximum value. This does modify this array!
395  template <typename ComparatorBool>
396  T selectNthLargest(exint idx, ComparatorBool is_less);
397 
398  /// Set the capacity of the array, i.e. grow it or shrink it. The
399  /// function copies the data after reallocating space for the array.
400  void setCapacity(exint newcapacity);
401  void setCapacityIfNeeded(exint mincapacity)
402  {
403  if (capacity() < mincapacity)
404  setCapacity(mincapacity);
405  }
406  /// If the capacity is smaller than mincapacity, expand the array
407  /// to at least mincapacity and to at least a constant factor of the
408  /// array's previous capacity, to avoid having a linear number of
409  /// reallocations in a linear number of calls to bumpCapacity.
410  void bumpCapacity(exint mincapacity)
411  {
412  if (capacity() >= mincapacity)
413  return;
414  // The following 4 lines are just
415  // SYSmax(mincapacity, UTbumpAlloc(capacity())), avoiding SYSmax
416  exint bumped = UTbumpAlloc(capacity());
417  exint newcapacity = mincapacity;
418  if (bumped > mincapacity)
419  newcapacity = bumped;
420  setCapacity(newcapacity);
421  }
422 
423  /// First bumpCapacity to ensure that there's space for newsize,
424  /// expanding either not at all or by at least a constant factor
425  /// of the array's previous capacity,
426  /// then set the size to newsize.
427  void bumpSize(exint newsize)
428  {
429  bumpCapacity(newsize);
430  setSize(newsize);
431  }
432  /// NOTE: bumpEntries() will be deprecated in favour of bumpSize() in a
433  /// future version.
434  void bumpEntries(exint newsize)
435  {
436  bumpSize(newsize);
437  }
438 
439  /// Query the capacity, i.e. the allocated length of the array.
440  /// NOTE: capacity() >= size().
441  exint capacity() const { return myCapacity; }
442  /// Query the size, i.e. the number of occupied elements in the array.
443  /// NOTE: capacity() >= size().
444  exint size() const { return mySize; }
445  /// Alias of size(). size() is preferred.
446  exint entries() const { return mySize; }
447  /// Returns true iff there are no occupied elements in the array.
448  bool isEmpty() const { return mySize==0; }
449 
450  /// Returns the amount of memory used by this UT_Array.
451  /// If inclusive is false, it only counts the memory of the array.
452  /// This is often necessary to avoid double-counting, e.g. if this
453  /// UT_Array is a member variable of a class whose memory is already
454  /// being counted by the caller.
455  int64 getMemoryUsage(bool inclusive=false) const
456  { return (inclusive ? sizeof(*this) : 0) + capacity()*sizeof(T); }
457 
458  /// Set the size, the number of occupied elements in the array.
459  /// NOTE: This will not do bumpCapacity, so if you call this
460  /// n times to increase the size, it may take
461  /// n^2 time.
462  void setSize(exint newsize)
463  {
464  if (newsize < 0)
465  newsize = 0;
466  if (newsize == mySize)
467  return;
468  setCapacityIfNeeded(newsize);
469  if (mySize > newsize)
470  trivialDestructRange(myData + newsize, mySize - newsize);
471  else // newsize > mySize
472  trivialConstructRange(myData + mySize, newsize - mySize);
473  mySize = newsize;
474  }
475  /// Alias of setSize(). setSize() is preferred.
476  void entries(exint newsize)
477  {
478  setSize(newsize);
479  }
480  /// Set the size, but unlike setSize(newsize), this function
481  /// will not initialize new POD elements to zero. Non-POD data types
482  /// will still have their constructors called.
483  /// This function is faster than setSize(ne) if you intend to fill in
484  /// data for all elements.
485  void setSizeNoInit(exint newsize)
486  {
487  if (newsize < 0)
488  newsize = 0;
489  if (newsize == mySize)
490  return;
491  setCapacityIfNeeded(newsize);
492  if (mySize > newsize)
493  trivialDestructRange(myData + newsize, mySize - newsize);
494  else if (!isPOD()) // newsize > mySize
495  trivialConstructRange(myData + mySize, newsize - mySize);
496  mySize = newsize;
497  }
498 
499  /// Decreases, but never expands, to the given maxsize.
500  void truncate(exint maxsize)
501  {
502  if (maxsize >= 0 && size() > maxsize)
503  setSize(maxsize);
504  }
505  /// Resets list to an empty list.
506  void clear() {
507  // Don't call setSize(0) since that would require a valid default
508  // constructor.
509  trivialDestructRange(myData, mySize);
510  mySize = 0;
511  }
512 
513  /// Assign array a to this array by copying each of a's elements with
514  /// memcpy for POD types, and with copy construction for class types.
515  UT_Array<T> & operator=(const UT_Array<T> &a);
516 
517  /// Replace the contents with those from the initializer_list ilist
518  UT_Array<T> & operator=(std::initializer_list<T> ilist);
519 
520  /// Move the contents of array a to this array.
521  UT_Array<T> & operator=(UT_Array<T> &&a);
522 
523  /// Compare two array and return true if they are equal and false otherwise.
524  /// Two elements are checked against each other using operator '==' or
525  /// compare() respectively.
526  /// NOTE: The capacities of the arrays are not checked when
527  /// determining whether they are equal.
528  bool operator==(const UT_Array<T> &a) const;
529  bool operator!=(const UT_Array<T> &a) const;
530  int isEqual(const UT_Array<T> &a, Comparator compare) const;
531 
532  /// Subscript operator
533  /// NOTE: This does NOT do any bounds checking unless paranoid
534  /// asserts are enabled.
536  {
537  UT_ASSERT_P(i >= 0 && i < mySize);
538  return myData[i];
539  }
540  /// Const subscript operator
541  /// NOTE: This does NOT do any bounds checking unless paranoid
542  /// asserts are enabled.
543  const T & operator()(exint i) const
544  {
545  UT_ASSERT_P(i >= 0 && i < mySize);
546  return myData[i];
547  }
548 
549  /// Subscript operator
550  /// NOTE: This does NOT do any bounds checking unless paranoid
551  /// asserts are enabled.
553  {
554  UT_ASSERT_P(i >= 0 && i < mySize);
555  return myData[i];
556  }
557  /// Const subscript operator
558  /// NOTE: This does NOT do any bounds checking unless paranoid
559  /// asserts are enabled.
560  const T & operator[](exint i) const
561  {
562  UT_ASSERT_P(i >= 0 && i < mySize);
563  return myData[i];
564  }
565 
566  /// forcedRef(exint) will grow the array if necessary, initializing any
567  /// new elements to zero for POD types and default constructing for
568  /// class types.
570  {
571  UT_ASSERT_P(i >= 0);
572  if (i >= mySize)
573  bumpSize(i+1);
574  return myData[i];
575  }
576 
577  /// forcedGet(exint) does NOT grow the array, and will return default
578  /// objects for out of bound array indices.
580  {
581  return (i >= 0 && i < mySize) ? myData[i] : T();
582  }
583 
584  T & last()
585  {
586  UT_ASSERT_P(mySize);
587  return myData[mySize-1];
588  }
589  const T & last() const
590  {
591  UT_ASSERT_P(mySize);
592  return myData[mySize-1];
593  }
594 
595  /// Apply a user-defined function to each element of the array
596  /// as int as the function returns zero. If applyFct returns
597  /// 1, apply() stops traversing the list and returns the current
598  /// index; otherwise, apply() returns the size.
599  exint apply(int (*applyFct)(T &t, void *d), void *d);
600 
601  template <typename BinaryOp>
602  T accumulate(const T &init_value, BinaryOp add) const;
603 
604  T * getArray() const { return myData; }
605  const T * getRawArray() const { return myData; }
606 
607  T * array() { return myData; }
608  const T * array() const { return myData; }
609 
610  T * data() { return myData; }
611  const T * data() const { return myData; }
612 
613  /// This method allows you to swap in a new raw T array, which must be
614  /// the same size as myCapacity. Use caution with this method.
615  T * aliasArray(T *newdata)
616  { T *data = myData; myData = newdata; return data; }
617 
618  template <typename IT, bool FORWARD>
619  class base_iterator :
620  public std::iterator<std::random_access_iterator_tag, T, exint>
621  {
622  public:
623  typedef IT& reference;
624  typedef IT* pointer;
625 
626  // Note: When we drop gcc 4.4 support and allow range-based for
627  // loops, we should also drop atEnd(), which means we can drop
628  // myEnd here.
629  base_iterator() : myCurrent(NULL), myEnd(NULL) {}
630 
631  // Allow iterator to const_iterator conversion
632  template<typename EIT>
634  : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
635 
637  { return FORWARD ? myCurrent : myCurrent - 1; }
638 
640  { return FORWARD ? *myCurrent : myCurrent[-1]; }
641 
642  reference item() const
643  { return FORWARD ? *myCurrent : myCurrent[-1]; }
644 
646  { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; }
647 
648  /// Pre-increment operator
650  {
651  if (FORWARD) ++myCurrent; else --myCurrent;
652  return *this;
653  }
654  /// Post-increment operator
656  {
657  base_iterator tmp = *this;
658  if (FORWARD) ++myCurrent; else --myCurrent;
659  return tmp;
660  }
661  /// Pre-decrement operator
663  {
664  if (FORWARD) --myCurrent; else ++myCurrent;
665  return *this;
666  }
667  /// Post-decrement operator
669  {
670  base_iterator tmp = *this;
671  if (FORWARD) --myCurrent; else ++myCurrent;
672  return tmp;
673  }
674 
676  {
677  if (FORWARD)
678  myCurrent += n;
679  else
680  myCurrent -= n;
681  return *this;
682  }
684  {
685  if (FORWARD)
686  return base_iterator(myCurrent + n, myEnd);
687  else
688  return base_iterator(myCurrent - n, myEnd);
689  }
690 
692  { return (*this) += (-n); }
694  { return (*this) + (-n); }
695 
696  bool atEnd() const { return myCurrent == myEnd; }
697  void advance() { this->operator++(); }
698 
699  // Comparators
700  template<typename ITR, bool FR>
702  { return myCurrent == r.myCurrent; }
703 
704  template<typename ITR, bool FR>
706  { return myCurrent != r.myCurrent; }
707 
708  template<typename ITR>
709  bool operator<(const base_iterator<ITR, FORWARD> &r) const
710  {
711  if (FORWARD)
712  return myCurrent < r.myCurrent;
713  else
714  return r.myCurrent < myCurrent;
715  }
716 
717  template<typename ITR>
719  {
720  if (FORWARD)
721  return myCurrent > r.myCurrent;
722  else
723  return r.myCurrent > myCurrent;
724  }
725 
726  template<typename ITR>
727  bool operator<=(const base_iterator<ITR, FORWARD> &r) const
728  {
729  if (FORWARD)
730  return myCurrent <= r.myCurrent;
731  else
732  return r.myCurrent <= myCurrent;
733  }
734 
735  template<typename ITR>
737  {
738  if (FORWARD)
739  return myCurrent >= r.myCurrent;
740  else
741  return r.myCurrent >= myCurrent;
742  }
743 
744  // Difference operator for std::distance
745  template<typename ITR>
747  {
748  if (FORWARD)
749  return exint(myCurrent - r.myCurrent);
750  else
751  return exint(r.myCurrent - myCurrent);
752  }
753 
754 
755  protected:
756  friend class UT_Array<T>;
757  base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
758  private:
759 
760  IT *myCurrent;
761  IT *myEnd;
762  };
763 
764  typedef base_iterator<T, true> iterator;
765  typedef base_iterator<const T, true> const_iterator;
766  typedef base_iterator<T, false> reverse_iterator;
767  typedef base_iterator<const T, false> const_reverse_iterator;
768  typedef const_iterator traverser; // For backward compatibility
769 
770  /// Begin iterating over the array. The contents of the array may be
771  /// modified during the traversal.
773  {
774  return iterator(myData, myData + mySize);
775  }
776  /// End iterator.
778  {
779  return iterator(myData + mySize,
780  myData + mySize);
781  }
782 
783  /// Begin iterating over the array. The array may not be modified during
784  /// the traversal.
786  {
787  return const_iterator(myData, myData + mySize);
788  }
789  /// End const iterator. Consider using it.atEnd() instead.
791  {
792  return const_iterator(myData + mySize,
793  myData + mySize);
794  }
795 
796  /// Begin iterating over the array in reverse.
798  {
799  return reverse_iterator(myData + mySize,
800  myData);
801  }
802  /// End reverse iterator.
804  {
805  return reverse_iterator(myData, myData);
806  }
807  /// Begin iterating over the array in reverse.
809  {
810  return const_reverse_iterator(myData + mySize,
811  myData);
812  }
813  /// End reverse iterator. Consider using it.atEnd() instead.
815  {
816  return const_reverse_iterator(myData, myData);
817  }
818 
820  { return UT_IteratorRange<iterator>(begin(), end()); }
822  { return UT_IteratorRange<const_iterator>(begin(), end()); }
823 
828 
829  /// Remove item specified by the reverse_iterator.
830  void removeItem(const reverse_iterator &it)
831  {
832  removeAt(&it.item() - myData);
833  }
834 
835 
836  /// Very dangerous methods to share arrays.
837  /// The array is not aware of the sharing, so ensure you clear
838  /// out the array prior a destructor or setCapacity operation.
840  {
841  myData = src.myData;
842  myCapacity = src.myCapacity;
843  mySize = src.mySize;
844  }
845  void unsafeShareData(T *src, exint srcsize)
846  {
847  myData = src;
848  myCapacity = srcsize;
849  mySize = srcsize;
850  }
852  {
853  myData = src;
854  mySize = size;
855  myCapacity = capacity;
856  }
858  {
859  myData = NULL;
860  myCapacity = 0;
861  mySize = 0;
862  }
863 
864  /// Returns true if the data used by the array was allocated on the heap.
865  inline bool isHeapBuffer() const
866  {
867  return (myData != (T *)(((char*)this) + sizeof(*this)));
868  }
869  inline bool isHeapBuffer(T* data) const
870  {
871  return (data != (T *)(((char*)this) + sizeof(*this)));
872  }
873 
874 protected:
875  // Check whether T may have a constructor, destructor, or copy
876  // constructor. This test is conservative in that some POD types will
877  // not be recognized as POD by this function. To mark your type as POD,
878  // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
879  static constexpr SYS_FORCE_INLINE bool isPOD()
880  {
881  return SYSisPOD<T>();
882  }
883 
884  /// Implements both append(const T &) and append(T &&) via perfect
885  /// forwarding. Unlike the variadic emplace_back(), its argument may be a
886  /// reference to another element in the array.
887  template <typename S>
888  exint appendImpl(S &&s);
889 
890  /// Similar to appendImpl() but for insertion.
891  template <typename S>
892  exint insertImpl(S &&s, exint index);
893 
894  /// In debug builds, verifies that the arguments to emplace_back() will not
895  /// be invalidated when realloc() is called.
896  template <typename First, typename... Rest>
897  void validateEmplaceArgs(First &&first, Rest&&... rest) const
898  {
900  static_cast<const void *>(&first) <
901  static_cast<const void *>(myData) ||
902  static_cast<const void *>(&first) >=
903  static_cast<const void *>(myData + mySize),
904  "Argument cannot reference an existing element in the array.");
905 
906  validateEmplaceArgs(std::forward<Rest>(rest)...);
907  }
908 
909  /// Base case for validateEmplaceArgs().
910  void validateEmplaceArgs() const
911  {
912  }
913 
914  // Construct the given type
915  template <typename... S>
916  static void construct(T &dst, S&&... s)
917  {
918  new (&dst) T(std::forward<S>(s)...);
919  }
920 
921  // Copy construct the given type
922  static void copyConstruct(T &dst, const T &src)
923  {
924  if (isPOD())
925  dst = src;
926  else
927  new (&dst) T(src);
928  }
929  static void copyConstructRange(T *dst, const T *src, exint n)
930  {
931  if (isPOD())
932  {
933  if (n > 0)
934  {
935  ::memcpy((void *)dst, (const void *)src,
936  n * sizeof(T));
937  }
938  }
939  else
940  {
941  for (exint i = 0; i < n; i++)
942  new (&dst[i]) T(src[i]);
943  }
944  }
945 
946  /// Element Constructor
947  static void trivialConstruct(T &dst)
948  {
949  if (!isPOD())
950  new (&dst) T();
951  else
952  memset((void *)&dst, 0, sizeof(T));
953  }
955  {
956  if (!isPOD())
957  {
958  for (exint i = 0; i < n; i++)
959  new (&dst[i]) T();
960  }
961  else if (n == 1)
962  {
963  // Special case for n == 1. If the size parameter
964  // passed to memset is known at compile time, this
965  // function call will be inlined. This results in
966  // much faster performance than a real memset
967  // function call which is required in the case
968  // below, where n is not known until runtime.
969  // This makes calls to append() much faster.
970  memset((void *)dst, 0, sizeof(T));
971  }
972  else
973  memset((void *)dst, 0, sizeof(T) * n);
974  }
975 
976  /// Element Destructor
977  static void trivialDestruct(T &dst)
978  {
979  if (!isPOD())
980  dst.~T();
981  }
983  {
984  if (!isPOD())
985  {
986  for (exint i = 0; i < n; i++)
987  dst[i].~T();
988  }
989  }
990 
991 private:
992  /// Pointer to the array of elements of type T
993  T *myData;
994 
995  /// The number of elements for which we have allocated memory
996  exint myCapacity;
997 
998  /// The actual number of valid elements in the array
999  exint mySize;
1000 
1001  // The guts of the remove() methods.
1002  exint removeAt(exint index);
1003 
1004  T * allocateCapacity(exint num_items);
1005 
1006  template<typename OS, typename S>
1007  friend OS &operator<<(OS &os, const UT_Array<S> &d);
1008 };
1009 
1010 // Assigns src to dest, using the default C++ conversion operator.
1011 template <typename T, typename S>
1012 void
1014 {
1015  exint n = src.size();
1016  dest.setCapacity(n);
1017  dest.setSize(n);
1018  for (exint i = 0; i < n; i++)
1019  dest(i) = T(src(i));
1020 }
1021 template <typename T, typename S>
1022 void
1024 {
1025  dest.setCapacity(n);
1026  dest.setSize(n);
1027  for (exint i = 0; i < n; i++)
1028  dest(i) = T(src[i]);
1029 }
1030 template <typename T, typename S>
1031 void
1033 {
1034  // We assume here that dest has enough memory for src.size()
1035  exint n = src.size();
1036  for (exint i = 0; i < n; i++)
1037  dest[i] = T(src(i));
1038 }
1039 template <typename T, typename S>
1040 void
1041 UTconvertArray(T *dest, const S *src, int64 n)
1042 {
1043  // We assume here that dest has enough memory for n elements
1044  for (int64 i = 0; i < n; i++)
1045  dest[i] = T(src[i]);
1046 }
1047 
1048 #include "UT_ArrayImpl.h"
1049 
1051 
1052 
1053 template<typename OS, typename S>
1054 inline OS &
1055 operator<<(OS &os, const UT_Array<S> &d)
1056 {
1057  os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
1058  return os;
1059 }
1060 
1061 // Overload for custom formatting of a UT_StringArray with UTformat.
1062 template <typename T> UT_API size_t
1063 format(char *buffer, size_t bufsize, const UT_Array<T> &v);
1064 
1065 /// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
1066 /// its elements
1067 template <template <typename> class ArrayT, typename T>
1068 static inline int64
1069 UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
1070 {
1071  int64 mem = inclusive ? sizeof(arr) : 0;
1072  mem += arr.getMemoryUsage(false);
1073  for (auto &&item : arr)
1074  mem += item.getMemoryUsage(false);
1075  return mem;
1076 }
1077 
1078 #endif // __UT_ARRAY_H_INCLUDED__
reference operator*() const
Definition: UT_Array.h:639
base_iterator & operator++()
Pre-increment operator.
Definition: UT_Array.h:649
base_iterator & operator--()
Pre-decrement operator.
Definition: UT_Array.h:662
T & last()
Definition: UT_Array.h:584
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:325
const T & operator[](exint i) const
Definition: UT_Array.h:560
void validateEmplaceArgs(First &&first, Rest &&...rest) const
Definition: UT_Array.h:897
exint append(const T &t)
Definition: UT_Array.h:96
const T * data() const
Definition: UT_Array.h:611
const T * getRawArray() const
Definition: UT_Array.h:605
bool isHeapBuffer() const
Returns true if the data used by the array was allocated on the heap.
Definition: UT_Array.h:865
pointer operator->() const
Definition: UT_Array.h:636
base_iterator operator+(exint n) const
Definition: UT_Array.h:683
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1817
void validateEmplaceArgs() const
Base case for validateEmplaceArgs().
Definition: UT_Array.h:910
GLsizei GLenum const void * indices
Definition: glcorearb.h:405
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:929
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1561
void unsafeShareData(T *src, exint size, exint capacity)
Definition: UT_Array.h:851
const GLdouble * v
Definition: glcorearb.h:836
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
void collapseIf(IsEqual is_equal)
Remove all matching elements. Also sets the capacity of the array.
Definition: UT_Array.h:250
T * aliasArray(T *newdata)
Definition: UT_Array.h:615
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:485
bool isValidIndex(exint index) const
Return true if given index is valid.
Definition: UT_Array.h:217
base_iterator< const T, false > const_reverse_iterator
Definition: UT_Array.h:767
static void trivialConstruct(T &dst)
Element Constructor.
Definition: UT_Array.h:947
UT_API size_t format(char *buffer, size_t bufsize, const UT_Array< T > &v)
const_iterator begin() const
Definition: UT_Array.h:785
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:455
void bumpEntries(exint newsize)
Definition: UT_Array.h:434
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
exint removeIndex(exint index)
Definition: UT_Array.h:225
T * array()
Definition: UT_Array.h:607
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:296
const_reverse_iterator rend() const
End reverse iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:814
#define UT_API
Definition: UT_API.h:12
bool isHeapBuffer(T *data) const
Definition: UT_Array.h:869
static constexpr SYS_FORCE_INLINE bool isPOD()
Definition: UT_Array.h:879
exint append(const T &t, bool check_dup)
Definition: UT_Array.h:98
exint index(const T &t) const
Definition: UT_Array.h:282
bool operator>=(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:736
reference item() const
Definition: UT_Array.h:642
void bumpCapacity(exint mincapacity)
Definition: UT_Array.h:410
GLuint buffer
Definition: glcorearb.h:659
void unsafeClearData()
Definition: UT_Array.h:857
png_uint_32 i
Definition: png.h:2877
exint size() const
Definition: UT_Array.h:444
void setSize(exint newsize)
Definition: UT_Array.h:462
bool operator==(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:701
static void trivialDestructRange(T *dst, exint n)
Definition: UT_Array.h:982
GLsizeiptr size
Definition: glcorearb.h:663
base_iterator operator-(exint n) const
Definition: UT_Array.h:693
void bumpSize(exint newsize)
Definition: UT_Array.h:427
bool operator>(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:718
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
base_iterator< T, false > reverse_iterator
Definition: UT_Array.h:766
void unsafeShareData(T *src, exint srcsize)
Definition: UT_Array.h:845
exint append(T &&t)
Definition: UT_Array.h:97
exint operator-(const base_iterator< ITR, FORWARD > &r) const
Definition: UT_Array.h:746
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
long long int64
Definition: SYS_Types.h:106
const_reverse_iterator rbegin() const
Begin iterating over the array in reverse.
Definition: UT_Array.h:808
exint safeIndex(const T &t) const
Definition: UT_Array.h:283
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:371
reverse_iterator rbegin()
Begin iterating over the array in reverse.
Definition: UT_Array.h:797
UT_SWAPPER_TEMPLATE(UT_Array)
static void construct(T &dst, S &&...s)
Definition: UT_Array.h:916
void entries(exint newsize)
Alias of setSize(). setSize() is preferred.
Definition: UT_Array.h:476
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
T & operator[](exint i)
Definition: UT_Array.h:552
const T & operator()(exint i) const
Definition: UT_Array.h:543
int64 exint
Definition: SYS_Types.h:115
static void trivialDestruct(T &dst)
Element Destructor.
Definition: UT_Array.h:977
reference operator[](exint n) const
Definition: UT_Array.h:645
exint insertAt(const T &t, exint index)
Definition: UT_Array.h:213
GLuint GLuint end
Definition: glcorearb.h:474
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
exint capacity() const
Definition: UT_Array.h:441
base_iterator< T, true > iterator
Definition: UT_Array.h:764
UT_IteratorRange< reverse_iterator > rrange()
Definition: UT_Array.h:824
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:633
static void trivialConstructRange(T *dst, exint n)
Definition: UT_Array.h:954
iterator begin()
Definition: UT_Array.h:772
base_iterator(IT *c, IT *e)
Definition: UT_Array.h:757
T forcedGet(exint i) const
Definition: UT_Array.h:579
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1601
static void copyConstruct(T &dst, const T &src)
Definition: UT_Array.h:922
GLboolean * data
Definition: glcorearb.h:130
#define SYS_DEPRECATED_HDK(__V__)
const_iterator end() const
End const iterator. Consider using it.atEnd() instead.
Definition: UT_Array.h:790
base_iterator & operator-=(exint n)
Definition: UT_Array.h:691
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:839
reverse_iterator rend()
End reverse iterator.
Definition: UT_Array.h:803
GLint GLsizei count
Definition: glcorearb.h:404
bool atEnd() const
Definition: UT_Array.h:696
bool operator()(I a, I b) const
Definition: UT_Array.h:330
bool operator!=(const base_iterator< ITR, FR > &r) const
Definition: UT_Array.h:705
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:446
base_iterator & operator+=(exint n)
Definition: UT_Array.h:675
GLenum GLenum dst
Definition: glcorearb.h:1792
void accumulate(const IterT &iter, XformOp &op, bool threaded=true)
T value_type
Definition: UT_Array.h:43
#define UT_ASSERT_MSG_P(ZZ, MM)
Definition: UT_Assert.h:104
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
#define SYS_NOEXCEPT
Definition: SYS_Compiler.h:49
T * data()
Definition: UT_Array.h:610
GLuint index
Definition: glcorearb.h:785
base_iterator operator--(int)
Post-decrement operator.
Definition: UT_Array.h:668
#define UT_API_TMPL
Definition: UT_API.h:13
const T & last() const
Definition: UT_Array.h:589
const T * array() const
Definition: UT_Array.h:608
base_iterator< const T, true > const_iterator
Definition: UT_Array.h:765
void stableArgSort(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:358
exint append(void)
Definition: UT_Array.h:95
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:500
void removeLast()
Definition: UT_Array.h:229
void setCapacityIfNeeded(exint mincapacity)
Definition: UT_Array.h:401
void removeItem(const reverse_iterator &it)
Remove item specified by the reverse_iterator.
Definition: UT_Array.h:830
void UTconvertArray(UT_Array< T > &dest, const UT_Array< S > &src)
Definition: UT_Array.h:1013
Comparator class for stableSortIndices.
Definition: UT_Array.h:322
GLboolean r
Definition: glcorearb.h:1221
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
#define const
Definition: zconf.h:214
void stableSort(ComparatorBool is_less)
Definition: UT_Array.h:310
T & forcedRef(exint i)
Definition: UT_Array.h:569
void clear()
Resets list to an empty list.
Definition: UT_Array.h:506
void stableSortIndices(UT_Array< I > &indices, ComparatorBool is_less) const
Definition: UT_Array.h:346
UT_IteratorRange< iterator > range()
Definition: UT_Array.h:819
UT_IteratorRange< const_iterator > range() const
Definition: UT_Array.h:821
const_iterator traverser
Definition: UT_Array.h:768
T & operator()(exint i)
Definition: UT_Array.h:535
GA_API const UT_StringHolder rest
T * getArray() const
Definition: UT_Array.h:604
base_iterator operator++(int)
Post-increment operator.
Definition: UT_Array.h:655
iterator end()
End iterator.
Definition: UT_Array.h:777
UT_IteratorRange< const_reverse_iterator > rrange() const
Definition: UT_Array.h:826
GLenum src
Definition: glcorearb.h:1792
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:448