BinarySearch.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Templates/IdentityFunctor.h"
#include "Templates/Invoke.h"
#include "Templates/Less.h"
 
namespace AlgoImpl
{
    template <typename RangeValueType, typename SizeType, typename PredicateValueType, typename ProjectionType, typename SortPredicateType>
    SizeType LowerBoundInternal(RangeValueType* First, const SizeType Num, const PredicateValueType& Value, ProjectionType Projection, SortPredicateType SortPredicate)
    {
        // Current start of sequence to check
        SizeType Start = 0;
        // Size of sequence to check
        SizeType Size = Num;
 
        // With this method, if Size is even it will do one more comparison than necessary, but because Size can be predicted by the CPU it is faster in practice
        while (Size > 0)
        {
            const SizeType LeftoverSize = Size % 2;
            Size = Size / 2;
 
            const SizeType CheckIndex = Start + Size;
            const SizeType StartIfLess = CheckIndex + LeftoverSize;
 
            auto&& CheckValue = Invoke(Projection, First[CheckIndex]);
            Start = SortPredicate(CheckValue, Value) ? StartIfLess : Start;
        }
        return Start;
    }
 
    template <typename RangeValueType, typename SizeType, typename PredicateValueType, typename ProjectionType, typename SortPredicateType>
    SizeType UpperBoundInternal(RangeValueType* First, const SizeType Num, const PredicateValueType& Value, ProjectionType Projection, SortPredicateType SortPredicate)
    {
        // Current start of sequence to check
        SizeType Start = 0;
        // Size of sequence to check
        SizeType Size = Num;
 
        // With this method, if Size is even it will do one more comparison than necessary, but because Size can be predicted by the CPU it is faster in practice
        while (Size > 0)
        {
            const SizeType LeftoverSize = Size % 2;
            Size = Size / 2;
 
            const SizeType CheckIndex = Start + Size;
            const SizeType StartIfLess = CheckIndex + LeftoverSize;
 
            auto&& CheckValue = Invoke(Projection, First[CheckIndex]);
            Start = !SortPredicate(Value, CheckValue) ? StartIfLess : Start;
        }
 
        return Start;
    }
}
 
namespace Algo
{
    template <typename RangeType, typename ValueType, typename SortPredicateType>
    [[nodiscard]] UE_REWRITE auto LowerBound(const RangeType& Range, const ValueType& Value, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        return AlgoImpl::LowerBoundInternal(GetData(Range), GetNum(Range), Value, FIdentityFunctor(), SortPredicate);
    }
    template <typename RangeType, typename ValueType>
    [[nodiscard]] UE_REWRITE auto LowerBound(const RangeType& Range, const ValueType& Value) -> decltype(GetNum(Range))
    {
        return AlgoImpl::LowerBoundInternal(GetData(Range), GetNum(Range), Value, FIdentityFunctor(), TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename ProjectionType, typename SortPredicateType>
    [[nodiscard]] UE_REWRITE auto LowerBoundBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        return AlgoImpl::LowerBoundInternal(GetData(Range), GetNum(Range), Value, Projection, SortPredicate);
    }
    template <typename RangeType, typename ValueType, typename ProjectionType>
    [[nodiscard]] UE_REWRITE auto LowerBoundBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection) -> decltype(GetNum(Range))
    {
        return AlgoImpl::LowerBoundInternal(GetData(Range), GetNum(Range), Value, Projection, TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename SortPredicateType>
    [[nodiscard]] UE_REWRITE auto UpperBound(const RangeType& Range, const ValueType& Value, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        return AlgoImpl::UpperBoundInternal(GetData(Range), GetNum(Range), Value, FIdentityFunctor(), SortPredicate);
    }
    template <typename RangeType, typename ValueType>
    [[nodiscard]] UE_REWRITE auto UpperBound(const RangeType& Range, const ValueType& Value) -> decltype(GetNum(Range))
    {
        return AlgoImpl::UpperBoundInternal(GetData(Range), GetNum(Range), Value, FIdentityFunctor(), TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename ProjectionType, typename SortPredicateType>
    [[nodiscard]] UE_REWRITE auto UpperBoundBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        return AlgoImpl::UpperBoundInternal(GetData(Range), GetNum(Range), Value, Projection, SortPredicate);
    }
    template <typename RangeType, typename ValueType, typename ProjectionType>
    [[nodiscard]] UE_REWRITE auto UpperBoundBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection) -> decltype(GetNum(Range))
    {
        return AlgoImpl::UpperBoundInternal(GetData(Range), GetNum(Range), Value, Projection, TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename SortPredicateType>
    [[nodiscard]] auto BinarySearch(const RangeType& Range, const ValueType& Value, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        auto CheckIndex = LowerBound(Range, Value, SortPredicate);
        if (CheckIndex < GetNum(Range))
        {
            auto&& CheckValue = GetData(Range)[CheckIndex];
            // Since we returned lower bound we already know Value <= CheckValue. So if Value is not < CheckValue, they must be equal
            if (!SortPredicate(Value, CheckValue))
            {
                return CheckIndex;
            }
        }
        return INDEX_NONE;
    }
    template <typename RangeType, typename ValueType>
    [[nodiscard]] UE_REWRITE auto BinarySearch(const RangeType& Range, const ValueType& Value)
    {
        return BinarySearch(Range, Value, TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename ProjectionType, typename SortPredicateType>
    [[nodiscard]] auto BinarySearchBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection, SortPredicateType SortPredicate) -> decltype(GetNum(Range))
    {
        auto CheckIndex = LowerBoundBy(Range, Value, Projection, SortPredicate);
        if (CheckIndex < GetNum(Range))
        {
            auto&& CheckValue = Invoke(Projection, GetData(Range)[CheckIndex]);
            // Since we returned lower bound we already know Value <= CheckValue. So if Value is not < CheckValue, they must be equal
            if (!SortPredicate(Value, CheckValue))
            {
                return CheckIndex;
            }
        }
        return INDEX_NONE;
    }
    template <typename RangeType, typename ValueType, typename ProjectionType>
    [[nodiscard]] UE_REWRITE auto BinarySearchBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection)
    {
        return BinarySearchBy(Range, Value, Projection, TLess<>());
    }
}