SlateInvalidationWidgetHeap.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreMinimal.h"
 
#include "FastUpdate/SlateInvalidationWidgetIndex.h"
#include "FastUpdate/SlateInvalidationWidgetList.h"
#include "FastUpdate/SlateInvalidationWidgetSortOrder.h"
 
#ifndef UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING
    #define UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING DO_CHECK
#endif
 
namespace UE::Slate::Private
{
#if UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING
    extern bool GSlateInvalidationWidgetHeapVerifyWidgetContains;
#endif
} // namespace
 
class FSlateInvalidationWidgetPreHeap
{
public:
    using FElement = FSlateInvalidationWidgetHeapElement;
    struct FWidgetOrderLess
    {
        FORCEINLINE bool operator()(const FElement& A, const FElement& B) const
        {
            return A.GetWidgetSortOrder() < B.GetWidgetSortOrder();
        }
    };
    using SortPredicate = FWidgetOrderLess;
    
    static constexpr int32 NumberOfPreAllocatedElement = 32;
    using FElementContainer = TArray<FElement, TInlineAllocator<NumberOfPreAllocatedElement>>;
 
    FSlateInvalidationWidgetPreHeap(FSlateInvalidationWidgetList& InOwnerList)
        : OwnerList(InOwnerList)
    { }
 
public:
    void HeapPushUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        check(InvalidationWidget.Index != FSlateInvalidationWidgetIndex::Invalid);
        VerifyContainsFlag(InvalidationWidget);
 
        if (!InvalidationWidget.bContainedByWidgetPreHeap)
        {
            InvalidationWidget.bContainedByWidgetPreHeap = true;
            Heap.HeapPush(FElement{ InvalidationWidget.Index, FSlateInvalidationWidgetSortOrder{OwnerList, InvalidationWidget.Index} }, SortPredicate());
        }
    }
 
    [[nodiscard]] FSlateInvalidationWidgetIndex HeapPop()
    {
        check(Heap.Num() > 0);
        FSlateInvalidationWidgetIndex Result = Heap.HeapTop().GetWidgetIndex();
        Heap.HeapPopDiscard(SortPredicate(), EAllowShrinking::No);
        OwnerList[Result].bContainedByWidgetPreHeap = false;
        return Result;
    }
 
    void HeapPopDiscard()
    {
        check(Heap.Num() > 0);
        FSlateInvalidationWidgetIndex Result = Heap.HeapTop().GetWidgetIndex();
        Heap.HeapPopDiscard(SortPredicate(), EAllowShrinking::No);
        OwnerList[Result].bContainedByWidgetPreHeap = false;
    }
    
    [[nodiscard]] inline FSlateInvalidationWidgetIndex HeapPeek() const
    {
        check(Heap.Num() > 0);
        return Heap.HeapTop().GetWidgetIndex();
    }
    
    [[nodiscard]] inline const FElement& HeapPeekElement() const
    {
        check(Heap.Num() > 0);
        return Heap.HeapTop();
    }
 
    int32 RemoveRange(const FSlateInvalidationWidgetList::FIndexRange& Range)
    {
        int32 RemoveCount = 0;
        for (int32 Index = 0; Index < Heap.Num(); ++Index)
        {
            if (Range.Include(Heap[Index].GetWidgetSortOrder()))
            {
                const FSlateInvalidationWidgetIndex WidgetIndex = Heap[Index].GetWidgetIndex();
                OwnerList[WidgetIndex].bContainedByWidgetPreHeap = false;
                Heap.HeapRemoveAt(Index, SortPredicate());
                Index = INDEX_NONE; // start again
            }
        }
        return RemoveCount;
    }
 
    void Reset(bool bResetContained)
    {
        if (bResetContained)
        {
            for (const FElement& Element : Heap)
            {
                OwnerList[Element.GetWidgetIndex()].bContainedByWidgetPreHeap = false;
            }
        }
 
        // Destroy the second allocator, if it exists.
        Heap.Empty(NumberOfPreAllocatedElement);
    }
 
    [[nodiscard]] inline int32 Num() const
    {
        return Heap.Num();
    }
 
    [[nodiscard]] bool Contains_Debug(const FSlateInvalidationWidgetIndex WidgetIndex) const
    {
        return Heap.ContainsByPredicate([WidgetIndex](const FElement& Element)
            {
                return Element.GetWidgetIndex() == WidgetIndex;
            });
    }
 
    [[nodiscard]] inline bool IsValidHeap_Debug()
    {
        return Algo::IsHeap(Heap, SortPredicate());
    }
 
    [[nodiscard]] inline const FElementContainer& GetRaw() const
    {
        return Heap;
    }
 
    template<typename Predicate>
    void ForEachIndexes(Predicate Pred)
    {
        for (FElement& Element : Heap)
        {
            Pred(Element);
        }
    }
 
private:
    void VerifyContainsFlag(const FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
#if UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING
        if (UE::Slate::Private::GSlateInvalidationWidgetHeapVerifyWidgetContains)
        {
            check(Contains_Debug(InvalidationWidget.Index) == InvalidationWidget.bContainedByWidgetPreHeap);
        }
#endif
    }
 
    FElementContainer Heap;
    FSlateInvalidationWidgetList& OwnerList;
};
 
 
class FSlateInvalidationWidgetPostHeap
{
public:
    using FElement = FSlateInvalidationWidgetHeapElement;
    struct FWidgetOrderGreater
    {
        FORCEINLINE bool operator()(const FElement& A, const FElement& B) const
        {
            return B.GetWidgetSortOrder() < A.GetWidgetSortOrder();
        }
    };
    using SortPredicate = FWidgetOrderGreater;
    
    static constexpr int32 NumberOfPreAllocatedElement = 100;
    using FElementContainer = TArray<FElement, TInlineAllocator<NumberOfPreAllocatedElement>>;
 
    FSlateInvalidationWidgetPostHeap(FSlateInvalidationWidgetList& InOwnerList)
        : OwnerList(InOwnerList)
        , WidgetCannotBeAdded(FSlateInvalidationWidgetIndex::Invalid)
        , bIsHeap(false)
    { }
 
public:
    void HeapPushUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        check(bIsHeap);
        check(InvalidationWidget.Index != FSlateInvalidationWidgetIndex::Invalid);
        VerifyContainsFlag(InvalidationWidget);
 
        if (!InvalidationWidget.bContainedByWidgetPostHeap)
        {
            InvalidationWidget.bContainedByWidgetPostHeap = true;
            Heap.HeapPush(FElement{ InvalidationWidget.Index, FSlateInvalidationWidgetSortOrder{OwnerList, InvalidationWidget.Index} }, SortPredicate());
        }
    }
 
    void PushBackUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        check(bIsHeap == false);
        check(InvalidationWidget.Index != FSlateInvalidationWidgetIndex::Invalid);
        VerifyContainsFlag(InvalidationWidget);
 
        if (!InvalidationWidget.bContainedByWidgetPostHeap)
        {
            InvalidationWidget.bContainedByWidgetPostHeap = true;
            Heap.Emplace(InvalidationWidget.Index, FSlateInvalidationWidgetSortOrder{OwnerList, InvalidationWidget.Index});
        }
    }
 
    void PushBackOrHeapUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        if (bIsHeap)
        {
            HeapPushUnique(InvalidationWidget);
        }
        else
        {
            PushBackUnique(InvalidationWidget);
        }
    }
 
    [[nodiscard]] FElement HeapPop()
    {
        check(bIsHeap == true);
        FElement Result = Heap.HeapTop();
        Heap.HeapPopDiscard(SortPredicate(), EAllowShrinking::No);
        OwnerList[Result.GetWidgetIndex()].bContainedByWidgetPostHeap = false;
        return Result;
    }
 
    int32 RemoveRange(const FSlateInvalidationWidgetList::FIndexRange& Range)
    {
        check(bIsHeap == false);
        int32 RemoveCount = 0;
        for (int32 Index = Heap.Num() -1; Index >= 0 ; --Index)
        {
            if (Range.Include(Heap[Index].GetWidgetSortOrder()))
            {
                const FSlateInvalidationWidgetIndex WidgetIndex = Heap[Index].GetWidgetIndex();
                OwnerList[WidgetIndex].bContainedByWidgetPostHeap = false;
                Heap.RemoveAtSwap(Index);
                ++RemoveCount;
            }
        }
 
        return RemoveCount;
    }
 
    void Reset(bool bResetContained)
    {
        if (bResetContained)
        {
            for (const FElement& Element : Heap)
            {
                OwnerList[Element.GetWidgetIndex()].bContainedByWidgetPostHeap = false;
            }
        }
 
        // Destroy the second allocator, if it exists.
        Heap.Empty(NumberOfPreAllocatedElement);
        bIsHeap = false;
    }
 
    void Heapify()
    {
        check(!bIsHeap);
        Heap.Heapify(SortPredicate());
        bIsHeap = true;
    }
 
    [[nodiscard]] inline int32 Num() const
    {
        return Heap.Num();
    }
 
    [[nodiscard]] inline bool IsHeap() const
    {
        return bIsHeap;
    }
 
    [[nodiscard]] bool Contains_Debug(const FSlateInvalidationWidgetIndex WidgetIndex) const
    {
        return Heap.ContainsByPredicate([WidgetIndex](const FElement& Element)
            {
                return Element.GetWidgetIndex() == WidgetIndex;
            });
    }
 
    [[nodiscard]] inline bool IsValidHeap_Debug()
    {
        return Algo::IsHeap(Heap, SortPredicate());
    }
 
    [[nodiscard]] inline const FElementContainer& GetRaw() const
    {
        return Heap;
    }
 
    template<typename Predicate>
    void ForEachIndexes(Predicate Pred)
    {
        for (FElement& Element : Heap)
        {
            Pred(Element);
        }
    }
    
public:
    struct FScopeWidgetCannotBeAdded
    {
        FScopeWidgetCannotBeAdded(FSlateInvalidationWidgetPostHeap& InHeap, FSlateInvalidationWidgetList::InvalidationWidgetType& InInvalidationWidget)
            : Heap(InHeap)
            , InvalidationWidget(InInvalidationWidget)
            , WidgetIndex(InvalidationWidget.Index)
        {
            check(!InvalidationWidget.bContainedByWidgetPostHeap
                && Heap.WidgetCannotBeAdded == FSlateInvalidationWidgetIndex::Invalid);
            Heap.WidgetCannotBeAdded = InvalidationWidget.Index;
            InvalidationWidget.bContainedByWidgetPostHeap = true;
        }
        ~FScopeWidgetCannotBeAdded()
        {
            Heap.WidgetCannotBeAdded = FSlateInvalidationWidgetIndex::Invalid;
            check(Heap.OwnerList.IsValidIndex(WidgetIndex));
            check(&Heap.OwnerList[WidgetIndex] == &InvalidationWidget);
            InvalidationWidget.bContainedByWidgetPostHeap = false;
        }
        FSlateInvalidationWidgetPostHeap& Heap;
        FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget;
        FSlateInvalidationWidgetIndex WidgetIndex;
    };
 
private:
    void VerifyContainsFlag(const FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
#if UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING
        if (UE::Slate::Private::GSlateInvalidationWidgetHeapVerifyWidgetContains)
        {
            check(Contains_Debug(InvalidationWidget.Index) == InvalidationWidget.bContainedByWidgetPostHeap
                || WidgetCannotBeAdded == InvalidationWidget.Index);
        }
#endif
    }
 
    FElementContainer Heap;
    FSlateInvalidationWidgetList& OwnerList;
    FSlateInvalidationWidgetIndex WidgetCannotBeAdded;
    bool bIsHeap;
};
 
class FSlateInvalidationWidgetPrepassHeap
{
public:
    using FElement = FSlateInvalidationWidgetHeapElement;
    struct FWidgetOrderGreater
    {
        FORCEINLINE bool operator()(const FElement& A, const FElement& B) const
        {
            return A.GetWidgetSortOrder() < B.GetWidgetSortOrder();
        }
    };
    using SortPredicate = FWidgetOrderGreater;
 
    static constexpr int32 NumberOfPreAllocatedElement = 32;
    using FElementContainer = TArray<FElement, TInlineAllocator<NumberOfPreAllocatedElement>>;
 
    FSlateInvalidationWidgetPrepassHeap(FSlateInvalidationWidgetList& InOwnerList)
        : OwnerList(InOwnerList)
        , bIsHeap(false)
    { }
 
public:
    void HeapPushUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        check(bIsHeap);
        check(InvalidationWidget.Index != FSlateInvalidationWidgetIndex::Invalid);
        VerifyContainsFlag(InvalidationWidget);
 
        if (!InvalidationWidget.bContainedByWidgetPrepassList)
        {
            InvalidationWidget.bContainedByWidgetPrepassList = true;
            Heap.HeapPush(FElement{ InvalidationWidget.Index, FSlateInvalidationWidgetSortOrder{OwnerList, InvalidationWidget.Index} }, SortPredicate());
        }
    }
 
    void PushBackUnique(FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
        check(bIsHeap == false);
        check(InvalidationWidget.Index != FSlateInvalidationWidgetIndex::Invalid);
        VerifyContainsFlag(InvalidationWidget);
 
        if (!InvalidationWidget.bContainedByWidgetPrepassList)
        {
            InvalidationWidget.bContainedByWidgetPrepassList = true;
            Heap.Emplace(InvalidationWidget.Index, FSlateInvalidationWidgetSortOrder{ OwnerList, InvalidationWidget.Index });
        }
    }
 
    [[nodiscard]] FElement HeapPop()
    {
        check(bIsHeap == true);
        FElement Result = Heap.HeapTop();
        Heap.HeapPopDiscard(SortPredicate(), EAllowShrinking::No);
        OwnerList[Result.GetWidgetIndex()].bContainedByWidgetPrepassList = false;
        return Result;
    }
 
    int32 RemoveRange(const FSlateInvalidationWidgetList::FIndexRange& Range)
    {
        check(bIsHeap == false);
        int32 RemoveCount = 0;
        for (int32 Index = Heap.Num() - 1; Index >= 0; --Index)
        {
            if (Range.Include(Heap[Index].GetWidgetSortOrder()))
            {
                const FSlateInvalidationWidgetIndex WidgetIndex = Heap[Index].GetWidgetIndex();
                OwnerList[WidgetIndex].bContainedByWidgetPrepassList = false;
                Heap.RemoveAtSwap(Index);
                ++RemoveCount;
            }
        }
 
        return RemoveCount;
    }
 
    void Reset(bool bResetContained)
    {
        if (bResetContained)
        {
            for (const FElement& Element : Heap)
            {
                OwnerList[Element.GetWidgetIndex()].bContainedByWidgetPrepassList = false;
            }
        }
 
        // Destroy the second allocator, if it exists.
        Heap.Empty(NumberOfPreAllocatedElement);
        bIsHeap = false;
    }
 
    void Heapify()
    {
        check(!bIsHeap);
        Heap.Heapify(SortPredicate());
        bIsHeap = true;
    }
 
    [[nodiscard]] inline int32 Num() const
    {
        return Heap.Num();
    }
 
    [[nodiscard]] inline bool IsHeap() const
    {
        return bIsHeap;
    }
 
    [[nodiscard]] bool Contains_Debug(const FSlateInvalidationWidgetIndex WidgetIndex) const
    {
        return Heap.ContainsByPredicate([WidgetIndex](const FElement& Element)
            {
                return Element.GetWidgetIndex() == WidgetIndex;
            });
    }
 
    [[nodiscard]] inline bool IsValidHeap_Debug()
    {
        return Algo::IsHeap(Heap, SortPredicate());
    }
 
    [[nodiscard]] inline const FElementContainer& GetRaw() const
    {
        return Heap;
    }
 
    template<typename Predicate>
    void ForEachIndexes(Predicate Pred)
    {
        for (FElement& Element : Heap)
        {
            Pred(Element);
        }
    }
 
private:
    void VerifyContainsFlag(const FSlateInvalidationWidgetList::InvalidationWidgetType& InvalidationWidget)
    {
#if UE_SLATE_WITH_INVALIDATIONWIDGETHEAP_DEBUGGING
        if (UE::Slate::Private::GSlateInvalidationWidgetHeapVerifyWidgetContains)
        {
            check(Contains_Debug(InvalidationWidget.Index) == InvalidationWidget.bContainedByWidgetPrepassList);
        }
#endif
    }
 
    FElementContainer Heap;
    FSlateInvalidationWidgetList& OwnerList;
    bool bIsHeap;
};