Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / wpf / src / Shared / MS / Internal / PriorityQueue.cs / 1 / PriorityQueue.cs
//------------------------------------------------------------------------ // // Microsoft Windows Client Platform // Copyright (C) Microsoft Corporation. All rights reserved. // // File: PriorityQueue.cs // // Contents: Implementation of PriorityQueue class. // // Created: 2-14-2005 Niklas Borson (niklasb) // //----------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections.Generic; namespace MS.Internal { ////// PriorityQueue provides a stack-like interface, except that objects /// "pushed" in arbitrary order are "popped" in order of priority, i.e., /// from least to greatest as defined by the specified comparer. /// ////// Push and Pop are each O(log N). Pushing N objects and them popping /// them all is equivalent to performing a heap sort and is O(N log N). /// internal class PriorityQueue{ // // The _heap array represents a binary tree with the "shape" property. // If we number the nodes of a binary tree from left-to-right and top- // to-bottom as shown, // // 0 // / \ // / \ // 1 2 // / \ / \ // 3 4 5 6 // /\ / // 7 8 9 // // The shape property means that there are no gaps in the sequence of // numbered nodes, i.e., for all N > 0, if node N exists then node N-1 // also exists. For example, the next node added to the above tree would // be node 10, the right child of node 4. // // Because of this constraint, we can easily represent the "tree" as an // array, where node number == array index, and parent/child relationships // can be calculated instead of maintained explicitly. For example, for // any node N > 0, the parent of N is at array index (N - 1) / 2. // // In addition to the above, the first _count members of the _heap array // compose a "heap", meaning each child node is greater than or equal to // its parent node; thus, the root node is always the minimum (i.e., the // best match for the specified style, weight, and stretch) of the nodes // in the heap. // // Initially _count < 0, which means we have not yet constructed the heap. // On the first call to MoveNext, we construct the heap by "pushing" all // the nodes into it. Each successive call "pops" a node off the heap // until the heap is empty (_count == 0), at which time we've reached the // end of the sequence. // #region constructors internal PriorityQueue(int capacity, IComparer comparer) { _heap = new T[capacity > 0 ? capacity : DefaultCapacity]; _count = 0; _comparer = comparer; } #endregion #region internal members /// /// Gets the number of items in the priority queue. /// internal int Count { get { return _count; } } ////// Gets the first or topmost object in the priority queue, which is the /// object with the minimum value. /// internal T Top { get { Debug.Assert(_count > 0); return _heap[0]; } } ////// Adds an object to the priority queue. /// internal void Push(T value) { // Increase the size of the array if necessary. if (_count == _heap.Length) { T[] temp = new T[_count * 2]; for (int i = 0; i < _count; ++i) { temp[i] = _heap[i]; } _heap = temp; } // Loop invariant: // // 1. index is a gap where we might insert the new node; initially // it's the end of the array (bottom-right of the logical tree). // int index = _count; while (index > 0) { int parentIndex = HeapParent(index); if (_comparer.Compare(value, _heap[parentIndex]) < 0) { // value is a better match than the parent node so exchange // places to preserve the "heap" property. _heap[index] = _heap[parentIndex]; index = parentIndex; } else { // we can insert here. break; } } _heap[index] = value; _count++; } ////// Removes the first node (i.e., the logical root) from the heap. /// internal void Pop() { Debug.Assert(_count != 0); if (_count > 1) { // Loop invariants: // // 1. parent is the index of a gap in the logical tree // 2. leftChild is // (a) the index of parent's left child if it has one, or // (b) a value >= _count if parent is a leaf node // int parent = 0; int leftChild = HeapLeftChild(parent); while (leftChild < _count) { int rightChild = HeapRightFromLeft(leftChild); int bestChild = (rightChild < _count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0) ? rightChild : leftChild; // Promote bestChild to fill the gap left by parent. _heap[parent] = _heap[bestChild]; // Restore invariants, i.e., let parent point to the gap. parent = bestChild; leftChild = HeapLeftChild(parent); } // Fill the last gap by moving the last (i.e., bottom-rightmost) node. _heap[parent] = _heap[_count - 1]; } _count--; } #endregion #region private members ////// Calculate the parent node index given a child node's index, taking advantage /// of the "shape" property. /// private static int HeapParent(int i) { return (i - 1) / 2; } ////// Calculate the left child's index given the parent's index, taking advantage of /// the "shape" property. If there is no left child, the return value is >= _count. /// private static int HeapLeftChild(int i) { return (i * 2) + 1; } ////// Calculate the right child's index from the left child's index, taking advantage /// of the "shape" property (i.e., sibling nodes are always adjacent). If there is /// no right child, the return value >= _count. /// private static int HeapRightFromLeft(int i) { return i + 1; } private T[] _heap; private int _count; private IComparer_comparer; private const int DefaultCapacity = 6; #endregion } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved. //------------------------------------------------------------------------ // // Microsoft Windows Client Platform // Copyright (C) Microsoft Corporation. All rights reserved. // // File: PriorityQueue.cs // // Contents: Implementation of PriorityQueue class. // // Created: 2-14-2005 Niklas Borson (niklasb) // //----------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections.Generic; namespace MS.Internal { /// /// PriorityQueue provides a stack-like interface, except that objects /// "pushed" in arbitrary order are "popped" in order of priority, i.e., /// from least to greatest as defined by the specified comparer. /// ////// Push and Pop are each O(log N). Pushing N objects and them popping /// them all is equivalent to performing a heap sort and is O(N log N). /// internal class PriorityQueue{ // // The _heap array represents a binary tree with the "shape" property. // If we number the nodes of a binary tree from left-to-right and top- // to-bottom as shown, // // 0 // / \ // / \ // 1 2 // / \ / \ // 3 4 5 6 // /\ / // 7 8 9 // // The shape property means that there are no gaps in the sequence of // numbered nodes, i.e., for all N > 0, if node N exists then node N-1 // also exists. For example, the next node added to the above tree would // be node 10, the right child of node 4. // // Because of this constraint, we can easily represent the "tree" as an // array, where node number == array index, and parent/child relationships // can be calculated instead of maintained explicitly. For example, for // any node N > 0, the parent of N is at array index (N - 1) / 2. // // In addition to the above, the first _count members of the _heap array // compose a "heap", meaning each child node is greater than or equal to // its parent node; thus, the root node is always the minimum (i.e., the // best match for the specified style, weight, and stretch) of the nodes // in the heap. // // Initially _count < 0, which means we have not yet constructed the heap. // On the first call to MoveNext, we construct the heap by "pushing" all // the nodes into it. Each successive call "pops" a node off the heap // until the heap is empty (_count == 0), at which time we've reached the // end of the sequence. // #region constructors internal PriorityQueue(int capacity, IComparer comparer) { _heap = new T[capacity > 0 ? capacity : DefaultCapacity]; _count = 0; _comparer = comparer; } #endregion #region internal members /// /// Gets the number of items in the priority queue. /// internal int Count { get { return _count; } } ////// Gets the first or topmost object in the priority queue, which is the /// object with the minimum value. /// internal T Top { get { Debug.Assert(_count > 0); return _heap[0]; } } ////// Adds an object to the priority queue. /// internal void Push(T value) { // Increase the size of the array if necessary. if (_count == _heap.Length) { T[] temp = new T[_count * 2]; for (int i = 0; i < _count; ++i) { temp[i] = _heap[i]; } _heap = temp; } // Loop invariant: // // 1. index is a gap where we might insert the new node; initially // it's the end of the array (bottom-right of the logical tree). // int index = _count; while (index > 0) { int parentIndex = HeapParent(index); if (_comparer.Compare(value, _heap[parentIndex]) < 0) { // value is a better match than the parent node so exchange // places to preserve the "heap" property. _heap[index] = _heap[parentIndex]; index = parentIndex; } else { // we can insert here. break; } } _heap[index] = value; _count++; } ////// Removes the first node (i.e., the logical root) from the heap. /// internal void Pop() { Debug.Assert(_count != 0); if (_count > 1) { // Loop invariants: // // 1. parent is the index of a gap in the logical tree // 2. leftChild is // (a) the index of parent's left child if it has one, or // (b) a value >= _count if parent is a leaf node // int parent = 0; int leftChild = HeapLeftChild(parent); while (leftChild < _count) { int rightChild = HeapRightFromLeft(leftChild); int bestChild = (rightChild < _count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0) ? rightChild : leftChild; // Promote bestChild to fill the gap left by parent. _heap[parent] = _heap[bestChild]; // Restore invariants, i.e., let parent point to the gap. parent = bestChild; leftChild = HeapLeftChild(parent); } // Fill the last gap by moving the last (i.e., bottom-rightmost) node. _heap[parent] = _heap[_count - 1]; } _count--; } #endregion #region private members ////// Calculate the parent node index given a child node's index, taking advantage /// of the "shape" property. /// private static int HeapParent(int i) { return (i - 1) / 2; } ////// Calculate the left child's index given the parent's index, taking advantage of /// the "shape" property. If there is no left child, the return value is >= _count. /// private static int HeapLeftChild(int i) { return (i * 2) + 1; } ////// Calculate the right child's index from the left child's index, taking advantage /// of the "shape" property (i.e., sibling nodes are always adjacent). If there is /// no right child, the return value >= _count. /// private static int HeapRightFromLeft(int i) { return i + 1; } private T[] _heap; private int _count; private IComparer_comparer; private const int DefaultCapacity = 6; #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
- ListViewSelectEventArgs.cs
- XmlSchemaSet.cs
- BamlReader.cs
- ControlBuilderAttribute.cs
- SafeCryptoHandles.cs
- Collection.cs
- ToolStripArrowRenderEventArgs.cs
- Debug.cs
- ExpressionVisitorHelpers.cs
- HttpException.cs
- PowerModeChangedEventArgs.cs
- RoutingEndpointTrait.cs
- CodeDefaultValueExpression.cs
- AdRotator.cs
- NavigationProperty.cs
- ValidationEventArgs.cs
- LessThanOrEqual.cs
- diagnosticsswitches.cs
- PrinterSettings.cs
- SecurityManager.cs
- UnsafeNativeMethods.cs
- PolygonHotSpot.cs
- TextBoxBase.cs
- LabelDesigner.cs
- DateBoldEvent.cs
- GenericXmlSecurityToken.cs
- HtmlShimManager.cs
- Trace.cs
- StandardBindingOptionalReliableSessionElement.cs
- DoubleAverageAggregationOperator.cs
- RawAppCommandInputReport.cs
- MobileControlsSection.cs
- XPathDocumentBuilder.cs
- SerializationException.cs
- ValueConversionAttribute.cs
- SpecialFolderEnumConverter.cs
- XmlTypeAttribute.cs
- SamlAssertion.cs
- codemethodreferenceexpression.cs
- PageWrapper.cs
- Util.cs
- AnimationClock.cs
- WebPartHelpVerb.cs
- MD5.cs
- NonParentingControl.cs
- FileLoadException.cs
- Color.cs
- NGCSerializationManagerAsync.cs
- Errors.cs
- PrintPreviewControl.cs
- TextElementEnumerator.cs
- BmpBitmapDecoder.cs
- ArgumentNullException.cs
- ClientScriptManager.cs
- GuidelineCollection.cs
- DecimalConverter.cs
- CopyAction.cs
- StandardToolWindows.cs
- Number.cs
- HttpListenerRequestTraceRecord.cs
- DetailsViewDeleteEventArgs.cs
- HwndPanningFeedback.cs
- AccessViolationException.cs
- Polyline.cs
- MatrixTransform3D.cs
- DispatcherExceptionFilterEventArgs.cs
- SqlConnectionPoolGroupProviderInfo.cs
- SplineKeyFrames.cs
- InputLanguage.cs
- AuthenticationSection.cs
- Opcode.cs
- WebServiceHost.cs
- Line.cs
- SpeechAudioFormatInfo.cs
- XPathNodeIterator.cs
- PrintDialog.cs
- DotExpr.cs
- FixUp.cs
- ToolBarTray.cs
- ColorMap.cs
- CodeAccessPermission.cs
- DataServiceQueryContinuation.cs
- PolyBezierSegment.cs
- TrackingMemoryStreamFactory.cs
- HttpListener.cs
- SmtpNtlmAuthenticationModule.cs
- Vector3DAnimation.cs
- SqlGatherConsumedAliases.cs
- ReadOnlyState.cs
- UpdateException.cs
- XmlArrayAttribute.cs
- GeometryConverter.cs
- PersonalizableTypeEntry.cs
- CompileXomlTask.cs
- DocumentXPathNavigator.cs
- AutomationPropertyInfo.cs
- MatrixTransform3D.cs
- Focus.cs
- TreeView.cs
- odbcmetadatacollectionnames.cs