Map.h

#pragma once
 
#include <Foundation/Containers/Deque.h>
 
template <typename KeyType, typename ValueType, typename Comparer>
class plMapBase;
 
template <typename KeyType, typename ValueType, typename Comparer, bool REVERSE>
struct plMapBaseConstIteratorBase
{
  using iterator_category = std::forward_iterator_tag;
  using value_type = plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, false>;
  using difference_type = std::ptrdiff_t;
  using pointer = plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, false>*;
  using reference = plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, false>&;
 
  PL_DECLARE_POD_TYPE();
 
  PL_ALWAYS_INLINE plMapBaseConstIteratorBase()
    : m_pElement(nullptr)
  {
  } // [tested]
 
  PL_ALWAYS_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
 
  PL_ALWAYS_INLINE bool operator==(const plMapBaseConstIteratorBase& it2) const { return (m_pElement == it2.m_pElement); }
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plMapBaseConstIteratorBase&);
 
  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_FORCE_INLINE const ValueType& Value() const
  {
    PL_ASSERT_DEBUG(IsValid(), "Cannot access the 'value' of an invalid iterator.");
    return m_pElement->m_Value;
  } // [tested]
 
  PL_ALWAYS_INLINE plMapBaseConstIteratorBase& operator*() { return *this; } // [tested]
 
  void Next(); // [tested]
 
  void Prev(); // [tested]
 
  PL_ALWAYS_INLINE void operator++() { Next(); } // [tested]
 
  PL_ALWAYS_INLINE void operator--() { Prev(); } // [tested]
 
protected:
  void Advance(const plInt32 dir0, const plInt32 dir1);
 
  friend class plMapBase<KeyType, ValueType, Comparer>;
 
  PL_ALWAYS_INLINE explicit plMapBaseConstIteratorBase(typename plMapBase<KeyType, ValueType, Comparer>::Node* pInit)
    : m_pElement(pInit)
  {
  }
 
  typename plMapBase<KeyType, ValueType, Comparer>::Node* m_pElement;
 
#if PL_ENABLED(PL_USE_CPP20_OPERATORS)
public:
  struct Pointer
  {
    std::pair<const KeyType&, const ValueType&> value;
    const std::pair<const KeyType&, const ValueType&>* operator->() const { return &value; }
  };
 
  PL_ALWAYS_INLINE Pointer operator->() const
  {
    return Pointer{.value = {Key(), Value()}};
  }
 
  // This function is used to return the values for structured bindings.
  // The number and type of each slot are defined in the inl file.
  template <std::size_t Index>
  std::tuple_element_t<Index, plMapBaseConstIteratorBase>& get() const
  {
    if constexpr (Index == 0)
      return Key();
    if constexpr (Index == 1)
      return Value();
  }
#endif
};
 
template <typename KeyType, typename ValueType, typename Comparer, bool REVERSE>
struct plMapBaseIteratorBase : public plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>
{
  using iterator_category = std::forward_iterator_tag;
  using value_type = plMapBaseIteratorBase<KeyType, ValueType, Comparer, REVERSE>;
  using difference_type = std::ptrdiff_t;
  using pointer = plMapBaseIteratorBase<KeyType, ValueType, Comparer, REVERSE>*;
  using reference = plMapBaseIteratorBase<KeyType, ValueType, Comparer, REVERSE>&;
 
  PL_DECLARE_POD_TYPE();
 
  PL_ALWAYS_INLINE plMapBaseIteratorBase()
    : plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>()
  {
  }
 
  PL_FORCE_INLINE ValueType& Value()
  {
    PL_ASSERT_DEBUG(this->IsValid(), "Cannot access the 'value' of an invalid iterator.");
    return this->m_pElement->m_Value;
  }
 
  PL_FORCE_INLINE ValueType& Value() const
  {
    PL_ASSERT_DEBUG(this->IsValid(), "Cannot access the 'value' of an invalid iterator.");
    return this->m_pElement->m_Value;
  }
 
  PL_ALWAYS_INLINE plMapBaseIteratorBase& operator*() { return *this; } // [tested]
 
private:
  friend class plMapBase<KeyType, ValueType, Comparer>;
 
  PL_ALWAYS_INLINE explicit plMapBaseIteratorBase(typename plMapBase<KeyType, ValueType, Comparer>::Node* pInit)
    : plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>(pInit)
  {
  }
 
#if PL_ENABLED(PL_USE_CPP20_OPERATORS)
public:
  struct Pointer
  {
    std::pair<const KeyType&, ValueType&> value;
    const std::pair<const KeyType&, ValueType&>* operator->() const { return &value; }
  };
 
  PL_ALWAYS_INLINE Pointer operator->() const
  {
    return Pointer{.value = {plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>::Key(), Value()}};
  }
 
 
  // These functions are used to return the values for structured bindings.
  // The number and type of type of each slot are defined in the inl file.
 
  template <std::size_t Index>
  std::tuple_element_t<Index, plMapBaseIteratorBase>& get()
  {
    if constexpr (Index == 0)
      return plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>::Key();
    if constexpr (Index == 1)
      return Value();
  }
 
  template <std::size_t Index>
  std::tuple_element_t<Index, plMapBaseIteratorBase>& get() const
  {
    if constexpr (Index == 0)
      return plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, REVERSE>::Key();
    if constexpr (Index == 1)
      return Value();
  }
#endif
};
 
template <typename KeyType, typename ValueType, typename Comparer>
class plMapBase
{
 
public:
  using ConstIterator = plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, false>;
  using ConstReverseIterator = plMapBaseConstIteratorBase<KeyType, ValueType, Comparer, true>;
 
  using Iterator = plMapBaseIteratorBase<KeyType, ValueType, Comparer, false>;
  using ReverseIterator = plMapBaseIteratorBase<KeyType, ValueType, Comparer, true>;
 
private:
  friend ConstIterator;
  friend ConstReverseIterator;
  friend Iterator;
  friend ReverseIterator;
  struct Node;
 
  struct NilNode
  {
    Node* m_pParent = nullptr;
    Node* m_pLink[2] = {nullptr, nullptr};
    plUInt8 m_uiLevel = 0;
  };
 
  struct Node : public NilNode
  {
    KeyType m_Key;
    ValueType m_Value;
  };
 
protected:
  plMapBase(const Comparer& comparer, plAllocator* pAllocator); // [tested]
 
  plMapBase(const plMapBase<KeyType, ValueType, Comparer>& cc, plAllocator* pAllocator); // [tested]
 
  ~plMapBase(); // [tested]
 
  void operator=(const plMapBase<KeyType, ValueType, Comparer>& rhs);
 
public:
  bool IsEmpty() const; // [tested]
 
  plUInt32 GetCount() const; // [tested]
 
  void Clear(); // [tested]
 
  Iterator GetIterator(); // [tested]
 
  ReverseIterator GetReverseIterator(); // [tested]
 
  ConstIterator GetIterator() const; // [tested]
 
  ConstReverseIterator GetReverseIterator() const; // [tested]
 
  template <typename CompatibleKeyType, typename CompatibleValueType>
  Iterator Insert(CompatibleKeyType&& key, CompatibleValueType&& value); // [tested]
 
  template <typename CompatibleKeyType>
  bool Remove(const CompatibleKeyType& key); // [tested]
 
  Iterator Remove(const Iterator& pos); // [tested]
 
  template <typename CompatibleKeyType>
  Iterator FindOrAdd(CompatibleKeyType&& key, bool* out_pExisted = nullptr); // [tested]
 
  template <typename CompatibleKeyType>
  ValueType& operator[](const CompatibleKeyType& key); // [tested]
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, ValueType& out_value) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, const ValueType*& out_pValue) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, ValueType*& out_pValue) const; // [tested]
 
  template <typename CompatibleKeyType>
  const ValueType* GetValue(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  ValueType* GetValue(const CompatibleKeyType& key); // [tested]
 
  template <typename CompatibleKeyType>
  const ValueType& GetValueOrDefault(const CompatibleKeyType& key, const ValueType& defaultValue) const; // [tested]
 
  template <typename CompatibleKeyType>
  Iterator Find(const CompatibleKeyType& key); // [tested]
 
  template <typename CompatibleKeyType>
  Iterator LowerBound(const CompatibleKeyType& key); // [tested]
 
  template <typename CompatibleKeyType>
  Iterator UpperBound(const CompatibleKeyType& key); // [tested]
 
  template <typename CompatibleKeyType>
  ConstIterator Find(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool Contains(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  ConstIterator LowerBound(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  ConstIterator UpperBound(const CompatibleKeyType& key) const; // [tested]
 
  plAllocator* GetAllocator() const { return m_Elements.GetAllocator(); }
 
  bool operator==(const plMapBase<KeyType, ValueType, Comparer>& rhs) const; // [tested]
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plMapBase<KeyType, ValueType, Comparer>&);
 
  plUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
 
  void Swap(plMapBase<KeyType, ValueType, 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, ValueType&& value, plUInt8 uiLevel, Node* pParent);
 
  void ReleaseNode(Node* pNode);
 
  // \brief Red-Black Tree stuff(Anderson Tree to be exact).
  // Code taken from here: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
  Node* SkewNode(Node* root);
  Node* SplitNode(Node* root);
  void Insert(const KeyType& key, const ValueType& value, 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;
 
  Node* m_pFreeElementStack;
 
  NilNode m_NilNode;
 
  plDeque<Node, plNullAllocatorWrapper, false> m_Elements;
 
  plUInt32 m_uiCount;
 
  Comparer m_Comparer;
};
 
 
template <typename KeyType, typename ValueType, typename Comparer = plCompareHelper<KeyType>, typename AllocatorWrapper = plDefaultAllocatorWrapper>
class plMap : public plMapBase<KeyType, ValueType, Comparer>
{
public:
  plMap();
  explicit plMap(plAllocator* pAllocator);
  plMap(const Comparer& comparer, plAllocator* pAllocator);
 
  plMap(const plMap<KeyType, ValueType, Comparer, AllocatorWrapper>& other);
  plMap(const plMapBase<KeyType, ValueType, Comparer>& other);
 
  void operator=(const plMap<KeyType, ValueType, Comparer, AllocatorWrapper>& rhs);
  void operator=(const plMapBase<KeyType, ValueType, Comparer>& rhs);
};
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::Iterator begin(plMapBase<KeyType, ValueType, Comparer>& ref_container)
{
  return ref_container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator begin(const plMapBase<KeyType, ValueType, Comparer>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator cbegin(const plMapBase<KeyType, ValueType, Comparer>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::Iterator end(plMapBase<KeyType, ValueType, Comparer>& ref_container)
{
  return typename plMapBase<KeyType, ValueType, Comparer>::Iterator();
}
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator end(const plMapBase<KeyType, ValueType, Comparer>& container)
{
  return typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator();
}
 
template <typename KeyType, typename ValueType, typename Comparer>
typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator cend(const plMapBase<KeyType, ValueType, Comparer>& container)
{
  return typename plMapBase<KeyType, ValueType, Comparer>::ConstIterator();
}
 
#include <Foundation/Containers/Implementation/Map_inl.h>