csutil/redblacktree.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2005 by Jorrit Tyberghein 00003 (C) 2005 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 #include "csutil/comparator.h" 00026 00027 // hack: work around problems caused by #defining 'new' 00028 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00029 # undef new 00030 #endif 00031 #include <new> 00032 00047 template <typename K> 00048 class csRedBlackTree 00049 { 00050 protected: 00051 enum NodeColor { Black = 0, Red = 1 }; 00053 struct Node 00054 { 00055 private: 00057 Node* parent; 00058 public: 00059 Node* left; 00060 Node* right; 00061 uint8 key[sizeof(K)]; 00062 00063 Node() : parent(0) {} 00064 ~Node() { ((K*)&key)->~K(); } 00065 inline Node* GetParent() const 00066 { return (Node*)((uintptr_t)parent & (uintptr_t)~1); } 00067 void SetParent(Node* p) 00068 { parent = (Node*)(((uintptr_t)p & (uintptr_t)~1) | (uint)GetColor()); } 00069 NodeColor GetColor() const 00070 { // Expression split over two statements to pacify some broken gcc's which 00071 // barf saying "can't convert Node* to NodeColor". 00072 uintptr_t const v = ((uintptr_t)parent & 1); 00073 return (NodeColor)v; 00074 } 00075 void SetColor (NodeColor color) 00076 { parent = (Node*)(((uintptr_t)parent & (uintptr_t)~1) | (uint)color); } 00077 }; 00078 csBlockAllocator<Node, CS::Memory::AllocatorAlign<2> > nodeAlloc; 00079 00080 Node* root; 00081 00083 Node* RecursiveInsert (Node* parent, Node*& node, const K& key) 00084 { 00085 if (node == 0) 00086 { 00087 node = nodeAlloc.Alloc(); 00088 node->SetParent (parent); 00089 node->left = node->right = 0; 00090 new ((K*)&node->key) K (key); 00091 node->SetColor (Red); 00092 return node; 00093 } 00094 else 00095 { 00096 int r = csComparator<K, K>::Compare (key, *((K*)&node->key)); 00097 if (r < 0) 00098 return RecursiveInsert (node, node->left, key); 00099 else 00100 return RecursiveInsert (node, node->right, key); 00101 } 00102 } 00104 void RotateLeft (Node* pivot) 00105 { 00106 Node* pivotReplace = pivot->right; 00107 pivot->right = pivotReplace->left; 00108 if (pivotReplace->left != 0) 00109 pivotReplace->left->SetParent (pivot); 00110 pivotReplace->SetParent (pivot->GetParent()); 00111 if (pivot->GetParent() == 0) 00112 root = pivotReplace; 00113 else 00114 { 00115 if (pivot == pivot->GetParent()->left) 00116 pivot->GetParent()->left = pivotReplace; 00117 else 00118 pivot->GetParent()->right = pivotReplace; 00119 } 00120 pivotReplace->left = pivot; 00121 pivot->SetParent (pivotReplace); 00122 } 00124 void RotateRight (Node* pivot) 00125 { 00126 Node* pivotReplace = pivot->left; 00127 pivot->left = pivotReplace->right; 00128 if (pivotReplace->right != 0) 00129 pivotReplace->right->SetParent (pivot); 00130 pivotReplace->SetParent (pivot->GetParent()); 00131 if (pivot->GetParent() == 0) 00132 root = pivotReplace; 00133 else 00134 { 00135 if (pivot == pivot->GetParent()->left) 00136 pivot->GetParent()->left = pivotReplace; 00137 else 00138 pivot->GetParent()->right = pivotReplace; 00139 } 00140 pivotReplace->right = pivot; 00141 pivot->SetParent (pivotReplace); 00142 } 00144 bool IsBlack (Node* node) const 00145 { return (node == 0) || (node->GetColor() == Black); } 00147 bool IsRed (Node* node) const 00148 { return (node != 0) && (node->GetColor() == Red); } 00150 void InsertFixup (Node* node) 00151 { 00152 Node* p; 00153 while (((p = node->GetParent()) != 0) && IsRed (p)) 00154 { 00155 Node* pp = p->GetParent(); 00156 if (pp == 0) break; 00157 if (p == pp->left) 00158 { 00159 Node* y = pp->right; 00160 if (IsRed (y)) 00161 { 00162 // Uncle of 'node' is red 00163 p->SetColor (Black); 00164 y->SetColor (Black); 00165 pp->SetColor (Red); 00166 node = pp; 00167 } 00168 else 00169 { 00170 if (node == p->right) 00171 { 00172 // Uncle of 'node' is black, node is right child 00173 node = p; 00174 RotateLeft (node); 00175 p = node->GetParent (); 00176 pp = p->GetParent(); 00177 } 00178 // Uncle of 'node' is black, node is left child 00179 p->SetColor (Black); 00180 pp->SetColor (Red); 00181 RotateRight (pp); 00182 } 00183 } 00184 else 00185 { 00186 Node* y = pp->left; 00187 if (IsRed (y)) 00188 { 00189 // Uncle of 'node' is red 00190 p->SetColor (Black); 00191 y->SetColor (Black); 00192 pp->SetColor (Red); 00193 node = pp; 00194 } 00195 else 00196 { 00197 if (node == p->left) 00198 { 00199 // Uncle of 'node' is black, node is left child 00200 node = p; 00201 RotateRight (node); 00202 p = node->GetParent (); 00203 pp = p->GetParent(); 00204 } 00205 // Uncle of 'node' is black, node is right child 00206 p->SetColor (Black); 00207 pp->SetColor (Red); 00208 RotateLeft (pp); 00209 } 00210 } 00211 } 00212 root->SetColor (Black); 00213 } 00214 00216 void DeleteNode (Node* node) 00217 { 00218 Node* y; // Node we will replace 'node' with 00219 if ((node->left == 0) || (node->right == 0)) 00220 y = node; 00221 else 00222 y = Successor (node); 00223 Node* x; 00224 if (y->left != 0) 00225 x = y->left; 00226 else 00227 x = y->right; 00228 Node* nilParent = 0; 00229 if (x != 0) 00230 x->SetParent (y->GetParent()); 00231 else 00232 nilParent = y->GetParent(); 00233 if (y->GetParent() == 0) 00234 root = x; 00235 else 00236 { 00237 if (y == y->GetParent()->left) 00238 y->GetParent()->left = x; 00239 else 00240 y->GetParent()->right = x; 00241 } 00242 if (y != node) 00243 { 00244 // Copy key 00245 *((K*)&node->key) = *((K*)&y->key); 00246 } 00247 if (y->GetColor() == Black) 00248 DeleteFixup (x, nilParent); 00249 nodeAlloc.Free (y); 00250 } 00252 void DeleteFixup (Node* node, Node* nilParent) 00253 { 00254 while ((node != root) && IsBlack (node)) 00255 { 00256 Node* p = node ? node->GetParent() : nilParent; 00257 if (node == p->left) 00258 { 00259 Node* w = p->right; 00260 if (IsRed (w)) 00261 { 00262 w->SetColor (Black); 00263 p->SetColor (Red); 00264 RotateLeft (p); 00265 p = node ? node->GetParent() : nilParent; 00266 w = p->right; 00267 } 00268 if (IsBlack (w->left) && IsBlack (w->right)) 00269 { 00270 w->SetColor (Red); 00271 node = p; 00272 } 00273 else 00274 { 00275 if (IsBlack (w->right)) 00276 { 00277 w->left->SetColor (Red); 00278 w->SetColor (Red); 00279 RotateRight (w); 00280 p = node ? node->GetParent() : nilParent; 00281 w = p->right; 00282 } 00283 w->SetColor (p->GetColor ()); 00284 p->SetColor (Black); 00285 w->right->SetColor (Black); 00286 RotateLeft (p); 00287 node = root; 00288 } 00289 } 00290 else 00291 { 00292 Node* w = p->left; 00293 if (IsRed (w)) 00294 { 00295 w->SetColor (Black); 00296 p->SetColor (Red); 00297 RotateRight (p); 00298 p = node ? node->GetParent() : nilParent; 00299 w = p->left; 00300 } 00301 if (IsBlack (w->left) && IsBlack (w->right)) 00302 { 00303 w->SetColor (Red); 00304 node = p; 00305 } 00306 else 00307 { 00308 if (IsBlack (w->left)) 00309 { 00310 w->right->SetColor (Red); 00311 w->SetColor (Red); 00312 RotateLeft (w); 00313 p = node ? node->GetParent() : nilParent; 00314 w = p->left; 00315 } 00316 w->SetColor (p->GetColor ()); 00317 p->SetColor (Black); 00318 w->left->SetColor (Black); 00319 RotateRight (p); 00320 node = root; 00321 } 00322 } 00323 } 00324 if (node != 0) node->SetColor (Black); 00325 } 00327 Node* LocateNode (Node* node, const K& key) const 00328 { 00329 if (node == 0) return 0; 00330 00331 int r = csComparator<K, K>::Compare (key, *((K*)&node->key)); 00332 if (r == 0) 00333 return node; 00334 else if (r < 0) 00335 return LocateNode (node->left, key); 00336 else 00337 return LocateNode (node->right, key); 00338 } 00340 Node* LocateNodeExact (Node* node, const K* key) const 00341 { 00342 if (node == 0) return 0; 00343 00344 if (key == (K*)&node->key) return node; 00345 int r = csComparator<K, K>::Compare (*key, *((K*)&node->key)); 00346 if (r == 0) 00347 { 00348 // @@@ Should that be really necessary? 00349 Node* n = LocateNodeExact (node->left, key); 00350 if (n != 0) return n; 00351 return LocateNodeExact (node->right, key); 00352 } 00353 else if (r < 0) 00354 return LocateNodeExact (node->left, key); 00355 else 00356 return LocateNodeExact (node->right, key); 00357 } 00359 static Node* Successor (const Node* node) 00360 { 00361 Node* succ; 00362 if (node->right != 0) 00363 { 00364 succ = node->right; 00365 while (succ->left != 0) succ = succ->left; 00366 return succ; 00367 } 00368 Node* y = node->GetParent(); 00369 while ((y != 0) && (node == y->right)) 00370 { 00371 node = y; 00372 y = y->GetParent(); 00373 } 00374 return y; 00375 } 00377 static Node* Predecessor (const Node* node) 00378 { 00379 Node* pred; 00380 if (node->left != 0) 00381 { 00382 pred = node->left; 00383 while (pred->right != 0) pred = pred->right; 00384 return pred; 00385 } 00386 Node* y = node->GetParent(); 00387 while ((y != 0) && (node == y->left)) 00388 { 00389 node = y; 00390 y = y->GetParent(); 00391 } 00392 return y; 00393 } 00395 00396 template<typename K2> 00397 const K* RecursiveFind (Node* node, const K2& other) const 00398 { 00399 if (node == 0) return 0; 00400 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00401 if (r == 0) 00402 return ((K*)&node->key); 00403 else if (r < 0) 00404 return RecursiveFind<K2> (node->left, other); 00405 else 00406 return RecursiveFind<K2> (node->right, other); 00407 } 00408 template<typename K2> 00409 K* RecursiveFind (Node* node, const K2& other) 00410 { 00411 if (node == 0) return 0; 00412 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00413 if (r == 0) 00414 return ((K*)&node->key); 00415 else if (r < 0) 00416 return RecursiveFind<K2> (node->left, other); 00417 else 00418 return RecursiveFind<K2> (node->right, other); 00419 } 00420 template<typename K2> 00421 const K& RecursiveFind (Node* node, const K2& other, const K& fallback) const 00422 { 00423 if (node == 0) return fallback; 00424 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00425 if (r == 0) 00426 return *((K*)&node->key); 00427 else if (r < 0) 00428 return RecursiveFind<K2> (node->left, other, fallback); 00429 else 00430 return RecursiveFind<K2> (node->right, other, fallback); 00431 } 00432 template<typename K2> 00433 K& RecursiveFind (Node* node, const K2& other, K& fallback) 00434 { 00435 if (node == 0) return fallback; 00436 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00437 if (r == 0) 00438 return *((K*)&node->key); 00439 else if (r < 0) 00440 return RecursiveFind (node->left, other, fallback); 00441 else 00442 return RecursiveFind (node->right, other, fallback); 00443 } 00445 00447 00448 template<typename K2> 00449 const K* RecursiveFindSGE (Node* node, const K2& other) const 00450 { 00451 if (node == 0) return 0; 00452 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00453 if (r == 0) 00454 return ((K*)&node->key); 00455 if (r < 0) 00456 { 00457 const K* x = RecursiveFindSGE<K2> (node->left, other); 00458 /* This node is currently the smallest known greater or equal to 00459 * 'other', so return that if a search in the left subtree does 00460 * not give a result */ 00461 return x ? x : ((K*)&node->key); 00462 } 00463 else 00464 return RecursiveFindSGE<K2> (node->right, other); 00465 } 00466 template<typename K2> 00467 const K& RecursiveFindSGE (Node* node, const K2& other, const K& fallback) const 00468 { 00469 if (node == 0) return 0; 00470 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00471 if (r == 0) 00472 return *((K*)&node->key); 00473 if (r < 0) 00474 { 00475 const K& x = RecursiveFindSGE<K2> (node->left, other); 00476 /* This node is currently the smallest known greater or equal to 00477 * 'other', so return that if a search in the left subtree does 00478 * not give a result */ 00479 return x ? x : *((K*)&node->key); 00480 } 00481 else 00482 return RecursiveFindSGE<K2> (node->right, other); 00483 } 00485 00487 template <typename CB> 00488 void RecursiveTraverseInOrder (Node* node, CB& callback) const 00489 { 00490 if (node->left != 0) RecursiveTraverseInOrder (node->left, callback); 00491 callback.Process (*((K*)&node->key)); 00492 if (node->right != 0) RecursiveTraverseInOrder (node->right, callback); 00493 } 00494 00496 00497 template<typename K2> 00498 K* Find (const K2& other) 00499 { 00500 return RecursiveFind<K2> (root, other); 00501 } 00502 template<typename K2> 00503 K& Find (const K2& other, K& fallback) 00504 { 00505 return RecursiveFind<K2> (root, other, fallback); 00506 } 00508 00510 void RecursiveCopy (Node*& to, Node* parent, const Node* from) 00511 { 00512 if (from == 0) 00513 { 00514 to = 0; 00515 return; 00516 } 00517 to = nodeAlloc.Alloc(); 00518 to->SetParent (parent); 00519 to->SetColor (from->GetColor()); 00520 new ((K*)&to->key) K (*((K*)&from->key)); 00521 RecursiveCopy (to->left, to, from->left); 00522 RecursiveCopy (to->right, to, from->right); 00523 } 00524 public: 00530 csRedBlackTree (size_t allocatorBlockSize = 4096) : 00531 nodeAlloc (allocatorBlockSize / sizeof(Node)), root(0) { } 00532 csRedBlackTree (const csRedBlackTree& other) : 00533 nodeAlloc (other.nodeAlloc.GetBlockElements()) 00534 { 00535 RecursiveCopy (root, 0, other.root); 00536 } 00537 00543 const K* Insert (const K& key) 00544 { 00545 Node* n = RecursiveInsert (0, root, key); 00546 if (n == 0) return 0; 00547 InsertFixup (n); 00548 return (K*)&n->key; 00549 } 00555 bool Delete (const K& key) 00556 { 00557 Node* n = LocateNode (root, key); 00558 if (n == 0) return false; 00559 DeleteNode (n); 00560 return true; 00561 } 00567 bool DeleteExact (const K* key) 00568 { 00569 Node* n = LocateNodeExact (root, key); 00570 if (n == 0) return false; 00571 DeleteNode (n); 00572 return true; 00573 } 00575 bool In (const K& key) const 00576 { 00577 return (LocateNode (root, key) != 0); 00578 } 00584 bool Contains (const K& key) const { return In (key); } 00585 00587 00588 template<typename K2> 00589 const K* Find (const K2& other) const 00590 { 00591 return RecursiveFind<K2> (root, other); 00592 } 00593 template<typename K2> 00594 const K& Find (const K2& other, const K& fallback) const 00595 { 00596 return RecursiveFind<K2> (root, other, fallback); 00597 } 00599 00601 00602 template<typename K2> 00603 const K* FindSmallestGreaterEqual (const K2& other) const 00604 { 00605 return RecursiveFindSGE<K2> (root, other); 00606 } 00607 template<typename K2> 00608 const K& FindSmallestGreaterEqual (const K2& other, 00609 const K& fallback) const 00610 { 00611 return RecursiveFindSGE<K2> (root, other, fallback); 00612 } 00614 00616 void DeleteAll() 00617 { 00618 nodeAlloc.Empty(); 00619 root = 0; 00620 } 00622 void Empty() { DeleteAll(); } 00624 bool IsEmpty() const { return (root == 0); } 00625 00627 00628 template <typename CB> 00629 void TraverseInOrder (CB& callback) const 00630 { 00631 if (root != 0) RecursiveTraverseInOrder (root, callback); 00632 } 00634 00636 00637 class ConstIterator 00638 { 00639 public: 00641 bool HasNext () const 00642 { 00643 return currentNode != 0; 00644 } 00645 00647 const K& Next () 00648 { 00649 const K& ret = *((const K*)¤tNode->key); 00650 currentNode = Successor (currentNode); 00651 return ret; 00652 } 00653 00654 protected: 00655 friend class csRedBlackTree; 00656 ConstIterator (const csRedBlackTree<K>* tree) 00657 : currentNode (tree->root) 00658 { 00659 while (currentNode && currentNode->left != 0) 00660 currentNode = currentNode->left; 00661 } 00662 00663 private: 00664 const typename csRedBlackTree<K>::Node *currentNode; 00665 }; 00666 friend class ConstIterator; 00667 00669 class ConstReverseIterator 00670 { 00671 public: 00673 bool HasNext () const 00674 { 00675 return currentNode != 0; 00676 } 00677 00679 const K& Next () 00680 { 00681 const K& ret = *((const K*)¤tNode->key); 00682 currentNode = Predecessor (currentNode); 00683 return ret; 00684 } 00685 00686 protected: 00687 friend class csRedBlackTree; 00688 ConstReverseIterator (const csRedBlackTree<K>* tree) 00689 : currentNode (tree->root) 00690 { 00691 while (currentNode && currentNode->right != 0) 00692 currentNode = currentNode->right; 00693 } 00694 00695 private: 00696 const typename csRedBlackTree<K>::Node *currentNode; 00697 }; 00698 friend class ConstReverseIterator; 00699 00703 ConstIterator GetIterator () const 00704 { 00705 return ConstIterator (this); 00706 } 00707 00711 ConstReverseIterator GetReverseIterator () 00712 { 00713 return ConstReverseIterator (this); 00714 } 00715 00717 00718 class Iterator 00719 { 00720 public: 00722 bool HasNext () const 00723 { 00724 return currentNode != 0; 00725 } 00726 00728 const K& PeekNext () 00729 { 00730 const K& ret = *((const K*)¤tNode->key); 00731 return ret; 00732 } 00733 00735 const K& Next () 00736 { 00737 const K& ret = *((const K*)¤tNode->key); 00738 currentNode = Successor (currentNode); 00739 return ret; 00740 } 00741 00742 protected: 00743 friend class csRedBlackTree; 00744 Iterator (csRedBlackTree<K>* tree) : currentNode (tree->root) 00745 { 00746 while (currentNode && currentNode->left != 0) 00747 currentNode = currentNode->left; 00748 } 00749 00750 private: 00751 typename csRedBlackTree<K>::Node *currentNode; 00752 }; 00753 friend class Iterator; 00754 00758 Iterator GetIterator () 00759 { 00760 return Iterator (this); 00761 } 00762 00767 void Delete (Iterator& it) 00768 { 00769 Node* n = it.currentNode; 00770 if (n == 0) return; 00771 Node* nPred = Predecessor (n); 00772 DeleteNode (n); 00773 Node* newNode; 00774 if (nPred == 0) 00775 { 00776 newNode = root; 00777 if (newNode != 0) 00778 { 00779 while (newNode->left != 0) newNode = newNode->left; 00780 } 00781 } 00782 else 00783 newNode = Successor (nPred); 00784 it.currentNode = newNode; 00785 } 00786 00788 }; 00789 00794 template <typename K, typename T> 00795 class csRedBlackTreePayload 00796 { 00797 K key; 00798 T value; 00799 public: 00800 csRedBlackTreePayload (const K& k, const T& v) : key(k), value(v) {} 00801 csRedBlackTreePayload (const csRedBlackTreePayload& other) : 00802 key(other.key), value(other.value) {} 00803 00804 const K& GetKey() const { return key; } 00805 const T& GetValue() const { return value; } 00806 T& GetValue() { return value; } 00807 bool operator < (const csRedBlackTreePayload& other) const 00808 { 00809 return (csComparator<K, K>::Compare (key, other.key) < 0); 00810 } 00811 bool operator < (const K& other) const 00812 { 00813 return (csComparator<K, K>::Compare (key, other) < 0); 00814 } 00815 friend bool operator < (const K& k1, const csRedBlackTreePayload& k2) 00816 { 00817 return (csComparator<K, K>::Compare (k1, k2.key) < 0); 00818 } 00819 operator const T&() const { return value; } 00820 operator T&() { return value; } 00821 }; 00822 00827 template <typename K, typename T> 00828 class csRedBlackTreeMap : protected csRedBlackTree<csRedBlackTreePayload<K, T> > 00829 { 00830 typedef csRedBlackTree<csRedBlackTreePayload<K, T> > supahclass; 00831 00832 template<typename CB> 00833 class TraverseCB 00834 { 00835 CB callback; 00836 public: 00837 TraverseCB (const CB& callback) : callback(callback) {} 00838 void Process (csRedBlackTreePayload<K, T>& value) 00839 { 00840 callback.Process (value.GetKey(), value.GetValue()); 00841 } 00842 }; 00843 public: 00849 T* Put (const K& key, const T &value) 00850 { 00851 csRedBlackTreePayload<K, T>* payload = (csRedBlackTreePayload<K, T>*) 00852 Insert (csRedBlackTreePayload<K, T>(key, value)); 00853 return (payload != 0) ? &payload->GetValue() : 0; 00854 } 00860 bool Delete (const K& key) 00861 { 00862 csRedBlackTreePayload<K, T>* payload = Find (key); 00863 if (payload == 0) return false; 00864 return supahclass::Delete (*payload); 00865 } 00867 00871 const T* GetElementPointer (const K& key) const 00872 { 00873 csRedBlackTreePayload<K, T>* payload = Find (key); 00874 if (payload == 0) return 0; 00875 return &payload->GetValue(); 00876 } 00877 T* GetElementPointer (const K& key) 00878 { 00879 csRedBlackTreePayload<K, T>* payload = Find (key); 00880 if (payload == 0) return 0; 00881 return &payload->GetValue(); 00882 } 00884 00886 00889 const T& Get (const K& key, const T& fallback) const 00890 { 00891 const csRedBlackTreePayload<K, T>* payload = Find (key); 00892 if (payload == 0) return fallback; 00893 return payload->GetValue(); 00894 } 00895 T& Get (const K& key, T& fallback) 00896 { 00897 csRedBlackTreePayload<K, T>* payload = Find (key); 00898 if (payload == 0) return fallback; 00899 return payload->GetValue(); 00900 } 00902 00903 void DeleteAll() { supahclass::Empty(); } 00905 void Empty() { DeleteAll(); } 00907 bool IsEmpty() const { return supahclass::IsEmpty(); } 00908 00910 00911 template <typename CB> 00912 void TraverseInOrder (CB& callback) const 00913 { 00914 TraverseCB<CB> traverser (callback); 00915 supahclass::TraverseInOrder (traverser); 00916 } 00918 00920 00921 class ConstIterator 00922 { 00923 public: 00925 bool HasNext () const 00926 { 00927 return currentNode != 0; 00928 } 00929 00931 const T& Next (K& key) 00932 { 00933 const csRedBlackTreePayload<K, T>& d = *((const csRedBlackTreePayload<K, T>*)¤tNode->key); 00934 currentNode = Successor (currentNode); 00935 key = d.GetKey (); 00936 return d.GetValue (); 00937 } 00938 00940 const T& Next () 00941 { 00942 const csRedBlackTreePayload<K, T>& d = *((const csRedBlackTreePayload<K, T>*)¤tNode->key); 00943 currentNode = Successor (currentNode); 00944 return d.GetValue (); 00945 } 00946 00947 protected: 00948 friend class csRedBlackTreeMap; 00949 ConstIterator (const csRedBlackTreeMap<K, T>* tree) 00950 : currentNode (tree->root) 00951 { 00952 while (currentNode && currentNode->left != 0) 00953 currentNode = currentNode->left; 00954 } 00955 00956 private: 00957 const typename csRedBlackTreeMap<K, T>::Node *currentNode; 00958 }; 00959 friend class ConstIterator; 00960 00962 class Iterator 00963 { 00964 public: 00966 bool HasNext () const 00967 { 00968 return currentNode != 0; 00969 } 00970 00972 T& Next (K& key) 00973 { 00974 csRedBlackTreePayload<K, T>& d = *((csRedBlackTreePayload<K, T>*)¤tNode->key); 00975 currentNode = Successor (currentNode); 00976 key = d.GetKey (); 00977 return d.GetValue (); 00978 } 00979 00980 T& Next () 00981 { 00982 csRedBlackTreePayload<K, T>& d = *((csRedBlackTreePayload<K, T>*)¤tNode->key); 00983 currentNode = Successor (currentNode); 00984 return d.GetValue (); 00985 } 00986 00987 protected: 00988 friend class csRedBlackTreeMap; 00989 Iterator (csRedBlackTreeMap<K, T>* tree) 00990 : currentNode (tree->root) 00991 { 00992 while (currentNode && currentNode->left != 0) 00993 currentNode = currentNode->left; 00994 } 00995 00996 private: 00997 typename csRedBlackTreeMap<K, T>::Node *currentNode; 00998 }; 00999 friend class Iterator; 01000 01002 class ConstReverseIterator 01003 { 01004 public: 01006 bool HasNext () const 01007 { 01008 return currentNode != 0; 01009 } 01010 01012 const T& Next (K& key) 01013 { 01014 const csRedBlackTreePayload<K, T>& d = *((const csRedBlackTreePayload<K, T>*)¤tNode->key); 01015 currentNode = Predecessor (currentNode); 01016 key = d.GetKey (); 01017 return d.GetValue (); 01018 } 01019 01021 const T& Next () 01022 { 01023 const csRedBlackTreePayload<K, T>& d = *((const csRedBlackTreePayload<K, T>*)¤tNode->key); 01024 currentNode = Predecessor (currentNode); 01025 return d.GetValue (); 01026 } 01027 01028 protected: 01029 friend class csRedBlackTreeMap; 01030 ConstReverseIterator (const csRedBlackTreeMap<K, T>* tree) 01031 : currentNode (tree->root) 01032 { 01033 while (currentNode->right != 0) 01034 currentNode = currentNode->right; 01035 } 01036 01037 private: 01038 const typename csRedBlackTreeMap<K, T>::Node *currentNode; 01039 }; 01040 friend class ConstReverseIterator; 01041 01043 class ReverseIterator 01044 { 01045 public: 01047 bool HasNext () const 01048 { 01049 return currentNode != 0; 01050 } 01051 01053 T& Next (K& key) 01054 { 01055 csRedBlackTreePayload<K, T>& d = *((csRedBlackTreePayload<K, T>*)¤tNode->key); 01056 currentNode = Predecessor (currentNode); 01057 key = d.GetKey (); 01058 return d.GetValue (); 01059 } 01060 01061 T& Next () 01062 { 01063 csRedBlackTreePayload<K, T>& d = *((csRedBlackTreePayload<K, T>*)¤tNode->key); 01064 currentNode = Predecessor (currentNode); 01065 return d.GetValue (); 01066 } 01067 01068 protected: 01069 friend class csRedBlackTreeMap; 01070 ReverseIterator (csRedBlackTreeMap<K, T>* tree) 01071 : currentNode (tree->root) 01072 { 01073 while (currentNode && currentNode->right != 0) 01074 currentNode = currentNode->right; 01075 } 01076 01077 private: 01078 typename csRedBlackTreeMap<K, T>::Node *currentNode; 01079 }; 01080 friend class ReverseIterator; 01081 01085 ConstIterator GetIterator () const 01086 { 01087 return ConstIterator (this); 01088 } 01089 01093 Iterator GetIterator () 01094 { 01095 return Iterator (this); 01096 } 01097 01101 ConstReverseIterator GetReverseIterator () const 01102 { 01103 return ConstReverseIterator (this); 01104 } 01105 01109 ReverseIterator GetReverseIterator () 01110 { 01111 return ReverseIterator (this); 01112 } 01114 }; 01115 01118 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 01119 # define new CS_EXTENSIVE_MEMDEBUG_NEW 01120 #endif 01121 01122 #endif // __CS_UTIL_REDBLACKTREE_H__
Generated for Crystal Space 1.4.0 by doxygen 1.5.8