Code:
/ DotNET / DotNET / 8.0 / untmp / WIN_WINDOWS / lh_tools_devdiv_wpf / Windows / wcp / Speech / Src / Internal / RedBlackList.cs / 1 / RedBlackList.cs
//------------------------------------------------------------------ //// Copyright (c) Microsoft Corporation. All rights reserved. // //----------------------------------------------------------------- using System; using System.Collections.Generic; using System.Text; using System.Collections; using System.Diagnostics; namespace System.Speech.Internal { ////// Sorted List using the Red-Black algorithm /// internal abstract class RedBackList : IEnumerable { //******************************************************************* // // Constructors // //******************************************************************* #region Constructors internal RedBackList () { } #endregion //******************************************************************** // // Internal Methods // //******************************************************************* #region Internal Methods internal void Add (object key) { #if DEBUG if (_root != null && _root._inEnumaration) { throw new InvalidOperationException (); } #endif TreeNode node = new TreeNode (key); node.IsRed = true; InsertNode (_root, node); FixUpInsertion (node); _root = FindRoot (node); } internal void Remove (object key) { #if DEBUG if (_root != null && _root._inEnumaration) { throw new InvalidOperationException (); } #endif TreeNode node = FindItem (_root, key); if (node == null) { throw new KeyNotFoundException (); } TreeNode nodeRemoved = DeleteNode (node); FixUpRemoval (nodeRemoved); if (nodeRemoved == _root) { if (_root.Left != null) { _root = FindRoot (_root.Left); } else if (_root.Right != null) { _root = FindRoot (_root.Right); } else { _root = null; } } else { _root = FindRoot (_root); } } public IEnumerator GetEnumerator () { return new MyEnumerator (_root); } #endregion //******************************************************************** // // Internal Properties // //******************************************************************** #region Internal Properties internal bool IsEmpty { get { return _root == null; } } internal bool CountIsOne { get { return _root != null && _root.Left == null && _root.Right == null; } } internal bool ContainsMoreThanOneItem { get { return _root != null && (_root.Right != null || _root.Left != null); } } internal object First { get { if (_root == null) { // We don't expect First to be called on empty graphs System.Diagnostics.Debug.Assert (false); return null; } // Set the current pointer to the last element return FindMinSubTree (_root).Key; } } #endregion //******************************************************************* // // Protected Methods // //******************************************************************** #region Protected Methods abstract protected int CompareTo (object object1, object object2); #endregion //******************************************************************* // // Private Methods // //******************************************************************* #region Private Methods #region Implement utility operations on Tree static private TreeNode GetUncle (TreeNode node) { if (node.Parent == node.Parent.Parent.Left) { return node.Parent.Parent.Right; } else { return node.Parent.Parent.Left; } } static private TreeNode GetSibling (TreeNode node, TreeNode parent) { if (node == parent.Left) { return parent.Right; } else { return parent.Left; } } static private NodeColor GetColor (TreeNode node) { return node == null ? NodeColor.BLACK : (node.IsRed ? NodeColor.RED : NodeColor.BLACK); } static private void SetColor (TreeNode node, NodeColor color) { if (node != null) { node.IsRed = (color == NodeColor.RED); } else { Debug.Assert (color == NodeColor.BLACK); } } static private void TakeParent (TreeNode node, TreeNode newNode) { if (node.Parent == null) { if (newNode != null) { newNode.Parent = null; } } else if (node.Parent.Left == node) { node.Parent.Left = newNode; } else if (node.Parent.Right == node) { node.Parent.Right = newNode; } else { throw new InvalidOperationException (); } } static private TreeNode RotateLeft (TreeNode node) { TreeNode newNode = node.Right; node.Right = newNode.Left; TakeParent (node, newNode); newNode.Left = node; return newNode; } static private TreeNode RotateRight (TreeNode node) { TreeNode newNode = node.Left; node.Left = newNode.Right; TakeParent (node, newNode); newNode.Right = node; return newNode; } static private TreeNode FindMinSubTree (TreeNode node) { while (node.Left != null) { node = node.Left; } return node; } static private TreeNode FindSuccessor (TreeNode node) { if (node.Right == null) { while (node.Parent != null && node.Parent.Left != node) { node = node.Parent; } return node.Parent == null ? null : node.Parent; } else { return FindMinSubTree (node.Right); } } // Return the actual node that is deleted static private TreeNode DeleteNode (TreeNode node) { if (node.Right == null) { TakeParent (node, node.Left); return node; } else if (node.Left == null) { TakeParent (node, node.Right); return node; } else { TreeNode successor = FindSuccessor (node); Debug.Assert (successor != null && successor.Left == null); node.CopyNode (successor); TakeParent (successor, successor.Right); return successor; } } #endregion Implement utility operations on Tree // Return the root of the new subtree private TreeNode InsertNode (TreeNode node, TreeNode newNode) { if (node == null) { return newNode; } int diff = CompareTo (newNode.Key, node.Key); if (diff < 0) { node.Left = InsertNode (node.Left, newNode); } else { node.Right = InsertNode (node.Right, newNode); } return node; } private TreeNode FindItem (TreeNode node, object key) { if (node == null) { return null; } int diff = CompareTo (key, node.Key); if (diff == 0) { return node; } else if (diff < 0) { return FindItem (node.Left, key); } else { return FindItem (node.Right, key); } } private TreeNode FindRoot (TreeNode node) { while (node.Parent != null) { node = node.Parent; } return node; } private void FixUpInsertion (TreeNode node) { FixInsertCase1 (node); } private void FixInsertCase1 (TreeNode node) { Debug.Assert (node.IsRed); if (node.Parent == null) { node.IsRed = false; } else { FixInsertCase2 (node); } } private void FixInsertCase2 (TreeNode node) { if (GetColor (node.Parent) == NodeColor.BLACK) { return; // Tree is still valid. } // Now, its parent is RED, so it must have an uncle since its parent is not root. // Also, its grandparent must be BLACK. Debug.Assert (GetColor (node.Parent.Parent) == NodeColor.BLACK); TreeNode uncle = GetUncle (node); if (GetColor (uncle) == NodeColor.RED) { SetColor (node.Parent, NodeColor.BLACK); SetColor (uncle, NodeColor.BLACK); SetColor (node.Parent.Parent, NodeColor.RED); FixInsertCase1 (node.Parent.Parent); // Move recursively up } else { FixInsertCase3 (node); } } private void FixInsertCase3 (TreeNode node) { // // Now it's RED, parent is RED, uncle is BLACK, // We want to rotate so that its uncle is on the opposite side if (node == node.Parent.Right && node.Parent == node.Parent.Parent.Left) { RotateLeft (node.Parent); node = node.Left; } else if (node == node.Parent.Left && node.Parent == node.Parent.Parent.Right) { RotateRight (node.Parent); node = node.Right; } FixInsertCase4 (node); } private void FixInsertCase4 (TreeNode node) { // // Must follow case 3, here we are finally done! // SetColor (node.Parent, NodeColor.BLACK); SetColor (node.Parent.Parent, NodeColor.RED); if (node == node.Parent.Left) { Debug.Assert (node.Parent == node.Parent.Parent.Left); // From case 3 RotateRight (node.Parent.Parent); } else { Debug.Assert (node.Parent == node.Parent.Parent.Right); // From case 3 RotateLeft (node.Parent.Parent); } } private static void FixUpRemoval (TreeNode node) { // This node must have at most 1 child Debug.Assert (node.Left == null || node.Right == null); TreeNode onlyChild = node.Left == null ? node.Right : node.Left; // This node should have been deleted already, and the child has replaced the this node. Debug.Assert (node.Parent == null || node.Parent.Left == onlyChild || node.Parent.Right == onlyChild); Debug.Assert (onlyChild == null || onlyChild.Parent == node.Parent); // // If the node removed was red, all properties still hold. // Otherwise, we need fix up. // if (GetColor (node) == NodeColor.BLACK) { if (GetColor (onlyChild) == NodeColor.RED) { SetColor (onlyChild, NodeColor.BLACK); } else if (node.Parent == null) // if we remove a root node, nothing has changed. { return; } else { // // Note that onlyChild could be null. // The deleted node and its only child are BLACK, and there is a real parent, therefore, // the total black height was at least 2 (excluding the real parent), thus the sibling subtree also has a black height of at least 2 // FixRemovalCase2 (GetSibling (onlyChild, node.Parent)); } } } private static void FixRemovalCase1 (TreeNode node) { Debug.Assert (GetColor (node) == NodeColor.BLACK); if (node.Parent == null) { return; } else { FixRemovalCase2 (GetSibling (node, node.Parent)); } } private static void FixRemovalCase2 (TreeNode sibling) { Debug.Assert (sibling != null); if (GetColor (sibling) == NodeColor.RED) { Debug.Assert (sibling.Left != null && sibling.Right != null); TreeNode parent = sibling.Parent; // the parent must be black SetColor (parent, NodeColor.RED); SetColor (sibling, NodeColor.BLACK); if (sibling == parent.Right) { RotateLeft (sibling.Parent); // new sibling was the old sibling left child, and must be non-leaf black sibling = parent.Right; } else { RotateRight (sibling.Parent); // new sibling was the old sibling right child, and must be non-leaf black sibling = parent.Left; } } // Now the sibling will be a BLACK non-leaf. FixRemovalCase3 (sibling); } private static void FixRemovalCase3 (TreeNode sibling) { if (GetColor (sibling.Parent) == NodeColor.BLACK && GetColor (sibling) == NodeColor.BLACK && GetColor (sibling.Left) == NodeColor.BLACK && GetColor (sibling.Right) == NodeColor.BLACK) { SetColor (sibling, NodeColor.RED); FixRemovalCase1 (sibling.Parent); } else { FixRemovalCase4 (sibling); } } private static void FixRemovalCase4 (TreeNode sibling) { if (GetColor (sibling.Parent) == NodeColor.RED && GetColor (sibling) == NodeColor.BLACK && GetColor (sibling.Left) == NodeColor.BLACK && GetColor (sibling.Right) == NodeColor.BLACK) { SetColor (sibling, NodeColor.RED); SetColor (sibling.Parent, NodeColor.BLACK); } else { FixRemovalCase5 (sibling); } } private static void FixRemovalCase5 (TreeNode sibling) { if (sibling == sibling.Parent.Right && GetColor (sibling) == NodeColor.BLACK && GetColor (sibling.Left) == NodeColor.RED && GetColor (sibling.Right) == NodeColor.BLACK) { SetColor (sibling, NodeColor.RED); SetColor (sibling.Left, NodeColor.BLACK); RotateRight (sibling); sibling = sibling.Parent; } else if (sibling == sibling.Parent.Left && GetColor (sibling) == NodeColor.BLACK && GetColor (sibling.Right) == NodeColor.RED && GetColor (sibling.Left) == NodeColor.BLACK) { SetColor (sibling, NodeColor.RED); SetColor (sibling.Right, NodeColor.BLACK); RotateLeft (sibling); sibling = sibling.Parent; } FixRemovalCase6 (sibling); } private static void FixRemovalCase6 (TreeNode sibling) { Debug.Assert (GetColor (sibling) == NodeColor.BLACK); SetColor (sibling, GetColor (sibling.Parent)); SetColor (sibling.Parent, NodeColor.BLACK); if (sibling == sibling.Parent.Right) { Debug.Assert (GetColor (sibling.Right) == NodeColor.RED); SetColor (sibling.Right, NodeColor.BLACK); RotateLeft (sibling.Parent); } else { Debug.Assert (GetColor (sibling.Left) == NodeColor.RED); SetColor (sibling.Left, NodeColor.BLACK); RotateRight (sibling.Parent); } } #if VSCOMPILE && DEBUG private void ValidateBinaryTree (TreeNode node, out object minValue, out object maxValue) { if (node == null) { minValue = maxValue = null; return; } object maxRight, minRight, maxLeft, minLeft; ValidateBinaryTree(node.Left, out minLeft, out maxLeft ); ValidateBinaryTree(node.Right, out minRight, out maxRight); object current = node.Key; if (maxLeft != null) { if (CompareTo (maxLeft, current) >= 0) { throw new InvalidOperationException(String.Format("Binary property violated on the left of {0}", node.ToString())); } } if (minRight != null) { if (CompareTo (minRight, current) < 0) { throw new InvalidOperationException(String.Format("Binary property violated on the right of {0}", node.ToString())); } } minValue = minLeft; maxValue = maxRight; } private int ValidateRedBlackNode(TreeNode node) { if (node == null) { return 1; } else { // Chilren of red node must be black if (GetColor(node) == NodeColor.RED) { if (GetColor(node.Left) == NodeColor.RED || GetColor(node.Right) == NodeColor.RED) { throw new InvalidOperationException(String.Format("Red node {0} has a red child\n", node.ToString())); } } // // Make sure black heights are equal // int leftCount = ValidateRedBlackNode(node.Left); int rightCount = ValidateRedBlackNode(node.Right); if (leftCount != rightCount) { throw new InvalidOperationException(String.Format("Black heights are different {0} != {1} at node {2}", leftCount, rightCount, node.ToString())); } return leftCount + (GetColor(node) == NodeColor.BLACK ? 1 : 0); } } internal void ValidateRedBlackTree() { if (GetColor(_root) != NodeColor.BLACK) { throw new InvalidOperationException("Root node is RED"); } object minValue, maxValue; ValidateBinaryTree(_root, out minValue, out maxValue); ValidateRedBlackNode(_root); } internal string ShowTree() { Liststrings = new List (); ShowTree(_root, strings, 0, 0); StringBuilder sb = new StringBuilder(); foreach (string s in strings) { sb.Append("\r\n"); sb.Append(s); } return sb.ToString(); } private int ShowTree(TreeNode node, List lines, int depth, int leftLength) { if (lines.Count <= depth) { lines.Add(""); } if (node != null) { int maxLength = ShowTree(node.Left, lines, depth + 1, leftLength); String current = node.ToString(); StringBuilder builder = new StringBuilder(lines[depth]); while (builder.Length < maxLength - current.Length / 2) { builder.Append(' '); } builder.Append(current); lines[depth] = builder.ToString(); maxLength = ShowTree(node.Right, lines, depth + 1, maxLength + 1); if (lines[depth].Length < maxLength) { lines[depth] += new String(' ', maxLength - lines[depth].Length); } return lines[depth].Length; } else { if (lines[depth].Length < leftLength) { lines[depth] += new String(' ', leftLength - lines[depth].Length); } return lines[depth].Length; } } #endif #endregion //******************************************************************* // // Private Fields // //******************************************************************** #region Private Fields private TreeNode _root; #endregion //******************************************************************* // // Private Types // //******************************************************************** #region Private Types private class MyEnumerator : IEnumerator { internal MyEnumerator (TreeNode node) { _root = node; } public object Current { get { if (_node == null) { throw new InvalidOperationException (); } return _node.Key; } } public bool MoveNext () { if (!_moved) { _node = _root != null ? FindMinSubTree (_root) : null; _moved = true; #if DEBUG if (_root != null) { _root._inEnumaration = true; } #endif } else { _node = _node != null ? FindSuccessor (_node) : null; } #if DEBUG if (_root != null) { _root._inEnumaration = _node != null; } #endif return _node != null; } public void Reset () { _moved = false; _node = null; } private TreeNode _node; private TreeNode _root; private bool _moved; } #if DEBUG [DebuggerDisplay ("{((System.Speech.Internal.SrgsCompiler.Arc)Key).ToString ()}")] #endif private class TreeNode { internal TreeNode (object key) { this._key = key; } internal TreeNode Left { get { return _leftChild; } set { _leftChild = value; if (_leftChild != null) { _leftChild._parent = this; } } } internal TreeNode Right { get { return _rightChild; } set { _rightChild = value; if (_rightChild != null) { _rightChild._parent = this; } } } internal TreeNode Parent { get { return _parent; } set { _parent = value; } } internal bool IsRed { get { return _isRed; } set { _isRed = value; } } internal object Key { get { return _key; } } internal void CopyNode (TreeNode from) { _key = from._key; } #if DEBUG internal bool _inEnumaration; #endif private object _key; private bool _isRed; private TreeNode _leftChild, _rightChild, _parent; } private enum NodeColor { BLACK = 0, RED = 1 } #endregion } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- StrokeCollectionConverter.cs
- QilStrConcat.cs
- ADRoleFactory.cs
- Encoder.cs
- cookiecollection.cs
- DbException.cs
- BrowserCapabilitiesCompiler.cs
- ApplicationDirectory.cs
- DataRecordInternal.cs
- CompilationSection.cs
- TableLayoutSettingsTypeConverter.cs
- ToolboxService.cs
- RequestQueue.cs
- ComponentManagerBroker.cs
- BindingGroup.cs
- HttpModulesSection.cs
- Pts.cs
- LocatorPart.cs
- ElementNotEnabledException.cs
- PropertyInfo.cs
- StrokeNode.cs
- ObjectFullSpanRewriter.cs
- ProfileManager.cs
- WorkItem.cs
- SynchronizationLockException.cs
- CodeTypeParameter.cs
- SqlConnectionFactory.cs
- OdbcConnectionPoolProviderInfo.cs
- TransportContext.cs
- QualifiedCellIdBoolean.cs
- SettingsProperty.cs
- TemplateEditingService.cs
- X509Certificate2Collection.cs
- TableStyle.cs
- TraversalRequest.cs
- XamlStackWriter.cs
- PriorityQueue.cs
- BmpBitmapEncoder.cs
- VisualProxy.cs
- DataViewListener.cs
- XmlDictionaryWriter.cs
- Themes.cs
- TreeNode.cs
- OleDbWrapper.cs
- CompareInfo.cs
- XmlSchemaExporter.cs
- RegionIterator.cs
- UIInitializationException.cs
- FileUpload.cs
- BaseTemplateCodeDomTreeGenerator.cs
- ToolStripLabel.cs
- ProtocolElementCollection.cs
- Random.cs
- NullRuntimeConfig.cs
- XmlSchemaComplexType.cs
- PrivateFontCollection.cs
- EFTableProvider.cs
- SmtpClient.cs
- XamlReader.cs
- EnvelopedSignatureTransform.cs
- XamlFigureLengthSerializer.cs
- XmlDocumentFragment.cs
- CommentEmitter.cs
- ConfigurationSectionGroup.cs
- ImageList.cs
- X509ClientCertificateAuthenticationElement.cs
- SimpleApplicationHost.cs
- ValidationPropertyAttribute.cs
- basenumberconverter.cs
- AppDomainFactory.cs
- SessionStateItemCollection.cs
- MetadataArtifactLoaderCompositeResource.cs
- ErrorRuntimeConfig.cs
- HyperLinkStyle.cs
- AuditLog.cs
- QueueAccessMode.cs
- TextElement.cs
- UnaryNode.cs
- ComplexBindingPropertiesAttribute.cs
- BinaryParser.cs
- FixedTextSelectionProcessor.cs
- SmiConnection.cs
- IPEndPointCollection.cs
- fixedPageContentExtractor.cs
- FileLevelControlBuilderAttribute.cs
- InvariantComparer.cs
- ObjRef.cs
- ColorAnimationUsingKeyFrames.cs
- QueueProcessor.cs
- Parameter.cs
- ResourceManagerWrapper.cs
- SmtpSection.cs
- Symbol.cs
- PageAction.cs
- AtomEntry.cs
- SelectiveScrollingGrid.cs
- DesignerVerbCollection.cs
- StylusShape.cs
- WindowsAltTab.cs
- ValidationErrorCollection.cs