Compare.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Templates/EqualTo.h"
#include "Templates/IdentityFunctor.h"
#include "Templates/Invoke.h"
#include "Templates/Less.h"
#include "Templates/UnrealTemplate.h"
 
namespace Algo::Private
{
    template <typename InAT, typename InBT, typename ProjectionT, typename PredicateT>
    constexpr bool Compare(const InAT& InputA, const InBT& InputB, ProjectionT Projection, PredicateT Predicate)
    {
        const SIZE_T SizeA = GetNum(InputA);
        const SIZE_T SizeB = GetNum(InputB);
 
        if (SizeA != SizeB)
        {
            return false;
        }
 
        auto* A = GetData(InputA);
        auto* B = GetData(InputB);
 
        for (SIZE_T Count = SizeA; Count; --Count)
        {
            if (!Invoke(Predicate, Invoke(Projection, *A++), Invoke(Projection, *B++)))
            {
                return false;
            }
        }
 
        return true;
    }
}
 
namespace Algo
{
    template <typename InAT, typename InBT>
    [[nodiscard]] constexpr bool Compare(const InAT& InputA, const InBT& InputB)
    {
        return Private::Compare(InputA, InputB, FIdentityFunctor(), TEqualTo<>());
    }
 
    template <typename InAT, typename InBT, typename PredicateT>
    [[nodiscard]] constexpr bool Compare(const InAT& InputA, const InBT& InputB, PredicateT Predicate)
    {
        return Private::Compare(InputA, InputB, FIdentityFunctor(), MoveTemp(Predicate));
    }
 
    template <typename InAT, typename InBT, typename ProjectionT>
    [[nodiscard]] constexpr bool CompareBy(const InAT& InputA, const InBT& InputB, ProjectionT Projection)
    {
        return Private::Compare(InputA, InputB, MoveTemp(Projection), TEqualTo<>());
    }
 
    template <typename InAT, typename InBT, typename ProjectionT, typename PredicateT>
    [[nodiscard]] constexpr bool CompareBy(const InAT& InputA, const InBT& InputB, ProjectionT Projection, PredicateT Predicate)
    {
        return Private::Compare(InputA, InputB, MoveTemp(Projection), MoveTemp(Predicate));
    }
 
    template <typename MapType, typename KeyLessThanType, typename ValueLessThanType>
    [[nodiscard]] int CompareMap(const MapType& A, const MapType& B, KeyLessThanType KeyLessThan, ValueLessThanType ValueLessThan)
    {
        using KeyType = typename MapType::KeyType;
        using ValueType = typename MapType::ValueType;
        if (A.Num() != B.Num())
        {
            return A.Num() < B.Num() ? -1 : 1;
        }
        if (A.Num() == 0)
        {
            return 0;
        }
 
        bool bAllKeysOfAAreInB = true;
        const KeyType* MinKeyWithDifference = nullptr;
        bool bMinKeyIsLessInA = false;
        for (const auto& Pair : A) // TPair<KeyType, ValueType>
        {
            const ValueType* BValue = B.Find(Pair.Key);
            int Compare = 0;
            if (!BValue)
            {
                bAllKeysOfAAreInB = false;
                Compare = -1;
            }
            else if (ValueLessThan(Pair.Value, *BValue))
            {
                Compare = -1;
            }
            else if (ValueLessThan(*BValue, Pair.Value))
            {
                Compare = 1;
            }
            if (Compare != 0)
            {
                if (!MinKeyWithDifference || KeyLessThan(Pair.Key, *MinKeyWithDifference))
                {
                    MinKeyWithDifference = &Pair.Key;
                    bMinKeyIsLessInA = Compare < 0;
                }
            }
        }
 
        // The number of keys in A and B is the same (checked above), so if all keys of A are in B, then there are
        // no additional keys in B that are not in A and we don't need to iterate over B.
        if (!bAllKeysOfAAreInB)
        {
            // If B has additional keys not in A then we need to check each of those not-in-A keys to see if they
            // are smaller than the MinKeyWithDifference, and if so they become the MinKeyWithDifference.
            for (const auto& Pair : B) // TPair<KeyType, ValueType>
            {
                if (!A.Contains(Pair.Key))
                {
                    if (!MinKeyWithDifference || KeyLessThan(Pair.Key, *MinKeyWithDifference))
                    {
                        MinKeyWithDifference = &Pair.Key;
                        bMinKeyIsLessInA = false;
                    }
                }
            }
        }
        if (MinKeyWithDifference)
        {
            return bMinKeyIsLessInA ? -1 : 1;
        }
        return 0;
    }
 
    template <typename MapType>
    [[nodiscard]] int CompareMap(const MapType& A, const MapType& B)
    {
        return CompareMap(A, B, TLess<>(), TLess<>());
    }
 
    template <typename MapType, typename KeyLessThanType>
    [[nodiscard]] int CompareMap(const MapType& A, const MapType& B, KeyLessThanType KeyLessThan)
    {
        return CompareMap(A, B, MoveTempIfPossible(KeyLessThan), TLess<>());
    }
 
    template <typename SetType, typename KeyLessThanType>
    [[nodiscard]] int CompareSet(const SetType& A, const SetType& B, KeyLessThanType KeyLessThan)
    {
        using KeyType = typename SetType::ElementType;
        if (A.Num() != B.Num())
        {
            return A.Num() < B.Num() ? -1 : 1;
        }
        if (A.Num() == 0)
        {
            return 0;
        }
 
        const KeyType* MinKeyWithDifference = nullptr;
        bool bMinKeyIsLessInA = false;
        for (const KeyType& AKey : A)
        {
            if (!B.Contains(AKey))
            {
                if (!MinKeyWithDifference || KeyLessThan(AKey, *MinKeyWithDifference))
                {
                    MinKeyWithDifference = &AKey;
                    bMinKeyIsLessInA = true;
                }
            }
        }
 
        // The number of keys in A and B is the same (checked above), so if all keys of A are in B, then there are
        // no additional keys in B that are not in A and we don't need to iterate over B.
        if (MinKeyWithDifference)
        {
            // If B has additional keys not in A then we need to check each of those not-in-A keys to see if they
            // are smaller than the MinKeyWithDifference, and if so they become the MinKeyWithDifference.
            for (const KeyType& BKey : B)
            {
                if (!A.Contains(BKey))
                {
                    if (!MinKeyWithDifference || KeyLessThan(BKey, *MinKeyWithDifference))
                    {
                        MinKeyWithDifference = &BKey;
                        bMinKeyIsLessInA = false;
                    }
                }
            }
        }
        if (MinKeyWithDifference)
        {
            return bMinKeyIsLessInA ? -1 : 1;
        }
        return 0;
    }
 
    template <typename SetType>
    [[nodiscard]] int CompareSet(const SetType& A, const SetType& B)
    {
        return CompareSet(A, B, TLess<>());
    }
}