UT_ArrayImpl.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:        Utility Library (C++)
 *
 * COMMENTS:
 *      This is meant to be included by UT_Array.h and includes
 *      the template implementations needed by external code.
 */

#pragma once

#ifndef __UT_ARRAYIMPL_H_INCLUDED__
#define __UT_ARRAYIMPL_H_INCLUDED__

#include "UT_ArrayHelp.h"
#include "UT_Assert.h"
#include "UT_Compare.h"
#include "UT_Swap.h"
#include <VM/VM_Math.h>
#include <SYS/SYS_Math.h>
#include <SYS/SYS_TypeTraits.h>
#include <SYS/SYS_Pragma.h>

#include <algorithm>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Increasing safety levels for relocation
#define UT_RELOCATION_SAFETY_NONE       0
#define UT_RELOCATION_SAFETY_PATCHY     1
#define UT_RELOCATION_SAFETY_PERMISSIVE 2
#define UT_RELOCATION_SAFETY_NORMAL     3
#define UT_RELOCATION_SAFETY_MAXIMUM    4

// Set current level
#define UT_RELOCATION_SAFETY_LEVEL UT_RELOCATION_SAFETY_PATCHY


#if (UT_RELOCATION_SAFETY_LEVEL >= UT_RELOCATION_SAFETY_MAXIMUM)

// Use trivial relocation for no types at all
template< typename T >
struct SYS_UseTrivialRelocation : SYS_FalseType {};

#elif (UT_RELOCATION_SAFETY_LEVEL >= UT_RELOCATION_SAFETY_NORMAL)

// Use trivial relocation only for types that are explicitly declared safe
template< typename T >
struct SYS_UseTrivialRelocation : SYS_IsTriviallyRelocatable< T > {};

#elif (UT_RELOCATION_SAFETY_LEVEL >= UT_RELOCATION_SAFETY_PERMISSIVE)

// Use trivial relocation for types that are explicitly declared safe
// and for types that must use it because of legacy code
template< typename T >
struct SYS_UseTrivialRelocation : 
    SYS_BoolConstant<
        SYS_IsTriviallyRelocatable< T >::value ||
        LegacyTrivialRelocationNoCV< std::remove_cv_t< T > >::value
    >
{};

#elif (UT_RELOCATION_SAFETY_LEVEL >= UT_RELOCATION_SAFETY_PATCHY)

// Use trivial relocation for types that are not explicitly declared unsafe
// and for types that must use it due to legacy code.
template< typename T >
struct SYS_UseTrivialRelocation : 
    SYS_BoolConstant<
        ( ! UnsafeTrivialRelocationNoCV< std::remove_cv_t< T > >::value ) ||
        LegacyTrivialRelocationNoCV< std::remove_cv_t< T > >::value
    >
{
    // If T is explicitly marked as unsafe using UnsafeTrivialRelocationNoCV,
    // then it cannot be explicitly marked as safe
    static_assert(
        ( ! UnsafeTrivialRelocationNoCV< std::remove_cv_t< T > >::value ) ||
        ( ! SYS_IsTriviallyRelocatable< T >::value ),
        "Not trivially relocatable"
    );
};

#else // if (UT_RELOCATION_SAFETY_LEVEL >= UT_RELOCATION_SAFETY_NONE)

// No safety at all: each type used with UT_Array is bitwise copied,
// regardless of whether it is safe to do so.
// This is the situation of Houdini 19.5.
template< typename T >
struct SYS_UseTrivialRelocation : SYS_TrueType {};

#endif

template< typename T >
constexpr auto SYS_UseTrivialRelocation_v = SYS_UseTrivialRelocation< T >::value;

template <typename T>
typename UT_Array<T>::LabeledCapacity
UT_Array<T>::labelOwned(const exint capacity) noexcept
{
    UT_ASSERT_P( capacity >= 0 );

#ifdef UT_ARRAY_STRICT_LABELED_CAPACITY

    return ownedLabeledCapacity( capacity );

#else

    UT_ASSERT_P( ( capacity & LABELED_CAPACITY_MASK_VALUE ) == capacity );

    // Don't set the external bit:
    return capacity;

#endif
}

template <typename T>
typename UT_Array<T>::LabeledCapacity
UT_Array<T>::labelExternal(const exint capacity) noexcept
{
    UT_ASSERT_P( capacity >= 0 );
    
#ifdef UT_ARRAY_STRICT_LABELED_CAPACITY

    return externalLabeledCapacity( capacity );

#else

    UT_ASSERT_P( ( capacity & LABELED_CAPACITY_MASK_VALUE ) == capacity );
    
    // Set the external bit:
    return capacity | LABELED_CAPACITY_FLAG_EXTERNAL;

#endif
}

template <typename T>
exint
UT_Array<T>::capacity() const
{
#ifdef UT_ARRAY_STRICT_LABELED_CAPACITY

    return capacityValue( myCapacity );

#else    

    return myCapacity & LABELED_CAPACITY_MASK_VALUE;

#endif
}

template <typename T>
T *
UT_Array<T>::allocateArray(const exint capacity) noexcept
{
    constexpr auto elem_size = sizeof(T); // NOLINT
   
    UT_ASSERT( capacity > 0 );

SYS_PRAGMA_PUSH_WARN()
SYS_PRAGMA_DISABLE_ALLOC_SIZE_LARGER_THAN()
    //TODO: Replace this C-style cast with a static_cast
    return (T *)malloc( capacity * elem_size );
SYS_PRAGMA_POP_WARN()
}

template <typename T>
T *
UT_Array<T>::reallocateArray(T *data, const exint capacity) noexcept
{
    constexpr auto elem_size = sizeof(T); // NOLINT
   
    UT_ASSERT( capacity > 0 );
   
SYS_PRAGMA_PUSH_WARN()
SYS_PRAGMA_DISABLE_ALLOC_SIZE_LARGER_THAN()
    //TODO: Replace this C-style cast with a static_cast
    return (T *)realloc( data, capacity * elem_size );
SYS_PRAGMA_POP_WARN()
}

template <typename T>
bool
UT_Array<T>::isHeapBuffer(T* data) const
{
    return (data != (T *)(((char*)this) + sizeof(*this)));
}
                    
template <typename T>
T *
UT_Array<T>::allocateArrayHeapIdentifiable(exint capacity)
{
    UT_ASSERT( capacity > 0 );

    T *data = allocateArray(capacity);

    // Avoid degenerate case if we happen to be aliased the wrong way
    if (!isHeapBuffer(data))
    {
        // `data` points to the end of us which erroneously causes
        // isHeapBuffer() to incorrectly identify us as a small buffer instead
        // of a heap buffer. Retry the allocation. Since `data` is still
        // occupied, the new allocation's address cannot be at our end anymore.
        T *prev = data;
        data = allocateArray(capacity);
        
        deallocateArray(prev);
    }

    return data;
}

template <typename T>
void
UT_Array<T>::deallocateArray(T *p) noexcept
{
SYS_PRAGMA_PUSH_WARN()
SYS_PRAGMA_DISABLE_FREE_NONHEAP_OBJECT()
SYS_PRAGMA_DISABLE_MISMATCHED_NEW_DELETE()
    free(p);
SYS_PRAGMA_POP_WARN()
}

template <typename T>
void SYS_FORCE_INLINE UT_Array<T>::constructElement(T &dst)
{
    if constexpr( ! SYS_IsPod_v< T > )
    {
        new (&dst) T();
    }
    else
    {
        //TODO: Eliminate C-style cast:
        memset((void *)&dst, 0, sizeof(T));
    }
}

template <typename T>
void UT_Array<T>::constructRange(T *dst, exint n)
{
    if constexpr( ! SYS_IsPod_v< T > )
    {
        for (exint i = 0; i < n; i++)
        {
            new (&dst[i]) T();
        }
    }
    else if (n == 1)
    {
        // Special case for n == 1. If the size parameter
        // passed to memset is known at compile time, this
        // function call will be inlined. This results in
        // much faster performance than a real memset
        // function call which is required in the case
        // below, where n is not known until runtime.
        // This makes calls to append() much faster.
        
        //TODO: Eliminate C-style cast:
        memset((void *)dst, 0, sizeof(T));
    }
    else
    {
        //TODO: Eliminate C-style cast:
        memset((void *)dst, 0, sizeof(T) * n);
    }
}

template <typename T>
SYS_FORCE_INLINE void UT_Array<T>::destroyElement(T &dst) noexcept
{
    if constexpr( ! SYS_IsPod_v< T > )
    {
        dst.~T();
    }
}

template <typename T>
void UT_Array<T>::destroyRange([[maybe_unused]] T *dst, exint n) noexcept
{
    if constexpr( ! SYS_IsPod_v< T > )
    {
        for (exint i = 0; i < n; i++)
        {
            dst[i].~T();
        }
    }
}

template <typename T>
void
UT_Array<T>::standardRelocateIncreasing(T *const dst, T *const src, exint n)
{
    for( exint i = 0; i != n; ++i )
    {
        new( dst + i ) T{ std::move( src[ i ] ) };
        src[ i ].~T();
    }
}

template <typename T>
void
UT_Array<T>::standardRelocateDecreasing(T *const dst, T *const src, exint n)
{
    for( exint i = n - 1; i >= 0; --i )
    {
        new( dst + i ) T{ std::move( src[ i ] ) };
        src[ i ].~T();
    }
}

template <typename T>
void
UT_Array<T>::standardRelocate(T *const dst, T *const src, exint n)
{
    if( dst < src )
    {
        standardRelocateIncreasing( dst, src, n );
    }
    else if( src < dst )
    {
        standardRelocateDecreasing( dst, src, n );
    }
}

// Return whether the ranges [ a, a + n ) and [ b, b + n ) overlap
template <typename T>
constexpr bool
UTareOverlapping( const T*const a, const T*const b, exint n ) noexcept
{
    return ! (
        ( b >= a + n ) ||
        ( a >= b + n )
    );
}

template <typename T>
void
UT_Array<T>::bitwiseRelocate(T *const dst, const T *const src, exint n) noexcept
{
    UT_ASSERT( dst != nullptr );
    UT_ASSERT( src != nullptr );
    UT_ASSERT( n >= 0 );

    //TODO: Eliminate these C-style casts;
    // they cause undefined behavior and
    // hide compiler warnings that indicate potential problems in our code base
    ::memmove( (void*)dst, (const void*)src, n * sizeof(T) ); // NOLINT
}

template <typename T>
void
UT_Array<T>::bitwiseRelocateNonoverlapping(
        T *const dst,
        const T *const src,
        exint n) noexcept
{
    UT_ASSERT( dst != nullptr );
    UT_ASSERT( src != nullptr );
    UT_ASSERT( n >= 0 );
    UT_ASSERT( ! UTareOverlapping( dst, src, n ) );

    //TODO: Eliminate these C-style casts;
    // they cause undefined behavior and
    // hide compiler warnings that indicate potential problems in our code base
    ::memcpy( (void*)dst, (const void*)src, n * sizeof(T) ); // NOLINT
}

template <typename T>
void
UT_Array<T>::relocateNonoverlapping(T *const dst, T *const src, exint n)
{
    UT_ASSERT( n >= 0 );
    UT_ASSERT( ! UTareOverlapping( dst, src, n ) );
    
    if constexpr( SYS_UseTrivialRelocation_v< T > )
    {
        if( n > 0 )
        {
            UT_ASSERT( dst != nullptr );
            UT_ASSERT( src != nullptr );

            bitwiseRelocateNonoverlapping( dst, src, n );
        }
    }
    else // constexpr
    {
        standardRelocateIncreasing( dst, src, n );
    }
}

template <typename T>
void UT_Array<T>::relocateIncreasing(T *dst, T *src, exint n)
{
    if constexpr( SYS_UseTrivialRelocation_v< T > )
    {
        if( n > 0 )
        {
            UT_ASSERT( dst != nullptr );
            UT_ASSERT( src != nullptr );

            bitwiseRelocate( dst, src, n );
        }
    }
    else // constexpr
    {
        standardRelocateIncreasing( dst, src, n );
    }
}

template <typename T>
void UT_Array<T>::relocateDecreasing(T *dst, T *src, exint n)
{
    if constexpr( SYS_UseTrivialRelocation_v< T > )
    {
        if( n > 0 )
        {
            UT_ASSERT( dst != nullptr );
            UT_ASSERT( src != nullptr );

            bitwiseRelocate( dst, src, n );
        }
    }
    else // constexpr
    {
        standardRelocateDecreasing( dst, src, n );
    }
}

template <typename T>
void
UT_Array<T>::relocate(T *const dst, T *const src, exint n)
{
    UT_ASSERT( n >= 0 );
    
    if constexpr( SYS_UseTrivialRelocation_v< T > )
    {
        if( n > 0 )
        {
            UT_ASSERT( dst != nullptr );
            UT_ASSERT( src != nullptr );

            bitwiseRelocate( dst, src, n );
        }
    }
    else // constexpr
    {
        standardRelocate( dst, src, n );
    }
}

template <typename T>
void
UT_Array<T>::swapNonoverlapping(T *const dst, T *const src, exint n)
{
    UT_ASSERT( n >= 0 );
    UT_ASSERT( ! UTareOverlapping( dst, src, n ) );
    
    if constexpr( SYS_UseTrivialRelocation_v< T > )
    {
        if( n > 0 )
        {
            UT_ASSERT( dst != nullptr );
            UT_ASSERT( src != nullptr );

            //TODO: bitwiseSwapNonoverlapping( dst, src, n )
            {
                char* bytes_dst{ reinterpret_cast< char* >( dst ) };
                char* bytes_src{ reinterpret_cast< char* >( src ) };

                const auto num_bytes{ n * sizeof( T ) };
                for( exint b = 0; b != num_bytes; ++b )
                {
                    UTswap( bytes_dst[ b ], bytes_src[ b ] );
                }
            }    
        }
    }
    else // constexpr
    {
        for( exint i = 0; i != n; ++i )
        {
            T t{ std::move( src[ i ] ) };

            src[ i ].~T();
            new( src + i ) T{ std::move( dst[ i ] ) };

            dst[ i ].~T();
            new( dst + i ) T{ std::move( t ) };
        }
    }
}

template <typename T>
void
UT_Array<T>::copyNonoverlapping(T *dst, const T *src, exint n)
{
    if constexpr( SYS_IsPod_v< T > )
    {
        if (n > 0)
        {
            bitwiseRelocateNonoverlapping(dst, src, n);
        }
    }
    else // constexpr
    {
        for (exint i = 0; i < n; i++)
        {
            new ( dst + i ) T{ src[i] };
        }
    }
}

template <typename T>
inline
UT_Array<T>::UT_Array(const UT_Array<T> &a)
    : myCapacity(labelOwned(a.size())), mySize(a.size())
{
    if (a.size() > 0)
    {
        myData = allocateArrayHeapIdentifiable(a.size());
        copyNonoverlapping(myData, a.array(), a.size());
    }
    else
    {
        myData = nullptr;
    }
}

template <typename T>
inline
UT_Array<T>::UT_Array(std::initializer_list<T> init)
    : myCapacity(labelOwned(init.size())), mySize(init.size())
{
    if (init.size() > 0)
    {
        myData = allocateArrayHeapIdentifiable(init.size());
        copyNonoverlapping(myData, init.begin(), init.size());
    }
    else
    {
        myData = nullptr;
    }
}

template <typename T>
inline
UT_Array<T>::UT_Array(UT_Array<T> &&a) noexcept :
    UT_Array{ UT_ArrayCT::GENERALIZED_MOVE, nullptr, 0, std::move( a ) }
{
}

template <typename T>
inline
UT_Array<T>::UT_Array(const exint capacity, const exint size) :
   myData{ capacity ? allocateArrayHeapIdentifiable(capacity) : nullptr },
   myCapacity{ labelOwned(capacity) },
   mySize{ (capacity < size) ? capacity : size }
{
    UT_ASSERT(capacity >= size);
    constructRange(myData, mySize);
}

template <typename T>
inline
UT_Array<T>::UT_Array(const exint capacity) :
    myData{ capacity ? allocateArrayHeapIdentifiable(capacity) : nullptr },
    myCapacity{ labelOwned(capacity) }, 
    mySize{ 0 }
{
}

template <typename T>
inline
UT_Array<T>::~UT_Array()
{
    destroyRange(myData, mySize);
    mySize = 0;
    
    if (isHeapBuffer())
    {
        deallocateArray(myData);
        return;
    }
    
    myData = nullptr;
    
    myCapacity = labelOwned(0);
}

template <typename T>
UT_Array<T>::UT_Array(
    const UT_ArrayCT::ExternalCapacity,
    T *external_data,
    const exint external_capacity
) : 
    myData{ external_data },
    myCapacity{ labelExternal(external_capacity) },
    mySize{ 0 }
{
}

template <typename T>
UT_Array<T>::UT_Array(
    const UT_ArrayCT::ExternalMove,
    T *external_data,
    const exint external_capacity,
    UT_Array&& a
) : 
    UT_Array{ UT_ArrayCT::GENERALIZED_MOVE, external_data, external_capacity, std::move( a ) }
{
}

template <typename T>
UT_Array<T>::UT_Array(
    const UT_ArrayCT::GeneralizedMove,
    T *external_data,
    const exint external_capacity,
    UT_Array&& a
) : 
    myData{ external_data },
    myCapacity{ labelExternal(external_capacity) },
    mySize{ 0 }
{
    if( ! a.isHeapBuffer() )
    {
        if( a.mySize > external_capacity )
        {
            myData = allocateArrayHeapIdentifiable(a.mySize);
            myCapacity = labelOwned(a.mySize);
        }
    
        relocateNonoverlapping(myData, a.myData, a.mySize);
        mySize = std::exchange( a.mySize, 0 );
        
        return;
    }
    
    myData = std::exchange( a.myData, nullptr );
    myCapacity = std::exchange( a.myCapacity, labelOwned(0) );

    mySize = std::exchange( a.mySize, 0 );
}

template <typename T>
void UT_Array<T>::convertToHeapBuffer(const exint capacity)
{
    UT_ASSERT(!isHeapBuffer());
    UT_ASSERT(mySize<=capacity);
    
    T *heap_data{ nullptr };
    
    if( capacity > 0 )
    {
        heap_data = allocateArray(capacity);
        relocateNonoverlapping(heap_data, myData, mySize);
    }

    myData = heap_data;
    myCapacity = labelOwned(capacity);
    
    // Because we were a nonheap buffer before the call,
    // it is for impossible myData to have been allocated exactly
    // at the end of the UT_Array part.
    // That part of memory is already occupied by UT_SmallArray.
    // So there is no chance of *this being incorrectly identified
    // as a nonheap buffer.
    UT_ASSERT(isHeapBuffer());
}

template <typename T>
inline void
UT_Array<T>::swap(UT_Array<T> &other)
{   
    if(
        ( ( ! isHeapBuffer() ) || ( ! other.isHeapBuffer() ) ) &&
        ( ( other.mySize <= capacity() ) && ( mySize <= other.capacity() ) )
    )
    {
        // Optimization that applies when one or both
        // UT_Array objects are nonheap buffers:
        // As long as each array has the capacity to store the contents of
        // the other, the elements can be swapped individually.
        // This avoids the need to convert any nonheap buffer to a heap buffer.

        swapNonoverlapping( myData, other.myData, SYSmin( mySize, other.mySize ) );

        if( mySize < other.mySize )
        {
            relocateNonoverlapping( myData + mySize, other.myData + mySize, other.mySize - mySize );
        } 
        else if( other.mySize < mySize )
        {
            relocateNonoverlapping( other.myData + other.mySize, myData + other.mySize, mySize - other.mySize );
        }
    }
    else
    {
        if( ! isHeapBuffer() )
        {
            convertToHeapBuffer( capacity() );
        }
    
        if( ! other.isHeapBuffer() )
        {
            other.convertToHeapBuffer( other.capacity() );
        }

        UTswap(myData, other.myData);
        UTswap(myCapacity, other.myCapacity);
    }
    
    UTswap(mySize, other.mySize);
}

template <typename T>
inline exint    
UT_Array<T>::insert(exint index)
{
    if (index >= mySize)
    {
        bumpCapacity(index + 1);

        constructRange(myData + mySize, index - mySize + 1);

        mySize = index+1;
        return index;
    }
    bumpCapacity(mySize + 1);

    UT_ASSERT_P(index >= 0);
    relocateDecreasing(myData + index + 1, myData + index, mySize-index);

    constructElement(myData[index]);

    mySize++;
    return index;
}

template <typename T>
template <typename S>
inline exint
UT_Array<T>::appendImpl(S &&s)
{
    if (mySize == capacity())
    {
        exint idx = safeIndex(s);

        // NOTE: UTbumpAlloc always returns a strictly larger value.
        setCapacity(UTbumpAlloc(capacity()));
        if (idx >= 0)
            construct(myData[mySize], std::forward<S>(myData[idx]));
        else
            construct(myData[mySize], std::forward<S>(s));
    }
    else
    {
        construct(myData[mySize], std::forward<S>(s));
    }
    return mySize++;
}

template <typename T>
template <typename... S>
inline exint
UT_Array<T>::emplace_back(S&&... s)
{
#if UT_ASSERT_LEVEL >= UT_ASSERT_LEVEL_PARANOID
    validateEmplaceArgs(std::forward<S>(s)...);
#endif

    if (mySize == capacity())
    {
        setCapacity(UTbumpAlloc(capacity()));
    }

    construct(myData[mySize], std::forward<S>(s)...);
    return mySize++;
}

template <typename T>
inline void
UT_Array<T>::append(const T *pt, exint count)
{
    bumpCapacity(mySize + count);
    copyNonoverlapping(myData + mySize, pt, count);
    mySize += count;
}

template <typename T>
inline void
UT_Array<T>::appendMultiple(const T &t, exint count)
{
    UT_ASSERT_P(count >= 0);
    if (count <= 0)
        return;
    if (mySize + count >= capacity())
    {
        exint tidx = safeIndex(t);

        bumpCapacity(mySize + count);

        for (exint i = 0; i < count; i++)
            copyConstruct(myData[mySize+i], tidx >= 0 ? myData[tidx] : t);
    }
    else
    {
        for (exint i = 0; i < count; i++)
            copyConstruct(myData[mySize+i], t);
    }
    mySize += count;
}

template <typename T>
inline exint
UT_Array<T>::sortedInsert(const T &t, Comparator compare)
{
    return sortedInsert(t, UTcompareLess(compare));
}

template <typename T>
template <typename ComparatorBool, typename>
inline exint
UT_Array<T>::sortedInsert(const T &t, ComparatorBool is_less)
{
    exint     low, mid, high;

    low = 0;
    high = size() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (is_less(t, myData[mid]))
            high = mid - 1;
        else if (is_less(myData[mid], t))
            low = mid + 1;
        else
        {
            insertAt(t, mid);
            return mid;
        }
    }
    insertAt(t, low);
    return low;
}

template <typename T>
template <typename S>
inline exint
UT_Array<T>::uniqueSortedInsertImpl(S &&s, Comparator compare)
{
    exint     low, mid, high;

    low = 0;
    high = size() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (compare(&s, &myData[mid]) < 0)
            high = mid - 1;
        else if (compare(&s, &myData[mid]) > 0)
            low = mid + 1;
        else
            return (exint)mid;
    }
    insertImpl(std::forward<S>(s), low);
    return low;
}

template <typename T>
template <typename ComparatorBool, typename>
inline exint
UT_Array<T>::uniqueSortedInsert(const T &t, ComparatorBool is_less)
{
    exint     low, mid, high;

    low = 0;
    high = size() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (t == myData[mid])
            return (exint)mid;
        else if (is_less(t, myData[mid]))
            high = mid - 1;
        else
            low = mid + 1;
    }
    insertAt(t, low);
    return low;
}

template <typename T>
template <typename ComparatorBool, typename>
inline exint
UT_Array<T>::uniqueSortedFind(const T &item, ComparatorBool is_less) const
{
    exint       len = size();
    exint       idx = 0;

    while(len > 0)
    {
        exint   h = len / 2;
        if (is_less(myData[idx + h], item))
        {
            idx += h + 1;
            len -= h + 1;
        }
        else
            len = h;
    }

    return (idx != size() && !is_less(item, myData[idx])) ? idx : -1;
}

template <typename T>
inline exint
UT_Array<T>::uniqueSortedFind(const T &item, Comparator compare) const
{
    return uniqueSortedFind(item, UTcompareLess(compare));
}

template <typename T>
inline exint
UT_Array<T>::heapPush(const T &t, Comparator compare)
{
    UT_ASSERT(safeIndex(t) < 0);
    exint i = append(t);

    // walk up towards the root restoring the heap condition
    while( i > 0 && compare(&myData[(i - 1) / 2], &t) < 0 )
    {
        myData[i] = myData[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    myData[i] = t;
    return i;
}

template <typename T>
inline T
UT_Array<T>::heapPop(Comparator compare)
{
    UT_ASSERT_P(mySize > 0);

    T result = myData[0];
    // move last item into the newly created hole
    myData[0] = myData[mySize - 1];
    removeAt(mySize - 1);
    // percolate down until the heap condition is restored
    exint idx = 0;
    for(;;)
    {
        exint largest = idx;

        // test heap condition with left child
        exint cidx = 2 * idx + 1;
        if( cidx < mySize && compare(&myData[largest], &myData[cidx]) < 0 )
            largest = cidx;
        // test heap condition with right child
        ++cidx;
        if( cidx < mySize && compare(&myData[largest], &myData[cidx]) < 0 )
            largest = cidx;
        if( largest == idx )
        {
            // heap condition has been restored
            break;
        }

        UTswap(myData[idx], myData[largest]);
        idx = largest;
    }

    return result;
}

template <typename T>
inline exint
UT_Array<T>::concat(const UT_Array<T> &a)
{
    bumpCapacity(mySize + a.mySize);
    copyNonoverlapping(myData + mySize, a.myData, a.mySize);
    mySize += a.mySize;

    return mySize;
}

template <typename T>
inline exint
UT_Array<T>::concat(UT_Array<T> &&a) noexcept
{
    // If this array was empty, we can just steal from the other array.
    if (mySize == 0)
    {
        operator=(std::move(a));
        return mySize;
    }

    const exint n = a.mySize;
    bumpCapacity(mySize + n);
    relocateNonoverlapping(myData + mySize, a.myData, n);
    mySize += n;
    a.mySize = 0;

    return mySize;
}

template <typename T>
inline exint
UT_Array<T>::multipleInsert(exint beg_index, exint count)
{
    exint end_index = beg_index + count;

    if (beg_index >= mySize)
    {
        bumpCapacity(end_index);

        constructRange(myData + mySize, end_index - mySize);

        mySize = end_index;
        return beg_index;
    }
    bumpCapacity(mySize+count);

    relocateDecreasing(myData + end_index, myData + beg_index, mySize-beg_index);
    mySize += count;

    constructRange(myData + beg_index, count);

    return beg_index;
}

template <typename T>
template <typename S>
inline exint
UT_Array<T>::insertImpl(S &&s, exint index)
{
    if (index == mySize)
    {
        // This case avoids an extraneous call to constructRange()
        // which the compiler may not optimize out.
        (void) appendImpl(std::forward<S>(s));
    }
    else if (index > mySize)
    {
        exint src_i = safeIndex(s);

        bumpCapacity(index + 1);

        constructRange(myData + mySize, index - mySize);

        if (src_i >= 0)
            construct(myData[index], std::forward<S>(myData[src_i]));
        else
            construct(myData[index], std::forward<S>(s));

        mySize = index + 1;
    }
    else // (index < mySize)
    {
        exint src_i = safeIndex(s);

        bumpCapacity(mySize + 1);

        relocateDecreasing(myData + index + 1, myData + index, mySize-index);

        if (src_i >= index)
            ++src_i;

        if (src_i >= 0)
            construct(myData[index], std::forward<S>(myData[src_i]));
        else
            construct(myData[index], std::forward<S>(s));

        ++mySize;
    }

    return index;
}

template <typename T>
template <typename S>
inline exint
UT_Array<T>::findAndRemove(const S &s)
{
    exint       idx = find(s);
    return (idx < 0) ? -1 : removeAt((exint)idx);
}

template <typename T>
inline exint
UT_Array<T>::removeAt(exint idx)
{
    destroyElement(myData[idx]);
    if (idx != --mySize)
    {
        relocateIncreasing(myData + idx, myData + idx + 1, mySize - idx);
    }

    return idx;
}

template <typename T>
inline void
UT_Array<T>::removeRange(exint begin_i, exint end_i)
{
    UT_ASSERT(begin_i <= end_i);
    UT_ASSERT(end_i <= mySize);

    const exint nelements = end_i - begin_i;
    if (nelements <= 0)
    {
        return;
    }
    
    destroyRange(myData + begin_i, nelements);
    relocateIncreasing(myData + begin_i, myData + end_i, mySize - end_i);
    mySize -= nelements;
}

template <typename T>
inline void
UT_Array<T>::extractRange(exint begin_i, exint end_i, UT_Array<T>& dest)
{
    UT_ASSERT_P(begin_i >= 0);
    UT_ASSERT_P(begin_i <= end_i);
    UT_ASSERT_P(end_i <= size());
    UT_ASSERT(this != &dest);

    exint nelements = end_i - begin_i;

    // grow the raw array if necessary.
    dest.setCapacityIfNeeded(nelements);

    if( nelements > 0 )
    {
        relocate(dest.myData, myData + begin_i, nelements);
    }
    dest.mySize = nelements;

    // we just asserted this was true, but just in case
    if (this != &dest)
    {
        if (end_i < size())
        {
            if( nelements > 0 )
            {
                relocateIncreasing(myData + begin_i, myData + end_i, mySize - end_i);
            }
        }
        mySize -= nelements;
        if (mySize<0)
            mySize=0;
    }
}

template <typename T>
inline void
UT_Array<T>::move(exint src_idx, exint dst_idx, exint how_many)
{
    // Make sure all the parameters are valid.
    if (src_idx < 0)
        src_idx = 0;
    if (dst_idx < 0)
        dst_idx = 0;
    // If we are told to move a set of elements that would extend beyond the
    // end of the current array, trim the group.
    if (src_idx + how_many > size())
        how_many = size() - src_idx;
    // If the dst_idx would have us move the source beyond the end of the
    // current array, move the dst_idx back.
    if (dst_idx + how_many > size())
        dst_idx = size() - how_many;
    if (src_idx != dst_idx && how_many > 0)
    {
        exint savelen = SYSabs(src_idx - dst_idx);
        
        T* tmp = allocateArray(savelen);

        if (src_idx > dst_idx && how_many > 0)
        {
            // We're moving the group backwards. Save all the stuff that
            // we would overwrite, plus everything beyond that to the
            // start of the source group. Then move the source group, then
            // tack the saved data onto the end of the moved group.
            relocateNonoverlapping(tmp, &myData[dst_idx], savelen);
            relocate(&myData[dst_idx], &myData[src_idx], how_many);
            relocateNonoverlapping(&myData[dst_idx + how_many], tmp, savelen);
        }
        if (src_idx < dst_idx && how_many > 0)
        {
            // We're moving the group forwards. Save from the end of the
            // group being moved to the end of the where the destination
            // group will end up. Then copy the source to the destination.
            // Then move back up to the original source location and drop
            // in our saved data.
            relocateNonoverlapping(tmp, &myData[src_idx + how_many], savelen);
            relocate(&myData[dst_idx], &myData[src_idx], how_many);
            relocateNonoverlapping(&myData[src_idx], tmp, savelen);
        }

        deallocateArray(tmp);
    }
}

template <typename T>
template <typename IsEqual>
inline exint
UT_Array<T>::removeIf(IsEqual is_equal)
{
    // Move dst to the first element to remove.
    exint dst;
    for (dst = 0; dst < mySize; dst++)
    {
        if (is_equal(myData[dst]))
            break;
    }
    // Now start looking at all the elements past the first one to remove.
    for (exint idx = dst+1; idx < mySize; idx++)
    {
        if (!is_equal(myData[idx]))
        {
            UT_ASSERT(idx != dst);
            myData[dst] = std::move(myData[idx]);
            dst++;
        }
        // On match, ignore.
    }

    // Don't call setSize(dst) 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 + dst, mySize - dst);
    mySize = dst;

    return mySize;
}

template <typename T>
inline void
UT_Array<T>::cycle(exint how_many)
{
    exint        numShift;      //  The number of items we shift
    exint        remaining;     //  mySize - numShift

    if (how_many == 0 || mySize < 1)
        return;

    numShift = how_many % (exint)mySize;
    if (numShift < 0) numShift += mySize;
    remaining = mySize - numShift;
    
    if( numShift == 0 )
    {
        return;
    }
    
    T* tmp = allocateArray(numShift);

    relocate(tmp, myData + remaining, numShift);
    relocate(myData + numShift, myData, remaining);
    relocate(myData + 0, tmp, numShift);

    deallocateArray(tmp);
}

template <typename T>
inline void
UT_Array<T>::constant(const T &value)
{
    for (exint i = 0; i < mySize; i++)
    {
        myData[i] = value;
    }
}

// This constant() specialization needs to be declared here and implemented
// in UT_Array.C.
template <>
UT_API void UT_Array<fpreal32>::constant(const fpreal32 &val);

template <typename T>
inline void
UT_Array<T>::zero()
{
    if constexpr( SYS_IsPod_v< T > )
    {
        ::memset((void *)myData, 0, mySize*sizeof(T)); // NOLINT
    }
    else // constexpr
    {
        constructRange(myData, mySize);
    }
}

template <typename T>
template <typename S>
inline exint
UT_Array<T>::find(const S &s, exint start) const
{
    const T *end = myData + mySize;
    for (const T *p = myData + start; p < end; ++p)
        if (*p == s)
            return (p - myData);
    return -1;
}

template <typename T>
exint
UT_Array<T>::sortedFind(const T &t, Comparator compare) const
{
    T   *found;

    if( mySize == 0 ) return -1;

    // NOLINTNEXTLINE
    found = (T *)::bsearch(&t, myData, mySize, sizeof(T),
                        (ut_ptr_compare_func_t)compare);
    return found ? (found - myData) : -1;
}

template <typename T>
inline void
UT_Array<T>::reverse()
{
    exint n = mySize / 2;
    for (exint i = 0; i < n; i++ )
        UTswap(myData[i], myData[mySize-1-i]);
}

template <typename T>
inline void             
UT_Array<T>::sort(Comparator compare)
{
    std::sort(myData, myData + mySize, UTcompareLess(compare));
}

template <typename T>
template <typename ComparatorBool>
inline T
UT_Array<T>::selectNthLargest(exint idx, ComparatorBool is_less)
{
    // The idea of returning doesn't make sense if we have
    // an empty array.
    UT_ASSERT(size() > 0);
    if (size() == 0)
        return T();

    idx = SYSclamp(idx, (exint)0, (exint)(size())-1);

    UTnth_element(myData, &myData[idx], &myData[size()], is_less);

    return myData[idx];
}

template <typename T>
inline void             
UT_Array<T>::setCapacity(exint new_capacity)
{
    // Do nothing when new capacity is the same as the current
    if (new_capacity == capacity())
    {
        return;
    }
    
    // Special case for non-heap buffers
    if (!isHeapBuffer())
    {
        if (new_capacity < mySize)
        {
            // Destroy the extra elements without changing capacity()
            destroyRange(myData + new_capacity, mySize - new_capacity);
            mySize = new_capacity;
        }
        else if (new_capacity > capacity())
        {
            convertToHeapBuffer(new_capacity);
        }
        else 
        {
            // Keep capacity unchanged in this case
            UT_ASSERT_P(new_capacity >= mySize && new_capacity <= capacity());
        }
        return;
    }

    if (new_capacity == 0)
    {
        if (myData)
        {
            destroyRange(myData, mySize);
            deallocateArray(myData);
        }
        myData     = nullptr;
        myCapacity = labelOwned(0);
        mySize = 0;
        return;
    }

    if (new_capacity < mySize)
    {
        destroyRange(myData + new_capacity, mySize - new_capacity);
        mySize = new_capacity;
    }

    if (myData)
    {
        if constexpr( SYS_UseTrivialRelocation_v< T > )
        {
            myData = reallocateArray(myData, new_capacity);
        }
        else // constexpr
        {
            T *prev = myData;
            myData = allocateArray(new_capacity);
            if (mySize > 0)
            {
                relocateNonoverlapping(myData, prev, mySize);
            }
        
            deallocateArray(prev);
        }
    }
    else
    {
        myData = allocateArray(new_capacity);
    }

    // Avoid degenerate case if we happen to be aliased the wrong way
    if (!isHeapBuffer())
    {
        // `myData` points to the end of us which erroneously causes
        // isHeapBuffer() to incorrectly identify us as a small buffer instead
        // of a heap buffer. Retry the allocation. Since `myData` is still
        // occupied, the new allocation's address cannot be at our end anymore.
        T *prev = myData;
        myData = allocateArray(new_capacity);
        if (mySize > 0)
        {
            relocateNonoverlapping(myData, prev, mySize);
        }
        
        deallocateArray(prev);
    }

    myCapacity = labelOwned(new_capacity);
    UT_ASSERT(myData);
}

template <typename T>
inline UT_Array<T> &
UT_Array<T>::operator=(const UT_Array<T> &a)
{
    if (this == &a)
    {
        return *this;
    }

    UT_Array t{ a };
    swap( t );

    return *this;
}

template <typename T>
inline UT_Array<T> &
UT_Array<T>::operator=(std::initializer_list<T> a)
{
    const exint new_size = a.size();

    // Grow the raw array if necessary.
    setCapacityIfNeeded(new_size);

    // Make sure destructors and constructors are called on all elements
    // being removed/added.
    destroyRange(myData, mySize);

    copyNonoverlapping(myData, a.begin(), new_size);

    mySize = new_size;

    return *this;
}

template <typename T>
inline UT_Array<T> &
UT_Array<T>::operator=(UT_Array<T> &&a)
{
    // Satisfy requirement that if 'a' has a heap buffer,
    // then *this has to have a heap buffer as well.
    if((!isHeapBuffer()) && a.isHeapBuffer())
    {
        destroyRange(myData, mySize);
        mySize = 0;
        convertToHeapBuffer(0);
    }

    UT_Array t{ std::move( a ) };
    swap( t );
    
    return *this;
}


template <typename T>
inline bool
UT_Array<T>::operator==(const UT_Array<T> &a) const
{
    if (this == &a) return true;
    if (mySize != a.size()) return false;
    for (exint i = 0; i < mySize; i++)
        if (!(myData[i] == a(i))) return false;
    return true;
}

template <typename T>
inline bool
UT_Array<T>::operator!=(const UT_Array<T> &a) const
{
    return (!operator==(a));
}

template <typename T>
template <typename ComparatorBool, typename>
inline bool
UT_Array<T>::isEqual(const UT_Array<T> &a, ComparatorBool is_equal) const
{
    if (this == &a) return true;
    if (mySize != a.size()) return false;
    for (exint i = 0; i < mySize; i++)
    {
        if (!is_equal(myData[i], a[i])) return false;
    }
    return true;
}

template <typename T>
inline int
UT_Array<T>::isEqual(const UT_Array<T> &a, Comparator compare) const
{
    return isEqual(a, UTcompareEqual(compare));
}

template <typename T>
inline exint    
UT_Array<T>::apply(int (*apply_func)(T &t, void *d), void *d)
{
    exint i;
    for (i = 0; i < mySize; i++)
    {
        if (apply_func(myData[i], d))
            break;
    }
    return i;
}

// 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 T>
template <typename ComparatorBool>
inline void
UT_Array<T>::merge(
        const UT_Array<T> &other, int direction, bool allow_dups,
        ComparatorBool is_less)
{
    UT_Array<T> result;
    exint               our_idx;
    exint               other_idx;

    // handle trivial cases to avoid extra work
    if (other.size() == 0)
        return;
    if (size() == 0)
    {
        concat(other);
        return;
    }

    UT_ASSERT( direction == -1 || direction == +1 );
    direction = (direction > 0) ? +1 : -1;

    our_idx = 0;
    other_idx = 0;
    while( our_idx < size() && other_idx < other.size() )
    {
        const T &our_item = (*this)(our_idx);
        const T &other_item = other(other_idx);
        exint    item_dir;

        if (our_item == other_item)
            item_dir = 0;
        else if (is_less(our_item, other_item))
            item_dir = -1;
        else
            item_dir = +1;

        if( item_dir != 0 )
        {
            // we need to do an comparison in the next line to take care of the
            // fact that -INT_MIN is still less than 0.
            item_dir = ( (item_dir > 0) ? +1 : -1 ) * direction;
        }

        if( item_dir < 0 )
        {
            result.append( our_item );
            our_idx++;
        }
        else if( item_dir > 0 )
        {
            result.append( other_item );
            other_idx++;
        }
        else
        {
            result.append( our_item );
            our_idx++;
            if( allow_dups )
                result.append( other_item );
            other_idx++;
        }
    }

    UT_ASSERT( our_idx == size() || other_idx == other.size() );
    for( ; our_idx < size(); our_idx++ )
        result.append( (*this)(our_idx) );
    for( ; other_idx < other.size(); other_idx++ )
        result.append( other(other_idx) );

    // finally swap the result into us
    swap( result );
}

template <typename T>
inline bool
UT_Array<T>::hasSortedSubset(
        const UT_Array<T> &other,
        Comparator compare) const
{
    return hasSortedSubset(other, UTcompareLess(compare));
}

template <typename T>
template <typename ComparatorBool, typename>
inline bool
UT_Array<T>::hasSortedSubset(
        const UT_Array<T> &other,
        ComparatorBool compare) const
{
    return std::includes(
                myData, myData + mySize,
                other.myData, other.myData + other.mySize,
                compare);
}

template <typename T>
inline void
UT_Array<T>::sortedUnion(const UT_Array<T> &other, Comparator compare)
{
    sortedUnion(other, UTcompareLess(compare));
}

template <typename T>
inline void
UT_Array<T>::sortedUnion(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        Comparator compare) const
{
    sortedUnion(other, result, UTcompareLess(compare));
}

template <typename T>
inline void
UT_Array<T>::sortedIntersection(const UT_Array<T> &other, Comparator compare)
{
    sortedIntersection(other, UTcompareLess(compare));
}

template <typename T>
inline void
UT_Array<T>::sortedIntersection(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        Comparator compare) const
{
    sortedIntersection(other, result, UTcompareLess(compare));
}

template <typename T>
inline void
UT_Array<T>::sortedSetDifference(const UT_Array<T> &other, Comparator compare)
{
    sortedSetDifference(other, UTcompareLess(compare));
}

template <typename T>
inline void
UT_Array<T>::sortedSetDifference(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        Comparator compare) const
{
    sortedSetDifference(other, result, UTcompareLess(compare));
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedUnion(const UT_Array<T> &other, ComparatorBool is_less)
{
    UT_Array<T>     temp;
    sortedUnion( other, temp, is_less );
    swap( temp );
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedUnion(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        ComparatorBool is_less) const
{
    // Can't store to either input.
    UT_ASSERT(&result != this && &result != &other);
    UT_ASSERT(result.size() == 0);

    std::set_union(
            begin(), end(), other.begin(), other.end(), AppendIterator(result),
            is_less);
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedIntersection(
        const UT_Array<T> &other,
        ComparatorBool is_less)
{
    UT_Array<T>     temp;
    sortedIntersection( other, temp, is_less );
    swap( temp );
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedIntersection(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        ComparatorBool is_less) const
{
    // Can't store to either input.
    UT_ASSERT(&result != this && &result != &other);
    UT_ASSERT(result.size() == 0);

    std::set_intersection(
            begin(), end(), other.begin(), other.end(), AppendIterator(result),
            is_less);
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedSetDifference(
        const UT_Array<T> &other,
        ComparatorBool is_less)
{
    UT_Array<T>     temp;
    sortedSetDifference(other, temp, is_less);
    swap( temp );
}

template <typename T>
template <typename ComparatorBool, typename>
inline void
UT_Array<T>::sortedSetDifference(
        const UT_Array<T> &other,
        UT_Array<T> &result,
        ComparatorBool is_less) const
{
    // Can't store to either input.
    UT_ASSERT(&result != this && &result != &other);
    UT_ASSERT(result.size() == 0);

    std::set_difference(
            begin(), end(), other.begin(), other.end(), AppendIterator(result),
            is_less);
}

template <typename T>
template <typename CompareEqual>
inline exint
UT_Array<T>::sortedRemoveDuplicatesIf(CompareEqual compare_equal)
{
    exint n = size();

    // Trivial, no duplicates!
    if (n < 2)
        return 0;

    exint dst = 1;
    for (exint i = 1; i < n; i++)
    {
        if (!compare_equal((*this)(i), (*this)(i-1)))
        {
            if (i != dst)
                (*this)(dst) = (*this)(i);
            dst++;
        }
    }

    // Store the number of remaining elements.
    setSize(dst);
    return n - dst;     // Return the number of elements removed
}

namespace {
    template<typename T>
    struct srdCompareEqual
    {
        bool operator()(const T& x, const T& y) const { return (x == y); }
    };
}

template <typename T>
inline exint
UT_Array<T>::sortedRemoveDuplicates()
{
    srdCompareEqual<T> cmp;
    return sortedRemoveDuplicatesIf(cmp);
}

template <typename T>
template <typename BinaryOp>
inline T
UT_Array<T>::accumulate(const T &init_value, BinaryOp add) const
{
    T sum(init_value);
    for (exint i = 0; i < mySize; i++)
        sum = add(sum, myData[i]);
    return sum;
}

#endif // __UT_ARRAYIMPL_H_INCLUDED__