Range.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Containers/Array.h"
#include "Misc/AssertionMacros.h"
#include "Misc/DateTime.h"
#include "Math/RangeBound.h"
#include "Misc/FrameNumber.h"
#include "Serialization/Archive.h"
 
 
template<typename ElementType> class TRange
{
public:
 
    typedef TRangeBound<ElementType> BoundsType;
 
    /*~ Typedef used to pass/return small element types by value rather than const& */
    typedef typename TCallTraits<ElementType>::ParamType ElementValueOrConstRef;
 
    [[nodiscard]] TRange() { }
 
    [[nodiscard]] explicit TRange(ElementValueOrConstRef A)
        : LowerBound(BoundsType::Inclusive(A))
        , UpperBound(BoundsType::Inclusive(A))
    { }
    
    [[nodiscard]] explicit TRange(ElementValueOrConstRef A, ElementValueOrConstRef B)
        : LowerBound(BoundsType::Inclusive(A))
        , UpperBound(BoundsType::Exclusive(B))
    { }
 
    [[nodiscard]] explicit TRange(const BoundsType& InLowerBound, const BoundsType& InUpperBound)
        : LowerBound(InLowerBound)
        , UpperBound(InUpperBound)
    { }
    
public:
 
    [[nodiscard]] bool operator==(const TRange& Other) const
    {
        if (IsEmpty() && Other.IsEmpty())
        {
            return true;
        }
 
        return ((LowerBound == Other.LowerBound) && (UpperBound == Other.UpperBound));
    }
 
    [[nodiscard]] bool operator!=(const TRange& Other) const
    {
        if (IsEmpty() && Other.IsEmpty())
        {
            return false;
        }
 
        return ((LowerBound != Other.LowerBound) || (UpperBound != Other.UpperBound));
    }
    
public:
 
    [[nodiscard]] bool Adjoins(const TRange& Other) const
    {
        if (IsEmpty() || Other.IsEmpty())
        {
            return false;
        }
 
        if (!UpperBound.IsOpen() && !Other.LowerBound.IsOpen() && UpperBound.GetValue() == Other.LowerBound.GetValue())
        {
            return ((UpperBound.IsInclusive() && Other.LowerBound.IsExclusive()) ||
                    (UpperBound.IsExclusive() && Other.LowerBound.IsInclusive()));
        }
        
        if (!Other.UpperBound.IsOpen() && !LowerBound.IsOpen() && Other.UpperBound.GetValue() == LowerBound.GetValue())
        {
            return ((Other.UpperBound.IsInclusive() && LowerBound.IsExclusive()) ||
                    (Other.UpperBound.IsExclusive() && LowerBound.IsInclusive()));
        }
 
        return false;
    }
 
    [[nodiscard]] bool Conjoins(const TRange& X, const TRange& Y) const
    {
        if (X.Overlaps(Y))
        {
            return false;
        }
 
        return (Adjoins(X) && Adjoins(Y));
    }
    
    [[nodiscard]] bool Contains(ElementValueOrConstRef Element) const
    {
        return ((BoundsType::MinLower(LowerBound, Element) == LowerBound) &&
                (BoundsType::MaxUpper(UpperBound, Element) == UpperBound));
    }
    
    [[nodiscard]] bool Contains(const TRange& Other) const
    {
        return ((BoundsType::MinLower(LowerBound, Other.LowerBound) == LowerBound) &&
                (BoundsType::MaxUpper(UpperBound, Other.UpperBound) == UpperBound));
    }
 
    [[nodiscard]] bool Contiguous(const TRange& Other) const
    {
        return (Overlaps(Other) || Adjoins(Other));
    }
    
    [[nodiscard]] BoundsType GetLowerBound() const
    {
        return LowerBound;
    }
 
    void SetLowerBound(const BoundsType& NewLowerBound)
    {
        LowerBound = NewLowerBound;
    }
 
    void SetLowerBoundValue(ElementValueOrConstRef NewLowerBoundValue)
    {
        LowerBound.SetValue(NewLowerBoundValue);
    }
 
    [[nodiscard]] ElementValueOrConstRef GetLowerBoundValue() const
    {
        return LowerBound.GetValue();
    }
 
    [[nodiscard]] BoundsType GetUpperBound() const
    {
        return UpperBound;
    }
 
    void SetUpperBound(const BoundsType& NewUpperBound)
    {
        UpperBound = NewUpperBound;
    }
 
    void SetUpperBoundValue(ElementValueOrConstRef NewUpperBoundValue)
    {
        UpperBound.SetValue(NewUpperBoundValue);
    }
 
    [[nodiscard]] ElementValueOrConstRef GetUpperBoundValue() const
    {
        return UpperBound.GetValue();
    }
 
    [[nodiscard]] bool HasLowerBound() const
    {
        return LowerBound.IsClosed();
    }
    
    [[nodiscard]] bool HasUpperBound() const
    {
        return UpperBound.IsClosed();
    }
 
    [[nodiscard]] bool IsDegenerate() const
    {
        return (LowerBound.IsInclusive() && (LowerBound == UpperBound));
    }
    
    [[nodiscard]] bool IsEmpty() const
    {
        if (LowerBound.IsClosed() && UpperBound.IsClosed())
        {
            if (LowerBound.GetValue() > UpperBound.GetValue())
            {
                return true;
            }
 
            return ((LowerBound.GetValue() == UpperBound.GetValue()) && (LowerBound.IsExclusive() || UpperBound.IsExclusive()));
        }
 
        return false;
    }
 
    [[nodiscard]] bool Overlaps(const TRange& Other) const
    {
        if (IsEmpty() || Other.IsEmpty())
        {
            return false;
        }
 
        bool bUpperOpen = UpperBound.IsOpen() || Other.LowerBound.IsOpen();
        bool bLowerOpen = LowerBound.IsOpen() || Other.UpperBound.IsOpen();
        
        // true in the case that the bounds are open (default)
        bool bUpperValid = true;
        bool bLowerValid = true;
 
        if (!bUpperOpen)
        {
            bool bUpperGreaterThan = UpperBound.GetValue() > Other.LowerBound.GetValue();
            bool bUpperGreaterThanOrEqualTo = UpperBound.GetValue() >= Other.LowerBound.GetValue();
            bool bUpperBothInclusive = UpperBound.IsInclusive() && Other.LowerBound.IsInclusive();
 
            bUpperValid = bUpperBothInclusive ? bUpperGreaterThanOrEqualTo : bUpperGreaterThan;
        }
 
        if (!bLowerOpen)
        {
            bool bLowerLessThan = LowerBound.GetValue() < Other.UpperBound.GetValue();
            bool bLowerLessThanOrEqualTo = LowerBound.GetValue() <= Other.UpperBound.GetValue();
            bool bLowerBothInclusive = LowerBound.IsInclusive() && Other.UpperBound.IsInclusive();
 
            bLowerValid = bLowerBothInclusive ? bLowerLessThanOrEqualTo : bLowerLessThan;
        }
 
        return bUpperValid && bLowerValid;
    }
 
    template<typename DifferenceType>
    [[nodiscard]] DifferenceType Size() const
    {
        check(LowerBound.IsClosed() && UpperBound.IsClosed());
 
        return (UpperBound.GetValue() - LowerBound.GetValue());
    }
    
    [[nodiscard]] TArray<TRange> Split(ElementValueOrConstRef Element) const
    {
        TArray<TRange> Result;
        
        if (Contains(Element))
        {
            Result.Add(TRange(LowerBound, BoundsType::Exclusive(Element)));
            Result.Add(TRange(BoundsType::Inclusive(Element), UpperBound));
        }
        else
        {
            Result.Add(*this);
        }
        
        return Result;
    }
 
public:
 
    [[nodiscard]] static inline TArray<TRange> Difference(const TRange& X, const TRange& Y)
    {
        TArray<TRange> Result;
 
        if (X.Overlaps(Y))
        {
            TRange LowerRange = TRange(X.LowerBound, BoundsType::FlipInclusion(Y.LowerBound));
            TRange UpperRange = TRange(BoundsType::FlipInclusion(Y.UpperBound), X.UpperBound);
        
            if (!LowerRange.IsEmpty())
            {
                Result.Add(LowerRange);
            }
 
            if (!UpperRange.IsEmpty())
            {
                Result.Add(UpperRange);
            }
        }
        else
        {
            Result.Add(X);
        }
 
        return Result;
    }
 
    [[nodiscard]] static inline TRange Hull(const TRange& X, const TRange& Y)
    {
        if (X.IsEmpty())
        {
            return Y;
        }
 
        if (Y.IsEmpty())
        {
            return X;
        }
 
        return TRange(BoundsType::MinLower(X.LowerBound, Y.LowerBound), BoundsType::MaxUpper(X.UpperBound, Y.UpperBound));
    }
    
    [[nodiscard]] static inline TRange Hull(const TArray<TRange>& Ranges)
    {
        if (Ranges.Num() == 0)
        {
            return TRange::Empty();
        }
 
        TRange Bounds = Ranges[0];
 
        for (int32 i = 1; i < Ranges.Num(); ++i)
        {
            Bounds = Hull(Bounds, Ranges[i]);
        }
 
        return Bounds;
    }
 
    [[nodiscard]] static inline TRange Intersection(const TRange& X, const TRange& Y)
    {
        if (X.IsEmpty())
        {
            return TRange::Empty();
        }
 
        if (Y.IsEmpty())
        {
            return TRange::Empty();
        }
 
        return TRange(BoundsType::MaxLower(X.LowerBound, Y.LowerBound), BoundsType::MinUpper(X.UpperBound, Y.UpperBound));
    }
    
    [[nodiscard]] static inline TRange Intersection(const TArray<TRange>& Ranges)
    {
        if (Ranges.Num() == 0)
        {
            return TRange::Empty();
        }
 
        TRange Bounds = Ranges[0];
 
        for (int32 i = 1; i < Ranges.Num(); ++i)
        {
            Bounds = Intersection(Bounds, Ranges[i]);
        }
 
        return Bounds;
    }
 
    [[nodiscard]] static inline TArray<TRange> Union(const TRange& X, const TRange& Y)
    {
        TArray<TRange> OutRanges;
 
        if (X.Contiguous(Y))
        {
            OutRanges.Add(TRange(BoundsType::MinLower(X.LowerBound, Y.LowerBound), BoundsType::MaxUpper(X.UpperBound, Y.UpperBound)));
        }
        else
        {
            if (!X.IsEmpty())
            {
                OutRanges.Add(X);
            }
 
            if (!Y.IsEmpty())
            {
                OutRanges.Add(Y);
            }
        }
        
        return OutRanges;
    }
 
public:
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange All()
    {
        return TRange(BoundsType::Open(), BoundsType::Open());
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange AtLeast(ElementValueOrConstRef Value)
    {
        return TRange(BoundsType::Inclusive(Value), BoundsType::Open());
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange AtMost(ElementValueOrConstRef Value)
    {
        return TRange(BoundsType::Open(), BoundsType::Inclusive(Value));
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange Empty()
    {
        return TRange(BoundsType::Exclusive(ElementType()), BoundsType::Exclusive(ElementType()));
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange Exclusive(ElementValueOrConstRef Min, ElementValueOrConstRef Max)
    {
        return TRange(BoundsType::Exclusive(Min), BoundsType::Exclusive(Max));
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange GreaterThan(ElementValueOrConstRef Value)
    {
        return TRange(BoundsType::Exclusive(Value), BoundsType::Open());
    }
    
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange Inclusive(ElementValueOrConstRef Min, ElementValueOrConstRef Max)
    {
        return TRange(BoundsType::Inclusive(Min), BoundsType::Inclusive(Max));
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT TRange LessThan(ElementValueOrConstRef Value)
    {
        return TRange(BoundsType::Open(), BoundsType::Exclusive(Value));
    }
    
public:
 
    friend class FArchive& operator<<(class FArchive& Ar, TRange& Range)
    {
        return Ar << Range.LowerBound << Range.UpperBound;
    }
 
    friend uint32 GetTypeHash(const TRange& Range)
    {
        return (GetTypeHash(Range.LowerBound) + 23 * GetTypeHash(Range.UpperBound));
    }
 
private:
 
    BoundsType LowerBound;
 
    BoundsType UpperBound;
};
 
 
/* Default ranges for built-in types
 *****************************************************************************/
 
#define DEFINE_RANGE_WRAPPER_STRUCT(Name, ElementType) \
    struct Name : TRange<ElementType> \
    { \
    private: \
        typedef TRange<ElementType> Super; \
     \
    public: \
        Name() \
            : Super() \
        { \
        } \
         \
        Name(const Super& Rhs) \
            : Super(Rhs) \
        { \
        } \
         \
        explicit Name(ElementValueOrConstRef A) \
            : Super(A) \
        { \
        } \
         \
        explicit Name(ElementValueOrConstRef A, ElementValueOrConstRef B) \
            : Super(A, B) \
        { \
        } \
         \
        explicit Name(const TRangeBound<ElementType>& InLowerBound, const TRangeBound<ElementType>& InUpperBound) \
            : Super(InLowerBound, InUpperBound) \
        { \
        } \
         \
        TArray<Name> Split(ElementValueOrConstRef Element) const \
        { \
            return TArray<Name>(Super::Split(Element)); \
        } \
         \
        static UE_FORCEINLINE_HINT TArray<Name> Difference(const Name& X, const Name& Y) \
        { \
            return TArray<Name>(Super::Difference(X, Y)); \
        } \
         \
        static UE_FORCEINLINE_HINT Name Empty() \
        { \
            return Super::Empty(); \
        } \
         \
        static UE_FORCEINLINE_HINT Name Hull(const Name& X, const Name& Y) \
        { \
            return Super::Hull(X, Y); \
        } \
         \
        static UE_FORCEINLINE_HINT Name Hull(const TArray<Name>& Ranges) \
        { \
            return Super::Hull(reinterpret_cast<const TArray<Super>&>(Ranges)); \
        } \
         \
        static UE_FORCEINLINE_HINT Name Intersection(const Name& X, const Name& Y) \
        { \
            return Super::Intersection(X, Y); \
        } \
         \
        static UE_FORCEINLINE_HINT Name Intersection(const TArray<Name>& Ranges) \
        { \
            return Super::Intersection(reinterpret_cast<const TArray<Super>&>(Ranges)); \
        } \
         \
        static UE_FORCEINLINE_HINT TArray<Name> Union(const Name& X, const Name& Y) \
        { \
            return TArray<Name>(Super::Union(X, Y)); \
        } \
         \
        static UE_FORCEINLINE_HINT Name All() \
        { \
            return Super::All(); \
        } \
         \
        static UE_FORCEINLINE_HINT Name AtLeast(ElementValueOrConstRef Value) \
        { \
            return Super::AtLeast(Value); \
        } \
         \
        static UE_FORCEINLINE_HINT Name AtMost(ElementValueOrConstRef Value) \
        { \
            return Super::AtMost(Value); \
        } \
         \
        static UE_FORCEINLINE_HINT TRange GreaterThan(ElementValueOrConstRef Value) \
        { \
            return Super::GreaterThan(Value); \
        } \
         \
        static UE_FORCEINLINE_HINT TRange LessThan(ElementValueOrConstRef Value) \
        { \
            return Super::LessThan(Value); \
        } \
    }; \
     \
    template <> \
    struct TIsBitwiseConstructible<Name, TRange<ElementType>> \
    { \
        enum { Value = true }; \
    }; \
     \
    template <> \
    struct TIsBitwiseConstructible<TRange<ElementType>, Name> \
    { \
        enum { Value = true }; \
    };
 
DEFINE_RANGE_WRAPPER_STRUCT(FDateRange,   FDateTime)
DEFINE_RANGE_WRAPPER_STRUCT(FDoubleRange, double)
DEFINE_RANGE_WRAPPER_STRUCT(FFloatRange,  float)
DEFINE_RANGE_WRAPPER_STRUCT(FInt8Range,   int8)
DEFINE_RANGE_WRAPPER_STRUCT(FInt16Range,  int16)
DEFINE_RANGE_WRAPPER_STRUCT(FInt32Range,  int32)
DEFINE_RANGE_WRAPPER_STRUCT(FInt64Range,  int64)
DEFINE_RANGE_WRAPPER_STRUCT(FFrameNumberRange, FFrameNumber)