Set.h

#pragma once
 
#include <Foundation/Containers/Deque.h>
 
template <typename KeyType, typename Comparer>
class plSetBase
{
private:
  struct Node;
 
  struct NilNode
  {
    plUInt16 m_uiLevel = 0;
    Node* m_pParent = nullptr;
    Node* m_pLink[2] = {nullptr, nullptr};
  };
 
  struct Node : public NilNode
  {
    KeyType m_Key;
  };
 
public:
  template <bool REVERSE>
  struct IteratorBase
  {
    using iterator_category = std::forward_iterator_tag;
    using value_type = IteratorBase<REVERSE>;
    using difference_type = std::ptrdiff_t;
    using pointer = IteratorBase<REVERSE>*;
    using reference = IteratorBase<REVERSE>&;
 
    PL_DECLARE_POD_TYPE();
 
    PL_ALWAYS_INLINE IteratorBase()
      : m_pElement(nullptr)
    {
    } // [tested]
 
    PL_ALWAYS_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
 
    PL_ALWAYS_INLINE bool operator==(const typename plSetBase<KeyType, Comparer>::IteratorBase<REVERSE>& it2) const { return (m_pElement == it2.m_pElement); }
    PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const typename plSetBase<KeyType, Comparer>::IteratorBase<REVERSE>&);
 
    PL_FORCE_INLINE const KeyType& Key() const
    {
      PL_ASSERT_DEBUG(IsValid(), "Cannot access the 'key' of an invalid iterator.");
      return m_pElement->m_Key;
    } // [tested]
 
    PL_ALWAYS_INLINE const KeyType& operator*() const { return Key(); }
 
    void Next(); // [tested]
 
    void Prev(); // [tested]
 
    PL_ALWAYS_INLINE void operator++() { Next(); } // [tested]
 
    PL_ALWAYS_INLINE void operator--() { Prev(); } // [tested]
 
  protected:
    void Advance(plInt32 dir0, plInt32 dir1);
 
    friend class plSetBase<KeyType, Comparer>;
 
    PL_ALWAYS_INLINE explicit IteratorBase(Node* pInit)
      : m_pElement(pInit)
    {
    }
 
    Node* m_pElement;
  };
 
  using Iterator = IteratorBase<false>;
  using ReverseIterator = IteratorBase<true>;
 
protected:
  plSetBase(const Comparer& comparer, plAllocator* pAllocator); // [tested]
 
  plSetBase(const plSetBase<KeyType, Comparer>& cc, plAllocator* pAllocator); // [tested]
 
  ~plSetBase(); // [tested]
 
  void operator=(const plSetBase<KeyType, Comparer>& rhs); // [tested]
 
public:
  bool IsEmpty() const; // [tested]
 
  plUInt32 GetCount() const; // [tested]
 
  void Clear(); // [tested]
 
  Iterator GetIterator() const; // [tested]
 
  ReverseIterator GetReverseIterator() const; // [tested]
 
  template <typename CompatibleKeyType>
  Iterator Insert(CompatibleKeyType&& key); // [tested]
 
  template <typename CompatibleKeyType>
  bool Remove(const CompatibleKeyType& key); // [tested]
 
  Iterator Remove(const Iterator& pos); // [tested]
 
  template <typename CompatibleKeyType>
  Iterator Find(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool Contains(const CompatibleKeyType& key) const; // [tested]
 
  bool ContainsSet(const plSetBase<KeyType, Comparer>& operand) const; // [tested]
 
  template <typename CompatibleKeyType>
  Iterator LowerBound(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  Iterator UpperBound(const CompatibleKeyType& key) const; // [tested]
 
  void Union(const plSetBase<KeyType, Comparer>& operand); // [tested]
 
  void Difference(const plSetBase<KeyType, Comparer>& operand); // [tested]
 
  void Intersection(const plSetBase<KeyType, Comparer>& operand); // [tested]
 
  plAllocator* GetAllocator() const { return m_Elements.GetAllocator(); }
 
  bool operator==(const plSetBase<KeyType, Comparer>& rhs) const; // [tested]
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plSetBase<KeyType, Comparer>&);
 
  plUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
 
  void Swap(plSetBase<KeyType, Comparer>& other); // [tested]
 
private:
  template <typename CompatibleKeyType>
  Node* Internal_Find(const CompatibleKeyType& key) const;
  template <typename CompatibleKeyType>
  Node* Internal_LowerBound(const CompatibleKeyType& key) const;
  template <typename CompatibleKeyType>
  Node* Internal_UpperBound(const CompatibleKeyType& key) const;
 
private:
  void Constructor();
 
  template <typename CompatibleKeyType>
  Node* AcquireNode(CompatibleKeyType&& key, plUInt16 uiLevel, Node* pParent);
 
  void ReleaseNode(Node* pNode);
 
  Node* SkewNode(Node* root);
  Node* SplitNode(Node* root);
 
  template <typename CompatibleKeyType>
  Node* Insert(Node* root, CompatibleKeyType&& key, Node*& pInsertedNode);
  template <typename CompatibleKeyType>
  Node* Remove(Node* root, const CompatibleKeyType& key, bool& bRemoved);
 
  Node* GetLeftMost() const;
 
  Node* GetRightMost() const;
 
  void SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew);
 
  Node* m_pRoot;
 
  NilNode m_NilNode;
 
  plUInt32 m_uiCount;
 
  plDeque<Node, plNullAllocatorWrapper, false> m_Elements;
 
  Node* m_pFreeElementStack;
 
  Comparer m_Comparer;
};
 
template <typename KeyType, typename Comparer = plCompareHelper<KeyType>, typename AllocatorWrapper = plDefaultAllocatorWrapper>
class plSet : public plSetBase<KeyType, Comparer>
{
public:
  plSet();
  explicit plSet(plAllocator* pAllocator);
  plSet(const Comparer& comparer, plAllocator* pAllocator);
 
  plSet(const plSet<KeyType, Comparer, AllocatorWrapper>& other);
  plSet(const plSetBase<KeyType, Comparer>& other);
 
  void operator=(const plSet<KeyType, Comparer, AllocatorWrapper>& rhs);
  void operator=(const plSetBase<KeyType, Comparer>& rhs);
};
 
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator begin(plSetBase<KeyType, Comparer>& ref_container)
{
  return ref_container.GetIterator();
}
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator begin(const plSetBase<KeyType, Comparer>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator cbegin(const plSetBase<KeyType, Comparer>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator end(plSetBase<KeyType, Comparer>& ref_container)
{
  return typename plSetBase<KeyType, Comparer>::Iterator();
}
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator end(const plSetBase<KeyType, Comparer>& container)
{
  return typename plSetBase<KeyType, Comparer>::Iterator();
}
 
template <typename KeyType, typename Comparer>
typename plSetBase<KeyType, Comparer>::Iterator cend(const plSetBase<KeyType, Comparer>& container)
{
  return typename plSetBase<KeyType, Comparer>::Iterator();
}
 
 
#include <Foundation/Containers/Implementation/Set_inl.h>