ezEngine  Milestone 9
Map.h
1 #pragma once
2 
3 #include <Foundation/Containers/Deque.h>
4 
16 template <typename KeyType, typename ValueType, typename Comparer>
17 class ezMapBase
18 {
19 private:
20  struct Node;
21 
23  struct NilNode
24  {
25  Node* m_pParent = nullptr;
26  Node* m_pLink[2] = {nullptr, nullptr};
27  ezUInt8 m_uiLevel = 0;
28  };
29 
31  struct Node : public NilNode
32  {
33  KeyType m_Key;
34  ValueType m_Value;
35  };
36 
37 public:
40  {
41  typedef std::forward_iterator_tag iterator_category;
42  typedef ConstIterator value_type;
43  typedef ptrdiff_t difference_type;
44  typedef ConstIterator* pointer;
45  typedef ConstIterator& reference;
46 
47  EZ_DECLARE_POD_TYPE();
48 
50  EZ_ALWAYS_INLINE ConstIterator()
51  : m_pElement(nullptr)
52  {
53  } // [tested]
54 
56  EZ_ALWAYS_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
57 
59  EZ_ALWAYS_INLINE bool operator==(const typename ezMapBase<KeyType, ValueType, Comparer>::ConstIterator& it2) const
60  {
61  return (m_pElement == it2.m_pElement);
62  }
63 
65  EZ_ALWAYS_INLINE bool operator!=(const typename ezMapBase<KeyType, ValueType, Comparer>::ConstIterator& it2) const
66  {
67  return (m_pElement != it2.m_pElement);
68  }
69 
71  EZ_FORCE_INLINE const KeyType& Key() const
72  {
73  EZ_ASSERT_DEBUG(IsValid(), "Cannot access the 'key' of an invalid iterator.");
74  return m_pElement->m_Key;
75  } // [tested]
76 
78  EZ_FORCE_INLINE const ValueType& Value() const
79  {
80  EZ_ASSERT_DEBUG(IsValid(), "Cannot access the 'value' of an invalid iterator.");
81  return m_pElement->m_Value;
82  } // [tested]
83 
85  EZ_ALWAYS_INLINE ConstIterator& operator*() { return *this; }
86 
88  void Next(); // [tested]
89 
91  void Prev(); // [tested]
92 
94  EZ_ALWAYS_INLINE void operator++() { Next(); } // [tested]
95 
97  EZ_ALWAYS_INLINE void operator--() { Prev(); } // [tested]
98 
99  protected:
100  friend class ezMapBase<KeyType, ValueType, Comparer>;
101 
102  EZ_ALWAYS_INLINE explicit ConstIterator(Node* pInit)
103  : m_pElement(pInit)
104  {
105  }
106 
107  Node* m_pElement;
108  };
109 
111  struct Iterator : public ConstIterator
112  {
113  typedef std::forward_iterator_tag iterator_category;
114  typedef Iterator value_type;
115  typedef ptrdiff_t difference_type;
116  typedef Iterator* pointer;
117  typedef Iterator& reference;
118 
119  // this is required to pull in the const version of this function
120  using ConstIterator::Value;
121 
122  EZ_DECLARE_POD_TYPE();
123 
125  EZ_ALWAYS_INLINE Iterator()
126  : ConstIterator()
127  {
128  }
129 
131  EZ_FORCE_INLINE ValueType& Value()
132  {
133  EZ_ASSERT_DEBUG(this->IsValid(), "Cannot access the 'value' of an invalid iterator.");
134  return this->m_pElement->m_Value;
135  }
136 
138  EZ_ALWAYS_INLINE Iterator& operator*() { return *this; }
139 
140  private:
141  friend class ezMapBase<KeyType, ValueType, Comparer>;
142 
143  EZ_ALWAYS_INLINE explicit Iterator(Node* pInit)
144  : ConstIterator(pInit)
145  {
146  }
147  };
148 
149 protected:
151  ezMapBase(const Comparer& comparer, ezAllocatorBase* pAllocator); // [tested]
152 
154  ezMapBase(const ezMapBase<KeyType, ValueType, Comparer>& cc, ezAllocatorBase* pAllocator); // [tested]
155 
157  ~ezMapBase(); // [tested]
158 
161 
162 public:
164  bool IsEmpty() const; // [tested]
165 
167  ezUInt32 GetCount() const; // [tested]
168 
170  void Clear(); // [tested]
171 
173  Iterator GetIterator(); // [tested]
174 
176  ConstIterator GetIterator() const; // [tested]
177 
179  Iterator GetLastIterator(); // [tested]
180 
182  ConstIterator GetLastIterator() const; // [tested]
183 
185  template <typename CompatibleKeyType, typename CompatibleValueType>
186  Iterator Insert(CompatibleKeyType&& key, CompatibleValueType&& value); // [tested]
187 
189  template <typename CompatibleKeyType>
190  bool Remove(const CompatibleKeyType& key); // [tested]
191 
194  Iterator Remove(const Iterator& pos); // [tested]
195 
198  template <typename CompatibleKeyType>
199  Iterator FindOrAdd(CompatibleKeyType&& key, bool* bExisted = nullptr); // [tested]
200 
203  template <typename CompatibleKeyType>
204  ValueType& operator[](const CompatibleKeyType& key); // [tested]
205 
207  template <typename CompatibleKeyType>
208  const ValueType* GetValue(const CompatibleKeyType& key) const; // [tested]
209 
211  template <typename CompatibleKeyType>
212  ValueType* GetValue(const CompatibleKeyType& key); // [tested]
213 
215  template <typename CompatibleKeyType>
216  const ValueType& GetValueOrDefault(const CompatibleKeyType& key, const ValueType& defaultValue) const; // [tested]
217 
219  template <typename CompatibleKeyType>
220  Iterator Find(const CompatibleKeyType& key); // [tested]
221 
224  template <typename CompatibleKeyType>
225  Iterator LowerBound(const CompatibleKeyType& key); // [tested]
226 
229  template <typename CompatibleKeyType>
230  Iterator UpperBound(const CompatibleKeyType& key); // [tested]
231 
233  template <typename CompatibleKeyType>
234  ConstIterator Find(const CompatibleKeyType& key) const; // [tested]
235 
237  template <typename CompatibleKeyType>
238  bool Contains(const CompatibleKeyType& key) const; // [tested]
239 
242  template <typename CompatibleKeyType>
243  ConstIterator LowerBound(const CompatibleKeyType& key) const; // [tested]
244 
247  template <typename CompatibleKeyType>
248  ConstIterator UpperBound(const CompatibleKeyType& key) const; // [tested]
249 
251  ezAllocatorBase* GetAllocator() const { return m_Elements.GetAllocator(); }
252 
254  bool operator==(const ezMapBase<KeyType, ValueType, Comparer>& rhs) const; // [tested]
255 
257  bool operator!=(const ezMapBase<KeyType, ValueType, Comparer>& rhs) const; // [tested]
258 
260  ezUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
261 
263  void Swap(ezMapBase<KeyType, ValueType, Comparer>& other); // [tested]
264 
265 private:
266  template <typename CompatibleKeyType>
267  Node* Internal_Find(const CompatibleKeyType& key) const;
268  template <typename CompatibleKeyType>
269  Node* Internal_LowerBound(const CompatibleKeyType& key) const;
270  template <typename CompatibleKeyType>
271  Node* Internal_UpperBound(const CompatibleKeyType& key) const;
272 
273 private:
274  void Constructor();
275 
277  template <typename CompatibleKeyType>
278  Node* AcquireNode(CompatibleKeyType&& key, ValueType&& value, int m_uiLevel, Node* pParent);
279 
281  void ReleaseNode(Node* pNode);
282 
283  // \brief Red-Black Tree stuff(Anderson Tree to be exact).
284  // Code taken from here: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
285  Node* SkewNode(Node* root);
286  Node* SplitNode(Node* root);
287  void Insert(const KeyType& key, const ValueType& value, Node*& pInsertedNode);
288  Node* Remove(Node* root, const KeyType& key, bool& bRemoved);
289 
291  Node* GetLeftMost() const;
292 
294  Node* GetRightMost() const;
295 
297  void SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew);
298 
300  Node* m_pRoot;
301 
303  NilNode m_NilNode;
304 
306  ezUInt32 m_uiCount;
307 
310 
312  Node* m_pFreeElementStack;
313 
315  Comparer m_Comparer;
316 };
317 
318 
320 template <typename KeyType, typename ValueType, typename Comparer = ezCompareHelper<KeyType>,
321  typename AllocatorWrapper = ezDefaultAllocatorWrapper>
322 class ezMap : public ezMapBase<KeyType, ValueType, Comparer>
323 {
324 public:
325  ezMap();
326  ezMap(const Comparer& comparer, ezAllocatorBase* pAllocator);
327 
330 
332  void operator=(const ezMapBase<KeyType, ValueType, Comparer>& rhs);
333 };
334 
335 template <typename KeyType, typename ValueType, typename Comparer>
337 {
338  return container.GetIterator();
339 }
340 
341 template <typename KeyType, typename ValueType, typename Comparer>
343 {
344  return container.GetIterator();
345 }
346 
347 template <typename KeyType, typename ValueType, typename Comparer>
349 {
350  return container.GetIterator();
351 }
352 
353 template <typename KeyType, typename ValueType, typename Comparer>
355 {
357 }
358 
359 template <typename KeyType, typename ValueType, typename Comparer>
361 {
363 }
364 
365 template <typename KeyType, typename ValueType, typename Comparer>
367 {
369 }
370 
371 #include <Foundation/Containers/Implementation/Map_inl.h>
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: Map.h:260
void Prev()
Advances the iterator to the previous element in the map. The iterator will not be valid anymore...
Definition: Map_inl.h:64
Base class for all memory allocators.
Definition: AllocatorBase.h:21
Iterator Insert(CompatibleKeyType &&key, CompatibleValueType &&value)
Inserts the key/value pair into the tree and returns an Iterator to it. O(log n) operation.
Definition: Map_inl.h:481
Definition: Map.h:322
EZ_ALWAYS_INLINE Iterator()
Constructs an invalid iterator.
Definition: Map.h:125
#define EZ_ASSERT_DEBUG(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:88
const ValueType & GetValueOrDefault(const CompatibleKeyType &key, const ValueType &defaultValue) const
Either returns the value of the entry with the given key, if found, or the provided default value...
void Swap(ezMapBase< KeyType, ValueType, Comparer > &other)
Swaps this map with the other one.
Definition: Map_inl.h:815
EZ_FORCE_INLINE ValueType & Value()
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: Map.h:131
EZ_ALWAYS_INLINE bool IsValid() const
Checks whether this iterator points to a valid element.
Definition: Map.h:56
Base class for all iterators.
Definition: Map.h:39
EZ_ALWAYS_INLINE bool operator!=(const typename ezMapBase< KeyType, ValueType, Comparer >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: Map.h:65
const ValueType * GetValue(const CompatibleKeyType &key) const
Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr...
EZ_FORCE_INLINE const ValueType & Value() const
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: Map.h:78
Iterator UpperBound(const CompatibleKeyType &key)
Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid i...
EZ_FORCE_INLINE const KeyType & Key() const
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: Map.h:71
EZ_ALWAYS_INLINE ConstIterator & operator*()
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: Map.h:85
bool operator!=(const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
Comparison operator.
Definition: Map_inl.h:774
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: Deque_inl.h:928
bool operator==(const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
Comparison operator.
Definition: Map_inl.h:750
EZ_ALWAYS_INLINE ConstIterator()
Constructs an invalid iterator.
Definition: Map.h:50
bool Remove(const CompatibleKeyType &key)
Erases the key/value pair with the given key, if it exists. O(log n) operation.
Definition: Map_inl.h:491
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: Deque.h:160
void Clear()
Destroys all elements in the map and resets its size to zero.
Definition: Map_inl.h:163
Iterator LowerBound(const CompatibleKeyType &key)
Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid ...
bool Contains(const CompatibleKeyType &key) const
Checks whether the given key is in the container.
bool IsEmpty() const
Returns whether there are no elements in the map. O(1) operation.
Definition: Map_inl.h:182
EZ_ALWAYS_INLINE void operator++()
Shorthand for &#39;Next&#39;.
Definition: Map.h:94
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: Map.h:251
Iterator Find(const CompatibleKeyType &key)
Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found...
ezMapBase(const Comparer &comparer, ezAllocatorBase *pAllocator)
Initializes the map to be empty.
Definition: Map_inl.h:134
ValueType & operator[](const CompatibleKeyType &key)
Allows read/write access to the value stored under the given key. If there is no such key...
Definition: Map_inl.h:396
EZ_ALWAYS_INLINE void operator--()
Shorthand for &#39;Prev&#39;.
Definition: Map.h:97
~ezMapBase()
Destroys all elements from the map.
Definition: Map_inl.h:148
An associative container. Similar to STL::map.
Definition: Map.h:17
Iterator GetIterator()
Returns an Iterator to the very first element.
Definition: Map_inl.h:195
void Next()
Advances the iterator to the next element in the map. The iterator will not be valid anymore...
Definition: Map_inl.h:10
Iterator FindOrAdd(CompatibleKeyType &&key, bool *bExisted=nullptr)
Searches for the given key and returns an iterator to it. If it did not exist yet, it is default-created. bExisted is set to true, if the key was found, false if it needed to be created.
Definition: Map_inl.h:403
Iterator GetLastIterator()
Returns an Iterator to the very last element. For reverse traversal.
Definition: Map_inl.h:207
ezUInt32 GetCount() const
Returns the number of elements currently stored in the map. O(1) operation.
Definition: Map_inl.h:188
EZ_ALWAYS_INLINE bool operator==(const typename ezMapBase< KeyType, ValueType, Comparer >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: Map.h:59
void operator=(const ezMapBase< KeyType, ValueType, Comparer > &rhs)
Copies all key/value pairs from the given map into this one.
Definition: Map_inl.h:154
EZ_ALWAYS_INLINE Iterator & operator*()
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: Map.h:138
Forward Iterator to iterate over all elements in sorted order.
Definition: Map.h:111