MovieSceneEvaluationTree.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Array.h"
#include "Containers/ArrayView.h"
#include "Math/Range.h"
#include "Math/RangeBound.h"
#include "Math/UnrealMathSSE.h"
#include "Misc/AssertionMacros.h"
#include "Misc/FrameNumber.h"
#include "Serialization/Archive.h"
#include "Templates/Function.h"
#include "Templates/MemoryOps.h"
#include "Templates/UnrealTemplate.h"
#include "UObject/SequencerObjectVersion.h"
 
struct FMovieSceneEvaluationTree;
struct FMovieSceneEvaluationTreeNode;
struct FMovieSceneEvaluationTreeRangeIterator;
template<typename DataType> struct TMovieSceneEvaluationTreeDataIterator;
template<typename DataType> struct TMovieSceneEvaluationTreeFormatter;
 
struct FEvaluationTreeEntryHandle
{
    FEvaluationTreeEntryHandle()
        : EntryIndex(INDEX_NONE)
    {}
 
    bool IsValid() const
    {
        return EntryIndex != INDEX_NONE;
    }
 
    friend bool operator==(const FEvaluationTreeEntryHandle& A, const FEvaluationTreeEntryHandle& B) { return A.EntryIndex == B.EntryIndex; }
 
    friend bool operator!=(const FEvaluationTreeEntryHandle& A, const FEvaluationTreeEntryHandle& B) { return A.EntryIndex != B.EntryIndex; }
 
    friend FArchive& operator<<(FArchive& Ar, FEvaluationTreeEntryHandle& In) { return Ar << In.EntryIndex; }
 
private:
    template<typename T> friend struct TEvaluationTreeEntryContainer;
    template<typename T> friend struct TMovieSceneEvaluationTreeFormatter;
    FEvaluationTreeEntryHandle(int32 InEntryIndex) : EntryIndex(InEntryIndex) {}
 
    int32 EntryIndex;
};
 
template<typename ElementType>
struct TEvaluationTreeEntryContainer
{
    FEvaluationTreeEntryHandle AllocateEntry(int32 InitialCapacity = 2);
 
    TArrayView<ElementType> Get(FEvaluationTreeEntryHandle ID);
 
    TArrayView<const ElementType> Get(FEvaluationTreeEntryHandle ID) const;
 
    void Add(FEvaluationTreeEntryHandle ID, ElementType&& Element);
 
    void Insert(FEvaluationTreeEntryHandle ID, int32 Index, ElementType&& Element);
 
    void Compact();
 
 
    void Reset()
    {
        Entries.Reset();
        Items.Reset();
    }
 
    friend FArchive& operator<<(FArchive& Ar, TEvaluationTreeEntryContainer& In)
    {
        if (Ar.IsSaving())
        {
            In.Compact();
        }
 
        Ar.UsingCustomVersion(FSequencerObjectVersion::GUID);
        return Ar << In.Entries << In.Items;
    }
 
    friend bool operator==(const TEvaluationTreeEntryContainer<ElementType>& A, const TEvaluationTreeEntryContainer<ElementType>& B)
    {
        return A.Entries == B.Entries && A.Items == B.Items;
    }
 
private:
 
    void ReserveEntry(FEvaluationTreeEntryHandle ID, int32 NewCapacity);
 
    struct FEntry
    {
        int32 StartIndex;
        int32 Size;
        int32 Capacity;
 
        friend FArchive& operator<<(FArchive& Ar, FEntry& In)
        {
            Ar << In.StartIndex << In.Size << In.Capacity;
            return Ar;
        }
 
        friend bool operator==(const FEntry& A, const FEntry& B)
        {
            return A.StartIndex == B.StartIndex && A.Size == B.Size && A.Capacity == B.Capacity;
        }
    };
 
    TArray<FEntry> Entries;
    TArray<ElementType> Items;
};
 
struct IMovieSceneEvaluationTreeNodeOperator
{
    virtual ~IMovieSceneEvaluationTreeNodeOperator() {}
 
    virtual void operator()(FMovieSceneEvaluationTreeNode& Node) const = 0;
};
 
struct FMovieSceneEvaluationTreeNodeHandle
{
    FMovieSceneEvaluationTreeNodeHandle(FEvaluationTreeEntryHandle InChildrenHandle, int32 InIndex)
        : ChildrenHandle(InChildrenHandle), Index(InIndex)
    {}
 
    static FMovieSceneEvaluationTreeNodeHandle Root()
    {
        return FMovieSceneEvaluationTreeNodeHandle(FEvaluationTreeEntryHandle(), 0);
    }
 
    static FMovieSceneEvaluationTreeNodeHandle Invalid()
    {
        return FMovieSceneEvaluationTreeNodeHandle(FEvaluationTreeEntryHandle(), INDEX_NONE);
    }
 
    bool IsRoot() const
    {
        return *this == Root();
    }
 
    bool IsValid() const
    {
        return ChildrenHandle.IsValid() || Index == 0;
    }
 
    FEvaluationTreeEntryHandle GetHandle() const
    {
        return ChildrenHandle;
    }
 
    int32 GetChildIndex() const
    {
        return Index;
    }
 
private:
 
    friend bool operator==(const FMovieSceneEvaluationTreeNodeHandle& A, const FMovieSceneEvaluationTreeNodeHandle& B) { return A.ChildrenHandle == B.ChildrenHandle && A.Index == B.Index; }
    friend bool operator!=(const FMovieSceneEvaluationTreeNodeHandle& A, const FMovieSceneEvaluationTreeNodeHandle& B) { return A.ChildrenHandle != B.ChildrenHandle || A.Index != B.Index; }
    friend FArchive& operator<<(FArchive& Ar, FMovieSceneEvaluationTreeNodeHandle& In) { return Ar << In.ChildrenHandle << In.Index; }
 
    FEvaluationTreeEntryHandle ChildrenHandle;
    int32 Index;
};
 
struct FMovieSceneEvaluationTreeNode
{
    FMovieSceneEvaluationTreeNode()
        : Range(TRange<FFrameNumber>::Empty())
        , Parent(FMovieSceneEvaluationTreeNodeHandle::Invalid())
    {}
 
    FMovieSceneEvaluationTreeNode(TRange<FFrameNumber> InRange, FMovieSceneEvaluationTreeNodeHandle InParent)
        : Range(InRange)
        , Parent(InParent)
    {}
 
    friend FArchive& operator<<(FArchive& Ar, FMovieSceneEvaluationTreeNode& In)
    {
        return Ar << In.Range << In.Parent << In.ChildrenID << In.DataID;
    }
 
    friend bool operator==(const FMovieSceneEvaluationTreeNode& A, const FMovieSceneEvaluationTreeNode& B)
    {
        return A.Range == B.Range && A.Parent == B.Parent && A.ChildrenID == B.ChildrenID && A.DataID == B.DataID;
    }
 
    TRange<FFrameNumber> Range;
    FMovieSceneEvaluationTreeNodeHandle Parent;
    FEvaluationTreeEntryHandle ChildrenID;
    FEvaluationTreeEntryHandle DataID;
};
 
struct FMovieSceneEvaluationTree
{
    FMovieSceneEvaluationTree()
        : RootNode(FMovieSceneEvaluationTreeNode(TRange<FFrameNumber>::All(), FMovieSceneEvaluationTreeNodeHandle::Invalid()))
    {}
 
    FMovieSceneEvaluationTree(const FMovieSceneEvaluationTree& RHS) = default;
 
    FMovieSceneEvaluationTree& operator=(const FMovieSceneEvaluationTree& RHS) = default;
 
    FMovieSceneEvaluationTree(FMovieSceneEvaluationTree&& RHS)
        : RootNode(RHS.RootNode)
        , ChildNodes(MoveTemp(RHS.ChildNodes))
    {
        RHS.RootNode = FMovieSceneEvaluationTreeNode(TRange<FFrameNumber>::All(), FMovieSceneEvaluationTreeNodeHandle::Invalid());
    }
 
    FMovieSceneEvaluationTree& operator=(FMovieSceneEvaluationTree&& RHS)
    {
        RootNode = RHS.RootNode;
        ChildNodes = MoveTemp(RHS.ChildNodes);
        RHS.RootNode = FMovieSceneEvaluationTreeNode(TRange<FFrameNumber>::All(), FMovieSceneEvaluationTreeNodeHandle::Invalid());
        return *this;
    }
 
    MOVIESCENE_API FMovieSceneEvaluationTreeRangeIterator IterateFromTime(FFrameNumber Time) const;
 
    MOVIESCENE_API FMovieSceneEvaluationTreeRangeIterator IterateFromLowerBound(TRangeBound<FFrameNumber> InStartingLowerBound) const;
 
    const FMovieSceneEvaluationTreeNode& GetRootNode() const
    {
        return RootNode;
    }
 
    FMovieSceneEvaluationTreeNode& GetNode(FMovieSceneEvaluationTreeNodeHandle Handle)
    {
        check(IsValid(Handle));
        return GetNode(Handle.GetHandle(), Handle.GetChildIndex());
    }
 
    const FMovieSceneEvaluationTreeNode& GetNode(FMovieSceneEvaluationTreeNodeHandle Handle) const
    {
        check(IsValid(Handle));
        return GetNode(Handle.GetHandle(), Handle.GetChildIndex());
    }
 
    MOVIESCENE_API TArrayView<const FMovieSceneEvaluationTreeNode> GetChildren(const FMovieSceneEvaluationTreeNode& InNode) const;
 
    MOVIESCENE_API TArrayView< FMovieSceneEvaluationTreeNode> GetChildren(const FMovieSceneEvaluationTreeNode& InNode);
 
    bool IsValid(FMovieSceneEvaluationTreeNodeHandle Handle) const
    {
        return Handle.GetHandle().IsValid() ? ChildNodes.Get(Handle.GetHandle()).IsValidIndex(Handle.GetChildIndex()) : Handle.GetChildIndex() == 0;
    }
 
    void Reset()
    {
        RootNode.DataID = RootNode.ChildrenID = FEvaluationTreeEntryHandle();
        ChildNodes.Reset();
    }
 
    MOVIESCENE_API void AddTimeRange(TRange<FFrameNumber> InTimeRange);
 
    friend FArchive& operator<<(FArchive& Ar, FMovieSceneEvaluationTree& In)
    {
        return Ar << In.RootNode << In.ChildNodes;
    }
 
protected:
 
    FMovieSceneEvaluationTreeNode& GetNode(FEvaluationTreeEntryHandle ChildrenID, int32 Index)
    {
        return ChildrenID.IsValid() ? ChildNodes.Get(ChildrenID)[Index] : RootNode;
    }
 
    const FMovieSceneEvaluationTreeNode& GetNode(FEvaluationTreeEntryHandle ChildrenID, int32 Index) const
    {
        return ChildrenID.IsValid() ? ChildNodes.Get(ChildrenID)[Index] : RootNode;
    }
 
    MOVIESCENE_API void AddTimeRange(TRange<FFrameNumber> InTimeRange, const IMovieSceneEvaluationTreeNodeOperator& InOperator, FMovieSceneEvaluationTreeNodeHandle InParent, const TFunctionRef<bool(FMovieSceneEvaluationTreeNodeHandle)>* Predicate);
 
    MOVIESCENE_API void InsertNewChild(TRange<FFrameNumber> InEffectiveRange, const IMovieSceneEvaluationTreeNodeOperator& InOperator, int32 InsertIndex, FMovieSceneEvaluationTreeNodeHandle InParent);
 
    FMovieSceneEvaluationTreeNode RootNode;
 
    TEvaluationTreeEntryContainer<FMovieSceneEvaluationTreeNode> ChildNodes;
};
 
struct FMovieSceneEvaluationTreeRangeIterator
{
    MOVIESCENE_API FMovieSceneEvaluationTreeRangeIterator(const FMovieSceneEvaluationTree& InTree);
 
    MOVIESCENE_API FMovieSceneEvaluationTreeRangeIterator(const FMovieSceneEvaluationTree& InTree, TRangeBound<FFrameNumber> StartingBound);
 
    FMovieSceneEvaluationTreeRangeIterator& operator++()
    {
        Iter(true);
        return *this;
    }
 
    FMovieSceneEvaluationTreeRangeIterator& operator--()
    {
        Iter(false);
        return *this;
    }
 
    FMovieSceneEvaluationTreeRangeIterator Next() const
    {
        FMovieSceneEvaluationTreeRangeIterator N = *this;
        return ++N;
    }
 
    FMovieSceneEvaluationTreeRangeIterator Previous() const
    {
        FMovieSceneEvaluationTreeRangeIterator P = *this;
        return --P;
    }
 
    TRange<FFrameNumber> Range() const
    {
        return CurrentRange;
    }
 
    FMovieSceneEvaluationTreeNodeHandle Node() const
    {
        return CurrentNodeHandle;
    }
 
    explicit operator bool() const
    {
        return CurrentNodeHandle.IsValid();
    }
 
private:
 
    friend bool operator==(const FMovieSceneEvaluationTreeRangeIterator& Lhs, const FMovieSceneEvaluationTreeRangeIterator& Rhs)
    {
        return Lhs.Tree == Rhs.Tree && Lhs.CurrentNodeHandle == Rhs.CurrentNodeHandle && Lhs.CurrentRange == Rhs.CurrentRange;
    }
    friend bool operator!=(const FMovieSceneEvaluationTreeRangeIterator& Lhs, const FMovieSceneEvaluationTreeRangeIterator& Rhs)
    {
        return Lhs.Tree != Rhs.Tree || Lhs.CurrentNodeHandle != Rhs.CurrentNodeHandle || Lhs.CurrentRange != Rhs.CurrentRange;
    }
 
    static bool CompareBound(bool bForwards, TRange<FFrameNumber> Range, TRangeBound<FFrameNumber> Bound)
    {
        return bForwards ? Range.GetLowerBound() == Bound : Range.GetUpperBound() == Bound;
    }
 
    static TRangeBound<FFrameNumber> GetLeadingBound(bool bForwards, TRange<FFrameNumber> Range)
    {
        return bForwards ? Range.GetLowerBound() : Range.GetUpperBound();
    }
 
    static TRangeBound<FFrameNumber> GetTrailingBound(bool bForwards, TRange<FFrameNumber> Range)
    {
        return bForwards ? Range.GetUpperBound() : Range.GetLowerBound();
    }
 
    MOVIESCENE_API void Iter(bool bForwards);
 
    MOVIESCENE_API FMovieSceneEvaluationTreeNodeHandle FindNextChild(FMovieSceneEvaluationTreeNodeHandle ParentNodeHandle, TRangeBound<FFrameNumber> PredicateBound, bool bForwards);
 
private:
    TRange<FFrameNumber> CurrentRange;
    FMovieSceneEvaluationTreeNodeHandle CurrentNodeHandle;
    const FMovieSceneEvaluationTree* Tree;
};
 
template<typename DataType>
struct TMovieSceneEvaluationTree : FMovieSceneEvaluationTree
{
 
    bool IsEmpty() const
    {
        return GetChildren(GetRootNode()).Num() == 0 && GetDataForSingleNode(GetRootNode()).Num() == 0;
    }
 
    void Add(TRange<FFrameNumber> InTimeRange)
    {
        struct FNullOperator : IMovieSceneEvaluationTreeNodeOperator
        {
            virtual void operator()(FMovieSceneEvaluationTreeNode& InNode) const override
            {}
        };
 
        AddTimeRange(InTimeRange, FNullOperator(), FMovieSceneEvaluationTreeNodeHandle::Root(), nullptr);
    }
 
    void AddUnique(TRange<FFrameNumber> InTimeRange, DataType InData)
    {
        AddTimeRange(InTimeRange, FAddUniqueOperator(*this, MoveTemp(InData)), FMovieSceneEvaluationTreeNodeHandle::Root(), nullptr);
    }
 
    void AddIfEmpty(TRange<FFrameNumber> InTimeRange, DataType InData)
    {
        AddSelective(InTimeRange, MoveTemp(InData), [this](FMovieSceneEvaluationTreeNodeHandle InNodeHandle){
            return this->GetAllData(InNodeHandle).IsValid() == false;
        });
    }
 
    void AddIfEmptySelective(TRange<FFrameNumber> InTimeRange, DataType InData, TFunctionRef<bool(FMovieSceneEvaluationTreeNodeHandle)> Predicate)
    {
        AddSelective(InTimeRange, MoveTemp(InData), [this, &Predicate](FMovieSceneEvaluationTreeNodeHandle InNodeHandle){
            return this->GetAllData(InNodeHandle).IsValid() && Predicate(InNodeHandle);
        });
    }
 
    void AddSelective(TRange<FFrameNumber> InTimeRange, DataType InData, TFunctionRef<bool(FMovieSceneEvaluationTreeNodeHandle)> Predicate)
    {
        AddTimeRange(InTimeRange, FAddOperator(*this, MoveTemp(InData)), FMovieSceneEvaluationTreeNodeHandle::Root(), &Predicate);
    }
 
    void Add(TRange<FFrameNumber> InTimeRange, DataType InData)
    {
        AddTimeRange(InTimeRange, FAddOperator(*this, MoveTemp(InData)), FMovieSceneEvaluationTreeNodeHandle::Root(), nullptr);
    }
 
    void Compact()
    {
        ChildNodes.Compact();
        Data.Compact();
    }
 
    void Reset()
    {
        FMovieSceneEvaluationTree::Reset();
        Data.Reset();
    }
 
    TArrayView<const DataType> GetDataForSingleNode(const FMovieSceneEvaluationTreeNode& InNode) const
    {
        return InNode.DataID.IsValid() ? Data.Get(InNode.DataID) : TArrayView<const DataType>();
    }
 
    TArrayView<DataType> GetMutableDataForSingleNode(const FMovieSceneEvaluationTreeNode& InNode)
    {
        return InNode.DataID.IsValid() ? Data.Get(InNode.DataID) : TArrayView<DataType>();
    }
 
    TMovieSceneEvaluationTreeDataIterator<DataType> GetAllData(FMovieSceneEvaluationTreeNodeHandle NodeHandle) const
    {
        return TMovieSceneEvaluationTreeDataIterator<DataType>(*this, NodeHandle);
    }
 
    friend FArchive& operator<<(FArchive& Ar, TMovieSceneEvaluationTree<DataType>& In)
    {
        auto& BaseTree = static_cast<FMovieSceneEvaluationTree&>(In);
        return Ar << BaseTree << In.Data;
    }
 
    friend bool operator==(const TMovieSceneEvaluationTree<DataType>& A, const TMovieSceneEvaluationTree<DataType>& B)
    {
        return A.Data == B.Data && A.RootNode == B.RootNode && A.ChildNodes == B.ChildNodes;
    }
 
private:
 
    TEvaluationTreeEntryContainer<DataType> Data;
 
    friend struct TMovieSceneEvaluationTreeFormatter<DataType>;
 
private:
    struct FAddUniqueOperator : IMovieSceneEvaluationTreeNodeOperator
    {
        FAddUniqueOperator(TMovieSceneEvaluationTree<DataType>& InTree, DataType&& InDataToInsert) : Tree(InTree), DataToInsert(InDataToInsert) {}
 
        virtual void operator()(FMovieSceneEvaluationTreeNode& InNode) const override
        {
            // If we haven't allocated data for this node yet, do so now
            if (!InNode.DataID.IsValid())
            {
                InNode.DataID = Tree.Data.AllocateEntry(1);
            }
 
            TArrayView<const DataType> NodeData = Tree.Data.Get(InNode.DataID);
            if (!NodeData.Contains(DataToInsert))
            {
                Tree.Data.Add(InNode.DataID, CopyTemp(DataToInsert));
            }
        }
        TMovieSceneEvaluationTree<DataType>& Tree;
        DataType DataToInsert;
    };
 
    struct FAddOperator : IMovieSceneEvaluationTreeNodeOperator
    {
        FAddOperator(TMovieSceneEvaluationTree<DataType>& InTree, DataType&& InDataToInsert) : Tree(InTree), DataToInsert(InDataToInsert) {}
 
        virtual void operator()(FMovieSceneEvaluationTreeNode& InNode) const override
        {
            // If we haven't allocated data for this node yet, do so now
            if (!InNode.DataID.IsValid())
            {
                InNode.DataID = Tree.Data.AllocateEntry(1);
            }
 
            Tree.Data.Add(InNode.DataID, CopyTemp(DataToInsert));
        }
        TMovieSceneEvaluationTree<DataType>& Tree;
        DataType DataToInsert;
    };
};
 
template<typename DataType>
struct TMovieSceneEvaluationTreeDataIterator
{
    TMovieSceneEvaluationTreeDataIterator(const TMovieSceneEvaluationTree<DataType>& InTree, FMovieSceneEvaluationTreeNodeHandle StartNode)
        : Tree(&InTree)
        , CurrentNode(StartNode.IsValid() ? &InTree.GetNode(StartNode) : nullptr)
        , DataIndex(0)
    {
        // Walk up the tree until we find some data. We reset the iterator so begin() == end() where there is no data
        while (CurrentNode && !InTree.GetDataForSingleNode(*CurrentNode).IsValidIndex(DataIndex))
        {
            CurrentNode = CurrentNode->Parent.IsValid() ? &InTree.GetNode(CurrentNode->Parent) : nullptr;
            DataIndex = 0;
        }
    }
 
    const DataType& operator*() const
    {
        return Tree->GetDataForSingleNode(*CurrentNode)[DataIndex];
    }
 
    const DataType* operator->() const
    {
        return &Tree->GetDataForSingleNode(*CurrentNode)[DataIndex];
    }
 
    bool IsValid() const
    {
        return CurrentNode && Tree->GetDataForSingleNode(*CurrentNode).IsValidIndex(DataIndex);
    }
 
    explicit operator bool() const
    {
        return IsValid();
    }
 
    TMovieSceneEvaluationTreeDataIterator& operator++()
    {
        ++DataIndex;
 
        // Skip up parents while the data index is invalid
        while (CurrentNode && !Tree->GetDataForSingleNode(*CurrentNode).IsValidIndex(DataIndex))
        {
            CurrentNode = CurrentNode->Parent.IsValid() ? &Tree->GetNode(CurrentNode->Parent) : nullptr;
            DataIndex = 0;
        }
        return *this;
    }
 
    friend TMovieSceneEvaluationTreeDataIterator<DataType> begin(const TMovieSceneEvaluationTreeDataIterator<DataType>& In)                      { return In; }
    friend TMovieSceneEvaluationTreeDataIterator<DataType> end(const TMovieSceneEvaluationTreeDataIterator<DataType>& In)                        { return TMovieSceneEvaluationTreeDataIterator<DataType>(*In.Tree, FMovieSceneEvaluationTreeNodeHandle::Invalid()); }
    friend bool operator==(const TMovieSceneEvaluationTreeDataIterator<DataType>& A, const TMovieSceneEvaluationTreeDataIterator<DataType>& B)   { return A.Tree == B.Tree && A.CurrentNode == B.CurrentNode && A.DataIndex == B.DataIndex; }
    friend bool operator!=(const TMovieSceneEvaluationTreeDataIterator<DataType>& A, const TMovieSceneEvaluationTreeDataIterator<DataType>& B)   { return A.Tree != B.Tree || A.CurrentNode != B.CurrentNode || A.DataIndex != B.DataIndex; }
 
private:
    const TMovieSceneEvaluationTree<DataType>* Tree;
    const FMovieSceneEvaluationTreeNode* CurrentNode;
    int32 DataIndex;
};
 
template<typename ElementType>
FEvaluationTreeEntryHandle TEvaluationTreeEntryContainer<ElementType>::AllocateEntry(int32 InitialCapacity)
{
    FEvaluationTreeEntryHandle ID{ Entries.Num() };
    Entries.Add(FEntry{Items.Num(), 0, InitialCapacity});
    Items.SetNum(Items.Num() + InitialCapacity);
    return ID;
}
 
template<typename ElementType>
TArrayView<ElementType> TEvaluationTreeEntryContainer<ElementType>::Get(FEvaluationTreeEntryHandle ID)
{
    const FEntry& Entry = Entries[ID.EntryIndex];
    return TArrayView<ElementType>(&Items[Entry.StartIndex], Entry.Size);
}
 
template<typename ElementType>
TArrayView<const ElementType> TEvaluationTreeEntryContainer<ElementType>::Get(FEvaluationTreeEntryHandle ID) const
{
    const FEntry& Entry = Entries[ID.EntryIndex];
    return TArrayView<const ElementType>(&Items[Entry.StartIndex], Entry.Size);
}
 
template<typename ElementType>
void TEvaluationTreeEntryContainer<ElementType>::Add(FEvaluationTreeEntryHandle ID, ElementType&& Element)
{
    FEntry& Entry = Entries[ID.EntryIndex];
    if (Entry.Size+1 > Entry.Capacity)
    {
        ReserveEntry(ID, FMath::Max<int32>(Entry.Capacity*2, 2));
    }
 
    Items[Entry.StartIndex + Entry.Size] = MoveTemp(Element);
    ++Entry.Size;
}
 
template<typename ElementType>
void TEvaluationTreeEntryContainer<ElementType>::Insert(FEvaluationTreeEntryHandle ID, int32 Index, ElementType&& Element)
{
    FEntry& Entry = Entries[ID.EntryIndex];
    if (Entry.Size+1 > Entry.Capacity)
    {
        ReserveEntry(ID, FMath::Max<int32>(Entry.Capacity*2, 2));
    }
 
    Index = FMath::Clamp(Index, 0, Entry.Capacity-1);
 
    // Shift anything >= the insert index up one
    if (Index <= Entry.Size-1)
    {
        ElementType* OldLocation = &Items[Entry.StartIndex + Index];
        void* NewLocation = &Items[Entry.StartIndex + Index + 1];
 
        RelocateConstructItems<ElementType>(NewLocation, OldLocation, Entry.Size - Index);
        DefaultConstructItems<ElementType>((void*)OldLocation, 1);
    }
 
    // Assign the new element
    ++Entry.Size;
    Items[Entry.StartIndex + Index] = MoveTemp(Element);
}
 
template<typename ElementType>
void TEvaluationTreeEntryContainer<ElementType>::Compact()
{
    TArray<ElementType> NewItems;
 
    for (FEntry& Entry : Entries)
    {
        if (Entry.Size > 0)
        {
            const int32 OldIndex = Entry.StartIndex;
            Entry.StartIndex = NewItems.Num();
 
            NewItems.Append(&Items[OldIndex], Entry.Size);
        }
        else
        {
            Entry.StartIndex = INDEX_NONE;
        }
        Entry.Capacity = Entry.Size;
    }
 
    NewItems.Shrink();
    Items = MoveTemp(NewItems);
}
 
template<typename ElementType>
void TEvaluationTreeEntryContainer<ElementType>::ReserveEntry(FEvaluationTreeEntryHandle ID, int32 NewCapacity)
{
    FEntry& Entry = Entries[ID.EntryIndex];
 
    // Function should only be called to grow an entry
    check(NewCapacity > Entry.Capacity);
    Entry.Capacity = NewCapacity;
 
    int32 NewStartIndex = Items.Num();
 
    // Reallocate the items to the new entry location
    Items.SetNum(Items.Num() + Entry.Capacity);
 
    ElementType* OldLocation = &Items[Entry.StartIndex];
    void* NewLocation = &Items[NewStartIndex];
    RelocateConstructItems<ElementType>(NewLocation, OldLocation, Entry.Size);
    DefaultConstructItems<ElementType>((void*)OldLocation, Entry.Size);
 
    Entry.StartIndex = NewStartIndex;
}