HashSet.h

#pragma once
 
#include <Foundation/Algorithm/HashingUtils.h>
#include <Foundation/Math/Math.h>
#include <Foundation/Memory/AllocatorWrapper.h>
 
 
template <typename KeyType, typename Hasher>
class plHashSetBase
{
public:
  class ConstIterator
  {
  public:
    bool IsValid() const; // [tested]
 
    bool operator==(const typename plHashSetBase<KeyType, Hasher>::ConstIterator& rhs) const;
 
    PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const typename plHashSetBase<KeyType, Hasher>::ConstIterator&);
 
    const KeyType& Key() const; // [tested]
 
    PL_ALWAYS_INLINE const KeyType& operator*() const { return Key(); } // [tested]
 
    void Next(); // [tested]
 
    void operator++(); // [tested]
 
  protected:
    friend class plHashSetBase<KeyType, Hasher>;
 
    explicit ConstIterator(const plHashSetBase<KeyType, Hasher>& hashSet);
    void SetToBegin();
    void SetToEnd();
 
    const plHashSetBase<KeyType, Hasher>* m_pHashSet = nullptr;
    plUInt32 m_uiCurrentIndex = 0; // current element index that this iterator points to.
    plUInt32 m_uiCurrentCount = 0; // current number of valid elements that this iterator has found so far.
  };
 
protected:
  explicit plHashSetBase(plAllocator* pAllocator); // [tested]
 
  plHashSetBase(const plHashSetBase<KeyType, Hasher>& rhs, plAllocator* pAllocator); // [tested]
 
  plHashSetBase(plHashSetBase<KeyType, Hasher>&& rhs, plAllocator* pAllocator); // [tested]
 
  ~plHashSetBase(); // [tested]
 
  void operator=(const plHashSetBase<KeyType, Hasher>& rhs); // [tested]
 
  void operator=(plHashSetBase<KeyType, Hasher>&& rhs); // [tested]
 
public:
  bool operator==(const plHashSetBase<KeyType, Hasher>& rhs) const; // [tested]
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plHashSetBase<KeyType, Hasher>&);
 
  void Reserve(plUInt32 uiCapacity); // [tested]
 
  void Compact(); // [tested]
 
  plUInt32 GetCount() const; // [tested]
 
  bool IsEmpty() const; // [tested]
 
  void Clear(); // [tested]
 
  template <typename CompatibleKeyType>
  bool Insert(CompatibleKeyType&& key); // [tested]
 
  template <typename CompatibleKeyType>
  bool Remove(const CompatibleKeyType& key); // [tested]
 
  ConstIterator Remove(const ConstIterator& pos); // [tested]
 
  template <typename CompatibleKeyType>
  bool Contains(const CompatibleKeyType& key) const; // [tested]
 
  bool ContainsSet(const plHashSetBase<KeyType, Hasher>& operand) const; // [tested]
 
  void Union(const plHashSetBase<KeyType, Hasher>& operand); // [tested]
 
  void Difference(const plHashSetBase<KeyType, Hasher>& operand); // [tested]
 
  void Intersection(const plHashSetBase<KeyType, Hasher>& operand); // [tested]
 
  ConstIterator GetIterator() const; // [tested]
 
  ConstIterator GetEndIterator() const;
 
  plAllocator* GetAllocator() const;
 
  plUInt64 GetHeapMemoryUsage() const; // [tested]
 
  void Swap(plHashSetBase<KeyType, Hasher>& other); // [tested]
 
  template <typename CompatibleKeyType>
  ConstIterator Find(const CompatibleKeyType& key) const;
 
private:
  KeyType* m_pEntries;
  plUInt32* m_pEntryFlags;
 
  plUInt32 m_uiCount;
  plUInt32 m_uiCapacity;
 
  plAllocator* m_pAllocator;
 
  enum
  {
    FREE_ENTRY = 0,
    VALID_ENTRY = 1,
    DELETED_ENTRY = 2,
    FLAGS_MASK = 3,
    CAPACITY_ALIGNMENT = 32
  };
 
  void SetCapacity(plUInt32 uiCapacity);
 
  void RemoveInternal(plUInt32 uiIndex);
 
  template <typename CompatibleKeyType>
  plUInt32 FindEntry(const CompatibleKeyType& key) const;
 
  template <typename CompatibleKeyType>
  plUInt32 FindEntry(plUInt32 uiHash, const CompatibleKeyType& key) const;
 
  plUInt32 GetFlagsCapacity() const;
  plUInt32 GetFlags(plUInt32* pFlags, plUInt32 uiEntryIndex) const;
  void SetFlags(plUInt32 uiEntryIndex, plUInt32 uiFlags);
 
  bool IsFreeEntry(plUInt32 uiEntryIndex) const;
  bool IsValidEntry(plUInt32 uiEntryIndex) const;
  bool IsDeletedEntry(plUInt32 uiEntryIndex) const;
 
  void MarkEntryAsFree(plUInt32 uiEntryIndex);
  void MarkEntryAsValid(plUInt32 uiEntryIndex);
  void MarkEntryAsDeleted(plUInt32 uiEntryIndex);
};
 
template <typename KeyType, typename Hasher = plHashHelper<KeyType>, typename AllocatorWrapper = plDefaultAllocatorWrapper>
class plHashSet : public plHashSetBase<KeyType, Hasher>
{
public:
  plHashSet();
  explicit plHashSet(plAllocator* pAllocator);
 
  plHashSet(const plHashSet<KeyType, Hasher, AllocatorWrapper>& other);
  plHashSet(const plHashSetBase<KeyType, Hasher>& other);
 
  plHashSet(plHashSet<KeyType, Hasher, AllocatorWrapper>&& other);
  plHashSet(plHashSetBase<KeyType, Hasher>&& other);
 
  void operator=(const plHashSet<KeyType, Hasher, AllocatorWrapper>& rhs);
  void operator=(const plHashSetBase<KeyType, Hasher>& rhs);
 
  void operator=(plHashSet<KeyType, Hasher, AllocatorWrapper>&& rhs);
  void operator=(plHashSetBase<KeyType, Hasher>&& rhs);
};
 
template <typename KeyType, typename Hasher>
typename plHashSetBase<KeyType, Hasher>::ConstIterator begin(const plHashSetBase<KeyType, Hasher>& set)
{
  return set.GetIterator();
}
 
template <typename KeyType, typename Hasher>
typename plHashSetBase<KeyType, Hasher>::ConstIterator cbegin(const plHashSetBase<KeyType, Hasher>& set)
{
  return set.GetIterator();
}
 
template <typename KeyType, typename Hasher>
typename plHashSetBase<KeyType, Hasher>::ConstIterator end(const plHashSetBase<KeyType, Hasher>& set)
{
  return set.GetEndIterator();
}
 
template <typename KeyType, typename Hasher>
typename plHashSetBase<KeyType, Hasher>::ConstIterator cend(const plHashSetBase<KeyType, Hasher>& set)
{
  return set.GetEndIterator();
}
 
#include <Foundation/Containers/Implementation/HashSet_inl.h>