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-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.7.6.1