ezEngine  Milestone 9
Map_inl.h
1 #pragma once
2 
3 #include <Foundation/Math/Math.h>
4 
5 // ***** Const Iterator *****
6 
7 #define STACK_SIZE 48
8 
9 template <typename KeyType, typename ValueType, typename Comparer>
11 {
12  const ezInt32 dir0 = 0;
13  const ezInt32 dir1 = 1;
14 
15  if (m_pElement == nullptr)
16  {
17  EZ_ASSERT_DEV(m_pElement != nullptr, "The Iterator is invalid (end).");
18  return;
19  }
20 
21  // if this element has a right child, go there and then search for the left most child of that
22  if (m_pElement->m_pLink[dir1] != m_pElement->m_pLink[dir1]->m_pLink[dir1])
23  {
24  m_pElement = m_pElement->m_pLink[dir1];
25 
26  while (m_pElement->m_pLink[dir0] != m_pElement->m_pLink[dir0]->m_pLink[dir0])
27  m_pElement = m_pElement->m_pLink[dir0];
28 
29  return;
30  }
31 
32  // if this element has a parent and this element is that parents left child, go directly to the parent
33  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
34  (m_pElement->m_pParent->m_pLink[dir0] == m_pElement))
35  {
36  m_pElement = m_pElement->m_pParent;
37  return;
38  }
39 
40  // if this element has a parent and this element is that parents right child, search for the next parent, whose left child this is
41  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
42  (m_pElement->m_pParent->m_pLink[dir1] == m_pElement))
43  {
44  while (m_pElement->m_pParent->m_pLink[dir1] == m_pElement)
45  m_pElement = m_pElement->m_pParent;
46 
47  // if we are at the root node..
48  if ((m_pElement->m_pParent == nullptr) ||
49  (m_pElement->m_pParent == m_pElement->m_pParent->m_pParent))
50  {
51  m_pElement = nullptr;
52  return;
53  }
54 
55  m_pElement = m_pElement->m_pParent;
56  return;
57  }
58 
59  m_pElement = nullptr;
60  return;
61 }
62 
63 template <typename KeyType, typename ValueType, typename Comparer>
65 {
66  const ezInt32 dir0 = 1;
67  const ezInt32 dir1 = 0;
68 
69  if (m_pElement == nullptr)
70  {
71  EZ_ASSERT_DEV(m_pElement != nullptr, "The Iterator is invalid (end).");
72  return;
73  }
74 
75  // if this element has a right child, go there and then search for the left most child of that
76  if (m_pElement->m_pLink[dir1] != m_pElement->m_pLink[dir1]->m_pLink[dir1])
77  {
78  m_pElement = m_pElement->m_pLink[dir1];
79 
80  while (m_pElement->m_pLink[dir0] != m_pElement->m_pLink[dir0]->m_pLink[dir0])
81  m_pElement = m_pElement->m_pLink[dir0];
82 
83  return;
84  }
85 
86  // if this element has a parent and this element is that parents left child, go directly to the parent
87  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
88  (m_pElement->m_pParent->m_pLink[dir0] == m_pElement))
89  {
90  m_pElement = m_pElement->m_pParent;
91  return;
92  }
93 
94  // if this element has a parent and this element is that parents right child, search for the next parent, whose left child this is
95  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
96  (m_pElement->m_pParent->m_pLink[dir1] == m_pElement))
97  {
98  while (m_pElement->m_pParent->m_pLink[dir1] == m_pElement)
99  m_pElement = m_pElement->m_pParent;
100 
101  // if we are at the root node..
102  if ((m_pElement->m_pParent == nullptr) ||
103  (m_pElement->m_pParent == m_pElement->m_pParent->m_pParent))
104  {
105  m_pElement = nullptr;
106  return;
107  }
108 
109  m_pElement = m_pElement->m_pParent;
110  return;
111  }
112 
113  m_pElement = nullptr;
114  return;
115 }
116 
117 // ***** ezMapBase *****
118 
119 template <typename KeyType, typename ValueType, typename Comparer>
121 {
122  m_uiCount = 0;
123 
124  m_NilNode.m_uiLevel = 0;
125  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
126  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
127  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
128 
129  m_pFreeElementStack = nullptr;
130  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
131 }
132 
133 template <typename KeyType, typename ValueType, typename Comparer>
134 ezMapBase<KeyType, ValueType, Comparer>::ezMapBase(const Comparer& comparer, ezAllocatorBase* pAllocator) : m_Elements(pAllocator), m_Comparer(comparer)
135 {
136  Constructor();
137 }
138 
139 template <typename KeyType, typename ValueType, typename Comparer>
141 {
142  Constructor();
143 
144  operator=(cc);
145 }
146 
147 template <typename KeyType, typename ValueType, typename Comparer>
149 {
150  Clear();
151 }
152 
153 template <typename KeyType, typename ValueType, typename Comparer>
155 {
156  Clear();
157 
158  for (ConstIterator it = rhs.GetIterator(); it.IsValid(); ++it)
159  Insert(it.Key(), it.Value());
160 }
161 
162 template <typename KeyType, typename ValueType, typename Comparer>
164 {
165  for (Iterator it = GetIterator(); it.IsValid(); ++it)
166  ezMemoryUtils::Destruct<Node>(it.m_pElement, 1);
167 
168  m_pFreeElementStack = nullptr;
169  m_Elements.Clear();
170 
171  m_uiCount = 0;
172 
173  m_NilNode.m_uiLevel = 0;
174  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
175  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
176  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
177 
178  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
179 }
180 
181 template <typename KeyType, typename ValueType, typename Comparer>
183 {
184  return (m_uiCount == 0);
185 }
186 
187 template <typename KeyType, typename ValueType, typename Comparer>
188 EZ_ALWAYS_INLINE ezUInt32 ezMapBase<KeyType, ValueType, Comparer>::GetCount() const
189 {
190  return m_uiCount;
191 }
192 
193 
194 template <typename KeyType, typename ValueType, typename Comparer>
196 {
197  return Iterator(GetLeftMost());
198 }
199 
200 template <typename KeyType, typename ValueType, typename Comparer>
202 {
203  return ConstIterator(GetLeftMost());
204 }
205 
206 template <typename KeyType, typename ValueType, typename Comparer>
208 {
209  return Iterator(GetRightMost());
210 }
211 
212 template <typename KeyType, typename ValueType, typename Comparer>
214 {
215  return ConstIterator(GetRightMost());
216 }
217 
218 template <typename KeyType, typename ValueType, typename Comparer>
220 {
221  if (IsEmpty())
222  return nullptr;
223 
224  Node* pNode = m_pRoot;
225 
226  while (pNode->m_pLink[0] != &m_NilNode)
227  pNode = pNode->m_pLink[0];
228 
229  return pNode;
230 }
231 
232 template <typename KeyType, typename ValueType, typename Comparer>
234 {
235  if (IsEmpty())
236  return nullptr;
237 
238  Node* pNode = m_pRoot;
239 
240  while (pNode->m_pLink[1] != &m_NilNode)
241  pNode = pNode->m_pLink[1];
242 
243  return pNode;
244 }
245 
246 template <typename KeyType, typename ValueType, typename Comparer>
247 template <typename CompatibleKeyType>
249 {
250  Node* pNode = m_pRoot;
251 
252  while (pNode != &m_NilNode)
253  {
254  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
255  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
256 
257  if (dir == dir2)
258  break;
259 
260  pNode = pNode->m_pLink[dir];
261  }
262 
263  if (pNode == &m_NilNode)
264  return nullptr;
265 
266  return pNode;
267 }
268 
269 template <typename KeyType, typename ValueType, typename Comparer>
270 template <typename CompatibleKeyType>
271 EZ_ALWAYS_INLINE const ValueType* ezMapBase<KeyType, ValueType, Comparer>::GetValue(const CompatibleKeyType& key) const
272 {
273  Node* pNode = Internal_Find<CompatibleKeyType>(key);
274  return pNode ? &pNode->m_Value : nullptr;
275 }
276 
277 template <typename KeyType, typename ValueType, typename Comparer>
278 template <typename CompatibleKeyType>
279 EZ_ALWAYS_INLINE ValueType* ezMapBase<KeyType, ValueType, Comparer>::GetValue(const CompatibleKeyType& key)
280 {
281  Node* pNode = Internal_Find<CompatibleKeyType>(key);
282  return pNode ? &pNode->m_Value : nullptr;
283 }
284 
285 template <typename KeyType, typename ValueType, typename Comparer>
286 template <typename CompatibleKeyType>
287 EZ_ALWAYS_INLINE const ValueType& ezMapBase<KeyType, ValueType, Comparer>::GetValueOrDefault(const CompatibleKeyType& key, const ValueType& defaultValue) const
288 {
289  Node* pNode = Internal_Find<CompatibleKeyType>(key);
290  return pNode ? pNode->m_Value : defaultValue;
291 }
292 
293 template <typename KeyType, typename ValueType, typename Comparer>
294 template <typename CompatibleKeyType>
295 EZ_ALWAYS_INLINE typename ezMapBase<KeyType, ValueType, Comparer>::Iterator ezMapBase<KeyType, ValueType, Comparer>::Find(const CompatibleKeyType& key)
296 {
297  return Iterator(Internal_Find<CompatibleKeyType>(key));
298 }
299 
300 template <typename KeyType, typename ValueType, typename Comparer>
301 template <typename CompatibleKeyType>
302 EZ_ALWAYS_INLINE typename ezMapBase<KeyType, ValueType, Comparer>::ConstIterator ezMapBase<KeyType, ValueType, Comparer>::Find(const CompatibleKeyType& key) const
303 {
304  return ConstIterator(Internal_Find<CompatibleKeyType>(key));
305 }
306 
307 template <typename KeyType, typename ValueType, typename Comparer>
308 template <typename CompatibleKeyType>
309 EZ_ALWAYS_INLINE bool ezMapBase<KeyType, ValueType, Comparer>::Contains(const CompatibleKeyType& key) const
310 {
311  return Internal_Find(key) != nullptr;
312 }
313 
314 template <typename KeyType, typename ValueType, typename Comparer>
315 template <typename CompatibleKeyType>
317 {
318  Node* pNode = m_pRoot;
319  Node* pNodeSmaller = nullptr;
320 
321  while (pNode != &m_NilNode)
322  {
323  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
324  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
325 
326  if (dir == dir2)
327  return pNode;
328 
329  if (dir == 0)
330  pNodeSmaller = pNode;
331 
332  pNode = pNode->m_pLink[dir];
333  }
334 
335  return pNodeSmaller;
336 }
337 
338 template <typename KeyType, typename ValueType, typename Comparer>
339 template <typename CompatibleKeyType>
341 {
342  return Iterator(Internal_LowerBound(key));
343 }
344 
345 template <typename KeyType, typename ValueType, typename Comparer>
346 template <typename CompatibleKeyType>
348 {
349  return ConstIterator(Internal_LowerBound(key));
350 }
351 
352 template <typename KeyType, typename ValueType, typename Comparer>
353 template <typename CompatibleKeyType>
355 {
356  Node* pNode = m_pRoot;
357  Node* pNodeSmaller = nullptr;
358 
359  while (pNode != &m_NilNode)
360  {
361  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
362  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
363 
364  if (dir == dir2)
365  {
366  ConstIterator it(pNode);
367  ++it;
368  return it.m_pElement;
369  }
370 
371  if (dir == 0)
372  pNodeSmaller = pNode;
373 
374  pNode = pNode->m_pLink[dir];
375  }
376 
377  return pNodeSmaller;
378 }
379 
380 template <typename KeyType, typename ValueType, typename Comparer>
381 template <typename CompatibleKeyType>
383 {
384  return Iterator(Internal_UpperBound(key));
385 }
386 
387 template <typename KeyType, typename ValueType, typename Comparer>
388 template <typename CompatibleKeyType>
390 {
391  return ConstIterator(Internal_UpperBound(key));
392 }
393 
394 template <typename KeyType, typename ValueType, typename Comparer>
395 template <typename CompatibleKeyType>
396 ValueType& ezMapBase<KeyType, ValueType, Comparer>::operator[](const CompatibleKeyType& key)
397 {
398  return FindOrAdd(key).Value();
399 }
400 
401 template <typename KeyType, typename ValueType, typename Comparer>
402 template <typename CompatibleKeyType>
404 {
405  Node* pNilNode = reinterpret_cast<Node*>(&m_NilNode);
406  Node* pInsertedNode = nullptr;
407 
408  {
409  Node* root = m_pRoot;
410 
411  if (m_pRoot != pNilNode)
412  {
413  Node* it = m_pRoot;
414  Node* up[STACK_SIZE];
415 
416  ezInt32 top = 0;
417  ezUInt32 dir = 0;
418 
419  while (true)
420  {
421  if (m_Comparer.Equal(it->m_Key, key))
422  {
423  if (bExisted)
424  *bExisted = true;
425 
426  return Iterator(it);
427  }
428 
429  dir = m_Comparer.Less(it->m_Key, key) ? 1 : 0;
430 
431  EZ_ASSERT_DEBUG(top < STACK_SIZE, "ezMapBase's internal stack is not large enough to be able to sort {0} elements.", GetCount());
432  up[top++] = it;
433 
434  if (it->m_pLink[dir] == pNilNode)
435  break;
436 
437  it = it->m_pLink[dir];
438  }
439 
440  pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), ValueType(), 1, it);
441  it->m_pLink[dir] = pInsertedNode;
442 
443  while (--top >= 0)
444  {
445  if (top != 0)
446  dir = (up[top - 1]->m_pLink[1] == up[top]) ? 1 : 0;
447 
448  up[top] = SkewNode(up[top]);
449  up[top] = SplitNode(up[top]);
450 
451  if (top != 0)
452  {
453  up[top - 1]->m_pLink[dir] = up[top];
454  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
455  }
456  else
457  root = up[top];
458  }
459  }
460  else
461  {
462  pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), ValueType(), 1, pNilNode);
463  root = pInsertedNode;
464  }
465 
466  m_pRoot = root;
467  m_pRoot->m_pParent = pNilNode;
468  m_NilNode.m_pParent = pNilNode;
469  }
470 
471  EZ_ASSERT_DEBUG(pInsertedNode != nullptr, "Implementation Error.");
472 
473  if (bExisted)
474  *bExisted = false;
475 
476  return Iterator(pInsertedNode);
477 }
478 
479 template <typename KeyType, typename ValueType, typename Comparer>
480 template <typename CompatibleKeyType, typename CompatibleValueType>
482 {
483  auto it = FindOrAdd(std::forward<CompatibleKeyType>(key));
484  it.Value() = std::forward<CompatibleValueType>(value);
485 
486  return it;
487 }
488 
489 template <typename KeyType, typename ValueType, typename Comparer>
490 template <typename CompatibleKeyType>
491 bool ezMapBase<KeyType, ValueType, Comparer>::Remove(const CompatibleKeyType& key)
492 {
493  bool bRemoved = true;
494  m_pRoot = Remove(m_pRoot, key, bRemoved);
495  m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
496  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
497 
498  return bRemoved;
499 }
500 
501 template <typename KeyType, typename ValueType, typename Comparer>
502 template <typename CompatibleKeyType>
503 typename ezMapBase<KeyType, ValueType, Comparer>::Node* ezMapBase<KeyType, ValueType, Comparer>::AcquireNode(CompatibleKeyType&& key, ValueType&& value, ezInt32 uiLevel, Node* pParent)
504 {
505  Node* pNode;
506 
507  if (m_pFreeElementStack == nullptr)
508  {
509  m_Elements.PushBack();
510  pNode = &m_Elements.PeekBack();
511  }
512  else
513  {
514  pNode = m_pFreeElementStack;
515  m_pFreeElementStack = m_pFreeElementStack->m_pParent;
516  }
517 
518  ezMemoryUtils::Construct(pNode, 1);
519 
520  pNode->m_pParent = pParent;
521  pNode->m_Key = std::forward<CompatibleKeyType>(key);
522  pNode->m_Value = std::move(value);
523  pNode->m_uiLevel = uiLevel;
524  pNode->m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
525  pNode->m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
526 
527  ++m_uiCount;
528 
529  return pNode;
530 }
531 
532 template <typename KeyType, typename ValueType, typename Comparer>
534 {
535  EZ_ASSERT_DEV(pNode != nullptr, "pNode is invalid.");
536  EZ_ASSERT_DEV(pNode != &m_NilNode, "pNode is invalid.");
537 
538  ezMemoryUtils::Destruct<Node>(pNode, 1);
539 
540  // try to reduce the element array, if possible
541  if (pNode == &m_Elements.PeekBack())
542  {
543  m_Elements.PopBack();
544  }
545  else if (pNode == &m_Elements.PeekFront())
546  {
547  m_Elements.PopFront();
548  }
549  else
550  {
551  pNode->m_pParent = m_pFreeElementStack;
552  m_pFreeElementStack = pNode;
553  }
554 
555  --m_uiCount;
556 }
557 
558 template <typename KeyType, typename ValueType, typename Comparer>
560 {
561  if ((root->m_pLink[0]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
562  {
563  Node* save = root->m_pLink[0];
564  root->m_pLink[0] = save->m_pLink[1];
565  root->m_pLink[0]->m_pParent = root;
566  save->m_pLink[1] = root;
567  save->m_pLink[1]->m_pParent = save;
568  root = save;
569  }
570 
571  return root;
572 }
573 
574 template <typename KeyType, typename ValueType, typename Comparer>
576 {
577  if ((root->m_pLink[1]->m_pLink[1]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
578  {
579  Node* save = root->m_pLink[1];
580  root->m_pLink[1] = save->m_pLink[0];
581  root->m_pLink[1]->m_pParent = root;
582  save->m_pLink[0] = root;
583  save->m_pLink[0]->m_pParent = save;
584  root = save;
585  ++root->m_uiLevel;
586  }
587 
588  return root;
589 }
590 
591 template <typename KeyType, typename ValueType, typename Comparer>
592 typename ezMapBase<KeyType, ValueType, Comparer>::Node* ezMapBase<KeyType, ValueType, Comparer>::Remove(Node* root, const KeyType& key, bool& bRemoved)
593 {
594  bRemoved = false;
595 
596  Node* ToErase = reinterpret_cast<Node*>(&m_NilNode);
597  Node* ToOverride = reinterpret_cast<Node*>(&m_NilNode);
598 
599  if (root != &m_NilNode)
600  {
601  Node* it = root;
602  Node* up[STACK_SIZE];
603  ezInt32 top = 0;
604  ezInt32 dir = 0;
605 
606  while (true)
607  {
608  EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error");
609  up[top++] = it;
610 
611  if (it == &m_NilNode)
612  return root;
613 
614  if (m_Comparer.Equal(it->m_Key, key))
615  break;
616 
617  dir = m_Comparer.Less(it->m_Key, key) ? 1 : 0;
618 
619  it = it->m_pLink[dir];
620  }
621 
622  ToOverride = it;
623 
624  if ((it->m_pLink[0] == &m_NilNode) || (it->m_pLink[1] == &m_NilNode))
625  {
626  ezInt32 dir2 = it->m_pLink[0] == &m_NilNode;
627 
628  if (--top != 0)
629  {
630  EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error");
631  up[top - 1]->m_pLink[dir] = it->m_pLink[dir2];
632  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
633  }
634  else
635  root = it->m_pLink[1];
636  }
637  else
638  {
639  Node* heir = it->m_pLink[1];
640  Node* prev = it;
641 
642  while (heir->m_pLink[0] != &m_NilNode)
643  {
644  EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error");
645  up[top++] = prev = heir;
646 
647  heir = heir->m_pLink[0];
648  }
649 
650  ToErase = heir;
651  ToOverride = it;
652 
653  prev->m_pLink[prev == it] = heir->m_pLink[1];
654  prev->m_pLink[prev == it]->m_pParent = prev;
655  }
656 
657  while (--top >= 0)
658  {
659  if (top != 0)
660  {
661  EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error");
662  dir = up[top - 1]->m_pLink[1] == up[top];
663  }
664 
665  EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error");
666 
667  if ((up[top]->m_pLink[0]->m_uiLevel < up[top]->m_uiLevel - 1) || (up[top]->m_pLink[1]->m_uiLevel < up[top]->m_uiLevel - 1))
668  {
669  if (up[top]->m_pLink[1]->m_uiLevel > --up[top]->m_uiLevel)
670  up[top]->m_pLink[1]->m_uiLevel = up[top]->m_uiLevel;
671 
672  up[top] = SkewNode(up[top]);
673  up[top]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]);
674  up[top]->m_pLink[1]->m_pParent = up[top];
675 
676  up[top]->m_pLink[1]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]->m_pLink[1]);
677  up[top] = SplitNode(up[top]);
678  up[top]->m_pLink[1] = SplitNode(up[top]->m_pLink[1]);
679  up[top]->m_pLink[1]->m_pParent = up[top];
680  }
681 
682  if (top != 0)
683  {
684  EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error");
685 
686  up[top - 1]->m_pLink[dir] = up[top];
687  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
688  }
689  else
690  {
691  EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error");
692  root = up[top];
693  }
694  }
695  }
696 
697  root->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
698 
699 
700  // if necessary, swap nodes
701  if (ToErase != &m_NilNode)
702  {
703  Node* parent = ToOverride->m_pParent;
704 
705  if (parent != &m_NilNode)
706  {
707  if (parent->m_pLink[0] == ToOverride)
708  {
709  parent->m_pLink[0] = ToErase;
710  parent->m_pLink[0]->m_pParent = parent;
711  }
712  if (parent->m_pLink[1] == ToOverride)
713  {
714  parent->m_pLink[1] = ToErase;
715  parent->m_pLink[1]->m_pParent = parent;
716  }
717  }
718  else
719  root = ToErase;
720 
721  ToErase->m_uiLevel = ToOverride->m_uiLevel;
722  ToErase->m_pLink[0] = ToOverride->m_pLink[0];
723  ToErase->m_pLink[0]->m_pParent = ToErase;
724  ToErase->m_pLink[1] = ToOverride->m_pLink[1];
725  ToErase->m_pLink[1]->m_pParent = ToErase;
726  }
727 
728  // remove the erased node
729  if (ToOverride != &m_NilNode)
730  {
731  bRemoved = true;
732  ReleaseNode(ToOverride);
733  }
734 
735  return root;
736 }
737 
738 template <typename KeyType, typename ValueType, typename Comparer>
740 {
741  EZ_ASSERT_DEV(pos.m_pElement != nullptr, "The Iterator(pos) is invalid.");
742 
743  Iterator temp(pos);
744  ++temp;
745  Remove(pos.Key());
746  return temp;
747 }
748 
749 template <typename KeyType, typename ValueType, typename Comparer>
751 {
752  if (GetCount() != rhs.GetCount())
753  return false;
754 
755  auto itLhs = GetIterator();
756  auto itRhs = rhs.GetIterator();
757 
758  while (itLhs.IsValid())
759  {
760  if (!m_Comparer.Equal(itLhs.Key(), itRhs.Key()))
761  return false;
762 
763  if (itLhs.Value() != itRhs.Value())
764  return false;
765 
766  ++itLhs;
767  ++itRhs;
768  }
769 
770  return true;
771 }
772 
773 template <typename KeyType, typename ValueType, typename Comparer>
775 {
776  return !operator==(rhs);
777 }
778 
779 #undef STACK_SIZE
780 
781 
782 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
783 ezMap<KeyType, ValueType, Comparer, AllocatorWrapper>::ezMap() : ezMapBase<KeyType, ValueType, Comparer>(Comparer(), AllocatorWrapper::GetAllocator())
784 {
785 }
786 
787 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
788 ezMap<KeyType, ValueType, Comparer, AllocatorWrapper>::ezMap(const Comparer& comparer, ezAllocatorBase* pAllocator) : ezMapBase<KeyType, ValueType, Comparer>(comparer, pAllocator)
789 {
790 }
791 
792 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
793 ezMap<KeyType, ValueType, Comparer, AllocatorWrapper>::ezMap(const ezMap<KeyType, ValueType, Comparer, AllocatorWrapper>& other) : ezMapBase<KeyType, ValueType, Comparer>(other, AllocatorWrapper::GetAllocator())
794 {
795 }
796 
797 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
798 ezMap<KeyType, ValueType, Comparer, AllocatorWrapper>::ezMap(const ezMapBase<KeyType, ValueType, Comparer>& other) : ezMapBase<KeyType, ValueType, Comparer>(other, AllocatorWrapper::GetAllocator())
799 {
800 }
801 
802 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
804 {
806 }
807 
808 template <typename KeyType, typename ValueType, typename Comparer, typename AllocatorWrapper>
810 {
812 }
813 
814 template <typename KeyType, typename ValueType, typename Comparer>
816 {
817  SwapNilNode(this->m_pRoot, &this->m_NilNode, &other.m_NilNode);
818  SwapNilNode(other.m_pRoot, &other.m_NilNode, &this->m_NilNode);
819 
820  ezMath::Swap(this->m_pRoot, other.m_pRoot);
821  ezMath::Swap(this->m_uiCount, other.m_uiCount);
822  ezMath::Swap(this->m_pFreeElementStack, other.m_pFreeElementStack);
823  ezMath::Swap(this->m_Comparer, other.m_Comparer);
824 
825  // the set allocator is stored in this array
826  m_Elements.Swap(other.m_Elements);
827 
828 }
829 
830 template <typename KeyType, typename ValueType, typename Comparer>
831 void ezMapBase<KeyType, ValueType, Comparer>::SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew)
832 {
833  if (pCurNode == pOld)
834  {
835  pCurNode = reinterpret_cast<Node*>(pNew);
836  return;
837  }
838 
839  SwapNilNode(pCurNode->m_pLink[0], pOld, pNew);
840  SwapNilNode(pCurNode->m_pLink[1], pOld, pNew);
841 }
842 
EZ_ALWAYS_INLINE void Swap(T &f1, T &f2)
Swaps the values in the two variables f1 and f2.
Definition: Math_inl.h:112
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
#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
Base class for all iterators.
Definition: Map.h:39
static void Construct(T *pDestination, size_t uiCount)
Constructs uiCount objects of type T in a raw buffer at pDestination.
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...
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...
bool operator!=(const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
Comparison operator.
Definition: Map_inl.h:774
#define EZ_ASSERT_DEV(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:116
bool operator==(const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
Comparison operator.
Definition: Map_inl.h:750
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
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
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
~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
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
Forward Iterator to iterate over all elements in sorted order.
Definition: Map.h:111