UT_Array.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT_Array.h (UT Library, C++)
 *
 * COMMENTS:    This is the array class implementation used by
 *              almost everything in the codebase.
 *              Please be careful if you need to change it!
 *
 * RELATION TO THE STL:
 *
 *              Use UT_Array instead of std::vector
 *
 *              EXCEPTION: T is not known to be bitwise copyable (trivially
 *                         relocatable)
 *
 *                Examples of types T that cannot be copied bitwise:
 *                - A smart pointer class that uses reference linking (instead
 *                  of reference counting)
 *                - A container with a fixed buffer optimization like
 *                  UT_WorkBuffer or UT_SmallArray.
 *
 *                Specific example: Don't use T = std::function< U >.
 *
 *                For a more comprehensive table of which STL types are not
 *                trivially relocatable, see
 *                    https://quuxplusone.github.io/blog/2019/02/20/p1144-what-types-are-relocatable/
 *
 *              Reasoning to not use std::vector:
 *
 *              - Performance: std::vector’s growth factor tends to be doubling,
 *                which pessimizes memory use.
 *                std::vector cannot detect trivially relocatable types,
 *                so it can’t use realloc nor memcpy to move data as quickly
 *                as UT_Array can.
 *
 *              - Aesthetics: std::vector<float> tries to pretend to be float*,
 *                with [] indexing.
 *                This is dangerous as distinguishing value from pointer is
 *                rather important.  Using () indexing makes this clear (and
 *                allows higher dimensional indexing).
 *
 */

#pragma once

#ifndef __UT_ARRAY_H_INCLUDED__
#define __UT_ARRAY_H_INCLUDED__

#include "UT_API.h"
#include "UT_ArrayHelp.h"
#include "UT_Assert.h"
#include "UT_ContainerPrinter.h"
#include "UT_IteratorRange.h"
#include "UT_Permute.h"
#include "UT_LabeledCapacity.h"

#include <SYS/SYS_Compiler.h>
#include <SYS/SYS_Deprecated.h>
#include <SYS/SYS_Inline.h>
#include <SYS/SYS_Types.h>
#include <SYS/SYS_TypeTraits.h>
#include <SYS/SYS_TypeDecorate.h>

#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <type_traits>
#include <utility>

#include <string.h>

// Enable this to encode labeled capacity using a wrapper class rather than
// directly as an integer type. This allows the compiler to catch cases
// where the numeric value of the encoding which includes the label bit
// is accidentally used directly as a capacity value.
#undef UT_ARRAY_STRICT_LABELED_CAPACITY

// Constructor tags for UT_Array
struct UT_ArrayCT
{
    static constexpr struct ExternalCapacity{} EXTERNAL_CAPACITY{};
    static constexpr struct ExternalMove{} EXTERNAL_MOVE{};
    static constexpr struct GeneralizedMove{} GENERALIZED_MOVE{};
};

template <typename T>
class UT_Array
{
public:
    typedef T value_type;

    typedef int (*Comparator)(const T *, const T *);

    /// Copy constructor. It duplicates the data.
    /// It's marked explicit so that it's not accidentally passed by value.
    /// You can always pass by reference and then copy it, if needed.
    /// If you have a line like:
    /// UT_Array<int> a = otherarray;
    /// and it really does need to copy instead of referencing,
    /// you can rewrite it as:
    /// UT_Array<int> a(otherarray);
    explicit UT_Array(const UT_Array<T> &a);
    
    /// Move constructor. Steals the working data from the original.
    UT_Array(UT_Array<T> &&a) noexcept;
    
    /// Construct based on given capacity and size
    UT_Array(const exint capacity, const exint size);

    /// Construct based on given capacity with a size of 0
    explicit UT_Array(const exint capacity = 0);

    /// Construct with the contents of an initializer list
    /// If you are wondering why we mark this as explicit...
    /// Imagine you have the following:
    /// void foo(int i); // 1
    /// void foo(UT_Array<int>); // 2
    /// Without explicit you can do this
    /// foo({1})
    /// and function 1 will be called when you probably meant
    /// for function 2 to be called.
    explicit UT_Array(std::initializer_list<T> init);

    ~UT_Array();

    void            swap(UT_Array<T> &other);

    /// Append an element to the current elements and return its index in the
    /// array, or insert the element at a specified position; if necessary,
    /// insert() grows the array to accommodate the element. The insert
    /// methods use the assignment operator '=' to place the element into the
    /// right spot; be aware that '=' works differently on objects and pointers.
    /// The test for duplicates uses the logical equal operator '=='; as with
    /// '=', the behaviour of the equality operator on pointers versus objects
    /// is not the same.
    /// Use the subscript operators instead of insert() if you are appending
    /// to the array, or if  you don't mind overwriting the element already 
    /// inserted at the given index.
    exint           append() { return insert(mySize); }
    exint           append(const T &t) { return appendImpl(t); }
    exint           append(T &&t) { return appendImpl(std::move(t)); }
    exint           append(const T &t, bool check_dup)
                    {
                        exint   idx;
                        if (check_dup && ((idx = find(t)) != -1))
                            return idx;
                        return append(t);
                    }
    void            append(const T *pt, exint count);
    void            appendMultiple(const T &t, exint count);
    exint           insert(exint index);
    exint           insert(const T &t, exint i)
                        { return insertImpl(t, i); }
    exint           insert(T &&t, exint i)
                        { return insertImpl(std::move(t), i); }

    /// Adds a new element to the array (resizing if necessary) and forwards
    /// the given arguments to T's constructor.
    /// NOTE: Unlike append(), the arguments cannot reference any existing
    /// elements in the array. Checking for and handling such cases would
    /// remove most of the performance gain versus append(T(...)). Debug builds
    /// will assert that the arguments are valid.
    template <typename... S>
    exint           emplace_back(S&&... s);
    
protected:

    // The constructors below create a UT_Array with an external data buffer
    // that's not allocated by UT_Array itself.
    // This is used by UT_SmallArray to create UT_Array superclass objects
    // that have a nonheap data buffer, created on the stack.

    explicit UT_Array(
        const UT_ArrayCT::ExternalCapacity,
        T *external_data,
        const exint external_capacity
    );

    explicit UT_Array(
        const UT_ArrayCT::ExternalMove,
        T *external_data,
        const exint external_capacity,
        UT_Array&& a
    );

private:

    // Move construct a UT_Array that uses (data, capacity) as its buffer.
    // This constructor works both for an externally provided
    // buffer (e.g., the UT_SmallArray case) and
    // for a heap buffer that's allocated and owned by UT_Array itself.
    explicit UT_Array(
        const UT_ArrayCT::GeneralizedMove,
        T *data,
        const exint capacity,
        UT_Array&& a
    );

    // Equivalent to std::less without bringing in <functional>
    template <typename Y>
    struct Less
    {
        constexpr bool operator()(const Y &left, const Y &right) const noexcept
        {
            return left < right;
        }
    };

    // SFINAE constraint for bool comparators to avoid ambiguity
    template <typename F>
    using IsBoolComp = decltype(std::declval<F>()(std::declval<T>(),
                                                  std::declval<T>()),
                                void());

public:
    /// Assuming the array is sorted, it inserts item t maintaining the sorted
    /// state of the array. It returns the index of the inserted item.
    /// @note This is O(N^2) behaviour if you call it in a loop! Do not use.
    /// @{
    SYS_DEPRECATED_HDK(13.0)
    exint           sortedInsert(const T &t, Comparator compare);

    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    SYS_DEPRECATED_HDK(13.0)
    exint           sortedInsert(const T &t, ComparatorBool is_less = {});
    /// @}

    SYS_DEPRECATED_HDK(13.0)
    exint           uniqueSortedInsert(const T &t, Comparator compare)
                    { return uniqueSortedInsertImpl(t, compare); }

    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    SYS_DEPRECATED_HDK(13.0)
    exint           uniqueSortedInsert(const T &t, ComparatorBool is_less = {});

    SYS_DEPRECATED_HDK(13.0)
    exint           uniqueSortedInsert(T &&t, Comparator compare)
                    { return uniqueSortedInsertImpl(std::move(t), compare); }

    /// Convenience method to perform binary search of a ascending sorted array
    /// with no duplicates.  Returns the index of the specified item, -1 if not
    /// found.
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    exint           uniqueSortedFind(const T &item,
                                     ComparatorBool is_less = {}) const;

    SYS_DEPRECATED_HDK_REPLACE(19.5, "Use ComparatorBool variant")
    exint           uniqueSortedFind(const T &item, Comparator compare) const;

    /// Merge the given array into us.
    /// If direction is -1, then it assumes us and 'other' are both already
    /// sorted in descending order. Similarly, +1 means ascending.
    /// If allow_dups is false, then it further assumes that both arrays have no
    /// duplicates and will produce a result that also has no duplicates.
    /// More work will be needed if you want allow_dups to mean remove duplicates
    template <typename ComparatorBool = Less<T>>
    void            merge(const UT_Array<T> &other, int direction,
                          bool allow_dups, ComparatorBool is_less = {});
    template <typename ComparatorBool = Less<T>>
    void            merge(UT_Array<T> &&other, int direction,
                          bool allow_dups, ComparatorBool is_less = {})
                          noexcept;

    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    bool            hasSortedSubset(const UT_Array<T> &other,
                                    ComparatorBool is_less = {}) const;

    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedUnion(
                        const UT_Array<T> &other,
                        ComparatorBool is_less = {});
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedUnion(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        ComparatorBool is_less = {}) const;
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        ComparatorBool is_less = {});
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        ComparatorBool is_less = {}) const;
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        ComparatorBool is_less = {});
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        ComparatorBool is_less = {}) const;

    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    bool            hasSortedSubset(const UT_Array<T> &other,
                                    Comparator compare) const;
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedUnion(
                        const UT_Array<T> &other,
                        Comparator compare);
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedUnion(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        Comparator compare);
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        Comparator compare);
    SYS_DEPRECATED_REPLACE(19.5, "Use ComparatorBool variant")
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;

    /// Assuming the array is already a heap, it inserts item t maintaining
    /// the heap. It returns the index of the inserted item.
    exint           heapPush(const T &t, Comparator compare);

    /// Assuming the array is already a heap, extracts the top (maximum)
    /// element from the heap and returns it.
    T               heapPop(Comparator compare);

    /// Assuming the array is already a heap, return the top (maximum)
    /// element.
    const T &       heapMax() const
    {
        UT_ASSERT_P(mySize > 0);
        return myData[0];
    }

    /// Takes another T array and concatenate it onto my end
    exint           concat(const UT_Array<T> &a);
    /// Takes another T array and concatenate it onto my end
    exint           concat(UT_Array<T> &&a) noexcept;

    /// Insert an element "count" times at the given index. Return the index.
    exint           multipleInsert(exint index, exint count);

    /// An alias for unique element insertion at a certain index. Also used by
    /// the other insertion methods.
    exint           insertAt(const T &t, exint index)
                        { return insertImpl(t, index); }

    /// Return true if given index is valid.
    bool            isValidIndex(exint index) const
                        { return (index >= 0 && index < mySize); }

    /// Remove one element from the array given the element itself or its
    /// position in the list, and fill the gap by shifting the elements down
    /// by one position.  Return the index of the element remove or -1 if
    /// the value was not found.
    template <typename S>
    exint           findAndRemove(const S &s);
    exint           removeIndex(exint index)
    {
        return isValidIndex(index) ? removeAt(index) : -1;
    }
    SYS_FORCE_INLINE void removeLast()
    {
        if (mySize)
        {
            exint idx = --mySize;
            destroyElement(myData[idx]);
        }
    }

    /// Remove the range [begin_i,end_i) of elements from the array.
    /// begin_i is the start index.
    /// end_i is the index to stop at, and isn't inclusive.
    void            removeRange(exint begin_i, exint end_i);

    /// Remove the range [begin_i, end_i) of elements from this array and place
    /// them in the dest array, shrinking/growing the dest array as necessary.
    /// begin_i is the start index, 
    /// end_i is index to stop at, and isn't inclusive.
    void            extractRange(exint begin_i, exint end_i,
                                 UT_Array<T>& dest);

    /// Removes all matching elements from the list, shuffling down and changing
    /// the size appropriately.
    /// Returns the number of elements left.
    template <typename IsEqual>
    exint           removeIf(IsEqual is_equal);

    /// Remove all matching elements. Also sets the capacity of the array.
    template <typename IsEqual>
    void            collapseIf(IsEqual is_equal)
    {
        removeIf(is_equal);
        setCapacity(size());
    }

    /// Move how_many objects starting at index src_idx to dst_idx;
    /// This method will remove the elements at [src_idx, src_idx+how_many) and
    /// then insert them at dst_idx.  This method can be used in place of
    /// the old shift() operation.
    void            move(exint src_idx, exint dst_idx, exint how_many);

    /// Cyclically shifts the entire array by how_many
    void            cycle(exint how_many);

    /// Quickly set the array to a single value.
    void            constant(const T &v);
    /// Zeros the array if a POD type, else trivial constructs if a class type.
    void            zero();

    /// Search for s linearly using the '==' operator, starting at index start.
    /// @returns the index of the matching element or (exint)-1.
    template <typename S>
    exint           find(const S &s, exint start = 0) const;

    /// Search for s linearly using functor, starting at index start.
    /// @returns the index of the matching element or (exint)-1.
    template <typename IsEqual>
    exint           findIf(IsEqual is_equal, exint start = 0) const;

    /// Search for t via binary search using the function specified in the
    /// parameter list, assuming the array is already sorted with respect to
    /// compare.
    /// @returns the index of the matching element or (exint)-1.
    exint           sortedFind(const T &t, Comparator compare) const;

    /// Reverses the array by swapping elements in mirrored locations.
    void            reverse();

    /// The fastest search possible, which does pointer arithmetic to find the
    /// index of the element. WARNING: index() does no out-of-bounds checking.
    /// @{
    exint           index(const T &t) const
                    { return SYSaddressof(t) - myData; }
    exint           safeIndex(const T &t) const
                    {
                        return (SYSaddressof(t) >= myData &&
                                SYSaddressof(t) < (myData + mySize))
                            ? SYSaddressof(t) - myData : -1;
                    }
    /// @}

    /// Sort using std::sort with bool comparator. Defaults to operator<().
    template <typename ComparatorBool = Less<T>,
              typename = IsBoolComp<ComparatorBool>>
    void            sort(ComparatorBool is_less = {})
    {
        std::sort(myData, myData + mySize, is_less);
    }

    /// Sort the array using a comparison function that you must provide. t1 and
    /// t2 are pointers to Thing.  The comparison function uses strcmp()
    /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
    SYS_DEPRECATED_HDK_REPLACE(19.5, "Use ComparatorBool variant")
    void            sort(Comparator compare);

    /// Sort using std::sort.  The ComparatorBool uses the less-than semantics
    template <typename ComparatorBool,
              typename = IsBoolComp<ComparatorBool>>
    SYS_DEPRECATED_REPLACE(19.5, "Use sort(ComparatorBool) overload")
    void            stdsort(ComparatorBool is_less)
    {
        std::sort(myData, myData + mySize, is_less);
    }

    /// stableSort is both stable, so keeps equal elements in the same
    /// order (note this is very useful for compatibility between 
    /// compilers) and templated.
    /// Either use a bool sort function or make a utility class with
    /// bool operator()(const T a, const T b)
    /// the utility class lets you bind data to avoid globals.
    /// The comparator returns true if a must occur before b in the list.
    /// For sorting ascending, this is a less than operation.
    template<typename ComparatorBool = Less<T>>
    void            stableSort(ComparatorBool is_less = {})
    {
        // No-op for small/empty arrays, avoiding out of
        // bounds assert on array()
        if (size() < 2)
            return;

        std::stable_sort(array(), array() + size(), is_less);
    }

    /// Like stableSort, but operates on a subset of the array.
    template<typename ComparatorBool = Less<T>>
    void            stableSortRange(exint start, exint end,
                                    ComparatorBool is_less = {})
    {
        // No-op for small/empty arrays or ranges, avoiding out of
        // bounds assert on array()
        if (end < 0)
            end = size();
        if (start < 0)
            start = 0;
        if (end < start + 2)
            return;

        std::stable_sort(array() + start, array() + end, is_less);
    }

    template<typename ComparatorBool>
    SYS_DEPRECATED_REPLACE(21.5, "Use stableSortRange(start, end, comparator)")
    void            stableSortRange(ComparatorBool is_less,
                                    exint start, exint end)
    {
        stableSortRange(start, end, is_less);
    }

    /// Comparator class for stableSortIndices
    template <typename I, typename V, typename ComparatorBool>
    class IndexedCompare
    {
    public:
        inline IndexedCompare(const UT_Array<V> &values,
                              const ComparatorBool &compare)
            : myValues(values)
            , myCompare(compare)
        {}
        inline bool operator()(I a, I b) const
        { return myCompare(myValues(a), myValues(b)); }
    private:
        const UT_Array<V> &myValues;
        const ComparatorBool &myCompare;
    };

    /// Sort indices array by the values indexed into this array using a
    /// stable sorting algorithm. To reorder the array in such a way
    /// that it would be sorted, or another array to be reordered the
    /// same way, include UT_Permute.h and use:
    /// UTinversePermute(values.getArray(), indices.getArray(),
    ///                  values.size());
    /// The ComparatorBool uses the less-than semantics.
    /// I must be an integer type.
    template <typename I, typename ComparatorBool = Less<T>>
    void            stableSortIndices(UT_Array<I> &indices,
                                      ComparatorBool is_less = {}) const
    {
        IndexedCompare<I, T, ComparatorBool> compare(*this, is_less);
        std::stable_sort(indices.getArray(),
                         indices.getArray() + indices.size(), compare);
    }

    /// Create an index array from 0..n-1 into this array and sort
    /// it with stableSortIndices.
    /// The index array will be resized & rebuilt by this.
    template <typename I, typename ComparatorBool = Less<T>>
    void            stableArgSort(UT_Array<I> &indices,
                                  ComparatorBool is_less = {}) const
    {
        indices.setSizeNoInit(size());
        for (exint i = 0; i < size(); i++)
            indices(i) = i;
        stableSortIndices(indices, is_less);
    }

    /// Sorts this array by an external key array. We assume a 1:1
    /// correspondence between our own elements and those of the key
    /// array. The comparator should be defined on the key type.
    template <typename K, typename ComparatorBool = Less<K>>
    void          stableSortByKey(const UT_Array<K> &keys,
                                  ComparatorBool is_less = {})
    {
        UT_ASSERT(keys.size() == size());
        if (keys.size() != size())
            return;
        UT_Array<exint> indices;
        keys.stableArgSort(indices, is_less);
        UTinversePermute(getArray(), indices.getArray(), size());
    }

    /// Assuming this array is sorted, remove all duplicate elements.
    /// Returns the number of elements removed.
    exint           sortedRemoveDuplicates();

    /// Assuming this array is sorted, remove all duplicate elements using the
    /// given binary predicate.
    /// Returns the number of elements removed
    template <typename CompareEqual>
    exint           sortedRemoveDuplicatesIf(CompareEqual compare_equal);

    /// Sort and then remove duplicates.
    /// By default, operator<() is used but if you supply a custom comparator,
    /// ensure that equal elements are adjacent after sorting.
    /// Returns the number of elements removed.
    template<typename ComparatorBool = Less<T>>
    exint           sortAndRemoveDuplicates(ComparatorBool is_less = {})
    {
        stableSort(is_less);
        return sortedRemoveDuplicates();
    }

    /// Partitions the array into values greater than or less than
    /// the Nth element, returns the resulting partition number.
    /// idx == 0 will get the minimum value, idx == size()-1 the
    /// maximum value.  This does modify this array!
    template <typename ComparatorBool = Less<T>>
    T               selectNthLargest(exint idx, ComparatorBool is_less = {});

    /// Set the capacity of the array, i.e. grow it or shrink it. The
    /// function copies the data after reallocating space for the array.
    void            setCapacity(exint new_capacity);
    void            setCapacityIfNeeded(exint min_capacity)
    {
        if (capacity() < min_capacity)
            setCapacity(min_capacity);
    }
    /// If the capacity is smaller than min_capacity, expand the array
    /// to at least min_capacity and to at least a constant factor of the
    /// array's previous capacity, to avoid having a linear number of
    /// reallocations in a linear number of calls to bumpCapacity.
    void            bumpCapacity(exint min_capacity)
    {
        if (capacity() >= min_capacity)
            return;
        // The following 4 lines are just
        // SYSmax(min_capacity, UTbumpAlloc(capacity())), avoiding SYSmax
        exint bumped = UTbumpAlloc(capacity());
        exint new_capacity = min_capacity;
        if (bumped > min_capacity)
            new_capacity = bumped;
        setCapacity(new_capacity);
    }

    /// First bumpCapacity to ensure that there's space for newsize,
    /// expanding either not at all or by at least a constant factor
    /// of the array's previous capacity,
    /// then set the size to newsize.
    void            bumpSize(exint newsize)
    {
        bumpCapacity(newsize);
        setSize(newsize);
    }
    /// NOTE: bumpEntries() will be deprecated in favour of bumpSize() in a
    ///       future version.
    void            bumpEntries(exint newsize)
    {
        bumpSize(newsize);
    }

    /// Query the capacity, i.e. the allocated length of the array.
    /// NOTE: capacity() >= size().
    exint           capacity() const;
    /// Query the size, i.e. the number of occupied elements in the array.
    /// NOTE: capacity() >= size().
    exint           size() const     { return mySize; }
    /// Alias of size().  size() is preferred.
    exint           entries() const  { return mySize; }
    /// Returns true iff there are no occupied elements in the array.
    bool            isEmpty() const  { return mySize==0; }

    /// Returns size in bytes.
    exint           sizeInBytes() const { return mySize * sizeof(T); }

    /// Returns the amount of memory used by this UT_Array.
    /// If inclusive is false, it only counts the memory of the array.
    /// This is often necessary to avoid double-counting, e.g. if this
    /// UT_Array is a member variable of a class whose memory is already
    /// being counted by the caller.
    int64           getMemoryUsage(bool inclusive=false) const
    {
        return (inclusive ? sizeof(*this) : 0) + capacity()*sizeof(T); // NOLINT
    }

    /// Set the size, the number of occupied elements in the array.
    /// NOTE: This will not do bumpCapacity, so if you call this
    ///       n times to increase the size, it may take
    ///       n^2 time.
    void            setSize(exint newsize)
    {
        if (newsize < 0)
            newsize = 0;
        if (newsize == mySize)
            return;
        setCapacityIfNeeded(newsize);
        if (mySize > newsize)
            destroyRange(myData + newsize, mySize - newsize);
        else // newsize > mySize
            constructRange(myData + mySize, newsize - mySize);
        mySize = newsize;
    }
    void            setSizeIfNeeded(exint minsize)
    {
        if (size() >= minsize)
            return;
        setSize(minsize);
    }
    /// Alias of setSize().  setSize() is preferred.
    void            entries(exint newsize)
    {
        setSize(newsize);
    }
    /// Set the size, but unlike setSize(newsize), this function
    /// will not initialize new POD elements to zero. Non-POD data types
    /// will still have their constructors called.
    /// This function is faster than setSize(ne) if you intend to fill in
    /// data for all elements.
    void            setSizeNoInit(exint newsize)
    {
        if (newsize < 0)
            newsize = 0;
        if (newsize == mySize)
            return;
        setCapacityIfNeeded(newsize);
        if (mySize > newsize)
            destroyRange(myData + newsize, mySize - newsize);
        else if (!isPOD()) // newsize > mySize
            constructRange(myData + mySize, newsize - mySize);
        mySize = newsize;
    }

    /// shrinks the capacity to the current size
    void            shrinkToFit()
    {
        // TODO: be more intelligent here
        setCapacity(size());
    }
    /// convenience method to set size and shrink-to-fit in a single call
    void            setSizeAndShrink(exint new_size)
    {
        setSize(new_size);
        shrinkToFit();
    }

    /// Decreases, but never expands, to the given maxsize.
    void            truncate(exint maxsize)
    {
        if (maxsize >= 0 && size() > maxsize)
            setSize(maxsize);
    }
    /// Resets list to an empty list.
    void            clear() 
    {
        // Don't call setSize(0) since it supports growing the array
        // which requires a default constructor.  Avoiding it allows
        // this to be used on types that lack a default constructor.
        destroyRange(myData, mySize);
        mySize = 0;
    }

    /// Assign array a to this array by copying each of a's elements with
    /// memcpy for POD types, and with copy construction for class types.
    UT_Array<T> &   operator=(const UT_Array<T> &a);

    /// Replace the contents with those from the initializer_list ilist
    UT_Array<T> &   operator=(std::initializer_list<T> ilist);

    /// Move the contents of array a to this array. 
    UT_Array<T> &   operator=(UT_Array<T> &&a) noexcept;

    /// Compare two array and return true if they are equal and false otherwise.
    /// Two elements are checked against each other using operator '==' or
    /// compare() respectively.
    /// NOTE: The capacities of the arrays are not checked when
    ///       determining whether they are equal.
    bool            operator==(const UT_Array<T> &a) const;
    bool            operator!=(const UT_Array<T> &a) const;


    template <typename ComparatorBool,
              typename = IsBoolComp<ComparatorBool>>
    bool            isEqual(const UT_Array<T> &a, ComparatorBool is_equal) const;

    SYS_DEPRECATED_REPLACE(20.5, "Use ComparatorBool variant")
    int             isEqual(const UT_Array<T> &a, Comparator compare) const;
     
    /// Subscript operator
    /// NOTE: This does NOT do any bounds checking unless paranoid
    ///       asserts are enabled.
    T &             operator()(exint i)
    {
        UT_ASSERT_P(i >= 0 && i < mySize);
        return myData[i];
    }
    /// Const subscript operator
    /// NOTE: This does NOT do any bounds checking unless paranoid
    ///       asserts are enabled.
    const T &       operator()(exint i) const
    {
        UT_ASSERT_P(i >= 0 && i < mySize);
        return myData[i];
    }

    /// Subscript operator
    /// NOTE: This does NOT do any bounds checking unless paranoid
    ///       asserts are enabled.
    T &             operator[](exint i)
    {
        UT_ASSERT_P(i >= 0 && i < mySize);
        return myData[i];
    }
    /// Const subscript operator
    /// NOTE: This does NOT do any bounds checking unless paranoid
    ///       asserts are enabled.
    const T &       operator[](exint i) const
    {
        UT_ASSERT_P(i >= 0 && i < mySize);
        return myData[i];
    }
    
    /// forcedRef(exint) will grow the array if necessary, initializing any
    /// new elements to zero for POD types and default constructing for
    /// class types.
    T &             forcedRef(exint i)
    {
        UT_ASSERT_P(i >= 0);
        if (i >= mySize)
            bumpSize(i+1);
        return myData[i];
    }

    /// forcedGet(exint) does NOT grow the array, and will return default
    /// objects for out of bound array indices.
    T               forcedGet(exint i) const
    {
        return (i >= 0 && i < mySize) ? myData[i] : T();
    }

    T &             last()
    {
        UT_ASSERT_P(mySize);
        return myData[mySize-1];
    }
    const T &       last() const
    {
        UT_ASSERT_P(mySize);
        return myData[mySize-1];
    }

    /// Apply a user-defined function to each element of the array
    /// as int as the function returns zero. If apply_func returns
    /// 1, apply() stops traversing the list and returns the current
    /// index; otherwise, apply() returns the size.
    exint           apply(int (*apply_func)(T &t, void *d), void *d);

    template <typename BinaryOp>
    T               accumulate(const T &init_value, BinaryOp add) const;

    T *             getArray() const                { return myData; }
    const T *       getRawArray() const             { return myData; }

    T *             array()                         { return myData; }
    const T *       array() const                   { return myData; }

    T *             data()                          { return myData; }
    const T *       data() const                    { return myData; }

    /// This method allows you to swap in a new raw T array, which must be
    /// the same size as capacity(). Use caution with this method.
    T *             aliasArray(T *newdata)
    { T *data = myData; myData = newdata; return data; }

    template <typename IT, bool FORWARD>
    class base_iterator
    {
        public:
            using iterator_category = std::random_access_iterator_tag;
            using value_type = T;
            using difference_type = exint;
            using pointer = IT*;
            using reference = IT&;
        
            // Note: When we drop gcc 4.4 support and allow range-based for
            // loops, we should also drop atEnd(), which means we can drop
            // myEnd here.
            base_iterator() : myCurrent(nullptr), myEnd(nullptr) {}
            
              // Allow iterator to const_iterator conversion
            template<typename EIT>
            base_iterator(const base_iterator<EIT, FORWARD> &src)
                : myCurrent(src.myCurrent), myEnd(src.myEnd) {}
            
            pointer     operator->() const 
                        { return FORWARD ? myCurrent : myCurrent - 1; }
            
            reference   operator*() const
                        { return FORWARD ? *myCurrent : myCurrent[-1]; }

            reference   item() const
                        { return FORWARD ? *myCurrent : myCurrent[-1]; }
            
            reference   operator[](exint n) const
                        { return FORWARD ? myCurrent[n] : myCurrent[-n - 1]; } 

            /// Pre-increment operator
            base_iterator &operator++()
                        {
                            if (FORWARD) ++myCurrent; else --myCurrent;
                            return *this;
                        }
            /// Post-increment operator
            base_iterator operator++(int)
                        {
                            base_iterator tmp = *this;
                            if (FORWARD) ++myCurrent; else --myCurrent;
                            return tmp;
                        }
            /// Pre-decrement operator
            base_iterator &operator--()
                        {
                            if (FORWARD) --myCurrent; else ++myCurrent;
                            return *this;
                        }
            /// Post-decrement operator
            base_iterator operator--(int)
                        {
                            base_iterator tmp = *this;
                            if (FORWARD) --myCurrent; else ++myCurrent;
                            return tmp;
                        }

            base_iterator &operator+=(exint n)   
                        {
                            if (FORWARD)
                                myCurrent += n;
                            else
                                myCurrent -= n;
                            return *this;
                        }
            base_iterator operator+(exint n) const
                        {
                            if (FORWARD)
                                return base_iterator(myCurrent + n, myEnd);
                            else
                                return base_iterator(myCurrent - n, myEnd);
                        }
            
            base_iterator &operator-=(exint n)
                        { return (*this) += (-n); }
            base_iterator operator-(exint n) const
                        { return (*this) + (-n); }
            
            bool         atEnd() const          { return myCurrent == myEnd; }
            void         advance()              { this->operator++(); }
            
            // Comparators
            template<typename ITR, bool FR>
            bool         operator==(const base_iterator<ITR, FR> &r) const
                         { return myCurrent == r.myCurrent; }
            
            template<typename ITR, bool FR>
            bool         operator!=(const base_iterator<ITR, FR> &r) const
                         { return myCurrent != r.myCurrent; }
            
            template<typename ITR>
            bool         operator<(const base_iterator<ITR, FORWARD> &r) const
            {
                if (FORWARD) 
                    return myCurrent < r.myCurrent;
                else
                    return r.myCurrent < myCurrent;
            }
            
            template<typename ITR>
            bool         operator>(const base_iterator<ITR, FORWARD> &r) const
            {
                if (FORWARD) 
                    return myCurrent > r.myCurrent;
                else
                    return r.myCurrent > myCurrent;
            }

            template<typename ITR>
            bool         operator<=(const base_iterator<ITR, FORWARD> &r) const
            {
                if (FORWARD) 
                    return myCurrent <= r.myCurrent;
                else
                    return r.myCurrent <= myCurrent;
            }

            template<typename ITR>
            bool         operator>=(const base_iterator<ITR, FORWARD> &r) const
            {
                if (FORWARD) 
                    return myCurrent >= r.myCurrent;
                else
                    return r.myCurrent >= myCurrent;
            }
            
            // Difference operator for std::distance
            template<typename ITR>
            exint        operator-(const base_iterator<ITR, FORWARD> &r) const
            {
                if (FORWARD) 
                    return exint(myCurrent - r.myCurrent);
                else
                    return exint(r.myCurrent - myCurrent);
            }

            // C++20 requires that { n + iter } -> std::same_as<I>;
            template<typename ITR>
            friend base_iterator operator+(
                    exint n,
                    const base_iterator<ITR, FORWARD> &next) noexcept
            {
                next += n;
                return next;
            }

        protected:
            friend class UT_Array<T>;
            base_iterator(IT *c, IT *e) : myCurrent(c), myEnd(e) {}
        private:

            IT                  *myCurrent;
            IT                  *myEnd;
    };
    
    typedef base_iterator<T, true>              iterator;
    typedef base_iterator<const T, true>        const_iterator;
    typedef base_iterator<T, false>             reverse_iterator;
    typedef base_iterator<const T, false>       const_reverse_iterator;
    typedef const_iterator      traverser; // For backward compatibility

    /// Begin iterating over the array.  The contents of the array may be 
    /// modified during the traversal.
    iterator            begin()
                        {
                            return iterator(myData, myData + mySize);
                        }
    /// End iterator.
    iterator            end()
                        {
                            return iterator(myData + mySize,
                                            myData + mySize);
                        }

    /// Begin iterating over the array.  The array may not be modified during
    /// the traversal.
    const_iterator      begin() const
                        {
                            return const_iterator(myData, myData + mySize);
                        }
    /// End const iterator.  Consider using it.atEnd() instead.
    const_iterator      end() const
                        {
                            return const_iterator(myData + mySize,
                                                  myData + mySize);
                        }
    
    /// Begin iterating over the array in reverse. 
    reverse_iterator    rbegin()
                        {
                            return reverse_iterator(myData + mySize,
                                                    myData);
                        }
    /// End reverse iterator.
    reverse_iterator    rend()
                        {
                            return reverse_iterator(myData, myData);
                        }
    /// Begin iterating over the array in reverse. 
    const_reverse_iterator rbegin() const
                        {
                            return const_reverse_iterator(myData + mySize,
                                                          myData);
                        }
    /// End reverse iterator.  Consider using it.atEnd() instead.
    const_reverse_iterator rend() const
                        {
                            return const_reverse_iterator(myData, myData);
                        }
    
    UT_IteratorRange<iterator> range()
                        { return UT_IteratorRange<iterator>(begin(), end()); }
    UT_IteratorRange<const_iterator> range() const
                        { return UT_IteratorRange<const_iterator>(begin(), end()); }
    
    UT_IteratorRange<reverse_iterator> rrange()
                        { return UT_IteratorRange<reverse_iterator>(rbegin(), rend()); }
    UT_IteratorRange<const_reverse_iterator> rrange() const
                        { return UT_IteratorRange<const_reverse_iterator>(rbegin(), rend()); }

    /// Remove item specified by the reverse_iterator.
    void                removeItem(const reverse_iterator &it)
                        {
                            removeAt(&it.item() - myData);
                        }


    /// Very dangerous methods to share arrays.
    /// The array is not aware of the sharing, so ensure you clear
    /// out the array prior a destructor or setCapacity operation.
    void            unsafeShareData(UT_Array<T> &src)
                    {
                        myData = src.myData;
                        myCapacity = labelExternal( src.capacity() );
                        mySize = src.mySize;
                    }
    void            unsafeShareData(T *src, exint srcsize)
                    {
                        myData = src;
                        myCapacity = labelExternal( srcsize );
                        mySize = srcsize;
                    }
    void            unsafeShareData(T *src, exint size, exint capacity)
                    {
                        myData = src;
                        mySize = size;
                        myCapacity = labelExternal( capacity );
                    }
    void            unsafeClearData()
                    {
                        myData = nullptr;
                        myCapacity = labelExternal( 0 );
                        mySize = 0;
                    }

    /// Returns true if the data used by the array was allocated on the heap.
    inline bool     isHeapBuffer() const
                    {
                        return isHeapBuffer(myData);
                    }

protected:
    // Check whether T may have a constructor, destructor, or copy
    // constructor.  This test is conservative in that some POD types will
    // not be recognized as POD by this function. To mark your type as POD,
    // use the SYS_DECLARE_IS_POD() macro in SYS_TypeDecorate.h.
    static constexpr SYS_FORCE_INLINE bool isPOD()
    {
        return SYS_IsPod_v< T >;
    }

    /// Implements both append(const T &) and append(T &&) via perfect
    /// forwarding. Unlike the variadic emplace_back(), its argument may be a
    /// reference to another element in the array.
    template <typename S>
    exint           appendImpl(S &&s);

    /// Similar to appendImpl() but for insertion.
    template <typename S>
    exint           insertImpl(S &&s, exint index);

    template <typename S>
    SYS_DEPRECATED_HDK(13.0)
    exint           uniqueSortedInsertImpl(S &&s, Comparator compare);

    /// In debug builds, verifies that the arguments to emplace_back() will not
    /// be invalidated when realloc() is called.
    template <typename First, typename... Rest>
    void validateEmplaceArgs(First &&first, Rest&&... rest) const
    {
        UT_ASSERT_MSG_P(
            static_cast<const void *>(&first) <
                static_cast<const void *>(myData) ||
            static_cast<const void *>(&first) >=
                static_cast<const void *>(myData + mySize),
            "Argument cannot reference an existing element in the array.");

        validateEmplaceArgs(std::forward<Rest>(rest)...);
    }

    /// Base case for validateEmplaceArgs().
    void validateEmplaceArgs() const
    {
    }

    // Construct the given type
    template <typename... S>
    static void     construct(T &dst, S&&... s)
                    {
                        new (&dst) T(std::forward<S>(s)...);
                    }

    // Copy construct the given type
    static void     copyConstruct(T &dst, const T &src)
                    {
                        if constexpr( SYS_IsPod_v< T > )
                        {
                            dst = src;
                        }
                        else // constexpr
                        {
                            new (&dst) T(src);
                        }
                    }

private:
    /// Equivalent to std::back_insert_iterator, but using the append() method
    /// for UT_Array. This is useful for appending to an array via STL
    /// algorithms that have an output iterator
    class AppendIterator
    {
    public:
        using iterator_category = std::output_iterator_tag;
        using value_type = void;
        using difference_type = void;
        using pointer = void;
        using reference = void;

        explicit AppendIterator(UT_Array<T> &arr) : myArray(&arr) {}

        /// @{
        /// Append the value when the iterator is assigned to.
        AppendIterator &operator=(const T &val)
        {
            myArray->append(val);
            return *this;
        }

        AppendIterator &operator=(T &&val)
        {
            myArray->append(std::move(val));
            return *this;
        }
        /// @}

        /// @{
        /// This iterator does not move, and dereferencing just returns itself.
        AppendIterator &operator*() { return *this; }
        AppendIterator &operator++() { return *this; }
        AppendIterator operator++(int) { return *this; }
        /// @}

    private:
        UT_Array<T> *myArray;
    };
    
#ifdef UT_ARRAY_STRICT_LABELED_CAPACITY
    using LabeledCapacity = UT_LabeledCapacity;
#else    
    using LabeledCapacity = UT_LabeledCapacityRep;
#endif

    /// Pointer to the array of elements of type T
    T *myData;

    /// The number of elements for which we have allocated memory
    LabeledCapacity myCapacity;

    /// The actual number of valid elements in the array
    exint mySize;
    
    // Create a Capacity that's labeled as owned by this UT_Array
    static LabeledCapacity labelOwned(const exint capacity) noexcept;
    
    // Create a Capacity that's labeled as external (not owned by this UT_Array)
    static LabeledCapacity labelExternal(const exint capacity) noexcept;

    // All memory allocations, reallocations and deallocations in UT_Array's
    // implementation go through the three functions
    // allocateArray, reallocateArray, deallocateArray below.
    // These functions make no calls to constructors/destructors.

    // Return an array with given capacity for elements of type T.
    // PRE: capacity > 0
    static T *allocateArray(const exint capacity) noexcept;

    // Return an array with given capacity for elements of type T.
    // reusing the passed-in 'data' if possible.
    // PRE: capacity > 0
    static T *reallocateArray(T *data, const exint capacity) noexcept;

    // NOTE: This will work correctly with data == nullptr
    static void deallocateArray(T *data) noexcept;

    // Identify whether 'data' is a heap buffer.
    // 'data' is decided to be a heap buffer when it is not
    // located at the first memory location after this UT_Array object
    // (a trick used by UT_SmallArray).
    // If a call to 'allocateArray' happens to return the first memory
    // location after this UT_Array object, then isHeapBuffer ends up false.
    // To avoid this, a second allocation should then by attempted,
    // see 'allocateArrayHeapIdentifiable' below.
    bool isHeapBuffer(T* data) const;
                    
    // Like allocateArray, except ensure that the returned array 'data'
    // is NOT located at the end of this UT_Array object, so that
    // isHeapBuffer( data) is true.
    // PRE: capacity > 0
    T *allocateArrayHeapIdentifiable(const exint capacity);
    
    //
    // Construct/destroy elements and ranges.
    // For POD types, construct* fills T objects with zeroes,
    // and destroy* does nothing.
    // For non-POD types, construct* calls the regular constructor
    // (by way of placement new), and destroy* calls the regular destructor.
    //

    static void constructElement(T &dst);
    static void constructRange(T *dst, exint n);

    static void destroyElement(T &dst) noexcept;
    static void destroyRange([[maybe_unused]] T *dst, exint n) noexcept;
    
    //
    // About relocation:
    // Relocating [ src, src + n ) to [ dst, dst + n ) should be equivalent
    // to the following:
    // For each i in [ 0, n ):
    // 1. move construct dst[ i ] from src[ i ]
    // 2. destroy src[ i ]
    //
    // The trivial relocation macros and traits defined in SYS_TypeDecorate.h
    // and SYS_TypeTraits.h can be used to indicate for which types T
    // bitwise copying is equivalent to the above construct and destroy steps.
    // 
    
    // The below "standardRelocate" methods relocate
    // [ src, src + n ) to [ dst, dst + n ) by invoking
    // T's move constructor and destructor.
   
    // Relocate elements in increasing order 0, 1, ..., n - 1
    static void standardRelocateIncreasing(T *dst, T *src, exint n);
    
    // Relocate elements in decreasing order n - 1,, ..., 1, 0 
    static void standardRelocateDecreasing(T *dst, T *src, exint n);
    
    // For use in cases where the source and destination ranges may overlap:
    // Relocate in increasing order if dst < src and
    // relocate in decreasing order if src < dst.
    static void standardRelocate(T *dst, T *src, exint n);
    
    //
    // The below "bitwiseRelocate" methods relocate
    // [ src, src + n ) to [ dst, dst +n ) using memcpy and memmove,
    // and do not invoke destructors afterwards.
    //

    // PRE:
    // * both 'dst' and 'src' are valid (not null)
    static void bitwiseRelocate(T *dst, const T *src, exint n) noexcept;
        
    // PRE:
    // * both 'dst' and 'src' are valid (not null)
    // * [ dst, dst + n ) and [ src, src + n ) don't overlap
    static void bitwiseRelocateNonoverlapping(
                        T *dst,
                        const T *src,
                        exint n) noexcept;

    //
    // The below relocate, copy and swap methods decide whether to use
    // standard or bitwise copying at compile time, based on traits.
    // Only these are the versions should be called directly by
    // the rest of the UT_Array implementation.
    //

    // For trivially relocatable types, bitwise copy [ src, src + n )
    // onto [ dst, dst + n ) instead.
    static void relocate(T *dst, T *src, exint n);
    
    // Version of relocate with a stronger precondition that is
    // exploited for potentially faster computation:    
    // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
    static void relocateNonoverlapping(T *dst, T *src, exint n);
    
    // PRE: dst < src
    static void relocateIncreasing(T *dst, T *src, exint n);
    
    // PRE: dst > src
    static void relocateDecreasing(T *dst, T *src, exint n);

    // copyNonoverlapping is similar to relocateNonoverlapping,
    // with the following to differences:
    // * Each value is copy constructed into its destination (not moved)
    // * The source values are not destroyed (no destructor invoked)
    // PRE: [ dst, dst + n ) and [ src, src + n ) don't overlap
    static void copyNonoverlapping(T *dst, const T *src, exint n);

    // swapNonoverlapping is equivalent to the following:
    // For each i in [ 0, n ): swap dst[ i ] and src[ i ]
    static void swapNonoverlapping(T *dst, T *src, exint n);

    // The guts of the remove() methods.
    exint removeAt(exint index);

    // Convert the current object's buffer from a non-heap buffer
    // to a heap buffer of given capacity
    // PRE: *this has a non-heap buffer
    //      'capacity' should be at least the size
    // POST: *this has a heap buffer with given capacity,
    //       and its initial size elements are the same as before the call
    void convertToHeapBuffer(const exint capacity);

    template<typename OS, typename S>
    friend OS &operator<<(OS &os, const UT_Array<S> &d);

    /// Friend specialization of std::swap() to use UT_String::swap()
    /// @internal This is needed because standard std::swap() implementations
    /// will try to copy the UT_String objects, causing hardened strings to
    /// become weak.
    friend void swap(UT_Array<T>& a, UT_Array<T>& b) { a.swap(b); }
};

// Suppress UT_Array<UT_StringHolder> instantations to avoid duplicate symbols
// when UT_Array<UT_StringHolder> is used with UT_StringArray which derives
// from it.
class UT_StringHolder;
UT_EXTERN_TEMPLATE(UT_Array<UT_StringHolder>);

// Assigns src to dest, using the default C++ conversion operator.
template <typename T, typename S>
void
UTconvertArray(UT_Array<T> &dest, const UT_Array<S> &src)
{
    exint n = src.size();
    dest.setCapacity(n);
    dest.setSize(n);
    for (exint i = 0; i < n; i++)
        dest(i) = T(src(i));
}
template <typename T, typename S>
void
UTconvertArray(UT_Array<T> &dest, const S *src, exint n)
{
    dest.setCapacity(n);
    dest.setSize(n);
    for (exint i = 0; i < n; i++)
        dest(i) = T(src[i]);
}
template <typename T, typename S>
void
UTconvertArray(T *dest, const UT_Array<S> &src)
{
    // We assume here that dest has enough memory for src.size()
    exint n = src.size();
    for (exint i = 0; i < n; i++)
        dest[i] = T(src(i));
}
template <typename T, typename S>
void
UTconvertArray(T *dest, const S *src, int64 n)
{
    // We assume here that dest has enough memory for n elements
    for (int64 i = 0; i < n; i++)
        dest[i] = T(src[i]);
}

#include "UT_ArrayImpl.h" // IWYU pragma: export


template<typename OS, typename S>
inline OS &
operator<<(OS &os, const UT_Array<S> &d)
{
    os << "UT_Array" << UT_ContainerPrinter<UT_Array<S> >(d);
    return os;
}

// Overload for custom formatting of a UT_StringArray with UTformat.
template <typename T> UT_API size_t
UTformatBuffer(char *buffer, size_t bufsize, const UT_Array<T> &v);

/// Unlike UT_Array::getMemoryUsage(), this also calls getMemoryUsage() on the
/// its elements
template <template <typename> class ArrayT, typename T>
static inline int64
UTarrayDeepMemoryUsage(const ArrayT<T> &arr, bool inclusive)
{
    int64 mem = inclusive ? sizeof(arr) : 0;
    mem += arr.getMemoryUsage(false);
    for (auto &&item : arr)
        mem += item.getMemoryUsage(false);
    return mem;
}

/// Utility to sort array using operator<
template <typename T>
static inline void
UTsort(UT_Array<T> &arr)
{
    arr.sort([](const T &a, const T &b) { return a < b; });
}

/// Utility to sort array using operator< and remove duplicates
template <typename T>
static inline void
UTsortAndRemoveDuplicates(UT_Array<T> &arr)
{
    arr.sortAndRemoveDuplicates([](const T &a, const T &b) { return a < b; });
}

// For UT::ArraySet.
namespace UT
{
template <typename T>
struct DefaultClearer;

template <typename T>
struct DefaultClearer<UT_Array<T>>
{
    static void clear(UT_Array<T> &v) { v.setCapacity(0); }
    static bool isClear(const UT_Array<T> &v) { return v.capacity() == 0; }
    static void clearConstruct(UT_Array<T> *p)
    {
        new ((void *)p) UT_Array<T>();
    }
    static const bool clearNeedsDestruction = false;
};
} // namespace UT

//
// Trivial relocation is not safe for UT_Array:
// UT_SmallArray, which has a fixed-buffer optimization inherits from UT_Array.
// At compile time, it cannot be known whether a UT_Array object is a
// UT_SmallArray object.
// For this reason alone, it cannot be safe to use trivial relocation on UT_Array.
//
// In addition to that, UT_Array is currently not safe for trivial relocation
// even if UT_SmallArray didn't get used anywhere, due to the isHeapBuffer() test,
// which may incorrectly return false after a UT_Array with a heap buffer gets
// trivially relocated (making it adjacent in memory to its myData).
//
template <typename T>
SYS_DECLARE_IS_NOT_TR_TEMPLATE(UT_Array<T>)

//
// Trivial relocation is not safe for std::string since most implementations
// use a small buffer optimization (aka SBO).
//
#if defined(MBSD) || defined(_LIBCPP_VERSION)
  #include <iosfwd>
  template <typename CharT, typename Traits, typename Allocator>
  SYS_DECLARE_IS_NOT_TR_TEMPLATE(std::basic_string<CharT,Traits,Allocator>)
#elif defined(__GLIBCXX__)
  #include <bits/stringfwd.h>
  template <typename CharT, typename Traits, typename Allocator>
  SYS_DECLARE_IS_NOT_TR_TEMPLATE(std::basic_string<CharT,Traits,Allocator>)
#else
  namespace std { template <class,class,class> class basic_string; }
  template <typename CharT, typename Traits, typename Allocator>
  SYS_DECLARE_IS_NOT_TR_TEMPLATE(std::basic_string<CharT,Traits,Allocator>)
#endif

#endif // __UT_ARRAY_H_INCLUDED__