UniqueIndexSet.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Array.h"
#include "CoreMinimal.h"
#include "HAL/Platform.h"
#include "HAL/PlatformCrt.h"
#include "HAL/UnrealMemory.h"
#include "Templates/UnrealTemplate.h"
 
namespace UE
{
namespace Geometry
{
 
class FUniqueIndexSet
{
    // TODO: second bit set that tracks which blocks of ints have been set.
    // This would allow for clears to be much quicker for subsets.
    // (would want to profile to see that it helps, but the bit set is still 0.125mb per million indices,
    // which isn't a trivial amount to set to zero...)
 
    // TODO: alternately, use a TSet instead of Bits array if we know that the number 
    // of values we are going to add is very small? This would avoid clears.
 
    // TODO: AtomicAdd()
 
    // TODO: support growing bit set
 
public:
    GEOMETRYCORE_API ~FUniqueIndexSet();
 
    inline void Initialize(int32 MaxIndexIn, int32 MaxValuesHint = 0)
    {
        this->MaxIndex = MaxIndexIn;
        int32 NeedWords = (MaxIndex / 64) + 1;
        if (NumWords < NeedWords)
        {
            if (Bits != nullptr)
            {
                delete[] Bits;
            }
            NumWords = NeedWords;
            Bits = new int64[NumWords];
        }
        FMemory::Memset(&Bits[0], (uint8)0, NeedWords * 8);
        Values.Reset();
        Values.Reserve(MaxValuesHint);
    }
 
    inline const int32 Num() const { return Values.Num(); }
 
    inline const TArray<int32>& Indices() const { return Values; }
 
    inline bool Add(int32 Index)
    {
        int64& Word = Bits[(int64)(Index / 64)];
        int64 Offset = (int64)(Index % 64);
        int64 Mask = (int64)1 << Offset;
        if ( (Word & Mask) == 0 )
        {
            Word |= Mask;
            Values.Add(Index);
            return true;
        }
        return false;
    }
 
    inline bool Contains(int32 Index) const
    {
        const int64& Word = Bits[(int64)(Index / 64)];
        int64 Offset = (int64)(Index % 64);
        int64 Mask = (int64)1 << Offset;
        return (Word & Mask) != 0;
    }
 
    template<typename ArrayType>
    void Collect(ArrayType& Storage) const
    {
        Storage.Reserve(Values.Num());
        for (int32 Value : Values)
        {
            Storage.Add(Value);
        }
    }
 
    inline TArray<int32>&& TakeValues()
    {
        return MoveTemp(Values);
    }
 
    inline void SwapValuesWith(TArray<int32>& OtherArray)
    {
        TArray<int32> Tmp = MoveTemp(Values);
        Values = MoveTemp(OtherArray);
        OtherArray = MoveTemp(Tmp);
    }
 
 
public:
    // range-for support. Do not directly call these functions.
    inline TArray<int32>::RangedForConstIteratorType begin() const { return Values.begin(); }
    inline TArray<int32>::RangedForConstIteratorType end() const { return Values.end(); }
 
 
protected:
    int32 MaxIndex;
    TArray<int32> Values;
    int64* Bits = nullptr;
    int32 NumWords = 0;
};
 
 
} // end namespace UE::Geometry
} // end namespace UE