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 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public 00016 License along with this library; if not, write to the Free 00017 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 00020 #ifndef __CS_UTIL_REDBLACKTREE_H__ 00021 #define __CS_UTIL_REDBLACKTREE_H__ 00022 00023 #include "csutil/blockallocator.h" 00024 #include "csutil/comparator.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 00046 template <typename K> 00047 class csRedBlackTree 00048 { 00049 protected: 00050 enum NodeColor { Black = 0, Red = 1 }; 00052 struct Node 00053 { 00054 private: 00056 Node* parent; 00057 public: 00058 Node* left; 00059 Node* right; 00060 uint8 key[sizeof(K)]; 00061 00062 Node() : parent(0) {} 00063 ~Node() { ((K*)&key)->~K(); } 00064 inline Node* GetParent() const 00065 { return (Node*)((uintptr_t)parent & (uintptr_t)~1); } 00066 void SetParent(Node* p) 00067 { parent = (Node*)(((uintptr_t)p & (uintptr_t)~1) | (uint)GetColor()); } 00068 NodeColor GetColor() const 00069 { // Expression split over two statements to pacify some broken gcc's which 00070 // barf saying "can't convert Node* to NodeColor". 00071 uintptr_t const v = ((uintptr_t)parent & 1); 00072 return (NodeColor)v; 00073 } 00074 void SetColor (NodeColor color) 00075 { parent = (Node*)(((uintptr_t)parent & (uintptr_t)~1) | (uint)color); } 00076 }; 00077 csBlockAllocator<Node, CS::Memory::AllocatorAlign<2> > nodeAlloc; 00078 00079 Node* root; 00080 00082 Node* RecursiveInsert (Node* parent, Node*& node, const K& key) 00083 { 00084 if (node == 0) 00085 { 00086 node = nodeAlloc.Alloc(); 00087 node->SetParent (parent); 00088 node->left = node->right = 0; 00089 new ((K*)&node->key) K (key); 00090 node->SetColor (Red); 00091 return node; 00092 } 00093 else 00094 { 00095 int r = csComparator<K, K>::Compare (key, *((K*)&node->key)); 00096 if (r == 0) 00097 return 0; 00098 else if (r < 0) 00099 return RecursiveInsert (node, node->left, key); 00100 else 00101 return RecursiveInsert (node, node->right, key); 00102 } 00103 } 00105 void RotateLeft (Node* pivot) 00106 { 00107 Node* pivotReplace = pivot->right; 00108 pivot->right = pivotReplace->left; 00109 if (pivotReplace->left != 0) 00110 pivotReplace->left->SetParent (pivot); 00111 pivotReplace->SetParent (pivot->GetParent()); 00112 if (pivot->GetParent() == 0) 00113 root = pivotReplace; 00114 else 00115 { 00116 if (pivot == pivot->GetParent()->left) 00117 pivot->GetParent()->left = pivotReplace; 00118 else 00119 pivot->GetParent()->right = pivotReplace; 00120 } 00121 pivotReplace->left = pivot; 00122 pivot->SetParent (pivotReplace); 00123 } 00125 void RotateRight (Node* pivot) 00126 { 00127 Node* pivotReplace = pivot->left; 00128 pivot->left = pivotReplace->right; 00129 if (pivotReplace->right != 0) 00130 pivotReplace->right->SetParent (pivot); 00131 pivotReplace->SetParent (pivot->GetParent()); 00132 if (pivot->GetParent() == 0) 00133 root = pivotReplace; 00134 else 00135 { 00136 if (pivot == pivot->GetParent()->left) 00137 pivot->GetParent()->left = pivotReplace; 00138 else 00139 pivot->GetParent()->right = pivotReplace; 00140 } 00141 pivotReplace->right = pivot; 00142 pivot->SetParent (pivotReplace); 00143 } 00145 bool IsBlack (Node* node) const 00146 { return (node == 0) || (node->GetColor() == Black); } 00148 bool IsRed (Node* node) const 00149 { return (node != 0) && (node->GetColor() == Red); } 00151 void InsertFixup (Node* node) 00152 { 00153 Node* p; 00154 while (((p = node->GetParent()) != 0) && IsRed (p)) 00155 { 00156 Node* pp = p->GetParent(); 00157 if (pp == 0) break; 00158 if (p == pp->left) 00159 { 00160 Node* y = pp->right; 00161 if (IsRed (y)) 00162 { 00163 // Uncle of 'node' is red 00164 p->SetColor (Black); 00165 y->SetColor (Black); 00166 pp->SetColor (Red); 00167 node = pp; 00168 } 00169 else 00170 { 00171 if (node == p->right) 00172 { 00173 // Uncle of 'node' is black, node is right child 00174 node = p; 00175 RotateLeft (node); 00176 p = node->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 } 00204 // Uncle of 'node' is black, node is right child 00205 p->SetColor (Black); 00206 pp->SetColor (Red); 00207 RotateLeft (pp); 00208 } 00209 } 00210 } 00211 root->SetColor (Black); 00212 } 00214 void DeleteNode (Node* node) 00215 { 00216 Node* y; // Node we will replace 'node' with 00217 if ((node->left == 0) || (node->right == 0)) 00218 y = node; 00219 else 00220 y = Successor (node); 00221 Node* x; 00222 if (y->left != 0) 00223 x = y->left; 00224 else 00225 x = y->right; 00226 Node* nilParent = 0; 00227 if (x != 0) 00228 x->SetParent (y->GetParent()); 00229 else 00230 nilParent = y->GetParent(); 00231 if (y->GetParent() == 0) 00232 root = x; 00233 else 00234 { 00235 if (y == y->GetParent()->left) 00236 y->GetParent()->left = x; 00237 else 00238 y->GetParent()->right = x; 00239 } 00240 if (y != node) 00241 { 00242 // Copy key 00243 ((K*)&node->key)->~K(); 00244 new ((K*)&node->key) K (*((K*)&y->key)); 00245 } 00246 if (y->GetColor() == Black) 00247 DeleteFixup (x, nilParent); 00248 nodeAlloc.Free (y); 00249 } 00251 void DeleteFixup (Node* node, Node* nilParent) 00252 { 00253 while ((node != root) && IsBlack (node)) 00254 { 00255 Node* p = node ? node->GetParent() : nilParent; 00256 if (node == p->left) 00257 { 00258 Node* w = p->right; 00259 if (IsRed (w)) 00260 { 00261 w->SetColor (Black); 00262 p->SetColor (Red); 00263 RotateLeft (p); 00264 w = p->right; 00265 } 00266 if (IsBlack (w->left) && IsBlack (w->right)) 00267 { 00268 w->SetColor (Red); 00269 node = p; 00270 } 00271 else 00272 { 00273 if (IsBlack (w->right)) 00274 { 00275 w->left->SetColor (Red); 00276 w->SetColor (Red); 00277 RotateRight (w); 00278 w = p->right; 00279 } 00280 w->SetColor (p->GetColor ()); 00281 p->SetColor (Black); 00282 w->right->SetColor (Black); 00283 RotateLeft (p); 00284 node = root; 00285 } 00286 } 00287 else 00288 { 00289 Node* w = p->left; 00290 if (IsRed (w)) 00291 { 00292 w->SetColor (Black); 00293 p->SetColor (Red); 00294 RotateRight (p); 00295 w = p->left; 00296 } 00297 if (IsBlack (w->left) && IsBlack (w->right)) 00298 { 00299 w->SetColor (Red); 00300 node = p; 00301 } 00302 else 00303 { 00304 if (IsBlack (w->left)) 00305 { 00306 w->right->SetColor (Red); 00307 w->SetColor (Red); 00308 RotateLeft (w); 00309 w = p->left; 00310 } 00311 w->SetColor (p->GetColor ()); 00312 p->SetColor (Black); 00313 w->left->SetColor (Black); 00314 RotateRight (p); 00315 node = root; 00316 } 00317 } 00318 } 00319 if (node != 0) node->SetColor (Black); 00320 } 00322 Node* LocateNode (Node* node, const K& key) const 00323 { 00324 if (node == 0) return 0; 00325 00326 int r = csComparator<K, K>::Compare (key, node->key); 00327 if (r == 0) 00328 return node; 00329 else if (r < 0) 00330 return LocateNode (node->left, key); 00331 else 00332 return LocateNode (node->right, key); 00333 } 00335 Node* Successor (Node* node) const 00336 { 00337 Node* succ; 00338 if (node->right != 0) 00339 { 00340 succ = node->right; 00341 while (succ->left != 0) succ = succ->left; 00342 return succ; 00343 } 00344 Node* y = node->GetParent(); 00345 while ((y != 0) && (node == y->right)) 00346 { 00347 node = y; 00348 y = y->GetParent(); 00349 } 00350 return y; 00351 } 00353 00354 template<typename K2> 00355 const K* RecursiveFind (Node* node, const K2& other) const 00356 { 00357 if (node == 0) return 0; 00358 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00359 if (r == 0) 00360 return ((K*)&node->key); 00361 else if (r < 0) 00362 return RecursiveFind (node->left, other); 00363 else 00364 return RecursiveFind (node->right, other); 00365 } 00366 template<typename K2> 00367 K* RecursiveFind (Node* node, const K2& other) 00368 { 00369 if (node == 0) return 0; 00370 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00371 if (r == 0) 00372 return ((K*)&node->key); 00373 else if (r < 0) 00374 return RecursiveFind (node->left, other); 00375 else 00376 return RecursiveFind (node->right, other); 00377 } 00378 template<typename K2> 00379 const K& RecursiveFind (Node* node, const K2& other, const K& fallback) const 00380 { 00381 if (node == 0) return fallback; 00382 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00383 if (r == 0) 00384 return *((K*)&node->key); 00385 else if (r < 0) 00386 return RecursiveFind (node->left, other); 00387 else 00388 return RecursiveFind (node->right, other); 00389 } 00390 template<typename K2> 00391 K& RecursiveFind (Node* node, const K2& other, K& fallback) 00392 { 00393 if (node == 0) return fallback; 00394 int r = csComparator<K2, K>::Compare (other, *((K*)&node->key)); 00395 if (r == 0) 00396 return *((K*)&node->key); 00397 else if (r < 0) 00398 return RecursiveFind (node->left, other); 00399 else 00400 return RecursiveFind (node->right, other); 00401 } 00403 00404 template <typename CB> 00405 void RecursiveTraverseInOrder (Node* node, CB& callback) const 00406 { 00407 if (node->left != 0) RecursiveTraverseInOrder (node->left, callback); 00408 callback.Process (*((K*)&node->key)); 00409 if (node->right != 0) RecursiveTraverseInOrder (node->right, callback); 00410 } 00411 00413 00414 template<typename K2> 00415 K* Find (const K2& other) 00416 { 00417 return RecursiveFind (root, other); 00418 } 00419 template<typename K2> 00420 K& Find (const K2& other, K& fallback) 00421 { 00422 return RecursiveFind (root, other, fallback); 00423 } 00425 00427 void RecursiveCopy (Node*& to, Node* parent, const Node* from) 00428 { 00429 if (from == 0) 00430 { 00431 to = 0; 00432 return; 00433 } 00434 to = nodeAlloc.Alloc(); 00435 to->SetParent (parent); 00436 to->SetColor (from->GetColor()); 00437 new ((K*)&to->key) K (*((K*)&from->key)); 00438 RecursiveCopy (to->left, to, from->left); 00439 RecursiveCopy (to->right, to, from->right); 00440 } 00441 public: 00447 csRedBlackTree (size_t allocatorBlockSize = 4096) : 00448 nodeAlloc (allocatorBlockSize / sizeof(Node)), root(0) { } 00449 csRedBlackTree (const csRedBlackTree& other) : 00450 nodeAlloc (other.nodeAlloc.GetBlockElements()) 00451 { 00452 RecursiveCopy (root, 0, other.root); 00453 } 00454 00460 const K* Insert (const K& key) 00461 { 00462 Node* n = RecursiveInsert (0, root, key); 00463 if (n == 0) return 0; 00464 InsertFixup (n); 00465 return (K*)&n->key; 00466 } 00472 bool Delete (const K& key) 00473 { 00474 Node* n = LocateNode (root, key); 00475 if (n == 0) return false; 00476 DeleteNode (n); 00477 return true; 00478 } 00480 bool In (const K& key) const 00481 { 00482 return (LocateNode (root, key) != 0); 00483 } 00489 bool Contains (const K& key) const { return In (key); } 00490 00492 00493 template<typename K2> 00494 const K* Find (const K2& other) const 00495 { 00496 return RecursiveFind (root, other); 00497 } 00498 template<typename K2> 00499 const K& Find (const K2& other, const K& fallback) const 00500 { 00501 return RecursiveFind (root, other, fallback); 00502 } 00504 00506 void DeleteAll() 00507 { 00508 nodeAlloc.Empty(); 00509 root = 0; 00510 } 00512 void Empty() { DeleteAll(); } 00514 bool IsEmpty() const { return (root == 0); } 00515 00517 00518 template <typename CB> 00519 void TraverseInOrder (CB& callback) const 00520 { 00521 if (root != 0) RecursiveTraverseInOrder (root, callback); 00522 } 00524 }; 00525 00530 template <typename K, typename T> 00531 class csRedBlackTreePayload 00532 { 00533 K key; 00534 T value; 00535 public: 00536 csRedBlackTreePayload (const K& k, const T& v) : key(k), value(v) {} 00537 csRedBlackTreePayload (const csRedBlackTreePayload& other) : 00538 key(other.key), value(other.value) {} 00539 00540 const K& GetKey() const { return key; } 00541 const T& GetValue() const { return value; } 00542 T& GetValue() { return value; } 00543 bool operator < (const csRedBlackTreePayload& other) const 00544 { 00545 return (csComparator<K, K>::Compare (key, other.key) < 0); 00546 } 00547 bool operator < (const K& other) const 00548 { 00549 return (csComparator<K, K>::Compare (key, other) < 0); 00550 } 00551 friend bool operator < (const K& k1, const csRedBlackTreePayload& k2) 00552 { 00553 return (csComparator<K, K>::Compare (k1, k2.key) < 0); 00554 } 00555 operator const T&() const { return value; } 00556 operator T&() { return value; } 00557 }; 00558 00563 template <typename K, typename T> 00564 class csRedBlackTreeMap : protected csRedBlackTree<csRedBlackTreePayload<K, T> > 00565 { 00566 typedef csRedBlackTree<csRedBlackTreePayload<K, T> > supahclass; 00567 00568 template<typename CB> 00569 class TraverseCB 00570 { 00571 CB callback; 00572 public: 00573 TraverseCB (const CB& callback) : callback(callback) {} 00574 void Process (csRedBlackTreePayload<K, T>& value) 00575 { 00576 callback.Process (value.GetKey(), value.GetValue()); 00577 } 00578 }; 00579 public: 00585 T* Put (const K& key, const T &value) 00586 { 00587 csRedBlackTreePayload<K, T>* payload = (csRedBlackTreePayload<K, T>*) 00588 Insert (csRedBlackTreePayload<K, T>(key, value)); 00589 return (payload != 0) ? &payload->GetValue() : 0; 00590 } 00596 bool Delete (const K& key) 00597 { 00598 csRedBlackTreePayload<K, T>* payload = Find (key); 00599 if (payload == 0) return false; 00600 return supahclass::Delete (*payload); 00601 } 00603 00607 const T* GetElementPointer (const K& key) const 00608 { 00609 csRedBlackTreePayload<K, T>* payload = Find (key); 00610 if (payload == 0) return 0; 00611 return &payload->GetValue(); 00612 } 00613 T* GetElementPointer (const K& key) 00614 { 00615 csRedBlackTreePayload<K, T>* payload = Find (key); 00616 if (payload == 0) return 0; 00617 return &payload->GetValue(); 00618 } 00620 00622 00625 const T& Get (const K& key, const T& fallback) const 00626 { 00627 csRedBlackTreePayload<K, T>* payload = Find (key); 00628 if (payload == 0) return fallback; 00629 return payload->GetValue(); 00630 } 00631 T& Get (const K& key, T& fallback) 00632 { 00633 csRedBlackTreePayload<K, T>* payload = Find (key); 00634 if (payload == 0) return fallback; 00635 return payload->GetValue(); 00636 } 00638 00639 void DeleteAll() { supahclass::Empty(); } 00641 void Empty() { DeleteAll(); } 00643 bool IsEmpty() const { return supahclass::IsEmpty(); } 00644 00646 00647 template <typename CB> 00648 void TraverseInOrder (CB& callback) const 00649 { 00650 TraverseCB<CB> traverser (callback); 00651 supahclass::TraverseInOrder (traverser); 00652 } 00654 }; 00655 00658 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00659 # define new CS_EXTENSIVE_MEMDEBUG_NEW 00660 #endif 00661 00662 #endif // __CS_UTIL_REDBLACKTREE_H__
Generated for Crystal Space 1.2.1 by doxygen 1.5.3