ezEngine  Milestone 9
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 == nullptr) ||
47  (m_pElement->m_pParent == m_pElement->m_pParent->m_pParent))
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 == nullptr) ||
101  (m_pElement->m_pParent == m_pElement->m_pParent->m_pParent))
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_ALWAYS_INLINE ezSetBase<KeyType, Comparer>::NilNode::NilNode() : m_uiLevel(0), m_pParent(nullptr)
119 {
120  m_pLink[0] = nullptr;
121  m_pLink[1] = nullptr;
122 }
123 
124 template <typename KeyType, typename Comparer>
126 {
127  m_uiCount = 0;
128 
129  m_NilNode.m_uiLevel = 0;
130  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
131  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
132  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
133 
134  m_pFreeElementStack = nullptr;
135  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
136 }
137 
138 template <typename KeyType, typename Comparer>
139 ezSetBase<KeyType, Comparer>::ezSetBase(const Comparer& comparer, ezAllocatorBase* pAllocator) : m_Elements(pAllocator), m_Comparer(comparer)
140 {
141  Constructor();
142 }
143 
144 template <typename KeyType, typename Comparer>
146 {
147  Constructor();
148 
149  operator=(cc);
150 }
151 
152 template <typename KeyType, typename Comparer>
154 {
155  Clear();
156 }
157 
158 template <typename KeyType, typename Comparer>
160 {
161  Clear();
162 
163  for (Iterator it = rhs.GetIterator(); it.IsValid(); ++it)
164  Insert(it.Key());
165 }
166 
167 template <typename KeyType, typename Comparer>
169 {
170  for (Iterator it = GetIterator(); it.IsValid(); ++it)
171  ezMemoryUtils::Destruct<Node>(it.m_pElement, 1);
172 
173  m_pFreeElementStack = nullptr;
174  m_Elements.Clear();
175 
176  m_uiCount = 0;
177 
178  m_NilNode.m_uiLevel = 0;
179  m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
180  m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
181  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
182 
183  m_pRoot = reinterpret_cast<Node*>(&m_NilNode);
184 }
185 
186 template <typename KeyType, typename Comparer>
187 EZ_ALWAYS_INLINE bool ezSetBase<KeyType, Comparer>::IsEmpty() const
188 {
189  return (m_uiCount == 0);
190 }
191 
192 template <typename KeyType, typename Comparer>
193 EZ_ALWAYS_INLINE ezUInt32 ezSetBase<KeyType, Comparer>::GetCount() const
194 {
195  return m_uiCount;
196 }
197 
198 
199 template <typename KeyType, typename Comparer>
201 {
202  return Iterator(GetLeftMost());
203 }
204 
205 template <typename KeyType, typename Comparer>
207 {
208  return Iterator(GetRightMost());
209 }
210 
211 template <typename KeyType, typename Comparer>
213 {
214  if (IsEmpty())
215  return nullptr;
216 
217  Node* pNode = m_pRoot;
218 
219  while (pNode->m_pLink[0] != &m_NilNode)
220  pNode = pNode->m_pLink[0];
221 
222  return pNode;
223 }
224 
225 template <typename KeyType, typename Comparer>
227 {
228  if (IsEmpty())
229  return nullptr;
230 
231  Node* pNode = m_pRoot;
232 
233  while (pNode->m_pLink[1] != &m_NilNode)
234  pNode = pNode->m_pLink[1];
235 
236  return pNode;
237 }
238 
239 template <typename KeyType, typename Comparer>
240 template <typename CompatibleKeyType>
241 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Internal_Find(const CompatibleKeyType& key) const
242 {
243  Node* pNode = m_pRoot;
244 
245  while (pNode != &m_NilNode) // && (pNode->m_Key != key))
246  {
247  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
248  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
249 
250  if (dir == dir2)
251  break;
252 
253  pNode = pNode->m_pLink[dir];
254  }
255 
256  if (pNode == &m_NilNode)
257  return nullptr;
258 
259  return pNode;
260 }
261 
262 template <typename KeyType, typename Comparer>
263 template <typename CompatibleKeyType>
264 EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::Find(const CompatibleKeyType& key) const
265 {
266  return Iterator(Internal_Find(key));
267 }
268 
269 template <typename KeyType, typename Comparer>
270 template <typename CompatibleKeyType>
271 EZ_ALWAYS_INLINE bool ezSetBase<KeyType, Comparer>::Contains(const CompatibleKeyType& key) const
272 {
273  return Internal_Find(key) != nullptr;
274 }
275 
276 template <typename KeyType, typename Comparer>
278 {
279  for (const KeyType& key : operand)
280  {
281  if (!Contains(key))
282  return false;
283  }
284 
285  return true;
286 }
287 
288 template <typename KeyType, typename Comparer>
289 template <typename CompatibleKeyType>
291 {
292  Node* pNode = m_pRoot;
293  Node* pNodeSmaller = nullptr;
294 
295  while (pNode != &m_NilNode)
296  {
297  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
298  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
299 
300  if (dir == dir2)
301  return pNode;
302 
303  if (dir == 0)
304  pNodeSmaller = pNode;
305 
306  pNode = pNode->m_pLink[dir];
307  }
308 
309  return pNodeSmaller;
310 }
311 
312 template <typename KeyType, typename Comparer>
313 template <typename CompatibleKeyType>
314 EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::LowerBound(const CompatibleKeyType& key) const
315 {
316  return Iterator(Internal_LowerBound(key));
317 }
318 
319 template <typename KeyType, typename Comparer>
320 template <typename CompatibleKeyType>
322 {
323  Node* pNode = m_pRoot;
324  Node* pNodeSmaller = nullptr;
325 
326  while (pNode != &m_NilNode)
327  {
328  const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key);
329  const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key);
330 
331  if (dir == dir2)
332  {
333  Iterator it(pNode);
334  ++it;
335  return it.m_pElement;
336  }
337 
338  if (dir == 0)
339  pNodeSmaller = pNode;
340 
341  pNode = pNode->m_pLink[dir];
342  }
343 
344  return pNodeSmaller;
345 }
346 
347 template <typename KeyType, typename Comparer>
348 template <typename CompatibleKeyType>
349 EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::UpperBound(const CompatibleKeyType& key) const
350 {
351  return Iterator(Internal_UpperBound(key));
352 }
353 
354 template <typename KeyType, typename Comparer>
356 {
357  for (const auto& key : operand)
358  {
359  Insert(key);
360  }
361 }
362 
363 template <typename KeyType, typename Comparer>
365 {
366  for (const auto& key : operand)
367  {
368  Remove(key);
369  }
370 }
371 
372 template <typename KeyType, typename Comparer>
374 {
375  for (auto it = GetIterator(); it.IsValid();)
376  {
377  if (!operand.Contains(it.Key()))
378  it = Remove(it);
379  else
380  ++it;
381  }
382 }
383 
384 template <typename KeyType, typename Comparer>
385 template <typename CompatibleKeyType>
387 {
388  Node* pInsertedNode = nullptr;
389 
390  m_pRoot = Insert(m_pRoot, std::forward<CompatibleKeyType>(key), pInsertedNode);
391  m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
392  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
393 
394  return Iterator(pInsertedNode);
395 }
396 
397 template <typename KeyType, typename Comparer>
398 template <typename CompatibleKeyType>
399 bool ezSetBase<KeyType, Comparer>::Remove(const CompatibleKeyType& key)
400 {
401  bool bRemoved = true;
402  m_pRoot = Remove(m_pRoot, key, bRemoved);
403  m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
404  m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode);
405 
406  return bRemoved;
407 }
408 
409 template <typename KeyType, typename Comparer>
410 template <typename CompatibleKeyType>
411 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::AcquireNode(CompatibleKeyType&& key, ezInt32 m_uiLevel, Node* pParent)
412 {
413  Node* pNode;
414 
415  if (m_pFreeElementStack == nullptr)
416  {
417  m_Elements.PushBack();
418  pNode = &m_Elements.PeekBack();
419  }
420  else
421  {
422  pNode = m_pFreeElementStack;
423  m_pFreeElementStack = m_pFreeElementStack->m_pParent;
424  }
425 
426  ezMemoryUtils::Construct<Node>(pNode, 1);
427 
428  pNode->m_pParent = pParent;
429  pNode->m_Key = std::forward<CompatibleKeyType>(key);
430  pNode->m_uiLevel = m_uiLevel;
431  pNode->m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode);
432  pNode->m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode);
433 
434  ++m_uiCount;
435 
436  return pNode;
437 }
438 
439 template <typename KeyType, typename Comparer>
441 {
442  EZ_ASSERT_DEV(pNode != nullptr, "pNode is invalid.");
443 
444  ezMemoryUtils::Destruct<Node>(pNode, 1);
445 
446  // try to reduce the element array, if possible
447  if (pNode == &m_Elements.PeekBack())
448  {
449  m_Elements.PopBack();
450  }
451  else if (pNode == &m_Elements.PeekFront())
452  {
453  m_Elements.PopFront();
454  }
455  else
456  {
457  pNode->m_pParent = m_pFreeElementStack;
458  m_pFreeElementStack = pNode;
459  }
460 
461  --m_uiCount;
462 }
463 
464 template <typename KeyType, typename Comparer>
466 {
467  if ((root->m_pLink[0]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
468  {
469  Node* save = root->m_pLink[0];
470  root->m_pLink[0] = save->m_pLink[1];
471  root->m_pLink[0]->m_pParent = root;
472  save->m_pLink[1] = root;
473  save->m_pLink[1]->m_pParent = save;
474  root = save;
475  }
476 
477  return root;
478 }
479 
480 template <typename KeyType, typename Comparer>
482 {
483  if ((root->m_pLink[1]->m_pLink[1]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0))
484  {
485  Node* save = root->m_pLink[1];
486  root->m_pLink[1] = save->m_pLink[0];
487  root->m_pLink[1]->m_pParent = root;
488  save->m_pLink[0] = root;
489  save->m_pLink[0]->m_pParent = save;
490  root = save;
491  ++root->m_uiLevel;
492  }
493 
494  return root;
495 }
496 
497 template <typename KeyType, typename Comparer>
498 template <typename CompatibleKeyType>
499 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Insert(Node* root, CompatibleKeyType&& key, Node*& pInsertedNode)
500 {
501  if (root == &m_NilNode)
502  {
503  pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), 1, reinterpret_cast<Node*>(&m_NilNode));
504  root = pInsertedNode;
505  }
506  else
507  {
508  Node* it = root;
509  Node* up[32];
510 
511  ezInt32 top = 0;
512  ezInt32 dir = 0;
513 
514  while (true)
515  {
516  up[top++] = it;
517  dir = m_Comparer.Less(it->m_Key, key) ? 1 : 0;
518 
519  // element is identical => do not insert
520  if ((ezInt32)m_Comparer.Less(key, it->m_Key) == dir)
521  {
522  pInsertedNode = it;
523  return root;
524  }
525 
526  if (it->m_pLink[dir] == &m_NilNode)
527  break;
528 
529  it = it->m_pLink[dir];
530  }
531 
532  pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), 1, it);
533  it->m_pLink[dir] = pInsertedNode;
534 
535  while (--top >= 0)
536  {
537  if (top != 0)
538  dir = up[top - 1]->m_pLink[1] == up[top];
539 
540  up[top] = SkewNode(up[top]);
541  up[top] = SplitNode(up[top]);
542 
543  if (top != 0)
544  {
545  up[top - 1]->m_pLink[dir] = up[top];
546  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
547  }
548  else
549  root = up[top];
550  }
551  }
552 
553  return root;
554 }
555 
556 template <typename KeyType, typename Comparer>
557 template <typename CompatibleKeyType>
558 typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Remove(Node* root, const CompatibleKeyType& key, bool& bRemoved)
559 {
560  bRemoved = false;
561 
562  Node* ToErase = reinterpret_cast<Node*>(&m_NilNode);
563  Node* ToOverride = reinterpret_cast<Node*>(&m_NilNode);
564 
565  if (root != &m_NilNode)
566  {
567  Node* it = root;
568  Node* up[32];
569  ezInt32 top = 0;
570  ezInt32 dir = 0;
571 
572  while (true)
573  {
574  up[top++] = it;
575 
576  if (it == &m_NilNode)
577  return root;
578 
579  ezInt32 newdir = (ezInt32)(m_Comparer.Less(it->m_Key, key));
580 
581  if (newdir == (ezInt32)(m_Comparer.Less(key, it->m_Key)))
582  break;
583 
584  dir = newdir;
585 
586  it = it->m_pLink[dir];
587  }
588 
589  ToOverride = it;
590 
591  if ((it->m_pLink[0] == &m_NilNode) || (it->m_pLink[1] == &m_NilNode))
592  {
593  ezInt32 dir2 = it->m_pLink[0] == &m_NilNode;
594 
595  if (--top != 0)
596  {
597  up[top - 1]->m_pLink[dir] = it->m_pLink[dir2];
598  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
599  }
600  else
601  root = it->m_pLink[1];
602  }
603  else
604  {
605  Node* heir = it->m_pLink[1];
606  Node* prev = it;
607 
608  while (heir->m_pLink[0] != &m_NilNode)
609  {
610  up[top++] = prev = heir;
611 
612  heir = heir->m_pLink[0];
613  }
614 
615  ToErase = heir;
616  ToOverride = it;
617 
618  prev->m_pLink[prev == it] = heir->m_pLink[1];
619  prev->m_pLink[prev == it]->m_pParent = prev;
620  }
621 
622  while (--top >= 0)
623  {
624  if (top != 0)
625  dir = up[top - 1]->m_pLink[1] == up[top];
626 
627  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))
628  {
629  if (up[top]->m_pLink[1]->m_uiLevel > --up[top]->m_uiLevel)
630  up[top]->m_pLink[1]->m_uiLevel = up[top]->m_uiLevel;
631 
632  up[top] = SkewNode(up[top]);
633  up[top]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]);
634  up[top]->m_pLink[1]->m_pParent = up[top];
635 
636  up[top]->m_pLink[1]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]->m_pLink[1]);
637  up[top] = SplitNode(up[top]);
638  up[top]->m_pLink[1] = SplitNode(up[top]->m_pLink[1]);
639  up[top]->m_pLink[1]->m_pParent = up[top];
640  }
641 
642  if (top != 0)
643  {
644  up[top - 1]->m_pLink[dir] = up[top];
645  up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1];
646  }
647  else
648  root = up[top];
649  }
650  }
651 
652  root->m_pParent = reinterpret_cast<Node*>(&m_NilNode);
653 
654 
655  // if necessary, swap nodes
656  if (ToErase != &m_NilNode)
657  {
658  Node* parent = ToOverride->m_pParent;
659 
660  if (parent != &m_NilNode)
661  {
662  if (parent->m_pLink[0] == ToOverride)
663  {
664  parent->m_pLink[0] = ToErase;
665  parent->m_pLink[0]->m_pParent = parent;
666  }
667  if (parent->m_pLink[1] == ToOverride)
668  {
669  parent->m_pLink[1] = ToErase;
670  parent->m_pLink[1]->m_pParent = parent;
671  }
672  }
673  else
674  root = ToErase;
675 
676  ToErase->m_uiLevel = ToOverride->m_uiLevel;
677  ToErase->m_pLink[0] = ToOverride->m_pLink[0];
678  ToErase->m_pLink[0]->m_pParent = ToErase;
679  ToErase->m_pLink[1] = ToOverride->m_pLink[1];
680  ToErase->m_pLink[1]->m_pParent = ToErase;
681  }
682 
683  // remove the erased node
684  if (ToOverride != &m_NilNode)
685  {
686  bRemoved = true;
687  ReleaseNode(ToOverride);
688  }
689 
690  return root;
691 }
692 
693 template <typename KeyType, typename Comparer>
695 {
696  EZ_ASSERT_DEV(pos.m_pElement != nullptr, "The Iterator(pos) is invalid.");
697 
698  Iterator temp(pos);
699  ++temp;
700  Remove(pos.Key());
701  return temp;
702 }
703 
704 template <typename KeyType, typename Comparer>
706 {
707  if (GetCount() != rhs.GetCount())
708  return false;
709 
710  auto itLhs = GetIterator();
711  auto itRhs = rhs.GetIterator();
712 
713  while (itLhs.IsValid())
714  {
715  if (!m_Comparer.Equal(itLhs.Key(), itRhs.Key()))
716  return false;
717 
718  ++itLhs;
719  ++itRhs;
720  }
721 
722  return true;
723 }
724 
725 template <typename KeyType, typename Comparer>
727 {
728  return !operator==(rhs);
729 }
730 
731 
732 
733 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
734 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet() : ezSetBase<KeyType, Comparer>(Comparer(), AllocatorWrapper::GetAllocator())
735 {
736 }
737 
738 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
739 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const Comparer& comparer, ezAllocatorBase* pAllocator) : ezSetBase<KeyType, Comparer>(comparer, pAllocator)
740 {
741 }
742 
743 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
744 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSet<KeyType, Comparer, AllocatorWrapper>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator())
745 {
746 }
747 
748 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
749 ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSetBase<KeyType, Comparer>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator())
750 {
751 }
752 
753 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
755 {
757 }
758 
759 template <typename KeyType, typename Comparer, typename AllocatorWrapper>
761 {
763 }
764 
765 template <typename KeyType, typename Comparer>
767 {
768  SwapNilNode(this->m_pRoot, &this->m_NilNode, &other.m_NilNode);
769  SwapNilNode(other.m_pRoot, &other.m_NilNode, &this->m_NilNode);
770 
771  ezMath::Swap(this->m_pRoot, other.m_pRoot);
772  ezMath::Swap(this->m_uiCount, other.m_uiCount);
773  ezMath::Swap(this->m_pFreeElementStack, other.m_pFreeElementStack);
774  ezMath::Swap(this->m_Comparer, other.m_Comparer);
775 
776  // the set allocator is stored in this array
777  m_Elements.Swap(other.m_Elements);
778 }
779 
780 template <typename KeyType, typename Comparer>
781 void ezSetBase<KeyType, Comparer>::SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew)
782 {
783  if (pCurNode == pOld)
784  {
785  pCurNode = reinterpret_cast<Node*>(pNew);
786  return;
787  }
788 
789  SwapNilNode(pCurNode->m_pLink[0], pOld, pNew);
790  SwapNilNode(pCurNode->m_pLink[1], pOld, pNew);
791 }
792 
EZ_ALWAYS_INLINE void Swap(T &f1, T &f2)
Swaps the values in the two variables f1 and f2.
Definition: Math_inl.h:112
Iterator LowerBound(const CompatibleKeyType &key) const
Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid ...
bool operator!=(const ezSetBase< KeyType, Comparer > &rhs) const
Comparison operator.
Definition: Set_inl.h:726
void Next()
Advances the iterator to the next element in the set. The iterator will not be valid anymore...
Definition: Set_inl.h:8
Base class for all memory allocators.
Definition: AllocatorBase.h:21
Iterator GetLastIterator() const
Returns a constant Iterator to the very last element. For reverse traversal.
Definition: Set_inl.h:206
Iterator UpperBound(const CompatibleKeyType &key) const
Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid i...
bool Remove(const CompatibleKeyType &key)
Erases the element with the given key, if it exists. O(log n) operation.
Definition: Set_inl.h:399
Definition: Set.h:229
ezUInt32 GetCount() const
Returns the number of elements currently stored in the set. O(1) operation.
Definition: Set_inl.h:193
Iterator GetIterator() const
Returns a constant Iterator to the very first element.
Definition: Set_inl.h:200
void Intersection(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the intersection of itself and the operand.
Definition: Set_inl.h:373
bool IsEmpty() const
Returns whether there are no elements in the set. O(1) operation.
Definition: Set_inl.h:187
bool Contains(const CompatibleKeyType &key) const
Checks whether the given key is in the container.
Base class for all iterators.
Definition: Set.h:35
Iterator Insert(CompatibleKeyType &&key)
Inserts the key into the tree and returns an Iterator to it. O(log n) operation.
Definition: Set_inl.h:386
#define EZ_ASSERT_DEV(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:116
void Union(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the union of itself and the operand.
Definition: Set_inl.h:355
void operator=(const ezSetBase< KeyType, Comparer > &rhs)
Copies all keys from the given set into this one.
Definition: Set_inl.h:159
ezSetBase(const Comparer &comparer, ezAllocatorBase *pAllocator)
Initializes the set to be empty.
Definition: Set_inl.h:139
void Swap(ezSetBase< KeyType, Comparer > &other)
Swaps this map with the other one.
Definition: Set_inl.h:766
bool operator==(const ezSetBase< KeyType, Comparer > &rhs) const
Comparison operator.
Definition: Set_inl.h:705
A set container that only stores whether an element resides in it or not. Similar to STL::set...
Definition: Set.h:12
void Difference(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the difference of itself and the operand, i.e. subtracts operand.
Definition: Set_inl.h:364
~ezSetBase()
Destroys all elements in the set.
Definition: Set_inl.h:153
void Prev()
Advances the iterator to the previous element in the set. The iterator will not be valid anymore...
Definition: Set_inl.h:62
Iterator Find(const CompatibleKeyType &key) const
Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found...
void Clear()
Destroys all elements in the set and resets its size to zero.
Definition: Set_inl.h:168
bool ContainsSet(const ezSetBase< KeyType, Comparer > &operand) const
Checks whether the given key is in the container.
Definition: Set_inl.h:277