00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef __CS_UTIL_REDBLACKTREE_H__
00022 #define __CS_UTIL_REDBLACKTREE_H__
00023
00024 #include "csutil/blockallocator.h"
00025
00026
00027 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00028 # undef new
00029 #endif
00030 #include <new>
00031
00039 template <typename K, typename Allocator,
00040 template<typename K, typename K2> class Ordering>
00041 class csRedBlackTree;
00042
00043 template <typename K, typename T>
00044 class csRedBlackTreePayload;
00045
00046 namespace CS
00047 {
00048 namespace Container
00049 {
00053 template <typename K>
00054 class RedBlackTreeNode
00055 {
00056 protected:
00057 enum Color { Black = 0, Red = 1 };
00058
00059 template <typename _T, typename _A,
00060 template<typename _K, typename _K2> class _O>
00061 friend class csRedBlackTree;
00062
00063 RedBlackTreeNode* left;
00064 RedBlackTreeNode* right;
00065 uint8 key[sizeof(K)];
00066
00067 RedBlackTreeNode() : parent(0) {}
00068 ~RedBlackTreeNode() { GetKey().~K(); }
00069 inline RedBlackTreeNode* GetParent() const
00070 { return (RedBlackTreeNode*)((uintptr_t)parent & (uintptr_t)~1); }
00071 void SetParent(RedBlackTreeNode* p)
00072 { parent = (RedBlackTreeNode*)(((uintptr_t)p & (uintptr_t)~1) | (uint)GetColor()); }
00073 Color GetColor() const
00074 {
00075
00076 uintptr_t const v = ((uintptr_t)parent & 1);
00077 return (Color)v;
00078 }
00079 void SetColor (Color color)
00080 { parent = (RedBlackTreeNode*)(((uintptr_t)parent & (uintptr_t)~1) | (uint)color); }
00081 private:
00083 RedBlackTreeNode* parent;
00084 public:
00086
00087 inline RedBlackTreeNode* GetLeft() const { return left; }
00088 inline RedBlackTreeNode* GetRight() const { return right; }
00089 inline K& GetKey ()
00090 {
00091
00092
00093
00094 void* p = &key;
00095 return *(reinterpret_cast<K*> (p));
00096 }
00097 inline const K& GetKey () const
00098 {
00099
00100 const void* p = &key;
00101 return *(reinterpret_cast<const K*> (p));
00102 }
00104 };
00105
00107 template <typename K>
00108 struct DefaultRedBlackTreeAllocator :
00109 public csFixedSizeAllocator<sizeof(RedBlackTreeNode<K>)>
00110 {
00111 };
00112
00113 template<typename T> struct RedBlackExtractKey
00114 {
00115 typedef T Key;
00116 const Key& key;
00117 RedBlackExtractKey(const Key& a) : key(a) {}
00118 };
00119
00120 template<typename T, typename U> struct RedBlackExtractKey<csRedBlackTreePayload<T, U> > : RedBlackExtractKey<T>
00121 {
00122 RedBlackExtractKey(const csRedBlackTreePayload<T, U>& a) : RedBlackExtractKey<T>(a.GetKey()) {}
00123 };
00124
00136 template <typename K, typename K2>
00137 class RedBlackTreeOrderingStrictWeak
00138 {
00139 const typename RedBlackExtractKey<K>::Key& a;
00140 const typename RedBlackExtractKey<K2>::Key& b;
00141 public:
00142 RedBlackTreeOrderingStrictWeak (const K& a, const K2& b)
00143 : a (RedBlackExtractKey<K>(a).key), b (RedBlackExtractKey<K2>(b).key) {}
00144
00145 bool AeqB () const { return a == b; }
00146 bool AleB () const { return a < b; }
00147 bool BleA () const { return b < a; }
00148 };
00149
00160 template <typename K, typename K2>
00161 class RedBlackTreeOrderingTotal
00162 {
00163 const typename RedBlackExtractKey<K>::Key& a;
00164 const typename RedBlackExtractKey<K2>::Key& b;
00165 bool lt;
00166 public:
00167 RedBlackTreeOrderingTotal (const K& a, const K2& b)
00168 : a (RedBlackExtractKey<K>(a).key), b (RedBlackExtractKey<K2>(b).key), lt (this->a <= this->b) {}
00169
00170 bool AeqB () const { return a == b; }
00171 bool AleB () const { return lt; }
00172
00173
00174
00175
00176
00177 bool BleA () const { return !lt; }
00178 };
00179
00194 template <typename K, typename K2>
00195 class RedBlackTreeOrderingPartial
00196 {
00197 const typename RedBlackExtractKey<K>::Key& a;
00198 const typename RedBlackExtractKey<K2>::Key& b;
00199 public:
00200 RedBlackTreeOrderingPartial (const K& a, const K2& b)
00201 : a (RedBlackExtractKey<K>(a).key), b (RedBlackExtractKey<K2>(b).key) {}
00202
00203 bool AeqB () const { return a == b; }
00204 bool AleB () const { return a <= b; }
00205 bool BleA () const { return b <= a; }
00206 };
00207 }
00208 }
00209
00237 template <typename K,
00238 typename Allocator =
00239 CS::Container::DefaultRedBlackTreeAllocator<K>,
00240 template<typename K, typename K2> class Ordering =
00241 CS::Container::RedBlackTreeOrderingTotal>
00242 class csRedBlackTree
00243 {
00244 protected:
00245 typedef CS::Container::RedBlackTreeNode<K> Node;
00246 public:
00247 enum { allocationUnitSize = sizeof (Node) };
00248 protected:
00249 CS::Memory::AllocatorPointerWrapper<Node, Allocator> root;
00250
00251 Node* AllocNode ()
00252 {
00253 Node* p = (Node*)root.Alloc (allocationUnitSize);
00254 CS_ASSERT_MSG("Allocator returned block that is not 2-byte-aligned",
00255 (uintptr_t(p) & 1) == 0);
00256 new (p) Node;
00257 return p;
00258 }
00259
00260 void FreeNode (Node* p)
00261 {
00262 p->~Node();
00263 root.Free (p);
00264 }
00265
00267 Node* CreateNode (Node* parent, const K& key)
00268 {
00269 Node* node;
00270 node = AllocNode();
00271 node->SetParent (parent);
00272 node->left = node->right = 0;
00273 new ((K*)&node->key) K (key);
00274 node->SetColor (Node::Red);
00275 return node;
00276 }
00277
00278 struct InsertCandidate
00279 {
00280 Node* parent;
00281 Node** node;
00282 uint depth;
00283
00284 InsertCandidate() : parent (0), node (0), depth ((uint)~0) {}
00285 };
00287 Node* RecursiveFindInsertCandidate (Node* parent, Node*& node,
00288 const K& key, uint depth,
00289 InsertCandidate& candidate)
00290 {
00291 if (node == 0)
00292 {
00293 if (depth < candidate.depth)
00294 {
00295 candidate.parent = parent;
00296 candidate.node = &node;
00297 candidate.depth = depth;
00298 }
00299 return 0;
00300 }
00301
00302 Ordering<K, K> _o (node->GetKey(), key);
00303 if (_o.AleB())
00304 {
00305
00306 InsertCandidate newCandidate;
00307 Node* n = RecursiveFindInsertCandidate (node, node->left, key, depth+1,
00308 newCandidate);
00309 if (n == 0)
00310 {
00311 n = *newCandidate.node = CreateNode (newCandidate.parent, key);
00312 }
00313 return n;
00314 }
00315
00316 if (_o.BleA())
00317 {
00318
00319 InsertCandidate newCandidate;
00320 Node* n = RecursiveFindInsertCandidate (node, node->right, key, depth+1,
00321 newCandidate);
00322 if (n == 0)
00323 {
00324 n = *newCandidate.node = CreateNode (newCandidate.parent, key);
00325 }
00326 return n;
00327 }
00328
00329
00330 Node* n = RecursiveFindInsertCandidate (node, node->left, key, depth+1,
00331 candidate);
00332 if (n == 0)
00333 n = RecursiveFindInsertCandidate (node, node->right, key, depth+1,
00334 candidate);
00335 if (n == 0)
00336 {
00337 n = *candidate.node = CreateNode (candidate.parent, key);
00338 }
00339 return n;
00340 }
00342 void RotateLeft (Node* pivot)
00343 {
00344 Node* pivotReplace = pivot->right;
00345 pivot->right = pivotReplace->left;
00346 if (pivotReplace->left != 0)
00347 pivotReplace->left->SetParent (pivot);
00348 pivotReplace->SetParent (pivot->GetParent());
00349 if (pivot->GetParent() == 0)
00350 root.p = pivotReplace;
00351 else
00352 {
00353 if (pivot == pivot->GetParent()->left)
00354 pivot->GetParent()->left = pivotReplace;
00355 else
00356 pivot->GetParent()->right = pivotReplace;
00357 }
00358 pivotReplace->left = pivot;
00359 pivot->SetParent (pivotReplace);
00360 }
00362 void RotateRight (Node* pivot)
00363 {
00364 Node* pivotReplace = pivot->left;
00365 pivot->left = pivotReplace->right;
00366 if (pivotReplace->right != 0)
00367 pivotReplace->right->SetParent (pivot);
00368 pivotReplace->SetParent (pivot->GetParent());
00369 if (pivot->GetParent() == 0)
00370 root.p = pivotReplace;
00371 else
00372 {
00373 if (pivot == pivot->GetParent()->left)
00374 pivot->GetParent()->left = pivotReplace;
00375 else
00376 pivot->GetParent()->right = pivotReplace;
00377 }
00378 pivotReplace->right = pivot;
00379 pivot->SetParent (pivotReplace);
00380 }
00382 bool IsBlack (Node* node) const
00383 { return (node == 0) || (node->GetColor() == Node::Black); }
00385 bool IsRed (Node* node) const
00386 { return (node != 0) && (node->GetColor() == Node::Red); }
00388 void InsertFixup (Node* node)
00389 {
00390 Node* p;
00391 while (((p = node->GetParent()) != 0) && IsRed (p))
00392 {
00393 Node* pp = p->GetParent();
00394 if (pp == 0) break;
00395 if (p == pp->left)
00396 {
00397 Node* y = pp->right;
00398 if (IsRed (y))
00399 {
00400
00401 p->SetColor (Node::Black);
00402 y->SetColor (Node::Black);
00403 pp->SetColor (Node::Red);
00404 node = pp;
00405 }
00406 else
00407 {
00408 if (node == p->right)
00409 {
00410
00411 node = p;
00412 RotateLeft (node);
00413 p = node->GetParent ();
00414 pp = p->GetParent();
00415 }
00416
00417 p->SetColor (Node::Black);
00418 pp->SetColor (Node::Red);
00419 RotateRight (pp);
00420 }
00421 }
00422 else
00423 {
00424 Node* y = pp->left;
00425 if (IsRed (y))
00426 {
00427
00428 p->SetColor (Node::Black);
00429 y->SetColor (Node::Black);
00430 pp->SetColor (Node::Red);
00431 node = pp;
00432 }
00433 else
00434 {
00435 if (node == p->left)
00436 {
00437
00438 node = p;
00439 RotateRight (node);
00440 p = node->GetParent ();
00441 pp = p->GetParent();
00442 }
00443
00444 p->SetColor (Node::Black);
00445 pp->SetColor (Node::Red);
00446 RotateLeft (pp);
00447 }
00448 }
00449 }
00450 root.p->SetColor (Node::Black);
00451 }
00452
00454 void DeleteNode (Node* node)
00455 {
00456 Node* y;
00457 if ((node->left == 0) || (node->right == 0))
00458 y = node;
00459 else
00460 y = Predecessor (node);
00461 Node* x;
00462 if (y->left != 0)
00463 x = y->left;
00464 else
00465 x = y->right;
00466 Node* nilParent = 0;
00467 if (x != 0)
00468 x->SetParent (y->GetParent());
00469 else
00470 nilParent = y->GetParent();
00471 if (y->GetParent() == 0)
00472 root.p = x;
00473 else
00474 {
00475 if (y == y->GetParent()->left)
00476 y->GetParent()->left = x;
00477 else
00478 y->GetParent()->right = x;
00479 }
00480 if (y != node)
00481 {
00482
00483 node->GetKey() = y->GetKey();
00484 }
00485 if (y->GetColor() == Node::Black)
00486 DeleteFixup (x, nilParent);
00487 FreeNode (y);
00488 }
00490 void DeleteFixup (Node* node, Node* nilParent)
00491 {
00492 while ((node != root.p) && IsBlack (node))
00493 {
00494 Node* p = node ? node->GetParent() : nilParent;
00495 if (node == p->left)
00496 {
00497 Node* w = p->right;
00498 if (IsRed (w))
00499 {
00500 w->SetColor (Node::Black);
00501 p->SetColor (Node::Red);
00502 RotateLeft (p);
00503 p = node ? node->GetParent() : nilParent;
00504 w = p->right;
00505 }
00506 if (IsBlack (w->left) && IsBlack (w->right))
00507 {
00508 w->SetColor (Node::Red);
00509 node = p;
00510 }
00511 else
00512 {
00513 if (IsBlack (w->right))
00514 {
00515 w->left->SetColor (Node::Red);
00516 w->SetColor (Node::Red);
00517 RotateRight (w);
00518 p = node ? node->GetParent() : nilParent;
00519 w = p->right;
00520 }
00521 w->SetColor (p->GetColor ());
00522 p->SetColor (Node::Black);
00523 w->right->SetColor (Node::Black);
00524 RotateLeft (p);
00525 node = root.p;
00526 }
00527 }
00528 else
00529 {
00530 Node* w = p->left;
00531 if (IsRed (w))
00532 {
00533 w->SetColor (Node::Black);
00534 p->SetColor (Node::Red);
00535 RotateRight (p);
00536 p = node ? node->GetParent() : nilParent;
00537 w = p->left;
00538 }
00539 if (IsBlack (w->left) && IsBlack (w->right))
00540 {
00541 w->SetColor (Node::Red);
00542 node = p;
00543 }
00544 else
00545 {
00546 if (IsBlack (w->left))
00547 {
00548 w->right->SetColor (Node::Red);
00549 w->SetColor (Node::Red);
00550 RotateLeft (w);
00551 p = node ? node->GetParent() : nilParent;
00552 w = p->left;
00553 }
00554 w->SetColor (p->GetColor ());
00555 p->SetColor (Node::Black);
00556 w->left->SetColor (Node::Black);
00557 RotateRight (p);
00558 node = root.p;
00559 }
00560 }
00561 }
00562 if (node != 0) node->SetColor (Node::Black);
00563 }
00565 template<typename K2>
00566 Node* LocateNode (Node* node, const K2& other) const
00567 {
00568 if (node == 0) return 0;
00569
00570 Ordering<K, K2> _o (node->GetKey(), other);
00571 if (_o.AeqB())
00572 return node;
00573 Node* n = 0;
00574
00575 bool leftTree = _o.AleB();
00576
00577 bool rightTree = _o.BleA();
00578
00579 if (leftTree || (!leftTree && !rightTree))
00580 n = LocateNode<K2> (node->left, other);
00581 if ((n == 0) && (rightTree || (!leftTree && !rightTree)))
00582 n = LocateNode<K2> (node->right, other);
00583 return n;
00584 }
00586 Node* LocateNodeExact (Node* node, const K* key) const
00587 {
00588 if (node == 0) return 0;
00589
00590 if (&(node->GetKey()) == key) return node;
00591
00592 Ordering<K, K> _o (node->GetKey(), *key);
00593 Node* n = 0;
00594
00595 bool leftTree = _o.AleB();
00596
00597 bool rightTree = _o.BleA();
00598
00599 if (leftTree || (!leftTree && !rightTree))
00600 n = LocateNodeExact (node->left, key);
00601
00602
00603 if ((n == 0) && (rightTree || (!leftTree && !rightTree) || _o.AeqB()))
00604 n = LocateNodeExact (node->right, key);
00605 return n;
00606 }
00608 static Node* Successor (const Node* node)
00609 {
00610 Node* succ;
00611 if (node->right != 0)
00612 {
00613 succ = node->right;
00614 while (succ->left != 0) succ = succ->left;
00615 return succ;
00616 }
00617 Node* y = node->GetParent();
00618 while ((y != 0) && (node == y->right))
00619 {
00620 node = y;
00621 y = y->GetParent();
00622 }
00623 return y;
00624 }
00626 static Node* Predecessor (const Node* node)
00627 {
00628 Node* pred;
00629 if (node->left != 0)
00630 {
00631 pred = node->left;
00632 while (pred->right != 0) pred = pred->right;
00633 return pred;
00634 }
00635 Node* y = node->GetParent();
00636 while ((y != 0) && (node == y->left))
00637 {
00638 node = y;
00639 y = y->GetParent();
00640 }
00641 return y;
00642 }
00643
00645
00646 template<typename K2>
00647 Node* RecursiveFindGSE (Node* node, const K2& other) const
00648 {
00649 if (node == 0) return 0;
00650 Ordering<K, K2> _o (node->GetKey (), other);
00651 if (_o.AeqB())
00652 return node;
00653 Node* n = 0;
00654
00655 bool leftTree = _o.AleB();
00656
00657 bool rightTree = _o.BleA();
00658
00659 if (leftTree || (!leftTree && !rightTree))
00660 {
00661 n = RecursiveFindGSE<K2> (node->left, other);
00662
00663
00664
00665 if (leftTree && (n == 0)) n = node;
00666 }
00667 if (n == 0)
00668 {
00669 n = RecursiveFindGSE<K2> (node->right, other);
00670 }
00671 return n;
00672 }
00674
00676
00677 template<typename K2>
00678 Node* RecursiveFindSGE (Node* node, const K2& other) const
00679 {
00680 if (node == 0) return 0;
00681 Ordering<K, K2> _o (node->GetKey (), other);
00682 if (_o.AeqB())
00683 return node;
00684 Node* n = 0;
00685
00686 bool leftTree = _o.AleB();
00687
00688 bool rightTree = _o.BleA();
00689
00690 if (rightTree || (!leftTree && !rightTree))
00691 {
00692 n = RecursiveFindSGE<K2> (node->right, other);
00693
00694
00695
00696 if (rightTree && (n == 0)) n = node;
00697 }
00698 if (n == 0)
00699 {
00700 n = RecursiveFindSGE<K2> (node->left, other);
00701 }
00702 return n;
00703 }
00705
00707 template <typename CB>
00708 void RecursiveTraverseInOrder (Node* node, CB& callback) const
00709 {
00710 if (node->right != 0) RecursiveTraverseInOrder (node->right, callback);
00711 callback (node->GetKey());
00712 if (node->left != 0) RecursiveTraverseInOrder (node->left, callback);
00713 }
00714
00716 void RecursiveCopy (Node*& to, Node* parent, const Node* from)
00717 {
00718 if (from == 0)
00719 {
00720 to = 0;
00721 return;
00722 }
00723 to = AllocNode ();
00724 to->SetParent (parent);
00725 to->SetColor (from->GetColor());
00726 new ((K*)&to->key) K (from->GetKey());
00727 RecursiveCopy (to->left, to, from->left);
00728 RecursiveCopy (to->right, to, from->right);
00729 }
00730
00732 void RecursiveDelete (Node* node)
00733 {
00734 if (node == 0) return;
00735 RecursiveDelete (node->left);
00736 RecursiveDelete (node->right);
00737 FreeNode (node);
00738 }
00739
00741
00742 template<typename K2>
00743 K* FindInternal (const K2& other)
00744 {
00745 Node* n = LocateNode<K2> (root.p, other);
00746 return n ? &(n->GetKey()) : 0;
00747 }
00748 template<typename K2>
00749 K& FindInternal (const K2& other, K& fallback)
00750 {
00751 Node* n = LocateNode<K2> (root.p, other);
00752 if(n)
00753 return n->GetKey();
00754 else
00755 return fallback;
00756 }
00758
00759 public:
00765 csRedBlackTree (const Allocator& alloc = Allocator()) : root(alloc, 0) { }
00766 csRedBlackTree (const csRedBlackTree& other) : root (other.root, 0)
00767 {
00768 RecursiveCopy (root.p, 0, other.root.p);
00769 }
00771 ~csRedBlackTree() { RecursiveDelete (root.p); }
00772
00777 const K* Insert (const K& key)
00778 {
00779 InsertCandidate newCandidate;
00780 Node* n = RecursiveFindInsertCandidate (0, root.p, key, 0, newCandidate);
00781 if (n == 0)
00782 n = *newCandidate.node = CreateNode (newCandidate.parent, key);
00783 InsertFixup (n);
00784 return &(n->GetKey());
00785 }
00791 bool Delete (const K& key)
00792 {
00793 Node* n = LocateNode<K> (root.p, key);
00794 if (n == 0) return false;
00795 DeleteNode (n);
00796 return true;
00797 }
00803 bool DeleteExact (const K* key)
00804 {
00805 Node* n = LocateNodeExact (root.p, key);
00806 if (n == 0) return false;
00807 DeleteNode (n);
00808 return true;
00809 }
00811 bool In (const K& key) const
00812 {
00813 return (LocateNode<K> (root.p, key) != 0);
00814 }
00820 bool Contains (const K& key) const { return In (key); }
00821
00823
00824 template<typename K2>
00825 const K* Find (const K2& other) const
00826 {
00827 Node* n = LocateNode<K2> (root.p, other);
00828 return n ? &(n->GetKey()) : 0;
00829 }
00830 template<typename K2>
00831 const K& Find (const K2& other, const K& fallback) const
00832 {
00833 Node* n = LocateNode<K2> (root.p, other);
00834 if(n)
00835 return n->GetKey();
00836 else
00837 return fallback;
00838 }
00840
00842
00843 template<typename K2>
00844 const K* FindSmallestGreaterEqual (const K2& other) const
00845 {
00846 Node* n = RecursiveFindSGE<K2> (root.p, other);
00847 return n ? &(n->GetKey()) : 0;
00848 }
00849 template<typename K2>
00850 const K& FindSmallestGreaterEqual (const K2& other,
00851 const K& fallback) const
00852 {
00853 Node* n = RecursiveFindSGE<K2> (root.p, other);
00854 return n ? n->GetKey() : fallback;
00855 }
00857
00859
00860 template<typename K2>
00861 const K* FindGreatestSmallerEqual (const K2& other) const
00862 {
00863 Node* n = RecursiveFindGSE<K2> (root.p, other);
00864 return n ? &(n->GetKey()) : 0;
00865 }
00866 template<typename K2>
00867 const K& FindGreatestSmallerEqual (const K2& other,
00868 const K& fallback) const
00869 {
00870 Node* n = RecursiveFindGSE<K2> (root.p, other);
00871 return n ? n->GetKey() : fallback;
00872 }
00874
00876 void DeleteAll()
00877 {
00878 RecursiveDelete (root.p);
00879 root.p = 0;
00880 }
00882 void Empty() { DeleteAll(); }
00884 bool IsEmpty() const { return (root.p == 0); }
00885
00887
00888 template <typename CB>
00889 void TraverseInOrder (CB& callback) const
00890 {
00891 if (root.p != 0) RecursiveTraverseInOrder (root.p, callback);
00892 }
00894
00896
00897 class ConstIterator
00898 {
00899 public:
00901 bool HasNext () const
00902 {
00903 return currentNode != 0;
00904 }
00905
00907 const K& Next ()
00908 {
00909 const K& ret = currentNode->GetKey();
00910 currentNode = Predecessor (currentNode);
00911 return ret;
00912 }
00913
00914 protected:
00915 friend class csRedBlackTree;
00916 ConstIterator (const csRedBlackTree<K, Allocator, Ordering>* tree)
00917 : currentNode (tree->root.p)
00918 {
00919 while (currentNode && currentNode->right != 0)
00920 currentNode = currentNode->right;
00921 }
00922
00923 private:
00924 const typename csRedBlackTree<K, Allocator, Ordering>::Node *currentNode;
00925 };
00926 friend class ConstIterator;
00927
00929 class ConstReverseIterator
00930 {
00931 public:
00933 bool HasNext () const
00934 {
00935 return currentNode != 0;
00936 }
00937
00939 const K& Next ()
00940 {
00941 const K& ret = currentNode->GetKey();
00942 currentNode = Successor (currentNode);
00943 return ret;
00944 }
00945
00946 protected:
00947 friend class csRedBlackTree;
00948 ConstReverseIterator (const csRedBlackTree<K, Allocator, Ordering>* tree)
00949 : currentNode (tree->root.p)
00950 {
00951 while (currentNode && currentNode->left != 0)
00952 currentNode = currentNode->left;
00953 }
00954
00955 private:
00956 const typename csRedBlackTree<K, Allocator, Ordering>::Node *currentNode;
00957 };
00958 friend class ConstReverseIterator;
00959
00963 ConstIterator GetIterator () const
00964 {
00965 return ConstIterator (this);
00966 }
00967
00971 ConstReverseIterator GetReverseIterator () const
00972 {
00973 return ConstReverseIterator (this);
00974 }
00975
00977
00978 class Iterator
00979 {
00980 public:
00982 bool HasNext () const
00983 {
00984 return currentNode != 0;
00985 }
00986
00988 K& PeekNext ()
00989 {
00990 K& ret = currentNode->GetKey();
00991 return ret;
00992 }
00993
00995 K& Next ()
00996 {
00997 K& ret = currentNode->GetKey();
00998 currentNode = Predecessor (currentNode);
00999 return ret;
01000 }
01001
01002 protected:
01003 friend class csRedBlackTree;
01004 Iterator (csRedBlackTree<K, Allocator, Ordering>* tree) : currentNode (tree->root.p)
01005 {
01006 while (currentNode && currentNode->GetRight() != 0)
01007 currentNode = currentNode->GetRight();
01008 }
01009
01010 private:
01011 typename csRedBlackTree<K, Allocator, Ordering>::Node *currentNode;
01012 };
01013 friend class Iterator;
01014
01018 Iterator GetIterator ()
01019 {
01020 return Iterator (this);
01021 }
01022
01027 void Delete (Iterator& it)
01028 {
01029 Node* n = it.currentNode;
01030 if (n == 0) return;
01031 Node* nSucc = Successor (n);
01032 DeleteNode (n);
01033 Node* newNode;
01034 if (nSucc == 0)
01035 {
01036 newNode = root.p;
01037 if (newNode != 0)
01038 {
01039 while (newNode->GetRight() != 0)
01040 newNode = newNode->GetRight();
01041 }
01042 }
01043 else
01044 newNode = Predecessor (nSucc);
01045 it.currentNode = newNode;
01046 }
01047
01049
01051 class ReverseIterator
01052 {
01053 public:
01055 bool HasNext () const
01056 {
01057 return currentNode != 0;
01058 }
01059
01061 K& PeekNext ()
01062 {
01063 K& ret = currentNode->GetKey();
01064 return ret;
01065 }
01066
01068 K& Next ()
01069 {
01070 K& ret = currentNode->GetKey();
01071 currentNode = Successor (currentNode);
01072 return ret;
01073 }
01074
01075 protected:
01076 friend class csRedBlackTree;
01077 ReverseIterator (csRedBlackTree<K, Allocator, Ordering>* tree) : currentNode (tree->root.p)
01078 {
01079 while (currentNode && currentNode->left != 0)
01080 currentNode = currentNode->left;
01081 }
01082
01083 private:
01084 typename csRedBlackTree<K, Allocator, Ordering>::Node *currentNode;
01085 };
01086 friend class ReverseIterator;
01087
01091 ReverseIterator GetReverseIterator ()
01092 {
01093 return ReverseIterator (this);
01094 }
01095 };
01096
01101 template <typename K, typename T>
01102 class csRedBlackTreePayload
01103 {
01104 K key;
01105 T value;
01106 public:
01107 csRedBlackTreePayload (const K& k, const T& v) : key(k), value(v) {}
01108 csRedBlackTreePayload (const csRedBlackTreePayload& other) :
01109 key(other.key), value(other.value) {}
01110
01111 const K& GetKey() const { return key; }
01112 const T& GetValue() const { return value; }
01113 T& GetValue() { return value; }
01114 operator const T&() const { return value; }
01115 operator T&() { return value; }
01116 };
01117
01122 template <typename K, typename T,
01123 typename Allocator =
01124 csFixedSizeAllocator<
01125 sizeof(CS::Container::RedBlackTreeNode<
01126 csRedBlackTreePayload<K, T> >)>,
01127 template<typename K1, typename K2> class Ordering =
01128 CS::Container::RedBlackTreeOrderingTotal >
01129 class csRedBlackTreeMap : protected csRedBlackTree<csRedBlackTreePayload<K, T>, Allocator, Ordering>
01130 {
01131 typedef csRedBlackTree<csRedBlackTreePayload<K, T>, Allocator, Ordering > supahclass;
01132
01133 template<typename CB>
01134 class TraverseCB
01135 {
01136 CB callback;
01137 public:
01138 TraverseCB (const CB& callback) : callback(callback) {}
01139 void operator() (csRedBlackTreePayload<K, T>& value)
01140 {
01141 callback (value.GetKey(), value.GetValue());
01142 }
01143 };
01144 public:
01145 enum { allocationUnitSize = supahclass::allocationUnitSize };
01146
01147 csRedBlackTreeMap (const Allocator& alloc = Allocator())
01148 : supahclass (alloc) {}
01149
01155 T* Put (const K& key, const T &value)
01156 {
01157 csRedBlackTreePayload<K, T>* payload = (csRedBlackTreePayload<K, T>*)
01158 Insert (csRedBlackTreePayload<K, T>(key, value));
01159 return (payload != 0) ? &payload->GetValue() : 0;
01160 }
01166 bool Delete (const K& key)
01167 {
01168 csRedBlackTreePayload<K, T>* payload = FindInternal (key);
01169 if (payload == 0) return false;
01170 return supahclass::DeleteExact (payload);
01171 }
01173
01177 const T* GetElementPointer (const K& key) const
01178 {
01179 const csRedBlackTreePayload<K, T>* payload = Find (key);
01180 if (payload == 0) return 0;
01181 return &payload->GetValue();
01182 }
01183 T* GetElementPointer (const K& key)
01184 {
01185 csRedBlackTreePayload<K, T>* payload = FindInternal (key);
01186 if (payload == 0) return 0;
01187 return &payload->GetValue();
01188 }
01190
01192
01195 const T& Get (const K& key, const T& fallback) const
01196 {
01197 const csRedBlackTreePayload<K, T>* payload = Find (key);
01198 if (payload == 0) return fallback;
01199 return payload->GetValue();
01200 }
01201 T& Get (const K& key, T& fallback)
01202 {
01203 csRedBlackTreePayload<K, T>* payload = FindInternal (key);
01204 if (payload == 0) return fallback;
01205 return payload->GetValue();
01206 }
01208
01209 void DeleteAll() { supahclass::Empty(); }
01211 void Empty() { DeleteAll(); }
01213 bool IsEmpty() const { return supahclass::IsEmpty(); }
01214
01216
01217 template <typename CB>
01218 void TraverseInOrder (CB& callback) const
01219 {
01220 TraverseCB<CB> traverser (callback);
01221 supahclass::TraverseInOrder (traverser);
01222 }
01224
01226
01227 class ConstIterator
01228 {
01229 public:
01231 bool HasNext () const
01232 {
01233 return treeIter.HasNext();
01234 }
01235
01237 const T& PeekNext (K& key)
01238 {
01239 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01240 key = d.GetKey ();
01241 return d.GetValue ();
01242 }
01243
01245 const T& PeekNext ()
01246 {
01247 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01248 return d.GetValue ();
01249 }
01250
01252 const T& Next (K& key)
01253 {
01254 const csRedBlackTreePayload<K, T>& d = treeIter.Next();
01255 key = d.GetKey ();
01256 return d.GetValue ();
01257 }
01258
01260 const T& Next ()
01261 {
01262 const csRedBlackTreePayload<K, T>& d = treeIter.Next();
01263 return d.GetValue ();
01264 }
01265
01266 protected:
01267 friend class csRedBlackTreeMap;
01268 typename supahclass::ConstIterator treeIter;
01269 ConstIterator (const csRedBlackTreeMap* map)
01270 : treeIter (static_cast<const supahclass*> (map)->GetIterator())
01271 {
01272 }
01273 };
01274 friend class ConstIterator;
01275
01277 class Iterator
01278 {
01279 public:
01281 bool HasNext () const
01282 {
01283 return treeIter.HasNext();
01284 }
01285
01287 T& PeekNext (K& key)
01288 {
01289 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01290 key = d.GetKey ();
01291 return d.GetValue ();
01292 }
01293
01295 T& PeekNext ()
01296 {
01297 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01298 return d.GetValue ();
01299 }
01300
01302 T& Next (K& key)
01303 {
01304 csRedBlackTreePayload<K, T>& d = treeIter.Next();
01305 key = d.GetKey ();
01306 return d.GetValue ();
01307 }
01308
01309 T& Next ()
01310 {
01311 csRedBlackTreePayload<K, T>& d = treeIter.Next();
01312 return d.GetValue ();
01313 }
01314
01315 protected:
01316 friend class csRedBlackTreeMap;
01317 typename supahclass::Iterator treeIter;
01318 Iterator (csRedBlackTreeMap* map)
01319 : treeIter (static_cast<supahclass*> (map)->GetIterator())
01320 {
01321 }
01322 };
01323 friend class Iterator;
01324
01326 class ConstReverseIterator
01327 {
01328 public:
01330 bool HasNext () const
01331 {
01332 return treeIter.HasNext();
01333 }
01334
01336 const T& PeekNext (K& key)
01337 {
01338 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01339 key = d.GetKey ();
01340 return d.GetValue ();
01341 }
01342
01344 const T& PeekNext ()
01345 {
01346 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01347 return d.GetValue ();
01348 }
01349
01351 const T& Next (K& key)
01352 {
01353 const csRedBlackTreePayload<K, T>& d = treeIter.Next();;
01354 key = d.GetKey ();
01355 return d.GetValue ();
01356 }
01357
01359 const T& Next ()
01360 {
01361 const csRedBlackTreePayload<K, T>& d = treeIter.Next();;
01362 return d.GetValue ();
01363 }
01364
01365 protected:
01366 friend class csRedBlackTreeMap;
01367 typename supahclass::ConstReverseIterator treeIter;
01368 ConstReverseIterator (const csRedBlackTreeMap* map)
01369 : treeIter (static_cast<const supahclass*> (map)->GetReverseIterator())
01370 {
01371 }
01372 };
01373 friend class ConstReverseIterator;
01374
01376 class ReverseIterator
01377 {
01378 public:
01380 bool HasNext () const
01381 {
01382 return treeIter.HasNext();
01383 }
01384
01386 T& PeekNext (K& key)
01387 {
01388 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01389 key = d.GetKey ();
01390 return d.GetValue ();
01391 }
01392
01394 T& PeekNext ()
01395 {
01396 csRedBlackTreePayload<K, T>& d = treeIter.PeekNext();
01397 return d.GetValue ();
01398 }
01399
01401 T& Next (K& key)
01402 {
01403 csRedBlackTreePayload<K, T>& d = treeIter.Next();;
01404 key = d.GetKey ();
01405 return d.GetValue ();
01406 }
01407
01408 T& Next ()
01409 {
01410 csRedBlackTreePayload<K, T>& d = treeIter.Next();;
01411 return d.GetValue ();
01412 }
01413
01414 protected:
01415 friend class csRedBlackTreeMap;
01416 typename supahclass::ReverseIterator treeIter;
01417 ReverseIterator (csRedBlackTreeMap* map)
01418 : treeIter (static_cast<supahclass*> (map)->GetReverseIterator())
01419 {
01420 }
01421 };
01422 friend class ReverseIterator;
01423
01427 ConstIterator GetIterator () const
01428 {
01429 return ConstIterator (this);
01430 }
01431
01435 Iterator GetIterator ()
01436 {
01437 return Iterator (this);
01438 }
01439
01443 ConstReverseIterator GetReverseIterator () const
01444 {
01445 return ConstReverseIterator (this);
01446 }
01447
01451 ReverseIterator GetReverseIterator ()
01452 {
01453 return ReverseIterator (this);
01454 }
01456
01461 void Delete (Iterator& it)
01462 {
01463 supahclass::Delete (it.treeIter);
01464 }
01465 };
01466
01469 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
01470 # define new CS_EXTENSIVE_MEMDEBUG_NEW
01471 #endif
01472
01473 #endif // __CS_UTIL_REDBLACKTREE_H__