The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ TreeRotation

  1. //------------------------------------------------------------------------------
  2. // <copyright file="TreeSet.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. namespace System.Collections.Generic
  16. {
  17.     using System;
  18.     using System.Diagnostics;
  19.     using System.Runtime.Serialization;
  20.    
  21.     //
  22.     // A binary search tree is a red-black tree if it satifies the following red-black properties:
  23.     // 1. Every node is either red or black
  24.     // 2. Every leaf (nil node) is black
  25.     // 3. If a node is red, the both its children are black
  26.     // 4. Every simple path from a node to a descendant leaf contains the same number of black nodes
  27.     //
  28.     // The basic idea of red-black tree is to represent 2-3-4 trees as standard BSTs but to add one extra bit of information
  29.     // per node to encode 3-nodes and 4-nodes.
  30.     // 4-nodes will be represented as: B
  31.     // R R
  32.     // 3 -node will be represented as: B or B
  33.     // R B B R
  34.     //
  35.     // For a detailed description of the algorithm, take a look at "Algorithm" by Rebert Sedgewick.
  36.     //
  37.    
  38.     internal delegate bool TreeWalkAction<T>(TreeSet<T>.Node node);
  39.    
  40.     internal enum TreeRotation
  41.     {
  42.         LeftRotation = 1,
  43.         RightRotation = 2,
  44.         RightLeftRotation = 3,
  45.         LeftRightRotation = 4
  46.     }
  47.    
  48.     [Serializable()]
  49.     internal class TreeSet<T> : ICollection<T>, ICollection, ISerializable, IDeserializationCallback
  50.     {
  51.         Node root;
  52.         IComparer<T> comparer;
  53.         int count;
  54.         int version;
  55.         private object _syncRoot;
  56.        
  57.         private const string ComparerName = "Comparer";
  58.         private const string CountName = "Count";
  59.         private const string ItemsName = "Items";
  60.         private const string VersionName = "Version";
  61.        
  62.         private SerializationInfo siInfo;
  63.         //A temporary variable which we need during deserialization.
  64.         public TreeSet(IComparer<T> comparer)
  65.         {
  66.             if (comparer == null) {
  67.                 this.comparer = Comparer<T>.Default;
  68.             }
  69.             else {
  70.                 this.comparer = comparer;
  71.             }
  72.         }
  73.        
  74.         protected TreeSet(SerializationInfo info, StreamingContext context)
  75.         {
  76.             siInfo = info;
  77.         }
  78.        
  79.        
  80.         public int Count {
  81.             get { return count; }
  82.         }
  83.        
  84.         public IComparer<T> Comparer {
  85.             get { return comparer; }
  86.         }
  87.        
  88.         bool ICollection<T>.IsReadOnly {
  89.             get { return false; }
  90.         }
  91.        
  92.         bool ICollection.IsSynchronized {
  93.             get { return false; }
  94.         }
  95.        
  96.         object ICollection.SyncRoot {
  97.             get {
  98.                 if (_syncRoot == null) {
  99.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  100.                 }
  101.                 return _syncRoot;
  102.             }
  103.         }
  104.        
  105.         public void Add(T item)
  106.         {
  107.             if (root == null) {
  108.                 // empty tree
  109.                 root = new Node(item, false);
  110.                 count = 1;
  111.                 return;
  112.             }
  113.            
  114.             //
  115.             // Search for a node at bottom to insert the new node.
  116.             // If we can guanratee the node we found is not a 4-node, it would be easy to do insertion.
  117.             // We split 4-nodes along the search path.
  118.             //
  119.             Node current = root;
  120.             Node parent = null;
  121.             Node grandParent = null;
  122.             Node greatGrandParent = null;
  123.            
  124.             int order = 0;
  125.             while (current != null) {
  126.                 order = comparer.Compare(item, current.Item);
  127.                 if (order == 0) {
  128.                     // We could have changed root node to red during the search process.
  129.                     // We need to set it to black before we return.
  130.                     root.IsRed = false;
  131.                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
  132.                 }
  133.                
  134.                 // split a 4-node into two 2-nodes
  135.                 if (Is4Node(current)) {
  136.                     Split4Node(current);
  137.                     // We could have introduced two consecutive red nodes after split. Fix that by rotation.
  138.                     if (IsRed(parent)) {
  139.                         InsertionBalance(current, ref parent, grandParent, greatGrandParent);
  140.                     }
  141.                 }
  142.                 greatGrandParent = grandParent;
  143.                 grandParent = parent;
  144.                 parent = current;
  145.                 current = (order < 0) ? current.Left : current.Right;
  146.             }
  147.            
  148.             Debug.Assert(parent != null, "Parent node cannot be null here!");
  149.             // ready to insert the new node
  150.             Node node = new Node(item);
  151.             if (order > 0) {
  152.                 parent.Right = node;
  153.             }
  154.             else {
  155.                 parent.Left = node;
  156.             }
  157.            
  158.             // the new node will be red, so we will need to adjust the colors if parent node is also red
  159.             if (parent.IsRed) {
  160.                 InsertionBalance(node, ref parent, grandParent, greatGrandParent);
  161.             }
  162.            
  163.             // Root node is always black
  164.             root.IsRed = false;
  165.             ++count;
  166.             ++version;
  167.         }
  168.        
  169.         public void Clear()
  170.         {
  171.             root = null;
  172.             count = 0;
  173.             ++version;
  174.         }
  175.        
  176.         public bool Contains(T item)
  177.         {
  178.             return FindNode(item) != null;
  179.         }
  180.        
  181.         //
  182.         // Do a in order walk on tree and calls the delegate for each node.
  183.         // If the action delegate returns false, stop the walk.
  184.         //
  185.         // Return true if the entire tree has been walked.
  186.         // Otherwise returns false.
  187.         //
  188.         internal bool InOrderTreeWalk(TreeWalkAction<T> action)
  189.         {
  190.             if (root == null) {
  191.                 return true;
  192.             }
  193.            
  194.             // The maximum height of a red-black tree is 2*lg(n+1).
  195.             // See page 264 of "Introduction to algorithms" by Thomas H. Cormen
  196.             Stack<Node> stack = new Stack<Node>(2 * (int)Math.Log(Count + 1));
  197.             Node current = root;
  198.             while (current != null) {
  199.                 stack.Push(current);
  200.                 current = current.Left;
  201.             }
  202.            
  203.             while (stack.Count != 0) {
  204.                 current = stack.Pop();
  205.                 if (!action(current)) {
  206.                     return false;
  207.                 }
  208.                
  209.                 Node node = current.Right;
  210.                 while (node != null) {
  211.                     stack.Push(node);
  212.                     node = node.Left;
  213.                 }
  214.             }
  215.             return true;
  216.         }
  217.        
  218.         public void CopyTo(T[] array, int index)
  219.         {
  220.             if (array == null) {
  221.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  222.             }
  223.            
  224.             if (index < 0) {
  225.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
  226.             }
  227.            
  228.             if (array.Length - index < Count) {
  229.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
  230.             }
  231.            
  232.             InOrderTreeWalk(delegate(Node node)
  233.             {
  234.                 array[index++] = node.Item;
  235.                 return true;
  236.             }
  237. );
  238.         }
  239.        
  240.         void ICollection.CopyTo(Array array, int index)
  241.         {
  242.             if (array == null) {
  243.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  244.             }
  245.            
  246.             if (array.Rank != 1) {
  247.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
  248.             }
  249.            
  250.             if (array.GetLowerBound(0) != 0) {
  251.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
  252.             }
  253.            
  254.             if (index < 0) {
  255.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  256.             }
  257.            
  258.             if (array.Length - index < Count) {
  259.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
  260.             }
  261.            
  262.             T[] tarray = array as T[];
  263.             if (tarray != null) {
  264.                 CopyTo(tarray, index);
  265.             }
  266.             else {
  267.                 object[] objects = array as object[];
  268.                 if (objects == null) {
  269.                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  270.                 }
  271.                
  272.                 try {
  273.                     InOrderTreeWalk(delegate(Node node)
  274.                     {
  275.                         objects[index++] = node.Item;
  276.                         return true;
  277.                     }
  278. );
  279.                 }
  280.                 catch (ArrayTypeMismatchException) {
  281.                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  282.                 }
  283.             }
  284.         }
  285.        
  286.         public Enumerator GetEnumerator()
  287.         {
  288.             return new Enumerator(this);
  289.         }
  290.        
  291.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
  292.         {
  293.             return new Enumerator(this);
  294.         }
  295.        
  296.         IEnumerator IEnumerable.GetEnumerator()
  297.         {
  298.             return new Enumerator(this);
  299.         }
  300.        
  301.         internal Node FindNode(T item)
  302.         {
  303.             Node current = root;
  304.             while (current != null) {
  305.                 int order = comparer.Compare(item, current.Item);
  306.                 if (order == 0) {
  307.                     return current;
  308.                 }
  309.                 else {
  310.                     current = (order < 0) ? current.Left : current.Right;
  311.                 }
  312.             }
  313.            
  314.             return null;
  315.         }
  316.        
  317.         public bool Remove(T item)
  318.         {
  319.             if (root == null) {
  320.                 return false;
  321.             }
  322.            
  323.             // Search for a node and then find its succesor.
  324.             // Then copy the item from the succesor to the matching node and delete the successor.
  325.             // If a node doesn't have a successor, we can replace it with its left child (if not empty.)
  326.             // or delete the matching node.
  327.             //
  328.             // In top-down implementation, it is important to make sure the node to be deleted is not a 2-node.
  329.             // Following code will make sure the node on the path is not a 2 Node.
  330.             //
  331.             Node current = root;
  332.             Node parent = null;
  333.             Node grandParent = null;
  334.             Node match = null;
  335.             Node parentOfMatch = null;
  336.             bool foundMatch = false;
  337.             while (current != null) {
  338.                 if (Is2Node(current)) {
  339.                     // fix up 2-Node
  340.                     if (parent == null) {
  341.                         // current is root. Mark it as red
  342.                         current.IsRed = true;
  343.                     }
  344.                     else {
  345.                         Node sibling = GetSibling(current, parent);
  346.                         if (sibling.IsRed) {
  347.                             // If parent is a 3-node, flip the orientation of the red link.
  348.                             // We can acheive this by a single rotation
  349.                             // This case is converted to one of other cased below.
  350.                             Debug.Assert(!parent.IsRed, "parent must be a black node!");
  351.                             if (parent.Right == sibling) {
  352.                                 RotateLeft(parent);
  353.                             }
  354.                             else {
  355.                                 RotateRight(parent);
  356.                             }
  357.                            
  358.                             parent.IsRed = true;
  359.                             sibling.IsRed = false;
  360.                             // parent's color
  361.                             // sibling becomes child of grandParent or root after rotation. Update link from grandParent or root
  362.                             ReplaceChildOfNodeOrRoot(grandParent, parent, sibling);
  363.                             // sibling will become grandParent of current node
  364.                             grandParent = sibling;
  365.                             if (parent == match) {
  366.                                 parentOfMatch = sibling;
  367.                             }
  368.                            
  369.                             // update sibling, this is necessary for following processing
  370.                             sibling = (parent.Left == current) ? parent.Right : parent.Left;
  371.                         }
  372.                         Debug.Assert(sibling != null || sibling.IsRed == false, "sibling must not be null and it must be black!");
  373.                        
  374.                         if (Is2Node(sibling)) {
  375.                             Merge2Nodes(parent, current, sibling);
  376.                         }
  377.                         else {
  378.                             // current is a 2-node and sibling is either a 3-node or a 4-node.
  379.                             // We can change the color of current to red by some rotation.
  380.                             TreeRotation rotation = RotationNeeded(parent, current, sibling);
  381.                             Node newGrandParent = null;
  382.                             switch (rotation) {
  383.                                 case TreeRotation.RightRotation:
  384.                                     Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
  385.                                     Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
  386.                                     sibling.Left.IsRed = false;
  387.                                     newGrandParent = RotateRight(parent);
  388.                                     break;
  389.                                 case TreeRotation.LeftRotation:
  390.                                     Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
  391.                                     Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
  392.                                     sibling.Right.IsRed = false;
  393.                                     newGrandParent = RotateLeft(parent);
  394.                                     break;
  395.                                 case TreeRotation.RightLeftRotation:
  396.                                    
  397.                                     Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
  398.                                     Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
  399.                                     newGrandParent = RotateRightLeft(parent);
  400.                                     break;
  401.                                 case TreeRotation.LeftRightRotation:
  402.                                    
  403.                                     Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
  404.                                     Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
  405.                                     newGrandParent = RotateLeftRight(parent);
  406.                                     break;
  407.                             }
  408.                            
  409.                             newGrandParent.IsRed = parent.IsRed;
  410.                             parent.IsRed = false;
  411.                             current.IsRed = true;
  412.                             ReplaceChildOfNodeOrRoot(grandParent, parent, newGrandParent);
  413.                             if (parent == match) {
  414.                                 parentOfMatch = newGrandParent;
  415.                             }
  416.                             grandParent = newGrandParent;
  417.                         }
  418.                     }
  419.                 }
  420.                
  421.                 // we don't need to compare any more once we found the match
  422.                 int order = foundMatch ? -1 : comparer.Compare(item, current.Item);
  423.                 if (order == 0) {
  424.                     // save the matching node
  425.                     foundMatch = true;
  426.                     match = current;
  427.                     parentOfMatch = parent;
  428.                 }
  429.                
  430.                 grandParent = parent;
  431.                 parent = current;
  432.                
  433.                 if (order < 0) {
  434.                     current = current.Left;
  435.                 }
  436.                 else {
  437.                     current = current.Right;
  438.                     // continue the search in right sub tree after we find a match
  439.                 }
  440.             }
  441.            
  442.             // move successor to the matching node position and replace links
  443.             if (match != null) {
  444.                 ReplaceNode(match, parentOfMatch, parent, grandParent);
  445.                 --count;
  446.             }
  447.            
  448.             if (root != null) {
  449.                 root.IsRed = false;
  450.             }
  451.             ++version;
  452.             return foundMatch;
  453.         }
  454.        
  455.         // LinkDemand here is unnecessary as this is a methodimpl and linkdemand from the interface should suffice
  456.         void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
  457.         {
  458.             GetObjectData(info, context);
  459.         }
  460.        
  461.         protected void GetObjectData(SerializationInfo info, StreamingContext context)
  462.         {
  463.             if (info == null) {
  464.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
  465.             }
  466.            
  467.             info.AddValue(CountName, count);
  468.             //This is the length of the bucket array.
  469.             info.AddValue(ComparerName, comparer, typeof(IComparer<T>));
  470.             info.AddValue(VersionName, version);
  471.            
  472.             if (root != null) {
  473.                 T[] items = new T[Count];
  474.                 CopyTo(items, 0);
  475.                 info.AddValue(ItemsName, items, typeof(T[]));
  476.             }
  477.         }
  478.        
  479.         void IDeserializationCallback.OnDeserialization(object sender)
  480.         {
  481.             OnDeserialization(sender);
  482.         }
  483.        
  484.         protected void OnDeserialization(object sender)
  485.         {
  486.             if (comparer != null) {
  487.                 return;
  488.                 //Somebody had a dependency on this class and fixed us up before the ObjectManager got to it.
  489.             }
  490.            
  491.             if (siInfo == null) {
  492.                 ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_InvalidOnDeser);
  493.             }
  494.            
  495.             comparer = (IComparer<T>)siInfo.GetValue(ComparerName, typeof(IComparer<T>));
  496.             int savedCount = siInfo.GetInt32(CountName);
  497.            
  498.             if (savedCount != 0) {
  499.                 T[] items = (T[])siInfo.GetValue(ItemsName, typeof(T[]));
  500.                
  501.                 if (items == null) {
  502.                     ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingValues);
  503.                 }
  504.                
  505.                 for (int i = 0; i < items.Length; i++) {
  506.                     Add(items[i]);
  507.                 }
  508.             }
  509.            
  510.             version = siInfo.GetInt32(VersionName);
  511.             if (count != savedCount) {
  512.                 ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MismatchedCount);
  513.             }
  514.             siInfo = null;
  515.         }
  516.        
  517.         private static Node GetSibling(Node node, Node parent)
  518.         {
  519.             if (parent.Left == node) {
  520.                 return parent.Right;
  521.             }
  522.             return parent.Left;
  523.         }
  524.        
  525.         // After calling InsertionBalance, we need to make sure current and parent up-to-date.
  526.         // It doesn't matter if we keep grandParent and greatGrantParent up-to-date
  527.         // because we won't need to split again in the next node.
  528.         // By the time we need to split again, everything will be correctly set.
  529.         //
  530.         private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent)
  531.         {
  532.             Debug.Assert(grandParent != null, "Grand parent cannot be null here!");
  533.             bool parentIsOnRight = (grandParent.Right == parent);
  534.             bool currentIsOnRight = (parent.Right == current);
  535.            
  536.             Node newChildOfGreatGrandParent;
  537.             if (parentIsOnRight == currentIsOnRight) {
  538.                 // same orientation, single rotation
  539.                 newChildOfGreatGrandParent = currentIsOnRight ? RotateLeft(grandParent) : RotateRight(grandParent);
  540.             }
  541.             else {
  542.                 // different orientaton, double rotation
  543.                 newChildOfGreatGrandParent = currentIsOnRight ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
  544.                 // current node now becomes the child of greatgrandparent
  545.                 parent = greatGrandParent;
  546.             }
  547.             // grand parent will become a child of either parent of current.
  548.             grandParent.IsRed = true;
  549.             newChildOfGreatGrandParent.IsRed = false;
  550.            
  551.             ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, newChildOfGreatGrandParent);
  552.         }
  553.        
  554.         private static bool Is2Node(Node node)
  555.         {
  556.             Debug.Assert(node != null, "node cannot be null!");
  557.             return IsBlack(node) && IsNullOrBlack(node.Left) && IsNullOrBlack(node.Right);
  558.         }
  559.        
  560.         private static bool Is4Node(Node node)
  561.         {
  562.             return IsRed(node.Left) && IsRed(node.Right);
  563.         }
  564.        
  565.         private static bool IsBlack(Node node)
  566.         {
  567.             return (node != null && !node.IsRed);
  568.         }
  569.        
  570.         private static bool IsNullOrBlack(Node node)
  571.         {
  572.             return (node == null || !node.IsRed);
  573.         }
  574.        
  575.         private static bool IsRed(Node node)
  576.         {
  577.             return (node != null && node.IsRed);
  578.         }
  579.        
  580.         private static void Merge2Nodes(Node parent, Node child1, Node child2)
  581.         {
  582.             Debug.Assert(IsRed(parent), "parent must be be red");
  583.             // combing two 2-nodes into a 4-node
  584.             parent.IsRed = false;
  585.             child1.IsRed = true;
  586.             child2.IsRed = true;
  587.         }
  588.        
  589.         // Replace the child of a parent node.
  590.         // If the parent node is null, replace the root.
  591.         private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild)
  592.         {
  593.             if (parent != null) {
  594.                 if (parent.Left == child) {
  595.                     parent.Left = newChild;
  596.                 }
  597.                 else {
  598.                     parent.Right = newChild;
  599.                 }
  600.             }
  601.             else {
  602.                 root = newChild;
  603.             }
  604.         }
  605.        
  606.         // Replace the matching node with its succesor.
  607.         private void ReplaceNode(Node match, Node parentOfMatch, Node succesor, Node parentOfSuccesor)
  608.         {
  609.             if (succesor == match) {
  610.                 // this node has no successor, should only happen if right child of matching node is null.
  611.                 Debug.Assert(match.Right == null, "Right child must be null!");
  612.                 succesor = match.Left;
  613.             }
  614.             else {
  615.                 Debug.Assert(parentOfSuccesor != null, "parent of successor cannot be null!");
  616.                 Debug.Assert(succesor.Left == null, "Left child of succesor must be null!");
  617.                 Debug.Assert((succesor.Right == null && succesor.IsRed) || (succesor.Right.IsRed && !succesor.IsRed), "Succesor must be in valid state");
  618.                 if (succesor.Right != null) {
  619.                     succesor.Right.IsRed = false;
  620.                 }
  621.                
  622.                 if (parentOfSuccesor != match) {
  623.                     // detach succesor from its parent and set its right child
  624.                     parentOfSuccesor.Left = succesor.Right;
  625.                     succesor.Right = match.Right;
  626.                 }
  627.                
  628.                 succesor.Left = match.Left;
  629.             }
  630.            
  631.             if (succesor != null) {
  632.                 succesor.IsRed = match.IsRed;
  633.             }
  634.            
  635.             ReplaceChildOfNodeOrRoot(parentOfMatch, match, succesor);
  636.         }
  637.        
  638.         internal void UpdateVersion()
  639.         {
  640.             ++version;
  641.         }
  642.        
  643.         private static Node RotateLeft(Node node)
  644.         {
  645.             Node x = node.Right;
  646.             node.Right = x.Left;
  647.             x.Left = node;
  648.             return x;
  649.         }
  650.        
  651.         private static Node RotateLeftRight(Node node)
  652.         {
  653.             Node child = node.Left;
  654.             Node grandChild = child.Right;
  655.            
  656.             node.Left = grandChild.Right;
  657.             grandChild.Right = node;
  658.             child.Right = grandChild.Left;
  659.             grandChild.Left = child;
  660.             return grandChild;
  661.         }
  662.        
  663.         private static Node RotateRight(Node node)
  664.         {
  665.             Node x = node.Left;
  666.             node.Left = x.Right;
  667.             x.Right = node;
  668.             return x;
  669.         }
  670.        
  671.         private static Node RotateRightLeft(Node node)
  672.         {
  673.             Node child = node.Right;
  674.             Node grandChild = child.Left;
  675.            
  676.             node.Right = grandChild.Left;
  677.             grandChild.Left = node;
  678.             child.Left = grandChild.Right;
  679.             grandChild.Right = child;
  680.             return grandChild;
  681.         }
  682.        
  683.         private static TreeRotation RotationNeeded(Node parent, Node current, Node sibling)
  684.         {
  685.             Debug.Assert(IsRed(sibling.Left) || IsRed(sibling.Right), "sibling must have at least one red child");
  686.             if (IsRed(sibling.Left)) {
  687.                 if (parent.Left == current) {
  688.                     return TreeRotation.RightLeftRotation;
  689.                 }
  690.                 return TreeRotation.RightRotation;
  691.             }
  692.             else {
  693.                 if (parent.Left == current) {
  694.                     return TreeRotation.LeftRotation;
  695.                 }
  696.                 return TreeRotation.LeftRightRotation;
  697.             }
  698.         }
  699.        
  700.         private static void Split4Node(Node node)
  701.         {
  702.             node.IsRed = true;
  703.             node.Left.IsRed = false;
  704.             node.Right.IsRed = false;
  705.         }
  706.        
  707.         internal class Node
  708.         {
  709.             bool isRed;
  710.             T item;
  711.             Node left;
  712.             Node right;
  713.            
  714.             public Node(T item)
  715.             {
  716.                 // The default color will be red, we never need to create a black node directly.
  717.                 this.item = item;
  718.                 isRed = true;
  719.             }
  720.            
  721.             public Node(T item, bool isRed)
  722.             {
  723.                 // The default color will be red, we never need to create a black node directly.
  724.                 this.item = item;
  725.                 this.isRed = isRed;
  726.             }
  727.            
  728.             public T Item {
  729.                 get { return item; }
  730.                 set { item = value; }
  731.             }
  732.            
  733.             public Node Left {
  734.                 get { return left; }
  735.                 set { left = value; }
  736.             }
  737.            
  738.             public Node Right {
  739.                 get { return right; }
  740.                 set { right = value; }
  741.             }
  742.            
  743.             public bool IsRed {
  744.                 get { return isRed; }
  745.                 set { isRed = value; }
  746.             }
  747.         }
  748.        
  749.         public struct Enumerator : IEnumerator<T>, IEnumerator
  750.         {
  751.             private TreeSet<T> tree;
  752.             private int version;
  753.             private Stack<TreeSet<T>.Node> stack;
  754.             private TreeSet<T>.Node current;
  755.             static TreeSet<T>.Node dummyNode = new TreeSet<T>.Node(default(T));
  756.            
  757.             private const string TreeName = "Tree";
  758.             private const string NodeValueName = "Item";
  759.             private const string EnumStartName = "EnumStarted";
  760.             private const string VersionName = "Version";
  761.            
  762.            
  763.             internal Enumerator(TreeSet<T> set)
  764.             {
  765.                 tree = set;
  766.                 version = tree.version;
  767.                
  768.                 // 2lg(n + 1) is the maximum height
  769.                 stack = new Stack<TreeSet<T>.Node>(2 * (int)Math.Log(set.Count + 1));
  770.                 current = null;
  771.                 Intialize();
  772.             }
  773.            
  774.             private void Intialize()
  775.             {
  776.                 current = null;
  777.                 TreeSet<T>.Node node = tree.root;
  778.                 while (node != null) {
  779.                     stack.Push(node);
  780.                     node = node.Left;
  781.                 }
  782.             }
  783.            
  784.             public bool MoveNext()
  785.             {
  786.                 if (version != tree.version) {
  787.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  788.                 }
  789.                
  790.                 if (stack.Count == 0) {
  791.                     current = null;
  792.                     return false;
  793.                 }
  794.                
  795.                 current = stack.Pop();
  796.                 TreeSet<T>.Node node = current.Right;
  797.                 while (node != null) {
  798.                     stack.Push(node);
  799.                     node = node.Left;
  800.                 }
  801.                 return true;
  802.             }
  803.            
  804.             public void Dispose()
  805.             {
  806.             }
  807.            
  808.             public T Current {
  809.                 get {
  810.                     if (current != null) {
  811.                         return current.Item;
  812.                     }
  813.                     return default(T);
  814.                 }
  815.             }
  816.            
  817.             object IEnumerator.Current {
  818.                 get {
  819.                     if (current == null) {
  820.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
  821.                     }
  822.                    
  823.                     return current.Item;
  824.                 }
  825.             }
  826.            
  827.             internal bool NotStartedOrEnded {
  828.                 get { return current == null; }
  829.             }
  830.            
  831.             internal void Reset()
  832.             {
  833.                 if (version != tree.version) {
  834.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  835.                 }
  836.                
  837.                 stack.Clear();
  838.                 Intialize();
  839.             }
  840.            
  841.             void IEnumerator.Reset()
  842.             {
  843.                 Reset();
  844.             }
  845.         }
  846.     }
  847. }

Developer Fusion