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)
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