ezEngine  Milestone 7
Set_inl.h
1 #pragma once
2 
3 #include <Foundation/Math/Math.h>
4 
5 // ***** Const Iterator *****
6 
7 template <typename KeyType, typename Comparer>
9 {
10  const ezInt32 dir0 = 0;
11  const ezInt32 dir1 = 1;
12 
13  if (m_pElement == nullptr)
14  {
15  EZ_ASSERT_DEV(m_pElement != nullptr, "The Iterator is invalid (end).");
16  return;
17  }
18 
19  // if this element has a right child, go there and then search for the left most child of that
20  if (m_pElement->m_pLink[dir1] != m_pElement->m_pLink[dir1]->m_pLink[dir1])
21  {
22  m_pElement = m_pElement->m_pLink[dir1];
23 
24  while (m_pElement->m_pLink[dir0] != m_pElement->m_pLink[dir0]->m_pLink[dir0])
25  m_pElement = m_pElement->m_pLink[dir0];
26 
27  return;
28  }
29 
30  // if this element has a parent and this element is that parents left child, go directly to the parent
31  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
32  (m_pElement->m_pParent->m_pLink[dir0] == m_pElement))
33  {
34  m_pElement = m_pElement->m_pParent;
35  return;
36  }
37 
38  // if this element has a parent and this element is that parents right child, search for the next parent, whose left child this is
39  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
40  (m_pElement->m_pParent->m_pLink[dir1] == m_pElement))
41  {
42  while (m_pElement->m_pParent->m_pLink[dir1] == m_pElement)
43  m_pElement = m_pElement->m_pParent;
44 
45  // if we are at the root node..
46  if ((m_pElement->m_pParent == m_pElement->m_pParent->m_pParent) ||
47  (m_pElement->m_pParent == nullptr))
48  {
49  m_pElement = nullptr;
50  return;
51  }
52 
53  m_pElement = m_pElement->m_pParent;
54  return;
55  }
56 
57  m_pElement = nullptr;
58  return;
59 }
60 
61 template <typename KeyType, typename Comparer>
63 {
64  const ezInt32 dir0 = 1;
65  const ezInt32 dir1 = 0;
66 
67  if (m_pElement == nullptr)
68  {
69  EZ_ASSERT_DEV(m_pElement != nullptr, "The Iterator is invalid (end).");
70  return;
71  }
72 
73  // if this element has a right child, go there and then search for the left most child of that
74  if (m_pElement->m_pLink[dir1] != m_pElement->m_pLink[dir1]->m_pLink[dir1])
75  {
76  m_pElement = m_pElement->m_pLink[dir1];
77 
78  while (m_pElement->m_pLink[dir0] != m_pElement->m_pLink[dir0]->m_pLink[dir0])
79  m_pElement = m_pElement->m_pLink[dir0];
80 
81  return;
82  }
83 
84  // if this element has a parent and this element is that parents left child, go directly to the parent
85  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
86  (m_pElement->m_pParent->m_pLink[dir0] == m_pElement))
87  {
88  m_pElement = m_pElement->m_pParent;
89  return;
90  }
91 
92  // if this element has a parent and this element is that parents right child, search for the next parent, whose left child this is
93  if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) &&
94  (m_pElement->m_pParent->m_pLink[dir1] == m_pElement))
95  {
96  while (m_pElement->m_pParent->m_pLink[dir1] == m_pElement)
97  m_pElement = m_pElement->m_pParent;
98 
99  // if we are at the root node..
100  if ((m_pElement->m_pParent == m_pElement->m_pParent->m_pParent) ||
101  (m_pElement->m_pParent == nullptr))
102  {
103  m_pElement = nullptr;
104  return;
105  }
106 
107  m_pElement = m_pElement->m_pParent;
108  return;
109  }
110 
111  m_pElement = nullptr;
112  return;
113 }
114 
115 // ***** ezSetBase *****
116 
117 template <typename KeyType, typename Comparer>
118 EZ_FORCE_INLINE ezSetBase<KeyType, Comparer>::NilNode::NilNode() : m_uiLevel(0), m_pParent(nullptr)
119 {
120 }
121 
122 template <typename KeyType, typename Comparer>
124 {
125  m_uiCount = 0;
126 
127  m_NilNode.m_uiLevel = 0;
128  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
129  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
130  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
131 
132  m_pFreeElementStack = nullptr;
133  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
134 }
135 
136 template <typename KeyType, typename Comparer>
137 ezSetBase<KeyType, Comparer>::ezSetBase(const Comparer& comparer, ezAllocatorBase* pAllocator) : m_Elements(pAllocator), m_Comparer(comparer)
138 {
139  Constructor();
140 }
141 
142 template <typename KeyType, typename Comparer>
144 {
145  Constructor();
146 
147  operator=(cc);
148 }
149 
150 template <typename KeyType, typename Comparer>
152 {
153  Clear();
154 }
155 
156 template <typename KeyType, typename Comparer>
158 {
159  Clear();
160 
161  for (Iterator it = rhs.GetIterator(); it.IsValid(); ++it)
162  Insert(it.Key());
163 }
164 
165 template <typename KeyType, typename Comparer>
167 {
168  for (Iterator it = GetIterator(); it.IsValid(); ++it)
169  ezMemoryUtils::Destruct<Node>(it.m_pElement, 1);
170 
171  m_pFreeElementStack = nullptr;
172  m_Elements.Clear();
173 
174  m_uiCount = 0;
175 
176  m_NilNode.m_uiLevel = 0;
177  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
178  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
179  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
180 
181  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
182 }
183 
184 template <typename KeyType, typename Comparer>
185 EZ_FORCE_INLINE bool ezSetBase<KeyType, Comparer>::IsEmpty() const
186 {
187  return (m_uiCount == 0);
188 }
189 
190 template <typename KeyType, typename Comparer>
191 EZ_FORCE_INLINE ezUInt32 ezSetBase<KeyType, Comparer>::GetCount() const
192 {
193  return m_uiCount;
194 }
195 
196 
197 template <typename KeyType, typename Comparer>
199 {
200  return Iterator(GetLeftMost());
201 }
202 
203 template <typename KeyType, typename Comparer>
205 {
206  return Iterator(GetRightMost());
207 }
208 
209 template <typename KeyType, typename Comparer>
211 {
212  if (IsEmpty())
213  return nullptr;
214 
215  Node* pNode = m_pRoot;
216 
217  while (pNode->m_pLink[0] != &m_NilNode)
218  pNode = pNode->m_pLink[0];
219 
220  return pNode;
221 }
222 
223 template <typename KeyType, typename Comparer>
225 {
226  if (IsEmpty())
227  return nullptr;
228 
229  Node* pNode = m_pRoot;
230 
231  while (pNode->m_pLink[1] != &m_NilNode)
232  pNode = pNode->m_pLink[1];
233 
234  return pNode;
235 }
236 
237 template <typename KeyType, typename Comparer>
239 {
240  Node* pNode = m_pRoot;
241 
242  while (pNode != &m_NilNode)// && (pNode->m_Key != key))
243  {
244  const ezInt32 dir = (ezInt32) m_Comparer.Less(pNode->m_Key, key);
245  const ezInt32 dir2= (ezInt32) m_Comparer.Less(key, pNode->m_Key);
246 
247  if (dir == dir2)
248  break;
249 
250  pNode = pNode->m_pLink[dir];
251  }
252 
253  if (pNode == &m_NilNode)
254  return nullptr;
255 
256  return pNode;
257 }
258 
259 template <typename KeyType, typename Comparer>
260 EZ_FORCE_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::Find(const KeyType& key) const
261 {
262  return Iterator(Internal_Find(key));
263 }
264 
265 template <typename KeyType, typename Comparer>
266 EZ_FORCE_INLINE bool ezSetBase<KeyType, Comparer>::Contains(const KeyType& key) const
267 {
268  return Internal_Find(key) != nullptr;
269 }
270 
271 template <typename KeyType, typename Comparer>
273 {
274  for (const KeyType& key : operand)
275  {
276  if (!Contains(key))
277  return false;
278  }
279 
280  return true;
281 }
282 
283 template <typename KeyType, typename Comparer>
285 {
286  Node* pNode = m_pRoot;
287  Node* pNodeSmaller = nullptr;
288 
289  while (pNode != &m_NilNode)
290  {
291  const ezInt32 dir = (ezInt32) m_Comparer.Less(pNode->m_Key, key);
292  const ezInt32 dir2= (ezInt32) m_Comparer.Less(key, pNode->m_Key);
293 
294  if (dir == dir2)
295  return pNode;
296 
297  if (dir == 0)
298  pNodeSmaller = pNode;
299 
300  pNode = pNode->m_pLink[dir];
301  }
302 
303  return pNodeSmaller;
304 }
305 
306 template <typename KeyType, typename Comparer>
308 {
309  return Iterator(Internal_LowerBound(key));
310 }
311 
312 template <typename KeyType, typename Comparer>
314 {
315  Node* pNode = m_pRoot;
316  Node* pNodeSmaller = nullptr;
317 
318  while (pNode != &m_NilNode)
319  {
320  const ezInt32 dir = (ezInt32) m_Comparer.Less(pNode->m_Key, key);
321  const ezInt32 dir2= (ezInt32) m_Comparer.Less(key, pNode->m_Key);
322 
323  if (dir == dir2)
324  {
325  Iterator it(pNode);
326  ++it;
327  return it.m_pElement;
328  }
329 
330  if (dir == 0)
331  pNodeSmaller = pNode;
332 
333  pNode = pNode->m_pLink[dir];
334  }
335 
336  return pNodeSmaller;
337 }
338 
339 template <typename KeyType, typename Comparer>
341 {
342  return Iterator(Internal_UpperBound(key));
343 }
344 
345 template <typename KeyType, typename Comparer>
347 {
348  for (const auto& key : operand)
349  {
350  Insert(key);
351  }
352 }
353 
354 template <typename KeyType, typename Comparer>
356 {
357  for (const auto& key : operand)
358  {
359  Remove(key);
360  }
361 }
362 
363 template <typename KeyType, typename Comparer>
365 {
366  for (auto it = GetIterator(); it.IsValid();)
367  {
368  if (!operand.Contains(it.Key()))
369  it = Remove(it);
370  else
371  ++it;
372  }
373 }
374 
375 template <typename KeyType, typename Comparer>
377 {
378  Node* pInsertedNode = nullptr;
379 
380  m_pRoot = Insert(m_pRoot, key, pInsertedNode);
381  m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
382  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
383 
384  return Iterator(pInsertedNode);
385 }
386 
387 template <typename KeyType, typename Comparer>
388 bool ezSetBase<KeyType, Comparer>::Remove(const KeyType& key)
389 {
390  bool bRemoved = true;
391  m_pRoot = Remove(m_pRoot, key, bRemoved);
392  m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
393  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
394 
395  return bRemoved;
396 }
397 
398 template <typename KeyType, typename Comparer>
399 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::AcquireNode(const KeyType& key, ezInt32 m_uiLevel, Node* pParent)
400 {
401  Node* pNode;
402 
403  if (m_pFreeElementStack == nullptr)
404  {
405  m_Elements.PushBack();
406  pNode = &m_Elements.PeekBack();
407  }
408  else
409  {
410  pNode = m_pFreeElementStack;
411  m_pFreeElementStack = m_pFreeElementStack->m_pParent;
412  }
413 
414  ezMemoryUtils::Construct<Node>(pNode, 1);
415 
416  pNode->m_pParent = pParent;
417  pNode->m_Key = key;
418  pNode->m_uiLevel = m_uiLevel;
419  pNode->m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
420  pNode->m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
421 
422  ++m_uiCount;
423 
424  return pNode;
425 }
426 
427 template <typename KeyType, typename Comparer>
429 {
430  EZ_ASSERT_DEV(pNode != nullptr, "pNode is invalid.");
431 
432  ezMemoryUtils::Destruct<Node>(pNode, 1);
433 
434  // try to reduce the element array, if possible
435  if (pNode == &m_Elements.PeekBack())
436  {
437  m_Elements.PopBack();
438  }
439  else
440  if (pNode == &m_Elements.PeekFront())
441  {
442  m_Elements.PopFront();
443  }
444  else
445  {
446  pNode->m_pParent = m_pFreeElementStack;
447  m_pFreeElementStack = pNode;
448  }
449 
450  --m_uiCount;
451 }
452 
453 template <typename KeyType, typename Comparer>
455 {
456  if ((root->m_pLink[0]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
457  {
458  Node* save = root->m_pLink[0];
459  root->m_pLink[0] = save->m_pLink[1];
460  root->m_pLink[0]->m_pParent = root;
461  save->m_pLink[1] = root;
462  save->m_pLink[1]->m_pParent = save;
463  root = save;
464  }
465 
466  return root;
467 }
468 
469 template <typename KeyType, typename Comparer>
471 {
472  if ((root->m_pLink[1]->m_pLink[1]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
473  {
474  Node* save = root->m_pLink[1];
475  root->m_pLink[1] = save->m_pLink[0];
476  root->m_pLink[1]->m_pParent = root;
477  save->m_pLink[0] = root;
478  save->m_pLink[0]->m_pParent = save;
479  root = save;
480  ++root->m_uiLevel;
481  }
482 
483  return root;
484 }
485 
486 template <typename KeyType, typename Comparer>
487 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Insert(Node* root, const KeyType& key, Node*& pInsertedNode)
488 {
489  if (root == &m_NilNode)
490  {
491  pInsertedNode = AcquireNode(key, 1, reinterpret_cast<Node*>(&m_NilNode));
492  root = pInsertedNode;
493  }
494  else
495  {
496  Node* it = root;
497  Node* up[32];
498 
499  ezInt32 top = 0;
500  ezInt32 dir = 0;
501 
502  while (true)
503  {
504  up[top++] = it;
505  dir = m_Comparer.Less(it->m_Key, key) ? 1 : 0;
506 
507  // element is identical => do not insert
508  if ((ezInt32) m_Comparer.Less(key, it->m_Key) == dir)
509  {
510  pInsertedNode = it;
511  return root;
512  }
513 
514  if (it->m_pLink[dir] == &m_NilNode)
515  break;
516 
517  it = it->m_pLink[dir];
518  }
519 
520  pInsertedNode = AcquireNode(key, 1, it);
521  it->m_pLink[dir] = pInsertedNode;
522 
523  while (--top >= 0)
524  {
525  if (top != 0)
526  dir = up[top - 1]->m_pLink[1] == up[top];
527 
528  up[top] = SkewNode(up[top]);
529  up[top] = SplitNode(up[top]);
530 
531  if (top != 0)
532  {
533  up[top - 1]->m_pLink[dir] = up[top];
534  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
535  }
536  else
537  root = up[top];
538  }
539  }
540 
541  return root;
542 }
543 
544 template <typename KeyType, typename Comparer>
545 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Remove(Node* root, const KeyType& key, bool& bRemoved)
546 {
547  bRemoved = false;
548 
549  Node* ToErase = reinterpret_cast<Node*>(&m_NilNode);
550  Node* ToOverride = reinterpret_cast<Node*>(&m_NilNode);
551 
552  if (root != &m_NilNode)
553  {
554  Node* it = root;
555  Node* up[32];
556  ezInt32 top = 0;
557  ezInt32 dir = 0;
558 
559  while (true)
560  {
561  up[top++] = it;
562 
563  if (it == &m_NilNode)
564  return root;
565 
566  ezInt32 newdir = (ezInt32) (m_Comparer.Less(it->m_Key, key));
567 
568  if (newdir == (ezInt32) (m_Comparer.Less(key, it->m_Key)))
569  break;
570 
571  dir = newdir;
572 
573  it = it->m_pLink[dir];
574  }
575 
576  ToOverride = it;
577 
578  if ((it->m_pLink[0] == &m_NilNode) || (it->m_pLink[1] == &m_NilNode))
579  {
580  ezInt32 dir2 = it->m_pLink[0] == &m_NilNode;
581 
582  if (--top != 0)
583  {
584  up[top - 1]->m_pLink[dir] = it->m_pLink[dir2];
585  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
586  }
587  else
588  root = it->m_pLink[1];
589  }
590  else
591  {
592  Node* heir = it->m_pLink[1];
593  Node* prev = it;
594 
595  while (heir->m_pLink[0] != &m_NilNode)
596  {
597  up[top++] = prev = heir;
598 
599  heir = heir->m_pLink[0];
600  }
601 
602  ToErase = heir;
603  ToOverride = it;
604 
605  prev->m_pLink[prev == it] = heir->m_pLink[1];
606  prev->m_pLink[prev == it]->m_pParent = prev;
607  }
608 
609  while (--top >= 0)
610  {
611  if (top != 0)
612  dir = up[top - 1]->m_pLink[1] == up[top];
613 
614  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))
615  {
616  if (up[top]->m_pLink[1]->m_uiLevel > --up[top]->m_uiLevel)
617  up[top]->m_pLink[1]->m_uiLevel = up[top]->m_uiLevel;
618 
619  up[top] = SkewNode(up[top]);
620  up[top]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]);
621  up[top]->m_pLink[1]->m_pParent = up[top];
622 
623  up[top]->m_pLink[1]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]->m_pLink[1]);
624  up[top] = SplitNode(up[top]);
625  up[top]->m_pLink[1] = SplitNode(up[top]->m_pLink[1]);
626  up[top]->m_pLink[1]->m_pParent = up[top];
627  }
628 
629  if (top != 0)
630  {
631  up[top - 1]->m_pLink[dir] = up[top];
632  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
633  }
634  else
635  root = up[top];
636  }
637  }
638 
639  root->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
640 
641 
642  // if necessary, swap nodes
643  if (ToErase != &m_NilNode)
644  {
645  Node* parent = ToOverride->m_pParent;
646 
647  if (parent != &m_NilNode)
648  {
649  if (parent->m_pLink[0] == ToOverride)
650  {
651  parent->m_pLink[0] = ToErase;
652  parent->m_pLink[0]->m_pParent = parent;
653  }
654  if (parent->m_pLink[1] == ToOverride)
655  {
656  parent->m_pLink[1] = ToErase;
657  parent->m_pLink[1]->m_pParent = parent;
658  }
659  }
660  else
661  root = ToErase;
662 
663  ToErase->m_uiLevel = ToOverride->m_uiLevel;
664  ToErase->m_pLink[0] = ToOverride->m_pLink[0];
665  ToErase->m_pLink[0]->m_pParent = ToErase;
666  ToErase->m_pLink[1] = ToOverride->m_pLink[1];
667  ToErase->m_pLink[1]->m_pParent = ToErase;
668  }
669 
670  // remove the erased node
671  if (ToOverride != &m_NilNode)
672  {
673  bRemoved = true;
674  ReleaseNode(ToOverride);
675  }
676 
677  return root;
678 }
679 
680 template <typename KeyType, typename Comparer>
682 {
683  EZ_ASSERT_DEV(pos.m_pElement != nullptr, "The Iterator(pos) is invalid.");
684 
685  Iterator temp(pos);
686  ++temp;
687  Remove(pos.Key());
688  return temp;
689 }
690 
691 template <typename KeyType, typename Comparer>
693 {
694  if (GetCount() != rhs.GetCount())
695  return false;
696 
697  auto itLhs = GetIterator();
698  auto itRhs = rhs.GetIterator();
699 
700  while (itLhs.IsValid())
701  {
702  if (!m_Comparer.Equal(itLhs.Key(), itRhs.Key()))
703  return false;
704 
705  ++itLhs;
706  ++itRhs;
707  }
708 
709  return true;
710 }
711 
712 template <typename KeyType, typename Comparer>
714 {
715  return !operator==(rhs);
716 }
717 
718 
719 
720 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
721 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet() : ezSetBase<KeyType, Comparer>(Comparer(), AllocatorWrapper::GetAllocator())
722 {
723 }
724 
725 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
726 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const Comparer& comparer, ezAllocatorBase* pAllocator) : ezSetBase<KeyType, Comparer>(comparer, pAllocator)
727 {
728 }
729 
730 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
731 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSet<KeyType, Comparer, AllocatorWrapper>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator())
732 {
733 }
734 
735 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
736 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSetBase<KeyType, Comparer>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator())
737 {
738 }
739 
740 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
742 {
744 }
745 
746 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
748 {
750 }
751