CrystalSpace

Public API Reference

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) 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     pivotReplace->right->SetParent (pivot);
00129     pivotReplace->SetParent (pivot->GetParent());
00130     if (pivot->GetParent() == 0)
00131       root = pivotReplace;
00132     else
00133     {
00134       if (pivot == pivot->GetParent()->left)
00135         pivot->GetParent()->left = pivotReplace;
00136       else
00137         pivot->GetParent()->right = pivotReplace;
00138     }
00139     pivotReplace->right = pivot;
00140     pivot->SetParent (pivotReplace);
00141   }
00143   bool IsBlack (Node* node) const
00144   { return (node == 0) || (node->GetColor() == Black); }
00146   bool IsRed (Node* node) const
00147   { return (node != 0) && (node->GetColor() == Red); }
00149   void InsertFixup (Node* node)
00150   {
00151     Node* p;
00152     while (((p = node->GetParent()) != 0) && IsRed (p))
00153     {
00154       Node* pp = p->GetParent();
00155       if (pp == 0) break;
00156       if (p == pp->left)
00157       {
00158         Node* y = pp->right;
00159         if (IsRed (y))
00160         {
00161           // Uncle of 'node' is red
00162           p->SetColor (Black);
00163           y->SetColor (Black);
00164           pp->SetColor (Red);
00165           node = pp;
00166         }
00167         else 
00168         {
00169           if (node == p->right)
00170           {
00171             // Uncle of 'node' is black, node is right child
00172             node = p;
00173             RotateLeft (node);
00174           }
00175           // Uncle of 'node' is black, node is left child
00176           p->SetColor (Black);
00177           pp->SetColor (Red);
00178           RotateRight (pp);
00179         }
00180       }
00181       else
00182       {
00183         Node* y = pp->left;
00184         if (IsRed (y))
00185         {
00186           // Uncle of 'node' is red
00187           p->SetColor (Black);
00188           y->SetColor (Black);
00189           pp->SetColor (Red);
00190           node = pp;
00191         }
00192         else 
00193         {
00194           if (node == p->left)
00195           {
00196             // Uncle of 'node' is black, node is left child
00197             node = p;
00198             RotateRight (node);
00199           }
00200           // Uncle of 'node' is black, node is right child
00201           p->SetColor (Black);
00202           pp->SetColor (Red);
00203           RotateLeft (pp);
00204         }
00205       }
00206     }
00207     root->SetColor (Black);
00208   }
00210   void DeleteNode (Node* node)
00211   {
00212     Node* y; // Node we will replace 'node' with
00213     if ((node->left == 0) || (node->right == 0))
00214       y = node;
00215     else
00216       y = Successor (node);
00217     Node* x;
00218     if (y->left != 0)
00219       x = y->left;
00220     else
00221       x = y->right;
00222     if (x != 0) x->SetParent (y->GetParent());
00223     if (y->GetParent() == 0)
00224       root = x;
00225     else
00226     {
00227       if (y == y->GetParent()->left)
00228         y->GetParent()->left = x;
00229       else
00230         y->GetParent()->right = x;
00231     }
00232     if (y != node)
00233     {
00234       // Copy key
00235       ((K*)&node->key)->~K();
00236       new ((K*)&node->key) K (*((K*)&y->key));
00237     }
00238     if (y->GetColor() == Black)
00239       DeleteFixup (node);
00240     nodeAlloc.Free (y);
00241   }
00243   void DeleteFixup (Node* node)
00244   {
00245     while ((node != root) && IsBlack (node))
00246     {
00247       Node* p = node->GetParent();
00248       if (node == p->left)
00249       {
00250         Node* w = p->right;
00251         if (IsRed (w))
00252         {
00253           w->SetColor (Black);
00254           p->SetColor (Red);
00255           RotateLeft (p);
00256           w = p->right;
00257         }
00258         if (IsBlack (w->left) && IsBlack (w->right))
00259         {
00260           w->SetColor (Red);
00261           node = p;
00262         }
00263         else
00264         {
00265           if (IsBlack (w->right))
00266           {
00267             w->left->SetColor (Red);
00268             w->SetColor (Red);
00269             RotateRight (w);
00270             w = p->right;
00271           }
00272           w->SetColor (p->GetColor ());
00273           p->SetColor (Black);
00274           w->right->SetColor (Black);
00275           RotateLeft (p);
00276           node = root;
00277         }
00278       }
00279       else
00280       {
00281         Node* w = p->left;
00282         if (IsRed (w))
00283         {
00284           w->SetColor (Black);
00285           p->SetColor (Red);
00286           RotateRight (p);
00287           w = p->left;
00288         }
00289         if (IsBlack (w->left) && IsBlack (w->right))
00290         {
00291           w->SetColor (Red);
00292           node = p;
00293         }
00294         else
00295         {
00296           if (IsBlack (w->left))
00297           {
00298             w->right->SetColor (Red);
00299             w->SetColor (Red);
00300             RotateLeft (w);
00301             w = p->left;
00302           }
00303           w->SetColor (p->GetColor ());
00304           p->SetColor (Black);
00305           w->left->SetColor (Black);
00306           RotateRight (p);
00307           node = root;
00308         }
00309       }
00310     }
00311     node->SetColor (Black);
00312   }
00314   Node* LocateNode (Node* node, const K& key) const
00315   {
00316     if (node == 0) return 0;
00317       
00318     int r = csComparator<K, K>::Compare (key, node->key);
00319     if (r == 0) 
00320       return node;
00321     else if (r < 0)
00322       return LocateNode (node->left, key);
00323     else
00324       return LocateNode (node->right, key);
00325   }
00327   Node* Successor (Node* node) const
00328   {
00329     Node* succ;
00330     if (node->right != 0)
00331     {
00332       succ = node->right;
00333       while (succ->left != 0) succ = succ->left;
00334       return succ;
00335     }
00336     Node* y = node->GetParent();
00337     while ((y != 0) && (node == y->right))
00338     {
00339       node = y;
00340       y = y->GetParent();
00341     }
00342     return y;
00343   }
00345 
00346   template<typename K2>
00347   const K* RecursiveFind (Node* node, const K2& other) const
00348   {
00349     if (node == 0) return 0;
00350     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
00351     if (r == 0)
00352       return ((K*)&node->key);
00353     else if (r < 0)
00354       return RecursiveFind (node->left, other);
00355     else
00356       return RecursiveFind (node->right, other);
00357   }
00358   template<typename K2>
00359   K* RecursiveFind (Node* node, const K2& other)
00360   {
00361     if (node == 0) return 0;
00362     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
00363     if (r == 0)
00364       return ((K*)&node->key);
00365     else if (r < 0)
00366       return RecursiveFind (node->left, other);
00367     else
00368       return RecursiveFind (node->right, other);
00369   }
00370   template<typename K2>
00371   const K& RecursiveFind (Node* node, const K2& other, const K& fallback) const
00372   {
00373     if (node == 0) return fallback;
00374     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
00375     if (r == 0)
00376       return *((K*)&node->key);
00377     else if (r < 0)
00378       return RecursiveFind (node->left, other);
00379     else
00380       return RecursiveFind (node->right, other);
00381   }
00382   template<typename K2>
00383   K& RecursiveFind (Node* node, const K2& other, K& fallback)
00384   {
00385     if (node == 0) return fallback;
00386     int r = csComparator<K2, K>::Compare (other, *((K*)&node->key));
00387     if (r == 0)
00388       return *((K*)&node->key);
00389     else if (r < 0)
00390       return RecursiveFind (node->left, other);
00391     else
00392       return RecursiveFind (node->right, other);
00393   }
00395 
00396   template <typename CB>
00397   void RecursiveTraverseInOrder (Node* node, CB& callback) const
00398   {
00399     if (node->left != 0) RecursiveTraverseInOrder (node->left, callback);
00400     callback.Process (*((K*)&node->key));
00401     if (node->right != 0) RecursiveTraverseInOrder (node->right, callback);
00402   }
00403 
00405 
00406   template<typename K2>
00407   K* Find (const K2& other)
00408   {
00409     return RecursiveFind (root, other);
00410   }
00411   template<typename K2>
00412   K& Find (const K2& other, K& fallback)
00413   {
00414     return RecursiveFind (root, other, fallback);
00415   }
00417 
00419   void RecursiveCopy (Node*& to, Node* parent, const Node* from)
00420   {
00421     if (from == 0)
00422     {
00423       to = 0; 
00424       return;
00425     }
00426     to = nodeAlloc.Alloc();
00427     to->SetParent (parent);
00428     to->SetColor (from->GetColor());
00429     new ((K*)&to->key) K (*((K*)&from->key));
00430     RecursiveCopy (to->left, to, from->left);
00431     RecursiveCopy (to->right, to, from->right);
00432   }
00433 public:
00439   csRedBlackTree (size_t allocatorBlockSize = 4096) : 
00440     nodeAlloc (allocatorBlockSize / sizeof(Node)), root(0) { }
00441   csRedBlackTree (const csRedBlackTree& other) : 
00442     nodeAlloc (other.nodeAlloc.GetBlockElements())
00443   {
00444     RecursiveCopy (root, 0, other.root);
00445   }
00446 
00452   const K* Insert (const K& key)
00453   {
00454     Node* n = RecursiveInsert (0, root, key);
00455     if (n == 0) return 0;
00456     InsertFixup (n);
00457     return (K*)&n->key;
00458   }
00464   bool Delete (const K& key)
00465   {
00466     Node* n = LocateNode (root, key);
00467     if (n == 0) return false;
00468     DeleteNode (n);
00469     return true;
00470   }
00472   bool In (const K& key) const
00473   {
00474     return (LocateNode (root, key) != 0);
00475   }
00481   bool Contains (const K& key) const { return In (key); }
00482   
00484 
00485   template<typename K2>
00486   const K* Find (const K2& other) const
00487   {
00488     return RecursiveFind (root, other);
00489   }
00490   template<typename K2>
00491   const K& Find (const K2& other, const K& fallback) const
00492   {
00493     return RecursiveFind (root, other, fallback);
00494   }
00496   
00498   void DeleteAll()
00499   {
00500     nodeAlloc.Empty();
00501     root = 0;
00502   }
00504   void Empty() { DeleteAll(); }
00506   bool IsEmpty() const { return (root == 0); }
00507 
00509 
00510   template <typename CB>
00511   void TraverseInOrder (CB& callback) const
00512   {
00513     if (root != 0) RecursiveTraverseInOrder (root, callback);
00514   }
00516 };
00517 
00522 template <typename K, typename T>
00523 class csRedBlackTreePayload
00524 {
00525   K key;
00526   T value;
00527 public:
00528   csRedBlackTreePayload (const K& k, const T& v) : key(k), value(v) {}
00529   csRedBlackTreePayload (const csRedBlackTreePayload& other) : 
00530     key(other.key), value(other.value) {}
00531 
00532   const K& GetKey() const { return key; }
00533   const T& GetValue() const { return value; }
00534   T& GetValue() { return value; }
00535   bool operator < (const csRedBlackTreePayload& other) const
00536   {
00537     return (csComparator<K, K>::Compare (key, other.key) < 0);
00538   }
00539   bool operator < (const K& other) const
00540   {
00541     return (csComparator<K, K>::Compare (key, other) < 0);
00542   }
00543   friend bool operator < (const K& k1, const csRedBlackTreePayload& k2)
00544   {
00545     return (csComparator<K, K>::Compare (k1, k2.key) < 0);
00546   }
00547   operator const T&() const { return value; }
00548   operator T&() { return value; }
00549 };
00550 
00555 template <typename K, typename T>
00556 class csRedBlackTreeMap : protected csRedBlackTree<csRedBlackTreePayload<K, T> >
00557 {
00558   typedef csRedBlackTree<csRedBlackTreePayload<K, T> > supahclass;
00559 
00560   template<typename CB>
00561   class TraverseCB
00562   {
00563     CB callback;
00564   public:
00565     TraverseCB (const CB& callback) : callback(callback) {}
00566     void Process (csRedBlackTreePayload<K, T>& value)
00567     {
00568       callback.Process (value.GetKey(), value.GetValue());
00569     }
00570   };
00571 public:
00577   T* Put (const K& key, const T &value)
00578   {
00579     csRedBlackTreePayload<K, T>* payload = (csRedBlackTreePayload<K, T>*)
00580       Insert (csRedBlackTreePayload<K, T>(key, value));
00581     return (payload != 0) ? &payload->GetValue() :  0;
00582   }
00588   bool Delete (const K& key)
00589   {
00590     csRedBlackTreePayload<K, T>* payload = Find (key);
00591     if (payload == 0) return false;
00592     return supahclass::Delete (*payload);
00593   }
00595 
00599   const T* GetElementPointer (const K& key) const
00600   {
00601     csRedBlackTreePayload<K, T>* payload = Find (key);
00602     if (payload == 0) return 0;
00603     return &payload->GetValue();
00604   }
00605   T* GetElementPointer (const K& key)
00606   {
00607     csRedBlackTreePayload<K, T>* payload = Find (key);
00608     if (payload == 0) return 0;
00609     return &payload->GetValue();
00610   }
00612 
00614 
00617   const T& Get (const K& key, const T& fallback) const
00618   {
00619     csRedBlackTreePayload<K, T>* payload = Find (key);
00620     if (payload == 0) return fallback;
00621     return payload->GetValue();
00622   }
00623   T& Get (const K& key, T& fallback)
00624   {
00625     csRedBlackTreePayload<K, T>* payload = Find (key);
00626     if (payload == 0) return fallback;
00627     return payload->GetValue();
00628   }
00630 
00631   void DeleteAll() { supahclass::Empty(); }
00633   void Empty() { DeleteAll(); }
00635   bool IsEmpty() const { return supahclass::IsEmpty(); }
00636 
00638 
00639   template <typename CB>
00640   void TraverseInOrder (CB& callback) const
00641   {
00642     TraverseCB<CB> traverser (callback);
00643     supahclass::TraverseInOrder (traverser);
00644   }
00646 };
00647 
00650 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00651 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00652 #endif
00653 
00654 #endif // __CS_UTIL_REDBLACKTREE_H__

Generated for Crystal Space 1.0.2 by doxygen 1.4.7