csutil/redblacktree.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2005 by Jorrit Tyberghein 00003 (C) 2005-2010 by Frank Richter 00004 (C) 2007-2008 by Marten Svanfeldt 00005 00006 This library is free software; you can redistribute it and/or 00007 modify it under the terms of the GNU Library General Public 00008 License as published by the Free Software Foundation; either 00009 version 2 of the License, or (at your option) any later version. 00010 00011 This library is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 Library General Public License for more details. 00015 00016 You should have received a copy of the GNU Library General Public 00017 License along with this library; if not, write to the Free 00018 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 */ 00020 00021 #ifndef __CS_UTIL_REDBLACKTREE_H__ 00022 #define __CS_UTIL_REDBLACKTREE_H__ 00023 00024 #include "csutil/blockallocator.h" 00025 00026 // hack: work around problems caused by #defining 'new' 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 { // Expression split over two statements to pacify some broken gcc's which 00075 // barf saying "can't convert Node* to NodeColor". 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 /* Cast through 'void*' to avoid strict aliasing warning. 00092 'key' is not ever actually accessed through an uint8*, so the strict 00093 aliasing assumption practically still holds. */ 00094 void* p = &key; 00095 return *(reinterpret_cast<K*> (p)); 00096 } 00097 inline const K& GetKey () const 00098 { 00099 // See above 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 /* Note: For a total ordering, at least either AleB or BleA is always 00173 * true. BleA is only used by csRedBlackTree if AeqB and AleB are false; 00174 * that the comparision here is actually 'b < a' instead of 'b <= a' 00175 * - which the name suggests - has thus no errorneous consequences. 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 } // namespace Container 00208 } // namespace CS 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 // New node _must_ be inserted somewhere in the left tree 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 // New node _must_ be inserted somewhere in the right tree 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 /* Left or right tree, doesn't matter. Try to find a place with a 00329 small depth to keep the tree as balanced as possible. */ 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 // Uncle of 'node' is red 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 // Uncle of 'node' is black, node is right child 00411 node = p; 00412 RotateLeft (node); 00413 p = node->GetParent (); 00414 pp = p->GetParent(); 00415 } 00416 // Uncle of 'node' is black, node is left child 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 // Uncle of 'node' is red 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 // Uncle of 'node' is black, node is left child 00438 node = p; 00439 RotateRight (node); 00440 p = node->GetParent (); 00441 pp = p->GetParent(); 00442 } 00443 // Uncle of 'node' is black, node is right child 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; // Node we will replace 'node' with 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 // Copy key 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 // key <= other, node with 'other' must be in left subtree 00575 bool leftTree = _o.AleB(); 00576 // other <= key, node with 'other' must be in right subtree 00577 bool rightTree = _o.BleA(); 00578 // (!leftTree && !rightTree) => node can be in either subtree 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 // key <= other, node with 'other' must be in left subtree 00595 bool leftTree = _o.AleB(); 00596 // other <= key, node with 'other' must be in right subtree 00597 bool rightTree = _o.BleA(); 00598 // (!leftTree && !rightTree) => node can be in either subtree 00599 if (leftTree || (!leftTree && !rightTree)) 00600 n = LocateNodeExact (node->left, key); 00601 /* @@@ Go down right node if key equals node value as sometimes 00602 the node we look for ended up in the right subtree. */ 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 // key <= other, node with 'other' must be in left subtree 00655 bool leftTree = _o.AleB(); 00656 // other <= key, node with 'other' must be in right subtree 00657 bool rightTree = _o.BleA(); 00658 // (!leftTree && !rightTree) => node can be in either subtree 00659 if (leftTree || (!leftTree && !rightTree)) 00660 { 00661 n = RecursiveFindGSE<K2> (node->left, other); 00662 /* This node is currently the smallest known greater or equal to 00663 * 'other', so return that if a search in the left subtree did 00664 * not give a result */ 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 // key <= other, node with 'other' must be in left subtree 00686 bool leftTree = _o.AleB(); 00687 // other <= key, node with 'other' must be in right subtree 00688 bool rightTree = _o.BleA(); 00689 // (!leftTree && !rightTree) => node can be in either subtree 00690 if (rightTree || (!leftTree && !rightTree)) 00691 { 00692 n = RecursiveFindSGE<K2> (node->right, other); 00693 /* This node is currently the smallest known greater or equal to 00694 * 'other', so return that if a search in the right subtree did 00695 * not give a result */ 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__
Generated for Crystal Space 2.0 by doxygen 1.6.1