RedBlackTree.NET Source Code

The RedBlackTree class has several nested classes. Click on the following links to go straight to the relevant source code.

All source code markup was produced by the excellent Copy As HTML Visual Studio extension.


    1 using System;
    2 using System.Collections;
    3 using Microsoft.VisualBasic.Collections;
    4 using System.Threading;
    5 
    6 
    7 public class RedBlackTree : IEnumerable, ICollection
    8 {
    9     //// Top-down implementation of a Red-Black Tree data structure (no parent pointers and no recursion).
   10 
   11     //// Full .NET Enumeration support (For Each value In tree... Next)
   12     //// Full .NET Sychronization support (thread safety via the RedBlackTree.Synchronized() method)
   13     //// Automated unit testing is supported through an embedded class (RedBlackTree.Test)
   14 
   15     //// Adapted by Robert Pinchbeck
   16     //// from C source code provided in a tutorial by Julienne Walker
   17     //// http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
   18 
   27 
   28     /////////////////////////////////////////////////////////////////////////
   29     //// Tree Node Class
   30     /////////////////////////////////////////////////////////////////////////
   31     protected class RedBlackTreeNode
   32     {
   33 
   34         //// Any class that can be compared with the default comparer can be used as a key.
   35         //// This includes most system types (string, integer, date, etc...) 
   36         //// as well as classes that implement the IComparable interface
   37         public object key;
   38 
   39         //// The tree class can also be used as a dictionary class by
   40         //// inserting a key/value pair...
   41         ////
   42         //// By default, value = key
   43         public object value;
   44 
   45         //// Link "pointers" to child nodes...
   46         ////
   47         //// link[0)=left child, link[1)=right child
   48         public RedBlackTreeNode[] link = new RedBlackTreeNode[2];
   49 
   50         public bool red;
   51 
   52         public RedBlackTreeNode(object key, RedBlackTreeNode left, RedBlackTreeNode right, bool red, object value)
   53         {
   54             this.key = key;
   55             this.link[LEFT] = left;
   56             this.link[RIGHT] = right;
   57             this.red = red;
   58             this.value = value;
   59         }
   60 
   61     }
   62 
   63 
   64     //// Direction constants for the child of a given node //
   65     protected const int LEFT = 0;
   66     protected const int RIGHT = 1;
   67     //// For debugging //
   68     protected const int DIR_NOTSET = -1;
   69 
   70     //// Comparison constant (for clarity) //
   71     protected const int EQUAL = 0;
   72 
   73     //// Head node points to actual tree root (via the right link)
   74     protected RedBlackTreeNode head;
   75 
   76     //// Sentinel node always points to itself (equivalent to null)
   77     //// ...allows reference to the children of leaf nodes without causing exceptions.
   78     protected RedBlackTreeNode _sentinel;
   79 
   80     //// By default, duplicate keys are not allowed to be inserted //
   81     //// Developer can change this by setting the AllowDuplicateKeys property //
   82     protected bool _preventDuplicateKeys;
   83 
   84     //// Enumeration support //
   85     protected int _count;
   86     protected long lastModified;
   87 
   88     //// Comparer for comparing keys (if not specified, uses the default comparer) //
   89     protected IComparer _comparer;
   90 
   91     //// Synchronization wrapper //
   92     protected ReaderWriterLock _readerWriterLock;
   93 
   94 
   95     private void CommonNew(IComparer comparer, bool allowDuplicateKeys)
   96     {
   97         //// Initialize sentinel node for this tree //
   98         _sentinel = new RedBlackTreeNode(null, null, null, false, null);
   99         _sentinel.link[LEFT] = _sentinel;
  100         _sentinel.link[RIGHT] = _sentinel;
  101         _sentinel.red = false;
  102 
  103         //// Initialize head node for this tree //
  104         head = new RedBlackTreeNode(null, _sentinel, _sentinel, false, null);
  105 
  106         //// Initialize private members //
  107         _preventDuplicateKeys = !allowDuplicateKeys;
  108 
  109         _comparer = comparer;
  110     }
  111 
  112     public RedBlackTree()
  113     {
  114         CommonNew(Comparer.Default, false);
  115     }
  116 
  117     public RedBlackTree(bool allowDuplicateKeys)
  118     {
  119         CommonNew(Comparer.Default, allowDuplicateKeys);
  120     }
  121 
  122     public RedBlackTree(IComparer comparer)
  123     {
  124         CommonNew(comparer, false);
  125     }
  126 
  127     public RedBlackTree(IComparer comparer, bool allowDuplicateKeys)
  128     {
  129         CommonNew(comparer, allowDuplicateKeys);
  130     }
  131 
  132     //// Copy Constructor (shallow copy) //
  133     public RedBlackTree(RedBlackTree tree)
  134     {
  135         this.head = tree.head;
  136         this._sentinel = tree._sentinel;
  137         this._preventDuplicateKeys = tree._preventDuplicateKeys;
  138         this._count = tree._count;
  139         this.lastModified = tree.lastModified;
  140         this._comparer = tree._comparer;
  141     }
  142 
  143 
  144     public bool AllowDuplicateKeys
  145     {
  146         //// By default, duplicate keys are not allowed 
  147         //// Developer can change this behavior by setting specifying it in the constructor //
  148         get { return !_preventDuplicateKeys; }
  149     }
  150 
  151 
  152     public virtual long LastModified
  153     {
  154         //// This property is used by enumerators to test for validity //
  155         //// A 64-bit integer is incremented whenever the tree changes //
  156         //// See IEnumerator interface for more information //
  157         get { return lastModified; }
  158     }
  159 
  160     public static RedBlackTree Synchronized(RedBlackTree tree)
  161     {
  162         return new RedBlackTreeSynchronized(tree);
  163     }
  164 
  165     protected int Opposite(int direction)
  166     {
  167         //// Return the opposite of the specified direction //
  168 
  169         if (direction == RIGHT)
  170         {
  171             return LEFT;
  172         }
  173 
  174         return RIGHT;
  175     }
  176 
  177 
  178     protected RedBlackTreeNode RotateSingle(RedBlackTreeNode node, int direction)
  179     {
  180         //// Rotate the specified node (and its children) in the specified direction //
  181 
  182         RedBlackTreeNode child;
  183         RedBlackTreeNode grandChild;
  184 
  185         child = node.link[Opposite(direction)];
  186         grandChild = child.link[direction];
  187 
  188         node.link[Opposite(direction)] = grandChild;
  189         child.link[direction] = node;
  190 
  191         node.red = true;
  192         child.red = false;
  193 
  194         return child;
  195     }
  196 
  197 
  198     protected RedBlackTreeNode RotateDouble(RedBlackTreeNode node, int direction)
  199     {
  200         //// Rotate the specified node (and its children) in the specified direction... //
  201         //// ...but first rotate its opposite child in the opposite direction //
  202 
  203         node.link[Opposite(direction)] = RotateSingle(node.link[Opposite(direction)], Opposite(direction));
  204 
  205         return RotateSingle(node, direction);
  206     }
  207 
  208 
  209     protected int CompareKeys(object key1, object key2)
  210     {
  211         return _comparer.Compare(key1, key2);
  212     }
  213 
  214 
  215     protected RedBlackTreeNode FindNode(object key)
  216     {
  217         //// Search for the specified key and return its containing node...
  218         //// If the key is not found, then the sentinel node is returned //
  219 
  220         RedBlackTreeNode current;
  221         int comparison;
  222 
  223         current = head.link[RIGHT];
  224 
  225         while ((!object.ReferenceEquals(current, _sentinel)))
  226         {
  227 
  228             comparison = CompareKeys(key, current.key);
  229 
  230             if (comparison < 0)
  231             {
  232                 current = current.link[LEFT];
  233             }
  234             else if (comparison > 0)
  235             {
  236                 current = current.link[RIGHT];
  237             }
  238             else
  239             {
  240                 goto ReturnResult;
  241             }
  242 
  243         }
  244 
  245         current = _sentinel;
  246     ReturnResult:
  247 
  248         return current;
  249     }
  250 
  251 
  252     protected virtual void IncrementCount()
  253     {
  254         //// Update count property whenever node is added/deleted //
  255         _count = _count + 1;
  256         lastModified = lastModified + 1;
  257     }
  258 
  259 
  260     protected virtual void DecrementCount()
  261     {
  262         //// Update count property whenever node is added/deleted //
  263         _count = _count - 1;
  264         lastModified = lastModified + 1;
  265     }
  266 
  267 
  268     public virtual void Add(object key)
  269     {
  270         this.Add(key, key);
  271     }
  272 
  273     public virtual void Add(object key, object value)
  274     {
  275         //// Adds an item/value to the tree //
  276 
  277         RedBlackTreeNode greatGrandParent;
  278         RedBlackTreeNode grandParent;
  279         RedBlackTreeNode parent;
  280         RedBlackTreeNode current;
  281 
  282         int direction;
  283         int lastDirection;
  284         int grandParentDirection;
  285 
  286         int comparison;
  287         bool keepSearching;
  288 
  289         try
  290         {
  291             //// Initialize search //
  292             greatGrandParent = null;
  293             grandParent = null;
  294             parent = head;
  295             current = head.link[RIGHT];
  296 
  297             direction = RIGHT;
  298             lastDirection = DIR_NOTSET;
  299 
  300 
  301             //// Search until node has been inserted //
  302             keepSearching = true;
  303 
  304             while (keepSearching)
  305             {
  306 
  307                 //// Check if insert position found //
  308                 if (object.ReferenceEquals(current, _sentinel))
  309                 {
  310 
  311                     //// Insert position found, add new node to tree //
  312                     current = new RedBlackTreeNode(key, _sentinel, _sentinel, true, value);
  313                     parent.link[direction] = current;
  314                     IncrementCount();
  315                     keepSearching = false;
  316                 }
  317 
  318                 else
  319                 {
  320 
  321                     //// Check if both children are red //
  322                     if (current.link[LEFT].red & current.link[RIGHT].red)
  323                     {
  324 
  325                         //// Both children are red, fix it //
  326                         current.red = true;
  327                         current.link[LEFT].red = false;
  328                         current.link[RIGHT].red = false;
  329                     }
  330 
  331                 }
  332 
  333 
  334                 //// Check for red violation //
  335                 if (current.red & parent.red)
  336                 {
  337 
  338                     //// Red violation detected, fix it //
  339 
  340                     if (lastDirection == DIR_NOTSET)
  341                     {
  342                         //// This should never happen, if it does, then halt execution //
  343                         Throw_OrDebug(new RedBlackTreeException("cannot add item to tree, last direction not set"));
  344                     }
  345 
  346                     if (greatGrandParent == null)
  347                     {
  348                         //// This should never happen, if it does, then halt execution //
  349                         Throw_OrDebug(new RedBlackTreeException("cannot add item to tree, greatgrandparent not set"));
  350                     }
  351 
  352                     if (object.ReferenceEquals(grandParent, greatGrandParent.link[LEFT]))
  353                     {
  354                         grandParentDirection = LEFT;
  355                     }
  356                     else
  357                     {
  358                         grandParentDirection = RIGHT;
  359                     }
  360 
  361                     if (object.ReferenceEquals(current, parent.link[lastDirection]))
  362                     {
  363                         greatGrandParent.link[grandParentDirection] = RotateSingle(grandParent, Opposite(lastDirection));
  364                     }
  365                     else
  366                     {
  367                         greatGrandParent.link[grandParentDirection] = RotateDouble(grandParent, Opposite(lastDirection));
  368                     }
  369 
  370                 }
  371 
  372 
  373                 if (keepSearching)
  374                 {
  375 
  376                     comparison = CompareKeys(key, current.key);
  377 
  378                     //// Check if duplicate keys are allowed //
  379                     if (_preventDuplicateKeys)
  380                     {
  381 
  382                         //// Duplicate keys not allowed, enforce it //
  383                         if (comparison == EQUAL)
  384                         {
  385                             throw new RedBlackTreeDuplicateKeyException("add to tree failed (duplicate key)");
  386                         }
  387                     }
  388 
  389                     lastDirection = direction;
  390 
  391                     if (comparison < 0)
  392                     {
  393                         direction = LEFT;
  394                     }
  395                     else
  396                     {
  397                         direction = RIGHT;
  398                     }
  399 
  400                     greatGrandParent = grandParent;
  401                     grandParent = parent;
  402                     parent = current;
  403                     current = current.link[direction];
  404                 }
  405             }
  406         }
  407 
  408         finally
  409         {
  410             //// Ensure that root node is never red //
  411             head.link[RIGHT].red = false;
  412         }
  413 
  414     }
  415 
  416 
  417     public virtual object Remove(object key)
  418     {
  419         //// Removes the specified key (and value) from the tree //
  420         //// If there are duplicate keys in the tree, only the first one found is removed //
  421 
  422         RedBlackTreeNode grandParent;
  423         RedBlackTreeNode parent;
  424         RedBlackTreeNode current;
  425         RedBlackTreeNode found;
  426 
  427         int direction;
  428         int parentDirection;
  429         int lastDirection;
  430         int comparison;
  431 
  432         RedBlackTreeNode newParent;
  433         RedBlackTreeNode sibling;
  434 
  435         try
  436         {
  437             found = _sentinel;
  438             grandParent = null;
  439             parent = null;
  440             current = head;
  441 
  442             direction = RIGHT;
  443 
  444             //// Search and push a red down //
  445             while ((!object.ReferenceEquals(current.link[direction], _sentinel)))
  446             {
  447                 lastDirection = direction;
  448 
  449                 grandParent = parent;
  450                 parent = current;
  451                 current = current.link[direction];
  452 
  453                 comparison = CompareKeys(key, current.key);
  454 
  455                 if (comparison < 0)
  456                 {
  457                     direction = LEFT;
  458                 }
  459                 else
  460                 {
  461                     direction = RIGHT;
  462                 }
  463 
  464                 if (comparison == EQUAL)
  465                 {
  466                     found = current;
  467                 }
  468 
  469                 //// Push the red node down //
  470                 if (!current.red & !current.link[direction].red)
  471                 {
  472 
  473                     if (current.link[Opposite(direction)].red)
  474                     {
  475 
  476                         newParent = RotateSingle(current, direction);
  477                         parent.link[lastDirection] = newParent;
  478                         parent = newParent;
  479                     }
  480 
  481                     else
  482                     {
  483 
  484                         sibling = parent.link[Opposite(lastDirection)];
  485 
  486                         if ((!object.ReferenceEquals(sibling, _sentinel)))
  487                         {
  488 
  489                             //// Check if sibling's children are both black //
  490                             if (!sibling.link[Opposite(lastDirection)].red & !sibling.link[lastDirection].red)
  491                             {
  492 
  493                                 //// Sibling's children are both black, color flip will suffice
  494                                 parent.red = false;
  495                                 sibling.red = true;
  496                                 current.red = true;
  497                             }
  498 
  499                             else
  500                             {
  501                                 //// One of sibling's children is red, balance tree as needed //
  502                                 if (object.ReferenceEquals(grandParent.link[LEFT], parent))
  503                                 {
  504                                     parentDirection = LEFT;
  505                                 }
  506                                 else
  507                                 {
  508                                     parentDirection = RIGHT;
  509                                 }
  510 
  511                                 if (sibling.link[lastDirection].red)
  512                                 {
  513 
  514                                     newParent = RotateDouble(parent, lastDirection);
  515                                 }
  516                                 else
  517                                 {
  518 
  519                                     newParent = RotateSingle(parent, lastDirection);
  520                                 }
  521 
  522                                 //// Ensure correct coloring after balancing //
  523                                 newParent.red = true;
  524                                 newParent.link[LEFT].red = false;
  525                                 newParent.link[RIGHT].red = false;
  526                                 grandParent.link[parentDirection] = newParent;
  527                                 current.red = true;
  528 
  529                             }
  530 
  531                         }
  532 
  533                     }
  534 
  535                 }
  536 
  537             }
  538 
  539             //// Check if key was not found //
  540             if (object.ReferenceEquals(found, _sentinel))
  541             {
  542 
  543                 //// Key was not found, throw exception //
  544                 throw new RedBlackTreeKeyNotFoundException("remove from tree failed (key not found)");
  545             }
  546 
  547             //// Found node is being removed, replace it with current node //
  548             found.key = current.key;
  549             found.value = current.value;
  550 
  551             if (object.ReferenceEquals(parent.link[LEFT], current))
  552             {
  553                 direction = LEFT;
  554             }
  555             else
  556             {
  557                 direction = RIGHT;
  558             }
  559 
  560             if (object.ReferenceEquals(current.link[LEFT], _sentinel))
  561             {
  562                 parentDirection = RIGHT;
  563             }
  564             else
  565             {
  566                 parentDirection = LEFT;
  567             }
  568 
  569             //// Remove current node from tree
  570             parent.link[direction] = current.link[parentDirection];
  571 
  572             //// Update counters //
  573             DecrementCount();
  574         }
  575 
  576         finally
  577         {
  578             //// Ensure that root node is never red //
  579             head.link[RIGHT].red = false;
  580         }
  581 
  582         if (object.ReferenceEquals(found, _sentinel))
  583         {
  584             return null;
  585         }
  586         else
  587         {
  588             return found.value;
  589         }
  590     }
  591 
  592     public virtual object this[object key]
  593     {
  594         //// Returns the value of the node with the specified key //
  595         //// If duplicate keys exist, then the first one found is returned //
  596         get
  597         {
  598             object result;
  599             RedBlackTreeNode node;
  600 
  601             node = FindNode(key);
  602 
  603             if (object.ReferenceEquals(node, _sentinel))
  604             {
  605                 throw new RedBlackTreeKeyNotFoundException("cannot retrieve item from tree (key not found)");
  606             }
  607 
  608             result = node.value;
  609 
  610             return result;
  611         }
  612     }
  613 
  614 
  615     protected virtual object OuterMostItem(int direction)
  616     {
  617         //// Returns the leftmost/rightmost value in the tree //
  618         //// Depending on direction //
  619         object result;
  620         RedBlackTreeNode node;
  621         RedBlackTreeNode previousNode;
  622 
  623         if (direction == LEFT || direction == RIGHT)
  624         {
  625         }
  626         //// do nothing
  627         else
  628         {
  629             Throw_OrDebug(new ArgumentException("invalid direction (" + direction + ")"));
  630         }
  631 
  632         previousNode = head;
  633         node = previousNode.link[RIGHT];
  634 
  635         while ((!object.ReferenceEquals(node, _sentinel)))
  636         {
  637             previousNode = node;
  638             node = node.link[direction];
  639         }
  640 
  641         if (object.ReferenceEquals(previousNode, head))
  642         {
  643             throw new RedBlackTreeEmptyException("cannot retrieve item from tree (tree is empty)");
  644         }
  645 
  646         result = previousNode.value;
  647 
  648         return result;
  649     }
  650 
  651     public object LeftMostItem()
  652     {
  653         //// Returns the value of the leftmost node //
  654         return OuterMostItem(DIR_LEFT);
  655     }
  656 
  657     public object RightMostItem()
  658     {
  659         //// Returns the value of the rightmost node //
  660         return OuterMostItem(DIR_RIGHT);
  661     }
  662 
  663 
  664     public virtual bool Contains(object key)
  665     {
  666         //// Checks if a node with the specified key exists...
  667         //// Returns true if it does, otherwise returns false //
  668 
  669         bool result = false;
  670         RedBlackTreeNode node;
  671 
  672         node = FindNode(key);
  673 
  674         if ((!object.ReferenceEquals(node, _sentinel)))
  675         {
  676             result = true;
  677         }
  678 
  679         return result;
  680     }
  681 
  682 
  683     static internal void Throw_OrDebug(Exception oException)
  684     {
  685 
  686 #if DEBUG
  687         //// When debugging, stop execution instead of throwing exception //
  688         //// (makes debugging the call stack easier) //
  689         System.Diagnostics.Debugger.Break();
  690 #else
  691         throw oException;
  692 #endif
  693 
  694     }
  695 
  696     internal virtual void DebugLock()
  697     {
  698         //// Do nothing, only synchronized class can be locked //
  699     }
  700 
  701     internal virtual void DebugRelease()
  702     {
  703         //// Do nothing, only synchronized class can be released //
  704     }
  705 
  706 
  707     /////////////////////////////////////////////////////////////////////////
  708     //// ICollection Interface //
  709     /////////////////////////////////////////////////////////////////////////
  710     void System.Collections.ICollection.CopyTo(Array array, int index)
  711     {
  712         foreach (object value in this)
  713         {
  714             if (value is ICloneable)
  715             {
  716                 ICloneable oCloneable;
  717                 object oClone;
  718 
  719                 oCloneable = (ICloneable)value;
  720                 oClone = oCloneable.Clone();
  721 
  722                 array.SetValue(oClone, index);
  723             }
  724             else
  725             {
  726                 array.SetValue(value, index);
  727             }
  728             index = index + 1;
  729         }
  730     }
  731 
  732 
  733     int System.Collections.ICollection.Count
  734     {
  735         get { return _count; }
  736     }
  737 
  738 
  739     bool System.Collections.ICollection.IsSynchronized
  740     {
  741         get { return false; }
  742     }
  743 
  744 
  745     object System.Collections.ICollection.SyncRoot
  746     {
  747         get { return this; }
  748     }
  749 
  750 
  751     /////////////////////////////////////////////////////////////////////////
  752     //// Synchronization Wrapper Class
  753     /////////////////////////////////////////////////////////////////////////
  754 
  755     protected class RedBlackTreeSynchronized : RedBlackTree, ICollection
  756     {
  757 
  758         //// Allow either reads or writes, but not both (favor reads with a ReaderWriterLock)
  759         protected RedBlackTree _wrappedTree;
  760 
  761         private RedBlackTreeSynchronized()
  762         {
  763             //// This class cannot be instantiated... it must be copied from an existing tree //
  764         }
  765 
  766         public RedBlackTreeSynchronized(RedBlackTree tree)
  767             : base(tree)
  768         {
  769 
  770             //// Wrapper class does not track count //
  771             _count = 0;
  772 
  773             _wrappedTree = tree;
  774 
  775             if (_wrappedTree._readerWriterLock == null)
  776             {
  777                 _wrappedTree._readerWriterLock = new ReaderWriterLock();
  778             }
  779         }
  780 
  781         private void BeginWrite()
  782         {
  783             _wrappedTree._readerWriterLock.AcquireWriterLock(Timeout.Infinite);
  784         }
  785 
  786 
  787         private void EndWrite()
  788         {
  789             _wrappedTree._readerWriterLock.ReleaseWriterLock();
  790         }
  791 
  792 
  793         private void BeginRead()
  794         {
  795             _wrappedTree._readerWriterLock.AcquireReaderLock(Timeout.Infinite);
  796         }
  797 
  798 
  799         private void EndRead()
  800         {
  801             _wrappedTree._readerWriterLock.ReleaseReaderLock();
  802         }
  803 
  804 
  805         public override long LastModified
  806         {
  807             get
  808             {
  809                 BeginRead();
  810                 try
  811                 {
  812                     return _wrappedTree.LastModified;
  813                 }
  814                 finally
  815                 {
  816                     EndRead();
  817                 }
  818             }
  819         }
  820 
  821 
  822         public override void Add(object key, object value)
  823         {
  824             BeginWrite();
  825             try
  826             {
  827                 _wrappedTree.Add(key, value);
  828             }
  829             finally
  830             {
  831                 EndWrite();
  832             }
  833 
  834         }
  835 
  836 
  837         public override object Remove(object key)
  838         {
  839             BeginWrite();
  840             try
  841             {
  842                 return _wrappedTree.Remove(key);
  843             }
  844             finally
  845             {
  846                 EndWrite();
  847             }
  848         }
  849 
  850 
  851         public override object this[object key]
  852         {
  853             get
  854             {
  855                 BeginRead();
  856                 try
  857                 {
  858                     return _wrappedTree[key];
  859                 }
  860                 finally
  861                 {
  862                     EndRead();
  863                 }
  864             }
  865         }
  866 
  867 
  868         protected override object OuterMostItem(int direction)
  869         {
  870             BeginRead();
  871             try
  872             {
  873                 return _wrappedTree.OuterMostItem(direction);
  874             }
  875             finally
  876             {
  877                 EndRead();
  878             }
  879         }
  880 
  881         public override bool Contains(object key)
  882         {
  883             BeginRead();
  884             try
  885             {
  886                 return _wrappedTree.Contains(key);
  887             }
  888             finally
  889             {
  890                 EndRead();
  891             }
  892         }
  893 
  894 
  895         void System.Collections.ICollection.CopyTo(Array array, int index)
  896         {
  897             BeginRead();
  898             try
  899             {
  900                 ((ICollection)_wrappedTree).CopyTo(array, index);
  901             }
  902             finally
  903             {
  904                 EndRead();
  905             }
  906         }
  907 
  908 
  909         int System.Collections.ICollection.Count
  910         {
  911             get
  912             {
  913                 BeginRead();
  914                 try
  915                 {
  916                     return ((ICollection)_wrappedTree).Count;
  917                 }
  918                 finally
  919                 {
  920                     EndRead();
  921                 }
  922             }
  923         }
  924 
  925 
  926         bool System.Collections.ICollection.IsSynchronized
  927         {
  928             get { return true; }
  929         }
  930 
  931 
  932         object System.Collections.ICollection.SyncRoot
  933         {
  934             get
  935             {
  936                 return ((ICollection)_wrappedTree).SyncRoot;
  937             }
  938         }
  939 
  940         internal override void DebugLock()
  941         {
  942             BeginWrite();
  943         }
  944 
  945         internal override void DebugRelease()
  946         {
  947             EndWrite();
  948         }
  949 
  950     }
  951 
  952 
  953     /////////////////////////////////////////////////////////////////////////
  954     //// IEnumerable Interface //
  955     /////////////////////////////////////////////////////////////////////////
  956     private class RedBlackTreeEnumerator : IEnumerator
  957     {
  958 
  959         private RedBlackTree _tree;
  960         private System.Collections.Stack _nodeStack;
  961         private RedBlackTreeNode _currentNode;
  962         private object _currentValue;
  963         private object _currentKey;
  964         private long _treeLastModified;
  965         private int _direction;
  966 
  967 
  968         public RedBlackTreeEnumerator(RedBlackTree tree, int direction)
  969         {
  970             _direction = direction;
  971 
  972             _tree = tree;
  973             _treeLastModified = tree.LastModified;
  974             ((IEnumerator)this).Reset();
  975         }
  976 
  977 
  978         object System.Collections.IEnumerator.Current
  979         {
  980             get
  981             {
  982                 if ((_currentKey == null))
  983                 {
  984                     Throw_OrDebug(new InvalidOperationException("current failed (invalid enumerator)"));
  985                 }
  986 
  987                 return _currentValue;
  988             }
  989         }
  990 
  991 
  992 
  993         bool System.Collections.IEnumerator.MoveNext()
  994         {
  995             bool result;
  996 
  997             if (_tree.LastModified != _treeLastModified)
  998             {
  999                 Throw_OrDebug(new InvalidOperationException("movenext failed (tree was modified during enumeration)"));
 1000             }
 1001 
 1002             if (object.ReferenceEquals(_currentNode, _tree._sentinel))
 1003             {
 1004                 _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
 1005 
 1006                 if (_currentNode == null)
 1007                 {
 1008                     result = false;
 1009                 }
 1010                 else
 1011                 {
 1012                     result = true;
 1013                 }
 1014 
 1015                 goto ExitSub;
 1016             }
 1017 
 1018             _currentNode = _currentNode.link[_tree.Opposite(_direction)];
 1019 
 1020             if (object.ReferenceEquals(_currentNode, _tree._sentinel))
 1021             {
 1022                 _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
 1023 
 1024                 if (_currentNode == null)
 1025                 {
 1026                     result = false;
 1027                 }
 1028                 else
 1029                 {
 1030                     result = true;
 1031                 }
 1032                 goto ExitSub;
 1033             }
 1034 
 1035             while ((!object.ReferenceEquals(_currentNode, _tree._sentinel)))
 1036             {
 1037                 _nodeStack.Push(_currentNode);
 1038                 _currentNode = _currentNode.link[_direction];
 1039             }
 1040 
 1041             _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
 1042 
 1043             result = true;
 1044         ExitSub:
 1045 
 1046             if (_currentNode == null)
 1047             {
 1048                 _currentKey = null;
 1049                 _currentValue = null;
 1050             }
 1051 
 1052             else if (object.ReferenceEquals(_currentNode, _tree._sentinel))
 1053             {
 1054                 _currentKey = null;
 1055                 _currentValue = null;
 1056             }
 1057 
 1058             else
 1059             {
 1060                 _currentKey = _currentNode.key;
 1061                 _currentValue = _currentNode.value;
 1062 
 1063             }
 1064 
 1065             return result;
 1066         }
 1067 
 1068 
 1069         void System.Collections.IEnumerator.Reset()
 1070         {
 1071             RedBlackTreeNode nextNode;
 1072 
 1073             if (_tree.LastModified != _treeLastModified)
 1074             {
 1075                 Throw_OrDebug(new InvalidOperationException("reset failed (tree was modified during enumeration)"));
 1076             }
 1077 
 1078             _currentKey = null;
 1079             _currentValue = null;
 1080 
 1081             _nodeStack = new System.Collections.Stack();
 1082             _nodeStack.Push(null);
 1083 
 1084             _currentNode = _tree.head.link[RIGHT];
 1085 
 1086             while ((!object.ReferenceEquals(_currentNode, _tree._sentinel)))
 1087             {
 1088                 _nodeStack.Push(_currentNode);
 1089 
 1090                 nextNode = _currentNode.link[_direction];
 1091 
 1092                 if (object.ReferenceEquals(nextNode, _tree._sentinel))
 1093                 {
 1094                     _currentKey = _currentNode.key;
 1095                     _currentValue = _currentNode.value;
 1096                 }
 1097 
 1098                 _currentNode = nextNode;
 1099             }
 1100         }
 1101     }
 1102 
 1103 
 1104     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 1105     {
 1106         //// Enumeration is from left to right by default (sorted ascending)
 1107         return new RedBlackTreeEnumerator(this, LEFT);
 1108     }
 1109 
 1110     System.Collections.IEnumerator GetLeftToRightEnumerator()
 1111     {
 1112         //// (sorted ascending)
 1113         return new RedBlackTreeEnumerator(this, LEFT);
 1114     }
 1115 
 1116     System.Collections.IEnumerator GetRightTleftEnumerator()
 1117     {
 1118         //// (sorted descending)
 1119         return new RedBlackTreeEnumerator(this, RIGHT);
 1120     }
 1121 
 1122 
 1123 
 1124     /////////////////////////////////////////////////////////////////////////
 1125     //// Exception Classes
 1126     /////////////////////////////////////////////////////////////////////////
 1127 
 1128     public class RedBlackTreeException : Exception
 1129     {
 1130 
 1131         public RedBlackTreeException(string message)
 1132             : base(message)
 1133         {
 1134         }
 1135     }
 1136 
 1137     public class RedBlackTreeDuplicateKeyException : ArgumentException
 1138     {
 1139 
 1140         public RedBlackTreeDuplicateKeyException(string message)
 1141             : base(message)
 1142         {
 1143         }
 1144     }
 1145 
 1146     public class RedBlackTreeKeyNotFoundException : ArgumentException
 1147     {
 1148 
 1149         public RedBlackTreeKeyNotFoundException(string message)
 1150             : base(message)
 1151         {
 1152         }
 1153     }
 1154 
 1155     public class RedBlackTreeEmptyException : RedBlackTreeException
 1156     {
 1157 
 1158         public RedBlackTreeEmptyException(string message)
 1159             : base(message)
 1160         {
 1161         }
 1162     }
 1864         }
 1865     }
 1866 }



Copyright (C) 2007-2009 by Robert Pinchbeck
All Rights Reserved