IsHeap.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Algo/Impl/BinaryHeap.h"
#include "Templates/IdentityFunctor.h"
#include "Templates/Invoke.h"
#include "Templates/Less.h"
#include "Templates/UnrealTemplate.h" // For GetData, GetNum
 
namespace AlgoImpl
{
    template <typename RangeValueType, typename IndexType, typename ProjectionType, typename PredicateType>
    bool IsHeapInternal(const RangeValueType* Heap, IndexType Num, ProjectionType Projection, PredicateType Predicate)
    {
        for (IndexType Index = 1; Index < Num; Index++)
        {
            IndexType ParentIndex = HeapGetParentIndex(Index);
            if (Predicate( Invoke(Projection, Heap[Index]), Invoke(Projection, Heap[ParentIndex]) ))
            {
                return false;
            }
        }
 
        return true;
    }
}
 
namespace Algo
{
    template <typename RangeType>
    [[nodiscard]] UE_REWRITE bool IsHeap(const RangeType& Range)
    {
        return AlgoImpl::IsHeapInternal(GetData(Range), GetNum(Range), FIdentityFunctor(), TLess<>());
    }
 
    template <typename RangeType, typename PredicateType>
    [[nodiscard]] UE_REWRITE bool IsHeap(const RangeType& Range, PredicateType Predicate)
    {
        return AlgoImpl::IsHeapInternal(GetData(Range), GetNum(Range), FIdentityFunctor(), MoveTemp(Predicate));
    }
 
    template <typename RangeType, typename ProjectionType>
    [[nodiscard]] UE_REWRITE bool IsHeapBy(const RangeType& Range, ProjectionType Projection)
    {
        return AlgoImpl::IsHeapInternal(GetData(Range), GetNum(Range), MoveTemp(Projection), TLess<>());
    }
 
    template <typename RangeType, typename ProjectionType, typename PredicateType>
    [[nodiscard]] UE_REWRITE bool IsHeapBy(const RangeType& Range, ProjectionType Projection, PredicateType Predicate)
    {
        return AlgoImpl::IsHeapInternal(GetData(Range), GetNum(Range), MoveTemp(Projection), MoveTemp(Predicate));
    }
}