BinarySearch.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "uLang/Common/Common.h"
#include "uLang/Common/Templates/IdentityFunctor.h"
#include "uLang/Common/Templates/Sorting.h"
 
// nb: this was copied over from Core until uLang can properly depend on Core.
 
namespace uLang
{
namespace AlgoImpl
{
    template <typename RangeValueType, typename SizeType, typename PredicateValueType, typename ProjectionType, typename SortPredicateType>
    ULANG_FORCEINLINE 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>
    ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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]] ULANG_FORCEINLINE 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 IndexNone;
    }
    template <typename RangeType, typename ValueType>
    [[nodiscard]] ULANG_FORCEINLINE auto BinarySearch(const RangeType& Range, const ValueType& Value)
    {
        return BinarySearch(Range, Value, TLess<>());
    }
 
    template <typename RangeType, typename ValueType, typename ProjectionType, typename SortPredicateType>
    [[nodiscard]] ULANG_FORCEINLINE 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 IndexNone;
    }
    template <typename RangeType, typename ValueType, typename ProjectionType>
    [[nodiscard]] ULANG_FORCEINLINE auto BinarySearchBy(const RangeType& Range, const ValueType& Value, ProjectionType Projection)
    {
        return BinarySearchBy(Range, Value, Projection, TLess<>());
    }
}
}