SparseIndexCollectionTypes.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
// partial port of geometry3sharp Indexing.cs
 
#pragma once
 
#include "IndexTypes.h"
 
#include <CoreMinimal.h>
 
 
namespace UE
{
namespace Geometry
{
 
class FIndexFlagSet
{
private:
    TOptional<TArray<bool>> Dense; // TODO: consider switching to bit array; but test first as performance of bit array may by significantly worse
    int DenseCount;      // only tracked for Dense
    TOptional<TSet<int>> Sparse;
 
public:
    FIndexFlagSet(bool bSetSparse = true, int MaxIndex = -1)
    {
        InitManual(bSetSparse, MaxIndex);
    }
 
    FIndexFlagSet(int MaxIndex, int SubsetCountEst)
    {
        InitAuto(MaxIndex, SubsetCountEst);
    }
 
    void InitAuto(int MaxIndex, int SubsetCountEst)
    {
        bool bSmall = MaxIndex < 32000;
        constexpr float PercentThresh = 0.05f;           
 
        InitManual(!bSmall && ((float)SubsetCountEst / (float)MaxIndex < PercentThresh), MaxIndex);
    }
 
    void InitManual(bool bSetSparse, int MaxIndex = -1)
    {
        if (bSetSparse)
        {
            Sparse = TSet<int>();
        }
        else
        {
            Dense = TArray<bool>();
            check(MaxIndex >= 0);
            Dense->SetNumZeroed(FMath::Max(0, MaxIndex));
        }
        DenseCount = 0;
    }
 
    inline bool Contains(int Index) const
    {
        if (Dense.IsSet())
        {
            return Dense.GetValue()[Index];
        }
        else
        {
            check(Sparse.IsSet());
            return Sparse->Contains(Index);
        }
    }
 
    inline void Add(int Index)
    {
        if (Dense.IsSet())
        {
            bool &Value = Dense.GetValue()[Index];
            if (!Value)
            {
                Value = true;
                DenseCount++;
            }
        }
        else
        {
            check(Sparse.IsSet());
            Sparse->Add(Index);
        }
    }
 
    inline void Remove(int Index)
    {
        if (Dense.IsSet())
        {
            bool &Value = Dense.GetValue()[Index];
            if (Value)
            {
                Value = false;
                DenseCount--;
            }
        }
        else
        {
            check(Sparse.IsSet());
            Sparse->Remove(Index);
        }
    }
 
    inline int Count() const
    {
        if (Dense.IsSet())
        {
            return DenseCount;
        }
        else
        {
            return Sparse->Num();
        }
    }
 
    inline const bool operator[](unsigned int Index) const
    {
        return Contains(Index);
    }
    
 
    // TODO: iterator support
 
};
 
struct FOptionallySparseIndexMap
{
    // storage used when map is dense
    TArray<int> Dense;
    // storage used when map is sparse
    TMap<int, int> Sparse;
 
    // mapping to assign defaults for indices that are not explicitly assigned; computed as Index*DefaultScale + DefaultOffset
    int DefaultOffset = -1, DefaultScale = 0;
 
    // max index in map; -1 will leave the map unbounded (invalid for Dense maps)
    int MaxIndex = -1;
 
    // different kinds of storage that could be used for the map
    enum class EMapType : uint8
    {
        Dense, Sparse, ScaleAndOffset
    };
 
    // choice of storage backing the map
    EMapType MapType = EMapType::Sparse;
 
    FOptionallySparseIndexMap()
    {}
 
    FOptionallySparseIndexMap(EMapType MapType, int MaxIndex = -1) : MaxIndex(MaxIndex), MapType(MapType)
    {
        if (MapType == EMapType::Dense)
        {
            check(MaxIndex > -1);
            Dense.SetNum(MaxIndex);
            InitDefaults();
        }
    }
 
    FOptionallySparseIndexMap(TArray<int> Dense, int MaxIndex = -1) : Dense(Dense), MaxIndex(MaxIndex), MapType(EMapType::Dense)
    {
    }
 
    FOptionallySparseIndexMap(int MaxIndex, int SubsetCountEst)
    {
        Initialize(MaxIndex, SubsetCountEst);
    }
 
    void Initialize(int MaxIndexIn, int SubsetCountEst)
    {
        Dense.Reset();
        Sparse.Reset();
        MaxIndex = MaxIndexIn;
 
        // if buffer is less than threshold, just use dense map
        bool bSmall = MaxIndex < 32000;
        float fPercent = (float)SubsetCountEst / (float)MaxIndex;
        float fPercentThresh = 0.1f;
 
        if (bSmall || fPercent > fPercentThresh)
        {
            Dense.SetNum(MaxIndex);
            MapType = EMapType::Dense;
        }
        else
        {
            MapType = EMapType::Sparse;
        }
        
        InitDefaults();
    }
 
    static FOptionallySparseIndexMap IdentityMap(int MaxIndex = -1)
    {
        FOptionallySparseIndexMap ToRet(EMapType::ScaleAndOffset, MaxIndex);
        ToRet.DefaultScale = 1;
        ToRet.DefaultOffset = 0;
        return ToRet;
    }
    
    static FOptionallySparseIndexMap ConstantMap(int ConstantValue, int MaxIndex = -1)
    {
        FOptionallySparseIndexMap ToRet(EMapType::ScaleAndOffset, MaxIndex);
        ToRet.DefaultScale = 0;
        ToRet.DefaultOffset = ConstantValue;
        return ToRet;
    }
 
    static FOptionallySparseIndexMap SparseIdentityMap(int MaxIndex = -1)
    {
        FOptionallySparseIndexMap ToRet(EMapType::Sparse, MaxIndex);
        ToRet.DefaultScale = 1;
        ToRet.DefaultOffset = 0;
        return ToRet;
    }
 
 
    /* Initialize default values for dense map (sparse defaults are computed on the fly) */
    void InitDefaults()
    {
        if (MapType == EMapType::Dense)
        {
            for (int i = 0; i < Dense.Num(); ++i)
            {
                Dense[i] = i*DefaultScale + DefaultOffset;
            }
        }
    }
 
    inline bool BadIndex(int Index) const
    {
        return (Index < 0) || (MaxIndex >= 0 && Index >= MaxIndex);
    }
 
    bool Contains(int Index)
    {
        if (BadIndex(Index))
        {
            return false;
        }
        switch (MapType)
        {
        case EMapType::Dense:
            return Dense[Index] >= 0;
        case EMapType::Sparse:
            return Sparse.Contains(Index) || (Index * DefaultScale + DefaultOffset >= 0);
        case EMapType::ScaleAndOffset:
            return Index * DefaultScale + DefaultOffset >= 0;
        }
        check(false);
        return false;
    }
 
    inline const int operator[](int Index) const
    {
        if (BadIndex(Index))
        {
            return IndexConstants::InvalidID;
        }
        switch (MapType)
        {
        case EMapType::Dense:
            return Dense[Index];
        case EMapType::Sparse:
        {
            const int *Value = Sparse.Find(Index);
            return Value ? (*Value) : (Index * DefaultScale + DefaultOffset);
        }
        case EMapType::ScaleAndOffset:
            return Index * DefaultScale + DefaultOffset;
        }
        check(false);
        return IndexConstants::InvalidID;
    }
 
    void Unset(int Index)
    {
        check(!BadIndex(Index));
        if (MapType == EMapType::Dense)
        {
            Dense[Index] = Index*DefaultScale + DefaultOffset;
        }
        else
        {
            Sparse.Remove(Index);
        }
    }
 
    void Set(int Index, int Value)
    {
        check(!BadIndex(Index));
        check(MapType != EMapType::ScaleAndOffset);
        if (MapType == EMapType::Dense)
        {
            Dense[Index] = Value;
        }
        else
        {
            Sparse.FindOrAdd(Index) = Value;
        }
    }
 
    inline void SetInvalid(int Index)
    {
        Set(Index, IndexConstants::InvalidID);
    }
};
 
} // end namespace UE::Geometry
} // end namespace UE