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
- MarkupCompilePass1.cs
- MimeTypePropertyAttribute.cs
- XmlReflectionMember.cs
- MessageRpc.cs
- InstanceDataCollection.cs
- DomainUpDown.cs
- Localizer.cs
- followingsibling.cs
- RadioButton.cs
- StructuredTypeEmitter.cs
- PropertyValueUIItem.cs
- SplineKeyFrames.cs
- ConnectionConsumerAttribute.cs
- CustomLineCap.cs
- TrackingMemoryStreamFactory.cs
- XPathQilFactory.cs
- LinearGradientBrush.cs
- MoveSizeWinEventHandler.cs
- DeploymentExceptionMapper.cs
- BindingSource.cs
- EnterpriseServicesHelper.cs
- DataGridViewTopLeftHeaderCell.cs
- BookmarkManager.cs
- ConnectionsZone.cs
- PeerPresenceInfo.cs
- SchemaCreator.cs
- DataRowView.cs
- FlowDocumentPageViewerAutomationPeer.cs
- XmlRawWriter.cs
- DataStorage.cs
- SchemaMerger.cs
- MaskedTextBoxTextEditor.cs
- MembershipSection.cs
- WS2007HttpBinding.cs
- RowCache.cs
- StringUtil.cs
- CustomAttribute.cs
- FileDetails.cs
- TextProperties.cs
- WindowsContainer.cs
- PersonalizationProviderHelper.cs
- EndpointReference.cs
- ToggleProviderWrapper.cs
- PropertyChangeTracker.cs
- NameTable.cs
- LayoutManager.cs
- AppDomainManager.cs
- SelectorItemAutomationPeer.cs
- ProxyHwnd.cs
- GridViewColumnCollection.cs
- CannotUnloadAppDomainException.cs
- StartFileNameEditor.cs
- IriParsingElement.cs
- SerializationEventsCache.cs
- AutoResizedEvent.cs
- StorageInfo.cs
- InternalRelationshipCollection.cs
- SuppressMergeCheckAttribute.cs
- SubtreeProcessor.cs
- DocumentXPathNavigator.cs
- IntMinMaxAggregationOperator.cs
- XmlObjectSerializerWriteContext.cs
- TableCellCollection.cs
- RemotingConfigParser.cs
- EmbeddedMailObjectsCollection.cs
- AppDomainFactory.cs
- SimpleBitVector32.cs
- ConfigurationSettings.cs
- SettingsBindableAttribute.cs
- TemplateManager.cs
- CounterCreationDataCollection.cs
- SafeArrayTypeMismatchException.cs
- AdornerPresentationContext.cs
- DataGridViewButtonColumn.cs
- PageCodeDomTreeGenerator.cs
- SolidColorBrush.cs
- TabletCollection.cs
- DirectoryNotFoundException.cs
- IgnoreDeviceFilterElement.cs
- CompoundFileStorageReference.cs
- OleDbFactory.cs
- DependencyPropertyDescriptor.cs
- ResponseStream.cs
- WebPartEditorCancelVerb.cs
- WebPartMovingEventArgs.cs
- XomlCompilerError.cs
- PersonalizationStateInfoCollection.cs
- ResourcesGenerator.cs
- SimpleApplicationHost.cs
- XPathMessageFilterElementCollection.cs
- CollectionConverter.cs
- BackStopAuthenticationModule.cs
- ToolboxBitmapAttribute.cs
- FrameworkTextComposition.cs
- ThumbButtonInfoCollection.cs
- RegexCompiler.cs
- LoadWorkflowByKeyAsyncResult.cs
- PowerStatus.cs
- Renderer.cs
- SmiMetaData.cs