SparseSet.h.inl

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#ifndef UE_TSPARSE_SET
#error "SparseSet.h.inl should only be included after defining UE_TSPARSE_SET"
#endif
 
#include "Containers/ContainerAllocationPolicies.h"
#include "Containers/ContainerElementTypeCompatibility.h"
#include "Containers/SetUtilities.h"
#include "Containers/SparseArray.h"
#include "Containers/SparseSetElement.h"
#include "ContainersFwd.h"
#include "Math/UnrealMathUtility.h"
#include "Misc/AssertionMacros.h"
#include "Misc/StructBuilder.h"
#include "Serialization/MemoryImageWriter.h"
#include "Serialization/StructuredArchive.h"
#include "Templates/Function.h"
#include "Templates/RetainedRef.h"
#include "Templates/Sorting.h"
#include "Templates/TypeHash.h"
#include "Templates/UnrealTemplate.h"
#include "Traits/IsTriviallyRelocatable.h"
#include <initializer_list>
#include <type_traits>
 
template <typename AllocatorType>
class TScriptSparseSet;
 
#define TSETPRIVATEFRIEND PREPROCESSOR_JOIN(UE_TSPARSE_SET, PrivateFriend)
 
template<
    typename InElementType,
    typename KeyFuncs /*= DefaultKeyFuncs<ElementType>*/,
    typename Allocator /*= FDefaultSparseSetAllocator*/
    >
class UE_TSPARSE_SET
{
public:
    typedef InElementType ElementType;
    typedef KeyFuncs    KeyFuncsType;
    typedef Allocator   AllocatorType;
 
    using SizeType = typename Allocator::SparseArrayAllocator::ElementAllocator::SizeType;
 
    static_assert(std::is_same_v<SizeType, int32>, "UE_TSPARSE_SET currently only supports 32-bit allocators");
 
private:
    using USizeType = std::make_unsigned_t<SizeType>;
 
    template <typename>
    friend class TScriptSparseSet;
 
    typedef typename KeyFuncs::KeyInitType     KeyInitType;
    typedef typename KeyFuncs::ElementInitType ElementInitType;
 
    typedef TSparseSetElement<InElementType> SetElementType;
 
public:
    [[nodiscard]] UE_FORCEINLINE_HINT constexpr UE_TSPARSE_SET() = default;
 
    [[nodiscard]] explicit consteval UE_TSPARSE_SET(EConstEval)
    : Elements(ConstEval)
    , Hash(ConstEval)
    {
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT UE_TSPARSE_SET(const UE_TSPARSE_SET& Copy)
    {
        *this = Copy;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT explicit UE_TSPARSE_SET(TArrayView<const ElementType> InArrayView)
    {
        Append(InArrayView);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT explicit UE_TSPARSE_SET(TArray<ElementType>&& InArray)
    {
        Append(MoveTemp(InArray));
    }
 
    UE_FORCEINLINE_HINT ~UE_TSPARSE_SET()
    {
        UE_STATIC_ASSERT_WARN(TIsTriviallyRelocatable_V<InElementType>, "TSet can only be used with trivially relocatable types");
        HashSize = 0;
    }
 
    // Start - intrusive TOptional<UE_TSPARSE_SET> state //
    constexpr static bool bHasIntrusiveUnsetOptionalState = true;
    using IntrusiveUnsetOptionalStateType = UE_TSPARSE_SET;
 
    [[nodiscard]] explicit UE_TSPARSE_SET(FIntrusiveUnsetOptionalState Tag)
        : Elements(Tag)
    {
    }
    [[nodiscard]] bool operator==(FIntrusiveUnsetOptionalState Tag) const
    {
        return Elements == Tag;
    }
    // End - intrusive TOptional<UE_TSPARSE_SET> state //
 
    UE_TSPARSE_SET& operator=(const UE_TSPARSE_SET& Copy)
    {
        if (this != &Copy)
        {
            UE::Core::Private::CopyHash(Hash, HashSize, Copy.Hash, Copy.HashSize);
 
            Elements = Copy.Elements;
        }
        return *this;
    }
 
private:
    template <typename SetType>
    static inline void Move(SetType& ToSet, SetType& FromSet)
    {
        ToSet.Elements = (ElementArrayType&&)FromSet.Elements;
 
        ToSet.Hash.MoveToEmpty(FromSet.Hash);
 
        ToSet  .HashSize = FromSet.HashSize;
        FromSet.HashSize = 0;
    }
 
public:
    [[nodiscard]] UE_TSPARSE_SET(std::initializer_list<ElementType> InitList)
        : HashSize(0)
    {
        Append(InitList);
    }
 
    [[nodiscard]] UE_TSPARSE_SET(UE_TSPARSE_SET&& Other)
        : HashSize(0)
    {
        this->Move(*this, Other);
    }
 
    UE_TSPARSE_SET& operator=(UE_TSPARSE_SET&& Other)
    {
        if (this != &Other)
        {
            this->Move(*this, Other);
        }
 
        return *this;
    }
 
    template<typename OtherAllocator>
    [[nodiscard]] UE_TSPARSE_SET(UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>&& Other)
        : HashSize(0)
    {
        Append(MoveTemp(Other));
    }
 
    template<typename OtherAllocator>
    [[nodiscard]] UE_TSPARSE_SET(const UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>& Other)
        : HashSize(0)
    {
        Append(Other);
    }
 
    template<typename OtherAllocator>
    UE_TSPARSE_SET& operator=(UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>&& Other)
    {
        Reset();
        Append(MoveTemp(Other));
        return *this;
    }
 
    template<typename OtherAllocator>
    UE_TSPARSE_SET& operator=(const UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>& Other)
    {
        Reset();
        Append(Other);
        return *this;
    }
 
    UE_TSPARSE_SET& operator=(std::initializer_list<ElementType> InitList)
    {
        Reset();
        Append(InitList);
        return *this;
    }
 
    void Empty(int32 ExpectedNumElements = 0)
    {
        // Empty the elements array, and reallocate it for the expected number of elements.
        const int32 DesiredHashSize = Allocator::GetNumberOfHashBuckets(ExpectedNumElements);
        const bool ShouldDoRehash = ShouldRehash(ExpectedNumElements, DesiredHashSize, EAllowShrinking::Yes);
 
        if (!ShouldDoRehash)
        {
            // If the hash was already the desired size, clear the references to the elements that have now been removed.
            UnhashElements();
        }
 
        Elements.Empty(ExpectedNumElements);
 
        // Resize the hash to the desired size for the expected number of elements.
        if (ShouldDoRehash)
        {
            HashSize = DesiredHashSize;
            Rehash();
        }
    }
 
    void Reset()
    {
        if (Num() == 0)
        {
            return;
        }
 
        // Reset the elements array.
        UnhashElements();
        Elements.Reset();
    }
 
    inline void Shrink()
    {
        Elements.Shrink();
        Relax();
    }
 
    inline void Compact()
    {
        if (Elements.Compact())
        {
            HashSize = Allocator::GetNumberOfHashBuckets(Elements.Num());
            Rehash();
        }
    }
 
    inline void CompactStable()
    {
        if (Elements.CompactStable())
        {
            HashSize = Allocator::GetNumberOfHashBuckets(Elements.Num());
            Rehash();
        }
    }
 
    inline void Reserve(int32 Number)
    {
        // makes sense only when Number > Elements.Num() since TSparseArray::Reserve
        // does any work only if that's the case
        if ((USizeType)Number > (USizeType)Elements.Num())
        {
            // Trap negative reserves
            if (Number < 0)
            {
                UE::Core::Private::OnInvalidSetNum((unsigned long long)Number);
            }
 
            // Preallocates memory for array of elements
            Elements.Reserve(Number);
 
            // Calculate the corresponding hash size for the specified number of elements.
            const int32 NewHashSize = Allocator::GetNumberOfHashBuckets(Number);
 
            // If the hash hasn't been created yet, or is smaller than the corresponding hash size, rehash
            // to force a preallocation of the hash table
            if(!HashSize || HashSize < NewHashSize)
            {
                HashSize = NewHashSize;
                Rehash();
            }
        }
    }
 
    UE_FORCEINLINE_HINT void Relax()
    {
        ConditionalRehash(Elements.Num(), EAllowShrinking::Yes);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT SIZE_T GetAllocatedSize( void ) const
    {
        return Elements.GetAllocatedSize() + Hash.GetAllocatedSize(HashSize, sizeof(FSetElementId));
    }
 
    inline void CountBytes(FArchive& Ar) const
    {
        Elements.CountBytes(Ar);
        Ar.CountBytes(HashSize * sizeof(int32),HashSize * sizeof(FSetElementId));
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return Elements.IsEmpty();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Num() const
    {
        return Elements.Num();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Max() const
    {
        return Elements.Max();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 GetMaxIndex() const
    {
        return Elements.GetMaxIndex();
    }
 
    [[nodiscard]] inline bool IsValidId(FSetElementId Id) const
    {
        SizeType Index = Id.AsInteger();
        return Index != INDEX_NONE &&
            Index >= 0 &&
            Index < Elements.GetMaxIndex() &&
            Elements.IsAllocated(Index);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType& operator[](FSetElementId Id)
    {
        return Elements[Id.AsInteger()].Value;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType& operator[](FSetElementId Id) const
    {
        return Elements[Id.AsInteger()].Value;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType& Get(FSetElementId Id)
    {
        return Elements[Id.AsInteger()].Value;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType& Get(FSetElementId Id) const
    {
        return Elements[Id.AsInteger()].Value;
    }
 
    UE_FORCEINLINE_HINT FSetElementId Add(const InElementType&  InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return Emplace(InElement, bIsAlreadyInSetPtr);
    }
    UE_FORCEINLINE_HINT FSetElementId Add(InElementType&& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return Emplace(MoveTempIfPossible(InElement), bIsAlreadyInSetPtr);
    }
 
    UE_FORCEINLINE_HINT ElementType& FindOrAdd(const InElementType& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return FindOrAddByHash(KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(InElement)), InElement, bIsAlreadyInSetPtr);
    }
    UE_FORCEINLINE_HINT ElementType& FindOrAdd(InElementType&& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return FindOrAddByHash(KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(InElement)), MoveTempIfPossible(InElement), bIsAlreadyInSetPtr);
    }
 
    UE_FORCEINLINE_HINT FSetElementId AddByHash(uint32 KeyHash, const InElementType& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return EmplaceByHash(KeyHash, InElement, bIsAlreadyInSetPtr);
    }
    UE_FORCEINLINE_HINT FSetElementId AddByHash(uint32 KeyHash,      InElementType&& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        return EmplaceByHash(KeyHash, MoveTempIfPossible(InElement), bIsAlreadyInSetPtr);
    }
 
    template <typename ElementReferenceType>
    ElementType& FindOrAddByHash(uint32 KeyHash, ElementReferenceType&& InElement, bool* bIsAlreadyInSetPtr = nullptr)
    {
        SizeType ExistingIndex = FindIndexByHash(KeyHash, KeyFuncs::GetSetKey(InElement));
        bool bIsAlreadyInSet = ExistingIndex != INDEX_NONE;
        if (bIsAlreadyInSetPtr)
        {
            *bIsAlreadyInSetPtr = bIsAlreadyInSet;
        }
        if (bIsAlreadyInSet)
        {
            return Elements[ExistingIndex].Value;
        }
 
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ElementReferenceType>(InElement));
        RehashOrLink(KeyHash, Element, ElementAllocation.Index);
        return Element.Value;
    }
 
private:
    bool TryReplaceExisting(uint32 KeyHash, SetElementType& Element, SizeType& InOutElementIndex, bool* bIsAlreadyInSetPtr)
    {
        bool bIsAlreadyInSet = false;
        if constexpr (!KeyFuncs::bAllowDuplicateKeys)
        {
            // If the set doesn't allow duplicate keys, check for an existing element with the same key as the element being added.
 
            // Don't bother searching for a duplicate if this is the first element we're adding
            if (Elements.Num() != 1)
            {
                SizeType ExistingIndex = FindIndexByHash(KeyHash, KeyFuncs::GetSetKey(Element.Value));
                bIsAlreadyInSet = ExistingIndex != INDEX_NONE;
                if (bIsAlreadyInSet)
                {
                    // If there's an existing element with the same key as the new element, replace the existing element with the new element.
                    MoveByRelocate(Elements[ExistingIndex].Value, Element.Value);
 
                    // Then remove the new element.
                    Elements.RemoveAtUninitialized(InOutElementIndex);
 
                    // Then point the return value at the replaced element.
                    InOutElementIndex = ExistingIndex;
                }
            }
        }
        if (bIsAlreadyInSetPtr)
        {
            *bIsAlreadyInSetPtr = bIsAlreadyInSet;
        }
        return bIsAlreadyInSet;
    }
 
    inline void RehashOrLink(uint32 KeyHash, SetElementType& Element, SizeType ElementIndex)
    {
        // Check if the hash needs to be resized.
        if (!ConditionalRehash(Elements.Num(), EAllowShrinking::No))
        {
            // If the rehash didn't add the new element to the hash, add it.
            LinkElement(ElementIndex, Element, KeyHash);
        }
    }
 
public:
    template <typename ArgType = ElementType>
    FSetElementId Emplace(ArgType&& Arg, bool* bIsAlreadyInSetPtr = nullptr)
    {
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ArgType>(Arg));
 
        SizeType NewHashIndex = ElementAllocation.Index;
 
        uint32 KeyHash = KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(Element.Value));
        if (!TryReplaceExisting(KeyHash, Element, NewHashIndex, bIsAlreadyInSetPtr))
        {
            RehashOrLink(KeyHash, Element, NewHashIndex);
        }
        return FSetElementId::FromInteger(NewHashIndex);
    }
 
    template <typename... ArgTypes>
    TPair<FSetElementId, bool> Emplace(EInPlace, ArgTypes&&... InArgs)
    {
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ArgTypes>(InArgs)...);
 
        SizeType NewHashIndex = ElementAllocation.Index;
        const uint32 KeyHash = KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(Element.Value));
 
        bool bAlreadyInSet = false;
        if (!TryReplaceExisting(KeyHash, Element, NewHashIndex, &bAlreadyInSet))
        {
            RehashOrLink(KeyHash, Element, NewHashIndex);
        }
 
        return TPair<FSetElementId, bool>(FSetElementId::FromInteger(NewHashIndex), bAlreadyInSet);
    }
    
    template <typename ArgType = ElementType>
    FSetElementId EmplaceByHash(uint32 KeyHash, ArgType&& Args, bool* bIsAlreadyInSetPtr = nullptr)
    {
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ArgType>(Args));
 
        SizeType NewHashIndex = ElementAllocation.Index;
 
        if (!TryReplaceExisting(KeyHash, Element, NewHashIndex, bIsAlreadyInSetPtr))
        {
            RehashOrLink(KeyHash, Element, NewHashIndex);
        }
        return FSetElementId::FromInteger(NewHashIndex);
    }
 
    template <typename... ArgTypes>
    TPair<FSetElementId, bool> EmplaceByHash(EInPlace, uint32 KeyHash, ArgTypes&&... InArgs)
    {
        // Create a new element.
        FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
        SetElementType& Element = *new (ElementAllocation) SetElementType(Forward<ArgTypes>(InArgs)...);
 
        SizeType NewHashIndex = ElementAllocation.Index;
        bool bAlreadyInSet = false;
        if (!TryReplaceExisting(KeyHash, Element, NewHashIndex, &bAlreadyInSet))
        {
            RehashOrLink(KeyHash, Element, NewHashIndex);
        }
        return TPair<FSetElementId, bool>(FSetElementId::FromInteger(NewHashIndex), bAlreadyInSet);
    }
 
    void Append(TArrayView<const ElementType> InElements)
    {
        Reserve(Elements.Num() + InElements.Num());
        for (const ElementType& Element : InElements)
        {
            Add(Element);
        }
    }
 
    template<typename ArrayAllocator>
    void Append(TArray<ElementType, ArrayAllocator>&& InElements)
    {
        Reserve(Elements.Num() + InElements.Num());
        for (ElementType& Element : InElements)
        {
            Add(MoveTempIfPossible(Element));
        }
        InElements.Reset();
    }
 
    template<typename OtherAllocator>
    void Append(const UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>& OtherSet)
    {
        Reserve(Elements.Num() + OtherSet.Num());
        for (const ElementType& Element : OtherSet)
        {
            Add(Element);
        }
    }
 
    template<typename OtherAllocator>
    void Append(UE_TSPARSE_SET<ElementType, KeyFuncs, OtherAllocator>&& OtherSet)
    {
        Reserve(Elements.Num() + OtherSet.Num());
        for (ElementType& Element : OtherSet)
        {
            Add(MoveTempIfPossible(Element));
        }
        OtherSet.Reset();
    }
 
    void Append(std::initializer_list<ElementType> InitList)
    {
        Reserve(Elements.Num() + (int32)InitList.size());
        for (const ElementType& Element : InitList)
        {
            Add(Element);
        }
    }
 
private:
    void RemoveByIndex(SizeType ElementIndex)
    {
        checkf(Elements.IsValidIndex(ElementIndex), TEXT("Invalid ElementIndex passed to UE_TSPARSE_SET::RemoveByIndex"));
 
        const SetElementType& ElementBeingRemoved = Elements[ElementIndex];
 
        // Remove the element from the hash.
        FSetElementId* HashPtr              = Hash.GetAllocation();
        FSetElementId* NextElementIndexIter = &HashPtr[ElementBeingRemoved.HashIndex];
        for (;;)
        {
            SizeType NextElementIndex = NextElementIndexIter->AsInteger();
            checkf(NextElementIndex != INDEX_NONE, TEXT("Corrupt hash"));
 
            if (NextElementIndex == ElementIndex)
            {
                *NextElementIndexIter = ElementBeingRemoved.HashNextId;
                break;
            }
 
            NextElementIndexIter = &Elements[NextElementIndex].HashNextId;
        }
 
        // Remove the element from the elements array.
        Elements.RemoveAt(ElementIndex);
    }
 
public:
    void Remove(FSetElementId ElementId)
    {
        RemoveByIndex(ElementId.AsInteger());
    }
 
    void RemoveStable(FSetElementId ElementId)
    {
        Remove(ElementId);
        CompactStable();
    }
 
private:
    template <typename ComparableKey>
    [[nodiscard]] SizeType FindIndexByHash(uint32 KeyHash, const ComparableKey& Key) const
    {
        if (Elements.Num() == 0)
        {
            return INDEX_NONE;
        }
 
        FSetElementId* HashPtr      = Hash.GetAllocation();
        SizeType       ElementIndex = HashPtr[KeyHash & (HashSize - 1)].AsInteger();
        for (;;)
        {
            if (ElementIndex == INDEX_NONE)
            {
                return INDEX_NONE;
            }
 
            if (KeyFuncs::Matches(KeyFuncs::GetSetKey(Elements[ElementIndex].Value), Key))
            {
                // Return the first match, regardless of whether the set has multiple matches for the key or not.
                return ElementIndex;
            }
 
            ElementIndex = Elements[ElementIndex].HashNextId.AsInteger();
        }
    }
 
public:
    [[nodiscard]] ElementType* FindArbitraryElement()
    {
        // The goal of this function is to be fast, and so the implementation may be improved at any time even if it gives different results.
 
        int32 Result = Elements.FindArbitraryElementIndex();
        return (Result != INDEX_NONE) ? &Elements[Result].Value : nullptr;
    }
    [[nodiscard]] const ElementType* FindArbitraryElement() const
    {
        return const_cast<UE_TSPARSE_SET*>(this)->FindArbitraryElement();
    }
 
    [[nodiscard]] FSetElementId FindId(KeyInitType Key) const
    {
        return FSetElementId::FromInteger(FindIndexByHash(KeyFuncs::GetKeyHash(Key), Key));
    }
 
    template<typename ComparableKey>
    [[nodiscard]] FSetElementId FindIdByHash(uint32 KeyHash, const ComparableKey& Key) const
    {
        PRAGMA_DISABLE_DEPRECATION_WARNINGS
        // Disable deprecations warnings to stop warnings being thrown by our check macro.
        checkSlow(KeyHash == KeyFuncs::GetKeyHash(Key));
        PRAGMA_ENABLE_DEPRECATION_WARNINGS
 
        return FSetElementId::FromInteger(FindIndexByHash(KeyHash, Key));
    }
 
    [[nodiscard]] inline ElementType* Find(KeyInitType Key)
    {
        SizeType ElementIndex = FindIndexByHash(KeyFuncs::GetKeyHash(Key), Key);
        if (ElementIndex != INDEX_NONE)
        {
            return &Elements[ElementIndex].Value;
        }
        else
        {
            return nullptr;
        }
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType* Find(KeyInitType Key) const
    {
        return const_cast<UE_TSPARSE_SET*>(this)->Find(Key);
    }
 
    template<typename ComparableKey>
    [[nodiscard]] ElementType* FindByHash(uint32 KeyHash, const ComparableKey& Key)
    {
        SizeType ElementIndex = FindIndexByHash(KeyHash, Key);
        if (ElementIndex != INDEX_NONE)
        {
            return &Elements[ElementIndex].Value;
        }
        else
        {
            return nullptr;
        }
    }
 
    template<typename ComparableKey>
    [[nodiscard]] const ElementType* FindByHash(uint32 KeyHash, const ComparableKey& Key) const
    {
        return const_cast<UE_TSPARSE_SET*>(this)->FindByHash(KeyHash, Key);
    }
 
private:
    template<typename ComparableKey>
    inline int32 RemoveImpl(uint32 KeyHash, const ComparableKey& Key)
    {
        int32 NumRemovedElements = 0;
 
        FSetElementId* NextElementId = &GetTypedHash(KeyHash);
        while (NextElementId->IsValidId())
        {
            const int32 ElementIndex = NextElementId->AsInteger();
            SetElementType& Element = Elements[ElementIndex];
 
            if (KeyFuncs::Matches(KeyFuncs::GetSetKey(Element.Value), Key))
            {
                // This element matches the key, remove it from the set.  Note that Remove sets *NextElementId to point to the next
                // element after the removed element in the hash bucket.
                RemoveByIndex(ElementIndex);
                NumRemovedElements++;
 
                if constexpr (!KeyFuncs::bAllowDuplicateKeys)
                {
                    // If the hash disallows duplicate keys, we're done removing after the first matched key.
                    break;
                }
            }
            else
            {
                NextElementId = &Element.HashNextId;
            }
        }
 
        return NumRemovedElements;
    }
 
public:
    int32 Remove(KeyInitType Key)
    {
        if (Elements.Num())
        {
            return RemoveImpl(KeyFuncs::GetKeyHash(Key), Key);
        }
 
        return 0;
    }
 
    int32 RemoveStable(KeyInitType Key)
    {
        int32 Result = 0;
 
        if (Elements.Num())
        {
            Result = RemoveImpl(KeyFuncs::GetKeyHash(Key), Key);
            CompactStable();
        }
 
        return Result;
    }
 
    template<typename ComparableKey>
    int32 RemoveByHash(uint32 KeyHash, const ComparableKey& Key)
    {
        PRAGMA_DISABLE_DEPRECATION_WARNINGS
        // Disable deprecations warnings to stop warnings being thrown by our check macro.
        checkSlow(KeyHash == KeyFuncs::GetKeyHash(Key));
        PRAGMA_ENABLE_DEPRECATION_WARNINGS
 
        if (Elements.Num())
        {
            return RemoveImpl(KeyHash, Key);
        }
 
        return 0;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool Contains(KeyInitType Key) const
    {
        return FindIndexByHash(KeyFuncs::GetKeyHash(Key), Key) != INDEX_NONE;
    }
 
    template<typename ComparableKey>
    [[nodiscard]] inline bool ContainsByHash(uint32 KeyHash, const ComparableKey& Key) const
    {
        PRAGMA_DISABLE_DEPRECATION_WARNINGS
        // Disable deprecations warnings to stop warnings being thrown by our check macro.
        checkSlow(KeyHash == KeyFuncs::GetKeyHash(Key));
        PRAGMA_ENABLE_DEPRECATION_WARNINGS
 
        return FindIndexByHash(KeyHash, Key) != INDEX_NONE;
    }
 
    template <typename PREDICATE_CLASS>
    void Sort( const PREDICATE_CLASS& Predicate )
    {
        // Sort the elements according to the provided comparison class.
        Elements.Sort( FElementCompareClass< PREDICATE_CLASS >( Predicate ) );
 
        // Rehash.
        Rehash();
    }
 
    template <typename PREDICATE_CLASS>
    void StableSort(const PREDICATE_CLASS& Predicate)
    {
        // Sort the elements according to the provided comparison class.
        Elements.StableSort(FElementCompareClass< PREDICATE_CLASS >(Predicate));
 
        // Rehash.
        Rehash();
    }
 
    void SortFreeList()
    {
        Elements.SortFreeList();
    }
 
    void Dump(FOutputDevice& Ar)
    {
        Ar.Logf( TEXT("UE_TSPARSE_SET: %i elements, %i hash slots"), Elements.Num(), HashSize );
        for (int32 HashIndex = 0, LocalHashSize = HashSize; HashIndex < LocalHashSize; ++HashIndex)
        {
            // Count the number of elements in this hash bucket.
            int32 NumElementsInBucket = 0;
            for(FSetElementId ElementId = GetTypedHash(HashIndex);
                ElementId.IsValidId();
                ElementId = Elements[ElementId.AsInteger()].HashNextId)
            {
                NumElementsInBucket++;
            }
 
            Ar.Logf(TEXT("   Hash[%i] = %i"),HashIndex,NumElementsInBucket);
        }
    }
 
    [[nodiscard]] bool VerifyHashElementsKey(KeyInitType Key) const
    {
        bool bResult=true;
        if (Elements.Num())
        {
            // iterate over all elements for the hash entry of the given key
            // and verify that the ids are valid
            FSetElementId ElementId = GetTypedHash(KeyFuncs::GetKeyHash(Key));
            while( ElementId.IsValidId() )
            {
                if( !IsValidId(ElementId) )
                {
                    bResult=false;
                    break;
                }
                ElementId = Elements[ElementId.AsInteger()].HashNextId;
            }
        }
        return bResult;
    }
 
    void DumpHashElements(FOutputDevice& Ar)
    {
        for (int32 HashIndex = 0, LocalHashSize = HashSize; HashIndex < LocalHashSize; ++HashIndex)
        {
            Ar.Logf(TEXT("   Hash[%i]"),HashIndex);
 
            // iterate over all elements for the all hash entries
            // and dump info for all elements
            FSetElementId ElementId = GetTypedHash(HashIndex);
            while( ElementId.IsValidId() )
            {
                if( !IsValidId(ElementId) )
                {
                    Ar.Logf(TEXT("      !!INVALID!! ElementId = %d"),ElementId.AsInteger());
                }
                else
                {
                    Ar.Logf(TEXT("      VALID ElementId = %d"),ElementId.AsInteger());
                }
                ElementId = Elements[ElementId].HashNextId;
            }
        }
    }
 
    [[nodiscard]] UE_TSPARSE_SET Intersect(const UE_TSPARSE_SET& OtherSet) const
    {
        const bool bOtherSmaller = (Num() > OtherSet.Num());
        const UE_TSPARSE_SET& A = (bOtherSmaller ? OtherSet : *this);
        const UE_TSPARSE_SET& B = (bOtherSmaller ? *this : OtherSet);
 
        UE_TSPARSE_SET Result;
        Result.Reserve(A.Num()); // Worst case is everything in smaller is in larger
 
        for(TConstIterator SetIt(A);SetIt;++SetIt)
        {
            if(B.Contains(KeyFuncs::GetSetKey(*SetIt)))
            {
                Result.Add(*SetIt);
            }
        }
        return Result;
    }
 
    [[nodiscard]] UE_TSPARSE_SET Union(const UE_TSPARSE_SET& OtherSet) const
    {
        UE_TSPARSE_SET Result;
        Result.Reserve(Num() + OtherSet.Num()); // Worst case is 2 totally unique Sets
 
        for(TConstIterator SetIt(*this);SetIt;++SetIt)
        {
            Result.Add(*SetIt);
        }
        for(TConstIterator SetIt(OtherSet);SetIt;++SetIt)
        {
            Result.Add(*SetIt);
        }
        return Result;
    }
 
    [[nodiscard]] UE_TSPARSE_SET Difference(const UE_TSPARSE_SET& OtherSet) const
    {
        UE_TSPARSE_SET Result;
        Result.Reserve(Num()); // Worst case is no elements of this are in Other
 
        for(TConstIterator SetIt(*this);SetIt;++SetIt)
        {
            if(!OtherSet.Contains(KeyFuncs::GetSetKey(*SetIt)))
            {
                Result.Add(*SetIt);
            }
        }
        return Result;
    }
 
    [[nodiscard]] bool Includes(const UE_TSPARSE_SET<ElementType,KeyFuncs,Allocator>& OtherSet) const
    {
        bool bIncludesSet = true;
        if (OtherSet.Num() <= Num())
        {
            for(TConstIterator OtherSetIt(OtherSet); OtherSetIt; ++OtherSetIt)
            {
                if (!Contains(KeyFuncs::GetSetKey(*OtherSetIt)))
                {
                    bIncludesSet = false;
                    break;
                }
            }
        }
        else
        {
            // Not possible to include if it is bigger than us
            bIncludesSet = false;
        }
        return bIncludesSet;
    }
 
    [[nodiscard]] TArray<ElementType> Array() const
    {
        TArray<ElementType> Result;
        Result.Reserve(Num());
        for(TConstIterator SetIt(*this);SetIt;++SetIt)
        {
            Result.Add(*SetIt);
        }
        return Result;
    }
 
    UE_FORCEINLINE_HINT void CheckAddress(const ElementType* Addr) const
    {
        Elements.CheckAddress(Addr);
    }
 
    template <
        typename OtherKeyFuncs,
        typename AliasElementType = ElementType
        UE_REQUIRES(TIsContainerElementTypeCopyable_V<AliasElementType>)
    >
    UE_TSPARSE_SET& operator=(UE_TSPARSE_SET<typename TContainerElementTypeCompatibility<ElementType>::CopyFromOtherType, OtherKeyFuncs, Allocator>&& Other)
    {
        TContainerElementTypeCompatibility<ElementType>::CopyingFromOtherType();
        Reset();
        Append(MoveTemp(Other));
        return *this;
    }
 
    template <
        typename OtherKeyFuncs,
        typename OtherAllocator,
        typename AliasElementType = ElementType
        UE_REQUIRES(TIsContainerElementTypeCopyable_V<AliasElementType>)
    >
    UE_TSPARSE_SET& operator=(const UE_TSPARSE_SET<typename TContainerElementTypeCompatibility<ElementType>::CopyFromOtherType, OtherKeyFuncs, OtherAllocator>& Other)
    {
        TContainerElementTypeCompatibility<ElementType>::CopyingFromOtherType();
        Reset();
        Append(Other);
        return *this;
    }
 
    template <
        typename OtherKeyFuncs,
        typename OtherAllocator,
        typename AliasElementType = ElementType
        UE_REQUIRES(TIsContainerElementTypeCopyable_V<AliasElementType>)
    >
    void Append(const UE_TSPARSE_SET<typename TContainerElementTypeCompatibility<ElementType>::CopyFromOtherType, OtherKeyFuncs, OtherAllocator>& OtherSet)
    {
        TContainerElementTypeCompatibility<ElementType>::CopyingFromOtherType();
        Reserve(Elements.Num() + OtherSet.Num());
        for (const ElementType& Element : OtherSet)
        {
            Add(Element);
        }
    }
 
    template <
        typename OtherKeyFuncs,
        typename AliasElementType = ElementType
        UE_REQUIRES(TIsContainerElementTypeCopyable_V<AliasElementType>)
    >
    void Append(UE_TSPARSE_SET<typename TContainerElementTypeCompatibility<ElementType>::CopyFromOtherType, OtherKeyFuncs, Allocator>&& OtherSet)
    {
        TContainerElementTypeCompatibility<ElementType>::CopyingFromOtherType();
        Reserve(Elements.Num() + OtherSet.Num());
        for (ElementType& Element : OtherSet)
        {
            Add(MoveTempIfPossible(Element));
        }
        OtherSet.Reset();
    }
 
private:
    template <typename PREDICATE_CLASS>
    class FElementCompareClass
    {
        TDereferenceWrapper< ElementType, PREDICATE_CLASS > Predicate;
 
    public:
        [[nodiscard]] UE_FORCEINLINE_HINT FElementCompareClass( const PREDICATE_CLASS& InPredicate )
            : Predicate( InPredicate )
        {
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator()( const SetElementType& A,const SetElementType& B ) const
        {
            return Predicate( A.Value, B.Value );
        }
    };
 
    using ElementArrayType = TSparseArray<SetElementType, typename Allocator::SparseArrayAllocator>;
    using HashType         = typename Allocator::HashAllocator::template ForElementType<FSetElementId>;
 
    ElementArrayType Elements;
 
    HashType Hash;
    int32    HashSize = 0;
 
public:
    void WriteMemoryImage(FMemoryImageWriter& Writer) const
    {
        checkf(!Writer.Is32BitTarget(), TEXT("UE_TSPARSE_SET does not currently support freezing for 32bits"));
        if constexpr (TAllocatorTraits<Allocator>::SupportsFreezeMemoryImage && THasTypeLayout<InElementType>::Value)
        {
            this->Elements.WriteMemoryImage(Writer);
            this->Hash.WriteMemoryImage(Writer, StaticGetTypeLayoutDesc<FSetElementId>(), this->HashSize);
            Writer.WriteBytes(this->HashSize);
        }
        else
        {
            Writer.WriteBytes(UE_TSPARSE_SET());
        }
    }
 
    void CopyUnfrozen(const FMemoryUnfreezeContent& Context, void* Dst) const
    {
        if constexpr (TAllocatorTraits<Allocator>::SupportsFreezeMemoryImage && THasTypeLayout<InElementType>::Value)
        {
            UE_TSPARSE_SET* DstObject = static_cast<UE_TSPARSE_SET*>(Dst);
            this->Elements.CopyUnfrozen(Context, &DstObject->Elements);
 
            ::new((void*)&DstObject->Hash) HashType();
            DstObject->Hash.ResizeAllocation(0, this->HashSize, sizeof(FSetElementId));
            FMemory::Memcpy(DstObject->Hash.GetAllocation(), this->Hash.GetAllocation(), sizeof(FSetElementId) * this->HashSize);
            DstObject->HashSize = this->HashSize;
        }
        else
        {
            ::new(Dst) UE_TSPARSE_SET();
        }
    }
 
    static void AppendHash(const FPlatformTypeLayoutParameters& LayoutParams, FSHA1& Hasher)
    {
        ElementArrayType::AppendHash(LayoutParams, Hasher);
    }
 
private:
 
    [[nodiscard]] UE_FORCEINLINE_HINT FSetElementId& GetTypedHash(int32 HashIndex) const
    {
        return ((FSetElementId*)Hash.GetAllocation())[HashIndex & (HashSize - 1)];
    }
 
    inline void LinkElement(SizeType ElementIndex, const SetElementType& Element, uint32 KeyHash) const
    {
        // Compute the hash bucket the element goes in.
        Element.HashIndex = KeyHash & (HashSize - 1);
 
        // Link the element into the hash bucket.
        FSetElementId& TypedHash = GetTypedHash(Element.HashIndex);
        Element.HashNextId = TypedHash;
        TypedHash = FSetElementId::FromInteger(ElementIndex);
    }
 
    UE_FORCEINLINE_HINT void HashElement(SizeType ElementIndex, const SetElementType& Element) const
    {
        LinkElement(ElementIndex, Element, KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(Element.Value)));
    }
 
    void UnhashElements()
    {
        FSetElementId* HashPtr = Hash.GetAllocation();
 
        // Check if it should be faster to clear the hash by going through elements instead of resetting the whole hash
        if (Num() < (HashSize / 4))
        {
            // Faster path: only reset hash buckets to invalid for elements in the hash
            for (const SetElementType& Element: Elements)
            {
                HashPtr[Element.HashIndex] = FSetElementId();
            }
        }
        else
        {
            static_assert(FSetElementId().AsInteger() == -1);
            FMemory::Memset(HashPtr, 0xFF, HashSize * sizeof(FSetElementId));
        }
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool ShouldRehash(int32 NumHashedElements, int32 DesiredHashSize, EAllowShrinking AllowShrinking) const
    {
        // If the hash hasn't been created yet, or is smaller than the desired hash size, rehash.
        // If shrinking is allowed and the hash is bigger than the desired hash size, rehash.
        return ((NumHashedElements > 0 && HashSize < DesiredHashSize) || (AllowShrinking == EAllowShrinking::Yes && HashSize > DesiredHashSize));
    }
 
    bool ConditionalRehash(int32 NumHashedElements, EAllowShrinking AllowShrinking)
    {
        // Calculate the desired hash size for the specified number of elements.
        const int32 DesiredHashSize = Allocator::GetNumberOfHashBuckets(NumHashedElements);
 
        if (ShouldRehash(NumHashedElements, DesiredHashSize, AllowShrinking))
        {
            HashSize = DesiredHashSize;
            Rehash();
            return true;
        }
 
        return false;
    }
 
    void Rehash()
    {
        UE::Core::Private::Rehash(Hash, HashSize);
 
        if (HashSize)
        {
            // Add the existing elements to the new hash.
            for(typename ElementArrayType::TConstIterator ElementIt(Elements);ElementIt;++ElementIt)
            {
                HashElement(ElementIt.GetIndex(), *ElementIt);
            }
        }
    }
 
    template<bool bConst, bool bRangedFor = false>
    class TBaseIterator
    {
    private:
        friend class UE_TSPARSE_SET;
 
        typedef std::conditional_t<bConst,const ElementType,ElementType> ItElementType;
 
    public:
        typedef std::conditional_t<
            bConst,
            std::conditional_t<bRangedFor, typename ElementArrayType::TRangedForConstIterator, typename ElementArrayType::TConstIterator>,
            std::conditional_t<bRangedFor, typename ElementArrayType::TRangedForIterator,      typename ElementArrayType::TIterator     >
        > ElementItType;
 
        [[nodiscard]] UE_FORCEINLINE_HINT TBaseIterator(const ElementItType& InElementIt)
            : ElementIt(InElementIt)
        {
        }
 
        UE_FORCEINLINE_HINT TBaseIterator& operator++()
        {
            ++ElementIt;
            return *this;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
        { 
            return !!ElementIt; 
        }
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!() const 
        {
            return !(bool)*this;
        }
 
        // Accessors.
        [[nodiscard]] UE_FORCEINLINE_HINT FSetElementId GetId() const
        {
            return FSetElementId::FromInteger(ElementIt.GetIndex());
        }
        [[nodiscard]] UE_FORCEINLINE_HINT ItElementType* operator->() const
        {
            return &ElementIt->Value;
        }
        [[nodiscard]] UE_FORCEINLINE_HINT ItElementType& operator*() const
        {
            return ElementIt->Value;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TBaseIterator& Rhs) const { return ElementIt != Rhs.ElementIt; }
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TBaseIterator& Rhs) const { return ElementIt == Rhs.ElementIt; }
 
        ElementItType ElementIt;
    };
 
    template<bool bConst>
    class TBaseKeyIterator
    {
    private:
        typedef std::conditional_t<bConst, const UE_TSPARSE_SET, UE_TSPARSE_SET> SetType;
        typedef std::conditional_t<bConst,const ElementType,ElementType> ItElementType;
        typedef typename TTypeTraits<typename KeyFuncs::KeyType>::ConstPointerType ReferenceOrValueType;
 
    public:
        using KeyArgumentType =
            std::conditional_t<
                std::is_reference_v<ReferenceOrValueType>,
                TRetainedRef<std::remove_reference_t<ReferenceOrValueType>>,
                KeyInitType
            >;
 
        [[nodiscard]] inline TBaseKeyIterator(SetType& InSet, KeyArgumentType InKey)
            : Set  (InSet)
            , Key  (InKey) //-V1041
            , Index(INDEX_NONE)
        {
            if (Set.HashSize)
            {
                NextIndex = Set.GetTypedHash(KeyFuncs::GetKeyHash(Key)).AsInteger();
                ++(*this);
            }
            else
            {
                NextIndex = INDEX_NONE;
            }
        }
 
        inline TBaseKeyIterator& operator++()
        {
            Index = NextIndex;
 
            while (Index != INDEX_NONE)
            {
                NextIndex = Set.Elements[Index].HashNextId.AsInteger();
                checkSlow(Index != NextIndex);
 
                if (KeyFuncs::Matches(KeyFuncs::GetSetKey(Set.Elements[Index].Value),Key))
                {
                    break;
                }
 
                Index = NextIndex;
            }
            return *this;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
        { 
            return Index != INDEX_NONE;
        }
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!() const
        {
            return !(bool)*this;
        }
 
        // Accessors.
        [[nodiscard]] UE_FORCEINLINE_HINT FSetElementId GetId() const
        {
            return FSetElementId::FromInteger(Index);
        }
        [[nodiscard]] UE_FORCEINLINE_HINT ItElementType* operator->() const
        {
            return &Set.Elements[Index].Value;
        }
        [[nodiscard]] UE_FORCEINLINE_HINT ItElementType& operator*() const
        {
            return Set.Elements[Index].Value;
        }
 
    protected:
        SetType& Set;
        ReferenceOrValueType Key;
        SizeType Index;
        SizeType NextIndex;
    };
 
public:
 
    class TConstIterator : public TBaseIterator<true>
    {
        friend class UE_TSPARSE_SET;
 
    public:
        [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator(const UE_TSPARSE_SET& InSet)
            : TBaseIterator<true>(InSet.Elements.begin())
        {
        }
    };
 
    class TIterator : public TBaseIterator<false>
    {
        friend class UE_TSPARSE_SET;
 
    public:
        [[nodiscard]] inline TIterator(UE_TSPARSE_SET& InSet)
            : TBaseIterator<false>(InSet.Elements.begin())
            , Set                 (InSet)
        {
        }
 
        UE_FORCEINLINE_HINT void RemoveCurrent()
        {
            Set.RemoveByIndex(TBaseIterator<false>::ElementIt.GetIndex());
        }
 
    private:
        UE_TSPARSE_SET& Set;
    };
 
    using TRangedForConstIterator = TBaseIterator<true, true>;
    using TRangedForIterator      = TBaseIterator<false, true>;
 
    class TConstKeyIterator : public TBaseKeyIterator<true>
    {
    private:
        using Super = TBaseKeyIterator<true>;
 
    public:
        using KeyArgumentType = typename Super::KeyArgumentType;
 
        [[nodiscard]] UE_FORCEINLINE_HINT TConstKeyIterator(const UE_TSPARSE_SET& InSet, KeyArgumentType InKey)
            : Super(InSet, InKey)
        {
        }
    };
 
    class TKeyIterator : public TBaseKeyIterator<false>
    {
    private:
        using Super = TBaseKeyIterator<false>;
 
    public:
        using KeyArgumentType = typename Super::KeyArgumentType;
 
        [[nodiscard]] UE_FORCEINLINE_HINT TKeyIterator(UE_TSPARSE_SET& InSet, KeyArgumentType InKey)
            : Super(InSet, InKey)
        {
        }
 
        inline void RemoveCurrent()
        {
            this->Set.RemoveByIndex(TBaseKeyIterator<false>::Index);
            TBaseKeyIterator<false>::Index = INDEX_NONE;
        }
    };
 
    [[nodiscard]] UE_FORCEINLINE_HINT TIterator CreateIterator()
    {
        return TIterator(*this);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator CreateConstIterator() const
    {
        return TConstIterator(*this);
    }
 
    friend struct TSETPRIVATEFRIEND;
 
public:
    [[nodiscard]] UE_FORCEINLINE_HINT TRangedForIterator begin()
    {
        return TRangedForIterator(Elements.begin());
    }
    [[nodiscard]] UE_FORCEINLINE_HINT TRangedForConstIterator begin() const
    {
        return TRangedForConstIterator(Elements.begin());
    }
    [[nodiscard]] UE_FORCEINLINE_HINT TRangedForIterator end()
    {
        return TRangedForIterator(Elements.end());
    }
    [[nodiscard]] UE_FORCEINLINE_HINT TRangedForConstIterator end() const
    {
        return TRangedForConstIterator(Elements.end());
    }
 
    // Maps are deliberately prevented from being hashed or compared, because this would hide potentially major performance problems behind default operations.
    friend uint32 GetTypeHash(const UE_TSPARSE_SET& Set) = delete;
    friend bool operator==(const UE_TSPARSE_SET&, const UE_TSPARSE_SET&) = delete;
    friend bool operator!=(const UE_TSPARSE_SET&, const UE_TSPARSE_SET&) = delete;
};
 
template <typename RangeType>
UE_TSPARSE_SET(RangeType&&) -> UE_TSPARSE_SET<TElementType_T<RangeType>>;
 
namespace Freeze
{
    template<typename ElementType, typename KeyFuncs, typename Allocator>
    void IntrinsicWriteMemoryImage(FMemoryImageWriter& Writer, const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Object, const FTypeLayoutDesc&)
    {
        Object.WriteMemoryImage(Writer);
    }
 
    template<typename ElementType, typename KeyFuncs, typename Allocator>
    uint32 IntrinsicUnfrozenCopy(const FMemoryUnfreezeContent& Context, const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Object, void* OutDst)
    {
        Object.CopyUnfrozen(Context, OutDst);
        return sizeof(Object);
    }
 
    template<typename ElementType, typename KeyFuncs, typename Allocator>
    uint32 IntrinsicAppendHash(const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>* DummyObject, const FTypeLayoutDesc& TypeDesc, const FPlatformTypeLayoutParameters& LayoutParams, FSHA1& Hasher)
    {
        UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>::AppendHash(LayoutParams, Hasher);
        return DefaultAppendHash(TypeDesc, LayoutParams, Hasher);
    }
}
 
DECLARE_TEMPLATE_INTRINSIC_TYPE_LAYOUT((template <typename ElementType, typename KeyFuncs, typename Allocator>), (UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>));
 
struct TSETPRIVATEFRIEND
{
    template<typename ElementType, typename KeyFuncs,typename Allocator>
    static FArchive& Serialize(FArchive& Ar,UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Set)
    {
        // Load the set's new elements.
        Ar << Set.Elements;
 
        if(Ar.IsLoading() || (Ar.IsModifyingWeakAndStrongReferences() && !Ar.IsSaving()))
        {
            // Free the old hash.
            Set.Hash.ResizeAllocation(0,0,sizeof(FSetElementId));
            Set.HashSize = 0;
 
            // Hash the newly loaded elements.
            Set.ConditionalRehash(Set.Elements.Num(), EAllowShrinking::No);
        }
 
        return Ar;
    }
 
    template<typename ElementType, typename KeyFuncs,typename Allocator>
    static void SerializeStructured(FStructuredArchive::FSlot Slot, UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Set)
    {
        Slot << Set.Elements;
 
        if (Slot.GetUnderlyingArchive().IsLoading() || (Slot.GetUnderlyingArchive().IsModifyingWeakAndStrongReferences() && !Slot.GetUnderlyingArchive().IsSaving()))
        {
            // Free the old hash.
            Set.Hash.ResizeAllocation(0, 0, sizeof(FSetElementId));
            Set.HashSize = 0;
 
            // Hash the newly loaded elements.
            Set.ConditionalRehash(Set.Elements.Num(), EAllowShrinking::No);
        }
    }
 
    // Legacy comparison operators.  Note that these also test whether the set's elements were added in the same order!
    template<typename ElementType, typename KeyFuncs,typename Allocator>
    [[nodiscard]] static bool LegacyCompareEqual(const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& A, const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& B)
    {
        return A.Elements == B.Elements;
    }
};
 
template<typename ElementType, typename KeyFuncs,typename Allocator>
FArchive& operator<<(FArchive& Ar, UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Set)
{
    return TSETPRIVATEFRIEND::Serialize(Ar, Set);
}
 
template<typename ElementType, typename KeyFuncs,typename Allocator>
void operator<<(FStructuredArchive::FSlot& Ar, UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& Set)
{
    TSETPRIVATEFRIEND::SerializeStructured(Ar, Set);
}
 
// Legacy comparison operators.  Note that these also test whether the set's elements were added in the same order!
template<typename ElementType, typename KeyFuncs,typename Allocator>
[[nodiscard]] bool LegacyCompareEqual(const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& A,const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& B)
{
    return TSETPRIVATEFRIEND::LegacyCompareEqual(A, B);
}
template<typename ElementType, typename KeyFuncs,typename Allocator>
[[nodiscard]] bool LegacyCompareNotEqual(const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& A,const UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>& B)
{
    return !TSETPRIVATEFRIEND::LegacyCompareEqual(A, B);
}
 
template <typename ElementType, typename KeyFuncs, typename Allocator> struct TIsTSet<               UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>> { enum { Value = true }; };
template <typename ElementType, typename KeyFuncs, typename Allocator> struct TIsTSet<const          UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>> { enum { Value = true }; };
template <typename ElementType, typename KeyFuncs, typename Allocator> struct TIsTSet<      volatile UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>> { enum { Value = true }; };
template <typename ElementType, typename KeyFuncs, typename Allocator> struct TIsTSet<const volatile UE_TSPARSE_SET<ElementType, KeyFuncs, Allocator>> { enum { Value = true }; };
 
#undef TSETPRIVATEFRIEND