虚幻 – Priority Queue 优先队列

众所周知，UE 没有提供优先队列这一常用容器。
但是在 TArray 中有一些堆函数，可以实现优先队列的操作。
这里提供一个简单封装，其中 Priority 值越小优先级越高。

template<typename ElementType, typename ArrayAllocator = FDefaultAllocator>
class TRFurPriorityQueue
{
public:

    FORCEINLINE TRFurPriorityQueue() = default;
    FORCEINLINE TRFurPriorityQueue(TRFurPriorityQueue&&) = default;
    FORCEINLINE TRFurPriorityQueue(const TRFurPriorityQueue&) = default;
    FORCEINLINE TRFurPriorityQueue& operator=(TRFurPriorityQueue&&) = default;
    FORCEINLINE TRFurPriorityQueue& operator=(const TRFurPriorityQueue&) = default;

    FORCEINLINE bool Pop(bool bAllowShrinking = true);
    FORCEINLINE void Empty(bool bAllowShrinking = true);
    FORCEINLINE void Enqueue(ElementType&& Item, int32 Priority);
    FORCEINLINE void Enqueue(const ElementType& Item, int32 Priority);
    FORCEINLINE bool Dequeue(ElementType& OutItem, bool bAllowShrinking = true);

    FORCEINLINE int32 Num() const;
    FORCEINLINE bool IsEmpty() const;

    FORCEINLINE const ElementType* Top() const;
    FORCEINLINE bool Top(ElementType& OutItem) const;

private:

    struct TNode
    {
        int32 Priority;
        ElementType Element;

        FORCEINLINE TNode();
        FORCEINLINE TNode(const ElementType& InElement, int32 InPriority);
        FORCEINLINE TNode(ElementType&& InElement, int32 InPriority);
    };

    struct TComparator
    {
        FORCEINLINE bool operator()(const TNode& A, const TNode& B) const;
    };

    TArray<TNode> Nodes;

};

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode()
{ }

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode(const ElementType& InElement, int32 InPriority)
    : Priority(InPriority)
    , Element(InElement)
{ }

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE TRFurPriorityQueue<ElementType, ArrayAllocator>::TNode::TNode(ElementType&& InElement, int32 InPriority)
    : Priority(InPriority)
    , Element(InElement)
{ }

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::TComparator::operator()(const TNode& A, const TNode& B) const
{
    return A.Priority < B.Priority;
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Pop(bool bAllowShrinking)
{
    if (IsEmpty())
    {
        return false;
    }
    else
    {
        Nodes.HeapPopDiscard(TComparator(), bAllowShrinking);
        return true;
    }
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Empty(bool bAllowShrinking)
{
    Nodes.SetNum(0, bAllowShrinking);
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Enqueue(ElementType&& Item, int32 Priority)
{
    Nodes.HeapPush(TNode(Item, Priority), TComparator());
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE void TRFurPriorityQueue<ElementType, ArrayAllocator>::Enqueue(const ElementType& Item, int32 Priority)
{
    Nodes.HeapPush(TNode(Item, Priority), TComparator());
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Dequeue(ElementType& OutItem, bool bAllowShrinking)
{
    if (IsEmpty())
    {
        return false;
    }
    else
    {
        OutItem = Nodes.HeapTop().Element;
        Nodes.HeapPopDiscard(TComparator(), bAllowShrinking);
        return true;
    }
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE int32 TRFurPriorityQueue<ElementType, ArrayAllocator>::Num() const
{
    return Nodes.Num();
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::IsEmpty() const
{
    return Num() == 0;
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE const ElementType* TRFurPriorityQueue<ElementType, ArrayAllocator>::Top() const
{
    return IsEmpty() ? nullptr : &Nodes.HeapTop().Element;
}

template<typename ElementType, typename ArrayAllocator>
FORCEINLINE bool TRFurPriorityQueue<ElementType, ArrayAllocator>::Top(ElementType& OutItem) const
{
    if (IsEmpty())
    {
        return false;
    }
    else
    {
        OutItem = Nodes.HeapTop().Element;
        return true;
    }
}