Array.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "uLang/Common/Algo/Sort.h"
#include "uLang/Common/Algo/StableSort.h"
#include "uLang/Common/Memory/Allocator.h"
#include "uLang/Common/Memory/MemoryOps.h"
#include "uLang/Common/Misc/MathUtils.h"
#include "uLang/Common/Templates/Sorting.h"
 
namespace uLang
{
 
namespace Private
{
    template <typename FromArrayType, typename ToArrayType>
    struct TCanMoveTArrayPointersBetweenArrayTypes
    {
        using FromAllocatorType = typename FromArrayType::ElementAllocatorType;
        using ToAllocatorType = typename ToArrayType::ElementAllocatorType;
        using FromElementType = typename FromArrayType::ElementType;
        using ToElementType = typename ToArrayType::ElementType;
 
        enum
        {
            Value =
                TAreTypesEqual<FromAllocatorType, ToAllocatorType>::Value && // Allocators must be equal
                TContainerTraits<FromArrayType>::MoveWillEmptyContainer &&   // A move must be allowed to leave the source array empty
                (
                    TAreTypesEqual         <ToElementType, FromElementType>::Value || // The element type of the container must be the same, or...
                    TIsBitwiseConstructible<ToElementType, FromElementType>::Value    // ... the element type of the source container must be bitwise constructible from the element type in the destination container
                )
        };
    };
}
 
template<typename InElementType, typename InElementAllocatorType, typename... RawAllocatorArgsType>
class TArrayG
{
    template <typename OtherElementType, typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    friend class TArrayG;
 
public:
 
    using ElementType = InElementType;
    using ElementAllocatorType = InElementAllocatorType;
 
    ULANG_FORCEINLINE TArrayG(RawAllocatorArgsType&&... RawAllocatorArgs)
        : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
        , _ArrayNum(0)
        , _ArrayMax(0)
    {}
 
    ULANG_FORCEINLINE TArrayG(const typename ElementAllocatorType::RawAllocatorType & RawAllocator)
        : _ElementStorage(RawAllocator)
        , _ArrayNum(0)
        , _ArrayMax(0)
    {}
 
    ULANG_FORCEINLINE TArrayG(const ElementType* Ptr, int32_t Count, RawAllocatorArgsType&&... RawAllocatorArgs)
        : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
    {
        ULANG_ASSERTF(Ptr != nullptr || Count == 0, "Attempted to construct array from invalid source data.");
 
        CopyToEmpty(Ptr, Count, 0, 0);
    }
 
    ULANG_FORCEINLINE TArrayG(int32_t Count, const ElementType& Value = ElementType(), RawAllocatorArgsType&&... RawAllocatorArgs)
        : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
    {
        _ArrayNum = Count;
        ResizeForCopy(Count, 0);
        for (ElementType* I = GetData(), * Last = I + Count; I != Last; ++I)
        {
            new (I) ElementType(Value);
        }
    }
 
    TArrayG(std::initializer_list<InElementType> InitList, RawAllocatorArgsType&&... RawAllocatorArgs)
        : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
    {
        // This is not strictly legal, as std::initializer_list's iterators are not guaranteed to be pointers, but
        // this appears to be the case on all of our implementations.  Also, if it's not true on a new implementation,
        // it will fail to compile rather than behave badly.
        CopyToEmpty(InitList.begin(), (int32_t)InitList.size(), 0, 0);
    }
 
    template <typename OtherElementType>
    TArrayG(std::initializer_list<OtherElementType> InitList, RawAllocatorArgsType&&... RawAllocatorArgs) : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
    {
        CopyToEmpty(InitList.begin(), (int32_t) InitList.size(), 0, 0);
    }
 
    template <typename OtherElementType, typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    ULANG_FORCEINLINE explicit TArrayG(const TArrayG<OtherElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>& Other, RawAllocatorArgsType&&... RawAllocatorArgs)
        : _ElementStorage(ForwardArg<RawAllocatorArgsType>(RawAllocatorArgs)...)
    {
        CopyToEmpty(Other.GetData(), Other.Num(), 0, 0);
    }
 
    ULANG_FORCEINLINE TArrayG(const TArrayG& Other)
        : _ElementStorage(Other._ElementStorage.GetRawAllocator())
    {
        CopyToEmpty(Other.GetData(), Other.Num(), 0, 0);
    }
 
    ULANG_FORCEINLINE TArrayG(const TArrayG& Other, int32_t ExtraSlack)
        : _ElementStorage(Other._ElementStorage.GetRawAllocator())
    {
        CopyToEmpty(Other.GetData(), Other.Num(), 0, ExtraSlack);
    }
 
    TArrayG& operator=(const TArrayG& Other)
    {
        if (this != &Other)
        {
            ULANG_ASSERTF(_ElementStorage.GetRawAllocator() == Other._ElementStorage.GetRawAllocator(), "Currently, can only assign between arrays using the same allocator.");
            DestructElements(GetData(), _ArrayNum);
            CopyToEmpty(Other.GetData(), Other.Num(), _ArrayMax, 0);
        }
        return *this;
    }
 
private:
 
    template <typename FromArrayType, typename ToArrayType>
    static ULANG_FORCEINLINE typename TEnableIf<Private::TCanMoveTArrayPointersBetweenArrayTypes<FromArrayType, ToArrayType>::Value>::Type MoveOrCopy(ToArrayType& ToArray, FromArrayType& FromArray, int32_t PrevMax)
    {
        ToArray._ElementStorage.MoveToEmpty(FromArray._ElementStorage);
 
        ToArray  ._ArrayNum = FromArray._ArrayNum;
        ToArray  ._ArrayMax = FromArray._ArrayMax;
        FromArray._ArrayNum = 0;
        FromArray._ArrayMax = 0;
    }
 
    template <typename FromArrayType, typename ToArrayType>
    static ULANG_FORCEINLINE typename TEnableIf<!Private::TCanMoveTArrayPointersBetweenArrayTypes<FromArrayType, ToArrayType>::Value>::Type MoveOrCopy(ToArrayType& ToArray, FromArrayType& FromArray, int32_t PrevMax)
    {
        ToArray._ElementStorage.SetRawAllocator(FromArray._ElementStorage.GetRawAllocator());
        ToArray.CopyToEmpty(FromArray.GetData(), FromArray.Num(), PrevMax, 0);
    }
 
    template <typename FromArrayType, typename ToArrayType>
    static ULANG_FORCEINLINE typename TEnableIf<Private::TCanMoveTArrayPointersBetweenArrayTypes<FromArrayType, ToArrayType>::Value>::Type MoveOrCopyWithSlack(ToArrayType& ToArray, FromArrayType& FromArray, int32_t PrevMax, int32_t ExtraSlack)
    {
        MoveOrCopy(ToArray, FromArray, PrevMax);
 
        ToArray.Reserve(ToArray._ArrayNum + ExtraSlack);
    }
 
    template <typename FromArrayType, typename ToArrayType>
    static ULANG_FORCEINLINE typename TEnableIf<!Private::TCanMoveTArrayPointersBetweenArrayTypes<FromArrayType, ToArrayType>::Value>::Type MoveOrCopyWithSlack(ToArrayType& ToArray, FromArrayType& FromArray, int32_t PrevMax, int32_t ExtraSlack)
    {
        ToArray._ElementStorage.SetRawAllocator(FromArray._ElementStorage.GetRawAllocator());
        ToArray.CopyToEmpty(FromArray.GetData(), FromArray.Num(), PrevMax, ExtraSlack);
    }
 
public:
    ULANG_FORCEINLINE TArrayG(TArrayG && Other)
    {
        MoveOrCopy(*this, Other, 0);
    }
 
    TArrayG(TArrayG && Other, int32_t ExtraSlack)
    {
        // We don't implement move semantics for general OtherAllocators, as there's no way
        // to tell if they're compatible with the current one.  Probably going to be a pretty
        // rare requirement anyway.
 
        MoveOrCopyWithSlack(*this, Other, 0, ExtraSlack);
    }
 
    template <typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    ULANG_FORCEINLINE explicit TArrayG(TArrayG<ElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>&& Other)
    {
        MoveOrCopy(*this, Other, 0);
    }
 
    TArrayG& operator=(TArrayG && Other)
    {
        if (this != &Other)
        {
            DestructElements(GetData(), _ArrayNum);
            MoveOrCopy(*this, Other, _ArrayMax);
        }
        return *this;
    }
 
    ~TArrayG()
    {
        DestructElements(GetData(), _ArrayNum);
    }
 
    ULANG_FORCEINLINE ElementType* GetData()
    {
        return (ElementType*)_ElementStorage.GetAllocation();
    }
 
    ULANG_FORCEINLINE const ElementType* GetData() const
    {
        return (const ElementType*)_ElementStorage.GetAllocation();
    }
 
    ULANG_FORCEINLINE uint32_t GetTypeSize() const
    {
        return sizeof(ElementType);
    }
 
    ULANG_FORCEINLINE uint32_t GetAllocatedSize(void) const
    {
        return _ElementStorage.GetAllocatedSize(_ArrayMax, sizeof(ElementType));
    }
 
    ULANG_FORCEINLINE int32_t GetSlack() const
    {
        return _ArrayMax - _ArrayNum;
    }
 
    ULANG_FORCEINLINE void CheckInvariants() const
    {
        ULANG_ASSERTF((_ArrayNum >= 0) & (_ArrayMax >= _ArrayNum), "Bad array configuration detected."); // & for one branch
    }
 
    ULANG_FORCEINLINE void RangeCheck(int32_t Index) const
    {
        CheckInvariants();
 
        // Template property, branch will be optimized out
        if (ElementAllocatorType::RequireRangeCheck)
        {
            ULANG_ASSERTF((Index >= 0) & (Index < _ArrayNum), "Array index out of bounds: %i from an array of size %i", Index, _ArrayNum); // & for one branch
        }
    }
 
    ULANG_FORCEINLINE bool IsValidIndex(int32_t Index) const
    {
        return Index >= 0 && Index < _ArrayNum;
    }
 
    ULANG_FORCEINLINE int32_t Num() const
    {
        return _ArrayNum;
    }
 
    ULANG_FORCEINLINE int32_t Max() const
    {
        return _ArrayMax;
    }
 
    ULANG_FORCEINLINE const typename ElementAllocatorType::RawAllocatorType & GetRawAllocator() const
    {
        return _ElementStorage.GetRawAllocator();
    }
 
    ULANG_FORCEINLINE bool IsEmpty() const
    {
        return _ArrayNum == 0;
    }
 
    ULANG_FORCEINLINE bool IsFilled() const
    {
        return _ArrayNum != 0;
    }
 
    ULANG_FORCEINLINE ElementType& operator[](int32_t Index)
    {
        RangeCheck(Index);
        return GetData()[Index];
    }
 
    ULANG_FORCEINLINE const ElementType& operator[](int32_t Index) const
    {
        RangeCheck(Index);
        return GetData()[Index];
    }
 
    ULANG_FORCEINLINE ElementType Pop(bool bAllowShrinking = true)
    {
        RangeCheck(0);
        ElementType Result = uLang::MoveIfPossible(GetData()[_ArrayNum - 1]);
        RemoveAt(_ArrayNum - 1, 1, bAllowShrinking);
        return Result;
    }
 
    ULANG_FORCEINLINE void Push(ElementType&& Item)
    {
        Add(uLang::MoveIfPossible(Item));
    }
 
    ULANG_FORCEINLINE void Push(const ElementType& Item)
    {
        Add(Item);
    }
 
    ULANG_FORCEINLINE ElementType& Top()
    {
        return Last();
    }
 
    ULANG_FORCEINLINE const ElementType& Top() const
    {
        return Last();
    }
 
    ULANG_FORCEINLINE ElementType& Last(int32_t IndexFromTheEnd = 0)
    {
        RangeCheck(_ArrayNum - IndexFromTheEnd - 1);
        return GetData()[_ArrayNum - IndexFromTheEnd - 1];
    }
 
    ULANG_FORCEINLINE const ElementType& Last(int32_t IndexFromTheEnd = 0) const
    {
        RangeCheck(_ArrayNum - IndexFromTheEnd - 1);
        return GetData()[_ArrayNum - IndexFromTheEnd - 1];
    }
 
    ULANG_FORCEINLINE void Shrink()
    {
        CheckInvariants();
        if (_ArrayMax != _ArrayNum)
        {
            ResizeTo(_ArrayNum);
        }
    }
 
    ULANG_FORCEINLINE bool Find(const ElementType& Item, int32_t& Index) const
    {
        Index = this->Find(Item);
        return Index != IndexNone;
    }
 
    int32_t Find(const ElementType& Item) const
    {
        const ElementType* ULANG_RESTRICT Start = GetData();
        for (const ElementType* ULANG_RESTRICT Data = Start, *ULANG_RESTRICT DataEnd = Data + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (*Data == Item)
            {
                return static_cast<int32_t>(Data - Start);
            }
        }
        return IndexNone;
    }
 
    ULANG_FORCEINLINE bool FindLast(const ElementType& Item, int32_t& Index) const
    {
        Index = this->FindLast(Item);
        return Index != IndexNone;
    }
 
    int32_t FindLast(const ElementType& Item) const
    {
        for (const ElementType* ULANG_RESTRICT Start = GetData(), *ULANG_RESTRICT Data = Start + _ArrayNum; Data != Start; )
        {
            --Data;
            if (*Data == Item)
            {
                return static_cast<int32_t>(Data - Start);
            }
        }
        return IndexNone;
    }
 
    template <typename Predicate>
    int32_t FindLastByPredicate(Predicate Pred, int32_t Count) const
    {
        ULANG_ASSERTF(Count >= 0 && Count <= this->Num(), "Bad range specified.");
        for (const ElementType* ULANG_RESTRICT Start = GetData(), *ULANG_RESTRICT Data = Start + Count; Data != Start; )
        {
            --Data;
            if (Pred(*Data))
            {
                return static_cast<int32_t>(Data - Start);
            }
        }
        return IndexNone;
    }
 
    template <typename Predicate>
    ULANG_FORCEINLINE int32_t FindLastByPredicate(Predicate Pred) const
    {
        return FindLastByPredicate(Pred, _ArrayNum);
    }
 
    template <typename KeyType>
    int32_t IndexOfByKey(const KeyType& Key) const
    {
        const ElementType* ULANG_RESTRICT Start = GetData();
        for (const ElementType* ULANG_RESTRICT Data = Start, *ULANG_RESTRICT DataEnd = Start + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (*Data == Key)
            {
                return static_cast<int32_t>(Data - Start);
            }
        }
        return IndexNone;
    }
 
    template <typename Predicate>
    int32_t IndexOfByPredicate(Predicate Pred) const
    {
        const ElementType* ULANG_RESTRICT Start = GetData();
        for (const ElementType* ULANG_RESTRICT Data = Start, *ULANG_RESTRICT DataEnd = Start + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (Pred(*Data))
            {
                return static_cast<int32_t>(Data - Start);
            }
        }
        return IndexNone;
    }
 
    template <typename KeyType>
    ULANG_FORCEINLINE const ElementType* FindByKey(const KeyType& Key) const
    {
        return const_cast<TArrayG*>(this)->FindByKey(Key);
    }
 
    template <typename KeyType>
    ElementType* FindByKey(const KeyType& Key)
    {
        for (ElementType* ULANG_RESTRICT Data = GetData(), *ULANG_RESTRICT DataEnd = Data + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (*Data == Key)
            {
                return Data;
            }
        }
 
        return nullptr;
    }
 
    template <typename Predicate>
    ULANG_FORCEINLINE const ElementType* FindByPredicate(Predicate Pred) const
    {
        return const_cast<TArrayG*>(this)->FindByPredicate(Pred);
    }
 
    template <typename Predicate>
    ElementType* FindByPredicate(Predicate Pred)
    {
        for (ElementType* ULANG_RESTRICT Data = GetData(), *ULANG_RESTRICT DataEnd = Data + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (Pred(*Data))
            {
                return Data;
            }
        }
 
        return nullptr;
    }
 
    template <typename Predicate>
    TArrayG FilterByPredicate(Predicate Pred) const
    {
        TArrayG FilterResults;
        for (const ElementType* ULANG_RESTRICT Data = GetData(), *ULANG_RESTRICT DataEnd = Data + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (Pred(*Data))
            {
                FilterResults.Add(*Data);
            }
        }
        return FilterResults;
    }
 
    template <typename ComparisonType>
    bool Contains(const ComparisonType& Item) const
    {
        for (const ElementType* ULANG_RESTRICT Data = GetData(), *ULANG_RESTRICT DataEnd = Data + _ArrayNum; Data != DataEnd; ++Data)
        {
            if (*Data == Item)
            {
                return true;
            }
        }
        return false;
    }
 
    template <typename Predicate>
    ULANG_FORCEINLINE bool ContainsByPredicate(Predicate Pred) const
    {
        return FindByPredicate(Pred) != nullptr;
    }
 
    bool operator==(const TArrayG& OtherArray) const
    {
        int32_t Count = Num();
 
        return Count == OtherArray.Num() && CompareElements(GetData(), OtherArray.GetData(), Count);
    }
 
    ULANG_FORCEINLINE bool operator!=(const TArrayG& OtherArray) const
    {
        return !(*this == OtherArray);
    }
 
    ULANG_FORCEINLINE int32_t AddUninitialized(int32_t Count = 1)
    {
        CheckInvariants();
        ULANG_ASSERTF(Count >= 0, "Number of elements to add to array must not be negative.");
 
        const int32_t OldNum = _ArrayNum;
        if ((_ArrayNum += Count) > _ArrayMax)
        {
            ResizeGrow(OldNum);
        }
        return OldNum;
    }
 
    void InsertUninitialized(int32_t Index, int32_t Count = 1)
    {
        CheckInvariants();
        ULANG_ASSERTF((Count >= 0) & (Index >= 0) & (Index <= _ArrayNum), "Cannot insert elements into array due to invalid parameters.");
 
        const int32_t OldNum = _ArrayNum;
        if ((_ArrayNum += Count) > _ArrayMax)
        {
            ResizeGrow(OldNum);
        }
        ElementType* Data = GetData() + Index;
        RelocateConstructElements<ElementType>(Data + Count, Data, OldNum - Index);
    }
 
    void InsertZeroed(int32_t Index, int32_t Count = 1)
    {
        InsertUninitialized(Index, Count);
        if (Count)
        {
            memset(GetData() + Index, 0, Count * sizeof(ElementType));
        }
    }
 
    ElementType& InsertZeroed_GetRef(int32_t Index)
    {
        InsertUninitialized(Index, 1);
        ElementType* Ptr = GetData() + Index;
        memset(Ptr, 0, sizeof(ElementType));
        return *Ptr;
    }
 
    void InsertDefaulted(int32_t Index, int32_t Count = 1)
    {
        InsertUninitialized(Index, Count);
        DefaultConstructElements<ElementType>(GetData() + Index, Count);
    }
 
    ElementType& InsertDefaulted_GetRef(int32_t Index)
    {
        InsertUninitialized(Index, 1);
        ElementType* Ptr = GetData() + Index;
        DefaultConstructElements<ElementType>(Ptr, 1);
        return *Ptr;
    }
 
    int32_t Insert(std::initializer_list<ElementType> InitList, const int32_t InIndex)
    {
        int32_t NumNewElements = (int32_t)InitList.size();
 
        InsertUninitialized(InIndex, NumNewElements);
        ConstructElements<ElementType>(GetData() + InIndex, InitList.begin(), NumNewElements);
 
        return InIndex;
    }
 
    template <typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    int32_t Insert(const TArrayG<ElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>& Items, const int32_t InIndex)
    {
        ULANG_ASSERTF((const void*)this != (const void*)&Items, "Attempted to insert array into itself.");
 
        int32_t NumNewElements = Items.Num();
 
        InsertUninitialized(InIndex, NumNewElements);
        ConstructElements<ElementType>(GetData() + InIndex, Items.GetData(), NumNewElements);
 
        return InIndex;
    }
 
    template <typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    int32_t Insert(TArrayG<ElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>&& Items, const int32_t InIndex)
    {
        ULANG_ASSERTF((const void*)this != (const void*)&Items, "Attempted to insert array into itself.");
 
        int32_t NumNewElements = Items.Num();
 
        InsertUninitialized(InIndex, NumNewElements);
        RelocateConstructElements<ElementType>(GetData() + InIndex, Items.GetData(), NumNewElements);
        Items._ArrayNum = 0;
 
        return InIndex;
    }
 
    int32_t Insert(const ElementType* Ptr, int32_t Count, int32_t Index)
    {
        ULANG_ASSERTF(Ptr != nullptr, "Elements to insert must not be null.");
 
        InsertUninitialized(Index, Count);
        ConstructElements<ElementType>(GetData() + Index, Ptr, Count);
 
        return Index;
    }
 
    ULANG_FORCEINLINE void CheckAddress(void const* Addr) const
    {
        ULANG_ASSERTF(Addr < GetData() || Addr >= (GetData() + _ArrayMax), "Attempting to use a container element (%p) which already comes from the container being modified (%p, ArrayMax: %d, ArrayNum: %d, SizeofElement: %d)!", Addr, GetData(), _ArrayMax, _ArrayNum, sizeof(ElementType));
    }
 
    int32_t Insert(ElementType&& Item, int32_t Index)
    {
        CheckAddress(&Item);
 
        // construct a copy in place at Index (this new operator will insert at
        // Index, then construct that memory with Item)
        InsertUninitialized(Index, 1);
        new(GetData() + Index) ElementType(uLang::MoveIfPossible(Item));
        return Index;
    }
 
    int32_t Insert(const ElementType& Item, int32_t Index)
    {
        CheckAddress(&Item);
 
        // construct a copy in place at Index (this new operator will insert at
        // Index, then construct that memory with Item)
        InsertUninitialized(Index, 1);
        new(GetData() + Index) ElementType(Item);
        return Index;
    }
 
    ElementType& Insert_GetRef(ElementType&& Item, int32_t Index)
    {
        CheckAddress(&Item);
 
        // construct a copy in place at Index (this new operator will insert at
        // Index, then construct that memory with Item)
        InsertUninitialized(Index, 1);
        ElementType* Ptr = GetData() + Index;
        new(Ptr) ElementType(uLang::MoveIfPossible(Item));
        return *Ptr;
    }
 
    ElementType& Insert_GetRef(const ElementType& Item, int32_t Index)
    {
        CheckAddress(&Item);
 
        // construct a copy in place at Index (this new operator will insert at
        // Index, then construct that memory with Item)
        InsertUninitialized(Index, 1);
        ElementType* Ptr = GetData() + Index;
        new(Ptr) ElementType(Item);
        return *Ptr;
    }
 
private:
    void RemoveAtImpl(int32_t Index, int32_t Count, bool bAllowShrinking)
    {
        if (Count)
        {
            CheckInvariants();
            ULANG_ASSERTF((Count >= 0) & (Index >= 0) & (Index + Count <= _ArrayNum), "Cannot remove elements from array due to invalid parameters.");
 
            DestructElements(GetData() + Index, Count);
 
            // Skip memmove in the common case that there is nothing to move.
            int32_t NumToMove = _ArrayNum - Index - Count;
            if (NumToMove)
            {
                memmove
                    (
                    (uint8_t*)_ElementStorage.GetAllocation() + (Index)* sizeof(ElementType),
                    (uint8_t*)_ElementStorage.GetAllocation() + (Index + Count) * sizeof(ElementType),
                    NumToMove * sizeof(ElementType)
                    );
            }
            _ArrayNum -= Count;
 
            if (bAllowShrinking)
            {
                ResizeShrink();
            }
        }
    }
 
public:
    ULANG_FORCEINLINE void RemoveAt(int32_t Index)
    {
        RemoveAtImpl(Index, 1, true);
    }
 
    template <typename CountType>
    ULANG_FORCEINLINE void RemoveAt(int32_t Index, CountType Count, bool bAllowShrinking = true)
    {
        static_assert(!TAreTypesEqual<CountType, bool>::Value, "TArrayG::RemoveAt: unexpected bool passed as the Count argument");
        RemoveAtImpl(Index, Count, bAllowShrinking);
    }
 
private:
    void RemoveAtSwapImpl(int32_t Index, int32_t Count = 1, bool bAllowShrinking = true)
    {
        if (Count)
        {
            CheckInvariants();
            ULANG_ASSERTF((Count >= 0) & (Index >= 0) & (Index + Count <= _ArrayNum), "Cannot remove elements from array due to invalid parameters.");
 
            DestructElements(GetData() + Index, Count);
 
            // Replace the elements in the hole created by the removal with elements from the end of the array, so the range of indices used by the array is contiguous.
            const int32_t NumElementsInHole = Count;
            const int32_t NumElementsAfterHole = _ArrayNum - (Index + Count);
            const int32_t NumElementsToMoveIntoHole = CMath::Min(NumElementsInHole, NumElementsAfterHole);
            if (NumElementsToMoveIntoHole)
            {
                memcpy(
                    (uint8_t*)_ElementStorage.GetAllocation() + (Index)* sizeof(ElementType),
                    (uint8_t*)_ElementStorage.GetAllocation() + (_ArrayNum - NumElementsToMoveIntoHole) * sizeof(ElementType),
                    NumElementsToMoveIntoHole * sizeof(ElementType)
                    );
            }
            _ArrayNum -= Count;
 
            if (bAllowShrinking)
            {
                ResizeShrink();
            }
        }
    }
 
public:
    ULANG_FORCEINLINE void RemoveAtSwap(int32_t Index)
    {
        RemoveAtSwapImpl(Index, 1, true);
    }
 
    template <typename CountType>
    ULANG_FORCEINLINE void RemoveAtSwap(int32_t Index, CountType Count, bool bAllowShrinking = true)
    {
        static_assert(!TAreTypesEqual<CountType, bool>::Value, "TArrayG::RemoveAtSwap: unexpected bool passed as the Count argument");
        RemoveAtSwapImpl(Index, Count, bAllowShrinking);
    }
 
    int32_t Replace(const ElementType& OldItem, const ElementType& NewItem)
    {
        int32_t Index = Find(OldItem);
 
        if (Index != IndexNone)
        {
            CheckAddress(&NewItem);
            GetData()[Index] = NewItem;
        }
 
        return Index;
    }
 
    void Reset(int32_t NewSize = 0)
    {
        // If we have space to hold the excepted size, then don't reallocate
        if (NewSize <= _ArrayMax)
        {
            DestructElements(GetData(), _ArrayNum);
            _ArrayNum = 0;
        }
        else
        {
            Empty(NewSize);
        }
    }
 
    void Empty(int32_t Slack = 0)
    {
        DestructElements(GetData(), _ArrayNum);
 
        ULANG_ASSERTF(Slack >= 0, "Array slack must be positive.");
        _ArrayNum = 0;
 
        if (_ArrayMax != Slack)
        {
            ResizeTo(Slack);
        }
    }
 
    void SetNum(int32_t NewNum, bool bAllowShrinking = true)
    {
        if (NewNum > Num())
        {
            const int32_t Diff = NewNum - _ArrayNum;
            const int32_t Index = AddUninitialized(Diff);
            DefaultConstructElements<ElementType>((uint8_t*)_ElementStorage.GetAllocation() + Index * sizeof(ElementType), Diff);
        }
        else if (NewNum < Num())
        {
            RemoveAt(NewNum, Num() - NewNum, bAllowShrinking);
        }
    }
 
    void SetNumZeroed(int32_t NewNum, bool bAllowShrinking = true)
    {
        if (NewNum > Num())
        {
            AddZeroed(NewNum - Num());
        }
        else if (NewNum < Num())
        {
            RemoveAt(NewNum, Num() - NewNum, bAllowShrinking);
        }
    }
 
    void SetNumUninitialized(int32_t NewNum, bool bAllowShrinking = true)
    {
        if (NewNum > Num())
        {
            AddUninitialized(NewNum - Num());
        }
        else if (NewNum < Num())
        {
            RemoveAt(NewNum, Num() - NewNum, bAllowShrinking);
        }
    }
 
    void SetNumUnsafeInternal(int32_t NewNum)
    {
        ULANG_ASSERTF(NewNum <= Num() && NewNum >= 0, "Incorrect new array size.");
        _ArrayNum = NewNum;
    }
 
    template <typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    void Append(const TArrayG<ElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>& Source)
    {
        ULANG_ASSERTF((void*)this != (void*)&Source, "Attempted to append array to itself.");
 
        int32_t SourceCount = Source.Num();
 
        // Do nothing if the source is empty.
        if (!SourceCount)
        {
            return;
        }
 
        // Allocate memory for the new elements.
        Reserve(_ArrayNum + SourceCount);
        ConstructElements<ElementType>(GetData() + _ArrayNum, Source.GetData(), SourceCount);
 
        _ArrayNum += SourceCount;
    }
 
    template <typename OtherElementAllocatorType, typename... OtherRawAllocatorArgsType>
    void Append(TArrayG<ElementType, OtherElementAllocatorType, OtherRawAllocatorArgsType...>&& Source)
    {
        ULANG_ASSERTF((void*)this != (void*)&Source, "Attempted to append array to itself.");
 
        int32_t SourceCount = Source.Num();
 
        // Do nothing if the source is empty.
        if (!SourceCount)
        {
            return;
        }
 
        // Allocate memory for the new elements.
        Reserve(_ArrayNum + SourceCount);
        RelocateConstructElements<ElementType>(GetData() + _ArrayNum, Source.GetData(), SourceCount);
        Source._ArrayNum = 0;
 
        _ArrayNum += SourceCount;
    }
 
    void Append(const ElementType* Ptr, int32_t Count)
    {
        ULANG_ASSERTF(Ptr != nullptr || Count == 0, "Attempted to append invalid array.");
 
        int32_t Pos = AddUninitialized(Count);
        ConstructElements<ElementType>(GetData() + Pos, Ptr, Count);
    }
 
    ULANG_FORCEINLINE void Append(std::initializer_list<ElementType> InitList)
    {
        int32_t Count = (int32_t)InitList.size();
 
        int32_t Pos = AddUninitialized(Count);
        ConstructElements<ElementType>(GetData() + Pos, InitList.begin(), Count);
    }
 
    TArrayG& operator+=(TArrayG&& Other)
    {
        Append(Move(Other));
        return *this;
    }
 
    TArrayG& operator+=(const TArrayG& Other)
    {
        Append(Other);
        return *this;
    }
 
    TArrayG& operator+=(std::initializer_list<ElementType> InitList)
    {
        Append(InitList);
        return *this;
    }
 
    template <typename... ArgsType>
    ULANG_FORCEINLINE int32_t Emplace(ArgsType&&... Args)
    {
        const int32_t Index = AddUninitialized(1);
        new(GetData() + Index) ElementType(ForwardArg<ArgsType>(Args)...);
        return Index;
    }
 
    template <typename... ArgsType>
    ULANG_FORCEINLINE ElementType& Emplace_GetRef(ArgsType&&... Args)
    {
        const int32_t Index = AddUninitialized(1);
        ElementType* Ptr = GetData() + Index;
        new(Ptr) ElementType(ForwardArg<ArgsType>(Args)...);
        return *Ptr;
    }
 
    template <typename... ArgsType>
    ULANG_FORCEINLINE void EmplaceAt(int32_t Index, ArgsType&&... Args)
    {
        InsertUninitialized(Index, 1);
        new(GetData() + Index) ElementType(ForwardArg<ArgsType>(Args)...);
    }
 
    template <typename... ArgsType>
    ULANG_FORCEINLINE ElementType& EmplaceAt_GetRef(int32_t Index, ArgsType&&... Args)
    {
        InsertUninitialized(Index, 1);
        ElementType* Ptr = GetData() + Index;
        new(Ptr) ElementType(ForwardArg<ArgsType>(Args)...);
        return *Ptr;
    }
 
    ULANG_FORCEINLINE int32_t Add(ElementType&& Item)
    {
        CheckAddress(&Item);
        return Emplace(uLang::MoveIfPossible(Item));
    }
 
    ULANG_FORCEINLINE int32_t Add(const ElementType& Item)
    {
        CheckAddress(&Item);
        return Emplace(Item);
    }
 
    ULANG_FORCEINLINE ElementType& Add_GetRef(ElementType&& Item)
    {
        CheckAddress(&Item);
        return Emplace_GetRef(uLang::MoveIfPossible(Item));
    }
 
    ULANG_FORCEINLINE ElementType& Add_GetRef(const ElementType& Item)
    {
        CheckAddress(&Item);
        return Emplace_GetRef(Item);
    }
 
    int32_t AddZeroed(int32_t Count = 1)
    {
        const int32_t Index = AddUninitialized(Count);
        if (Count)
        {
            memset((uint8_t*)_ElementStorage.GetAllocation() + Index*sizeof(ElementType), 0, Count*sizeof(ElementType));
        }
        return Index;
    }
 
    ElementType& AddZeroed_GetRef()
    {
        const int32_t Index = AddUninitialized(1);
        ElementType* Ptr = GetData() + Index;
        memset(Ptr, 0, sizeof(ElementType));
        return *Ptr;
    }
 
    int32_t AddDefaulted(int32_t Count = 1)
    {
        const int32_t Index = AddUninitialized(Count);
        DefaultConstructElements<ElementType>((uint8_t*)_ElementStorage.GetAllocation() + Index * sizeof(ElementType), Count);
        return Index;
    }
 
    ElementType& AddDefaulted_GetRef()
    {
        const int32_t Index = AddUninitialized(1);
        ElementType* Ptr = GetData() + Index;
        DefaultConstructElements<ElementType>(Ptr, 1);
        return *Ptr;
    }
 
private:
 
    template <typename ArgsType>
    int32_t AddUniqueImpl(ArgsType&& Args)
    {
        int32_t Index;
        if (Find(Args, Index))
        {
            return Index;
        }
 
        return Add(ForwardArg<ArgsType>(Args));
    }
 
public:
 
    ULANG_FORCEINLINE int32_t AddUnique(ElementType&& Item) { return AddUniqueImpl(uLang::MoveIfPossible(Item)); }
 
    ULANG_FORCEINLINE int32_t AddUnique(const ElementType& Item) { return AddUniqueImpl(Item); }
 
    ULANG_FORCEINLINE void Reserve(int32_t Number)
    {
        if (Number > _ArrayMax)
        {
            ResizeTo(Number);
        }
    }
 
    void Init(const ElementType& Element, int32_t Number)
    {
        Empty(Number);
        for (int32_t Index = 0; Index < Number; ++Index)
        {
            new(*this) ElementType(Element);
        }
    }
 
    int32_t RemoveSingle(const ElementType& Item)
    {
        int32_t Index = Find(Item);
        if (Index == IndexNone)
        {
            return 0;
        }
 
        auto* RemovePtr = GetData() + Index;
 
        // Destruct items that match the specified Item.
        DestructElements(RemovePtr, 1);
        RelocateConstructElements<ElementType>(RemovePtr, RemovePtr + 1, _ArrayNum - (Index + 1));
 
        // Update the array count
        --_ArrayNum;
 
        // Removed one item
        return 1;
    }
 
    template <typename OtherElementType>
    int32_t Remove(const OtherElementType& Item)
    {
        CheckAddress(&Item);
 
        // Element is non-const to preserve compatibility with existing code with a non-const operator==() member function
        return RemoveAll([&Item](ElementType& Element) { return Element == Item; });
    }
 
    template <class PREDICATE_CLASS>
    int32_t RemoveAll(const PREDICATE_CLASS& Predicate)
    {
        const int32_t OriginalNum = _ArrayNum;
        if (!OriginalNum)
        {
            return 0; // nothing to do, loop assumes one item so need to deal with this edge case here
        }
 
        int32_t WriteIndex = 0;
        int32_t ReadIndex = 0;
        bool NotMatch = !Predicate(GetData()[ReadIndex]); // use a ! to guarantee it can't be anything other than zero or one
        do
        {
            int32_t RunStartIndex = ReadIndex++;
            while (ReadIndex < OriginalNum && NotMatch == !Predicate(GetData()[ReadIndex]))
            {
                ReadIndex++;
            }
            int32_t RunLength = ReadIndex - RunStartIndex;
            ULANG_ASSERTF(RunLength > 0, "RunLength must be positive here.");
            if (NotMatch)
            {
                // this was a non-matching run, we need to move it
                if (WriteIndex != RunStartIndex)
                {
                    RelocateConstructElements<ElementType>(&GetData()[WriteIndex], &GetData()[RunStartIndex], RunLength);
                }
                WriteIndex += RunLength;
            }
            else
            {
                // this was a matching run, delete it
                DestructElements(GetData() + RunStartIndex, RunLength);
            }
            NotMatch = !NotMatch;
        } while (ReadIndex < OriginalNum);
 
        _ArrayNum = WriteIndex;
        return OriginalNum - _ArrayNum;
    }
 
    template <class PREDICATE_CLASS>
    void RemoveAllSwap(const PREDICATE_CLASS& Predicate, bool bAllowShrinking = true)
    {
        for (int32_t ItemIndex = 0; ItemIndex < Num();)
        {
            if (Predicate((*this)[ItemIndex]))
            {
                RemoveAtSwap(ItemIndex, 1, bAllowShrinking);
            }
            else
            {
                ++ItemIndex;
            }
        }
    }
 
    int32_t RemoveSingleSwap(const ElementType& Item, bool bAllowShrinking = true)
    {
        int32_t Index = Find(Item);
        if (Index == IndexNone)
        {
            return 0;
        }
 
        RemoveAtSwap(Index, 1, bAllowShrinking);
 
        // Removed one item
        return 1;
    }
 
    int32_t RemoveSwap(const ElementType& Item)
    {
        CheckAddress(&Item);
 
        const int32_t OriginalNum = _ArrayNum;
        for (int32_t Index = 0; Index < _ArrayNum; Index++)
        {
            if ((*this)[Index] == Item)
            {
                RemoveAtSwap(Index--);
            }
        }
        return OriginalNum - _ArrayNum;
    }
 
public:
 
    ULANG_FORCEINLINE ElementType *       begin()       { return GetData(); }
    ULANG_FORCEINLINE const ElementType * begin() const { return GetData(); }
    ULANG_FORCEINLINE ElementType *       end()         { return GetData() + Num(); }
    ULANG_FORCEINLINE const ElementType * end() const   { return GetData() + Num(); }
 
public:
 
    void Sort()
    {
        Algo::Sort( *this, TDereferenceWrapper<TLess<ElementType>>( TLess<ElementType>() ) );
    }
 
    template <class PredicateType>
    void Sort(const PredicateType& Predicate)
    {
        Algo::Sort( *this, TDereferenceWrapper<PredicateType>( Predicate ) );
    }
 
    template <class PredicateType>
    void StableSort(const PredicateType& Predicate)
    {
        Algo::StableSort(*this, TDereferenceWrapper<PredicateType>( Predicate ) );
    }
 
    void RemoveSuccessiveDuplicates()
    {
        ElementType* LastEntry = nullptr;
        int32_t ToIndex = 0;
        int32_t FromIndex = 0;
        while (FromIndex < Num())
        {
            ElementType ThisEntry = Move((*this)[FromIndex++]);
            if (!LastEntry || !(*LastEntry == ThisEntry))
            {
                LastEntry = &(*this)[ToIndex];
                (*this)[ToIndex++] = Move(ThisEntry);
            }
        }
        RemoveAt(ToIndex, Num() - ToIndex);
    }
 
private:
 
    ULANG_FORCENOINLINE void ResizeGrow(int32_t OldNum)
    {
        _ArrayMax = _ElementStorage.CalculateSlackGrow(_ArrayNum, _ArrayMax, sizeof(ElementType));
        _ElementStorage.ResizeAllocation(OldNum, _ArrayMax, sizeof(ElementType));
    }
    ULANG_FORCENOINLINE void ResizeShrink()
    {
        const int32_t NewArrayMax = _ElementStorage.CalculateSlackShrink(_ArrayNum, _ArrayMax, sizeof(ElementType));
        if (NewArrayMax != _ArrayMax)
        {
            _ArrayMax = NewArrayMax;
            ULANG_ASSERTF(_ArrayMax >= _ArrayNum, "Attempted to shrink array to less than its count.");
            _ElementStorage.ResizeAllocation(_ArrayNum, _ArrayMax, sizeof(ElementType));
        }
    }
    ULANG_FORCENOINLINE void ResizeTo(int32_t NewMax)
    {
        if (NewMax)
        {
            NewMax = _ElementStorage.CalculateSlackReserve(NewMax, sizeof(ElementType));
        }
        if (NewMax != _ArrayMax)
        {
            _ArrayMax = NewMax;
            _ElementStorage.ResizeAllocation(_ArrayNum, _ArrayMax, sizeof(ElementType));
        }
    }
    ULANG_FORCENOINLINE void ResizeForCopy(int32_t NewMax, int32_t PrevMax)
    {
        if (NewMax)
        {
            NewMax = _ElementStorage.CalculateSlackReserve(NewMax, sizeof(ElementType));
        }
        if (NewMax != PrevMax)
        {
            _ElementStorage.ResizeAllocation(0, NewMax, sizeof(ElementType));
        }
        _ArrayMax = NewMax;
    }
 
 
    template <typename OtherElementType>
    void CopyToEmpty(const OtherElementType* OtherData, int32_t OtherNum, int32_t PrevMax, int32_t ExtraSlack)
    {
        ULANG_ASSERTF(ExtraSlack >= 0, "Array slack must be positive.");
        _ArrayNum = OtherNum;
        if (OtherNum || ExtraSlack || PrevMax)
        {
            ResizeForCopy(OtherNum + ExtraSlack, PrevMax);
            ConstructElements<ElementType>(GetData(), OtherData, OtherNum);
        }
        else
        {
            _ArrayMax = 0;
        }
    }
 
protected:
 
    using ElementStorageType = typename TChooseClass<
        ElementAllocatorType::NeedsElementType,
        typename ElementAllocatorType::template ForElementType<ElementType>,
        typename ElementAllocatorType::ForAnyElementType
        >::Result;
 
    ElementStorageType _ElementStorage;
    int32_t            _ArrayNum;
    int32_t            _ArrayMax;
 
};
 
template<class ElementType>
using TArray = TArrayG<ElementType, TDefaultElementAllocator<CHeapRawAllocator>>;
 
template<class ElementType>
using TArrayA = TArrayG<ElementType, TDefaultElementAllocator<CInstancedRawAllocator>, CAllocatorInstance *>;
 
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType>
struct TIsZeroConstructType<TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>>
{
    enum { Value = TAllocatorTraits<ElementAllocatorType>::IsZeroConstruct };
};
 
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType>
struct TContainerTraits<TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>> : public TContainerTraitsBase<TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>>
{
    static_assert(TAllocatorTraits<ElementAllocatorType>::SupportsMove, "TArrayG no longer supports move-unaware allocators");
    enum { MoveWillEmptyContainer = TAllocatorTraits<ElementAllocatorType>::SupportsMove };
};
 
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType>
struct TIsContiguousContainer<TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>>
{
    enum { Value = true };
};
 
 
template <typename T> struct TIsTArray { enum { Value = false }; };
 
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType> struct TIsTArray<               TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>> { enum { Value = true }; };
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType> struct TIsTArray<const          TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>> { enum { Value = true }; };
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType> struct TIsTArray<      volatile TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>> { enum { Value = true }; };
template <typename ElementType, typename ElementAllocatorType, typename... RawAllocatorArgsType> struct TIsTArray<const volatile TArrayG<ElementType, ElementAllocatorType, RawAllocatorArgsType...>> { enum { Value = true }; };
 
template <typename T>
ULANG_FORCEINLINE uint32_t GetTypeHash(const TArray<T> Array)
{
    uint32_t Result = 0;
    for (const T& Element : Array)
    {
        Result = HashCombineFast(Result, GetTypeHash(Element));
    }
    return Result;
}
}