Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / Utils / FixedMaxHeap.cs / 1305376 / FixedMaxHeap.cs
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// FixedMaxHeap.cs
//
// [....]
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
using System.Collections.Generic;
using System.Diagnostics.Contracts;
namespace System.Linq.Parallel
{
///
/// Very simple heap data structure, of fixed size.
///
///
{
private TElement[] m_elements; // Element array.
private int m_count; // Current count.
private IComparer m_comparer; // Element comparison routine.
//------------------------------------------------------------------------------------
// Create a new heap with the specified maximum size.
//
internal FixedMaxHeap(int maximumSize) : this(maximumSize, Util.GetDefaultComparer())
{
}
internal FixedMaxHeap(int maximumSize, IComparer comparer)
{
m_elements = new TElement[maximumSize];
m_comparer = comparer;
}
//-----------------------------------------------------------------------------------
// Retrieve the count (i.e. how many elements are in the heap).
//
internal int Count
{
get { return m_count; }
}
//-----------------------------------------------------------------------------------
// Retrieve the size (i.e. the maximum size of the heap).
//
internal int Size
{
get { return m_elements.Length; }
}
//-----------------------------------------------------------------------------------
// Get the current maximum value in the max-heap.
//
// Note: The heap stores the maximumSize smallest elements that were inserted.
// So, if the heap is full, the value returned is the maximumSize-th smallest
// element that was inserted into the heap.
//
internal TElement MaxValue
{
get
{
if (m_count == 0)
{
throw new InvalidOperationException(SR.GetString(SR.NoElements));
}
// The maximum element is in the 0th position.
return m_elements[0];
}
}
//------------------------------------------------------------------------------------
// Removes all elements from the heap.
//
internal void Clear()
{
m_count = 0;
}
//-----------------------------------------------------------------------------------
// Inserts the new element, maintaining the heap property.
//
// Return Value:
// If the element is greater than the current max element, this function returns
// false without modifying the heap. Otherwise, it returns true.
//
internal bool Insert(TElement e)
{
if (m_count < m_elements.Length)
{
// There is room. We can add it and then max-heapify.
m_elements[m_count] = e;
m_count++;
HeapifyLastLeaf();
return true;
}
else
{
// No more room. The element might not even fit in the heap. The check
// is simple: if it's greater than the maximum element, then it can't be
// inserted. Otherwise, we replace the head with it and reheapify.
if (m_comparer.Compare(e, m_elements[0]) < 0)
{
m_elements[0] = e;
HeapifyRoot();
return true;
}
return false;
}
}
//------------------------------------------------------------------------------------
// Replaces the maximum value in the heap with the user-provided value, and restores
// the heap property.
//
internal void ReplaceMax(TElement newValue)
{
Contract.Assert(m_count > 0);
m_elements[0] = newValue;
HeapifyRoot();
}
//------------------------------------------------------------------------------------
// Removes the maximum value from the heap, and restores the heap property.
//
internal void RemoveMax()
{
Contract.Assert(m_count > 0);
m_count--;
if (m_count > 0)
{
m_elements[0] = m_elements[m_count];
HeapifyRoot();
}
}
//-----------------------------------------------------------------------------------
// Private helpers to swap elements, and to reheapify starting from the root or
// from a leaf element, depending on what is needed.
//
private void Swap(int i, int j)
{
TElement tmpElement = m_elements[i];
m_elements[i] = m_elements[j];
m_elements[j] = tmpElement;
}
private void HeapifyRoot()
{
// We are heapifying from the head of the list.
int i = 0;
int n = m_count;
while (i < n)
{
// Calculate the current child node indexes.
int n0 = ((i + 1) * 2) - 1;
int n1 = n0 + 1;
if (n0 < n && m_comparer.Compare(m_elements[i], m_elements[n0]) < 0)
{
// We have to select the bigger of the two subtrees, and float
// the current element down. This maintains the max-heap property.
if (n1 < n && m_comparer.Compare(m_elements[n0], m_elements[n1]) < 0)
{
Swap(i, n1);
i = n1;
}
else
{
Swap(i, n0);
i = n0;
}
}
else if (n1 < n && m_comparer.Compare(m_elements[i], m_elements[n1]) < 0)
{
// Float down the "right" subtree. We needn't compare this subtree
// to the "left", because if the element was smaller than that, the
// first if statement's predicate would have evaluated to true.
Swap(i, n1);
i = n1;
}
else
{
// Else, the current key is in its final position. Break out
// of the current loop and return.
break;
}
}
}
private void HeapifyLastLeaf()
{
int i = m_count - 1;
while (i > 0)
{
int j = ((i + 1) / 2) - 1;
if (m_comparer.Compare(m_elements[i], m_elements[j]) > 0)
{
Swap(i, j);
i = j;
}
else
{
break;
}
}
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// FixedMaxHeap.cs
//
// [....]
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
using System.Collections.Generic;
using System.Diagnostics.Contracts;
namespace System.Linq.Parallel
{
///
/// Very simple heap data structure, of fixed size.
///
///
{
private TElement[] m_elements; // Element array.
private int m_count; // Current count.
private IComparer m_comparer; // Element comparison routine.
//------------------------------------------------------------------------------------
// Create a new heap with the specified maximum size.
//
internal FixedMaxHeap(int maximumSize) : this(maximumSize, Util.GetDefaultComparer())
{
}
internal FixedMaxHeap(int maximumSize, IComparer comparer)
{
m_elements = new TElement[maximumSize];
m_comparer = comparer;
}
//-----------------------------------------------------------------------------------
// Retrieve the count (i.e. how many elements are in the heap).
//
internal int Count
{
get { return m_count; }
}
//-----------------------------------------------------------------------------------
// Retrieve the size (i.e. the maximum size of the heap).
//
internal int Size
{
get { return m_elements.Length; }
}
//-----------------------------------------------------------------------------------
// Get the current maximum value in the max-heap.
//
// Note: The heap stores the maximumSize smallest elements that were inserted.
// So, if the heap is full, the value returned is the maximumSize-th smallest
// element that was inserted into the heap.
//
internal TElement MaxValue
{
get
{
if (m_count == 0)
{
throw new InvalidOperationException(SR.GetString(SR.NoElements));
}
// The maximum element is in the 0th position.
return m_elements[0];
}
}
//------------------------------------------------------------------------------------
// Removes all elements from the heap.
//
internal void Clear()
{
m_count = 0;
}
//-----------------------------------------------------------------------------------
// Inserts the new element, maintaining the heap property.
//
// Return Value:
// If the element is greater than the current max element, this function returns
// false without modifying the heap. Otherwise, it returns true.
//
internal bool Insert(TElement e)
{
if (m_count < m_elements.Length)
{
// There is room. We can add it and then max-heapify.
m_elements[m_count] = e;
m_count++;
HeapifyLastLeaf();
return true;
}
else
{
// No more room. The element might not even fit in the heap. The check
// is simple: if it's greater than the maximum element, then it can't be
// inserted. Otherwise, we replace the head with it and reheapify.
if (m_comparer.Compare(e, m_elements[0]) < 0)
{
m_elements[0] = e;
HeapifyRoot();
return true;
}
return false;
}
}
//------------------------------------------------------------------------------------
// Replaces the maximum value in the heap with the user-provided value, and restores
// the heap property.
//
internal void ReplaceMax(TElement newValue)
{
Contract.Assert(m_count > 0);
m_elements[0] = newValue;
HeapifyRoot();
}
//------------------------------------------------------------------------------------
// Removes the maximum value from the heap, and restores the heap property.
//
internal void RemoveMax()
{
Contract.Assert(m_count > 0);
m_count--;
if (m_count > 0)
{
m_elements[0] = m_elements[m_count];
HeapifyRoot();
}
}
//-----------------------------------------------------------------------------------
// Private helpers to swap elements, and to reheapify starting from the root or
// from a leaf element, depending on what is needed.
//
private void Swap(int i, int j)
{
TElement tmpElement = m_elements[i];
m_elements[i] = m_elements[j];
m_elements[j] = tmpElement;
}
private void HeapifyRoot()
{
// We are heapifying from the head of the list.
int i = 0;
int n = m_count;
while (i < n)
{
// Calculate the current child node indexes.
int n0 = ((i + 1) * 2) - 1;
int n1 = n0 + 1;
if (n0 < n && m_comparer.Compare(m_elements[i], m_elements[n0]) < 0)
{
// We have to select the bigger of the two subtrees, and float
// the current element down. This maintains the max-heap property.
if (n1 < n && m_comparer.Compare(m_elements[n0], m_elements[n1]) < 0)
{
Swap(i, n1);
i = n1;
}
else
{
Swap(i, n0);
i = n0;
}
}
else if (n1 < n && m_comparer.Compare(m_elements[i], m_elements[n1]) < 0)
{
// Float down the "right" subtree. We needn't compare this subtree
// to the "left", because if the element was smaller than that, the
// first if statement's predicate would have evaluated to true.
Swap(i, n1);
i = n1;
}
else
{
// Else, the current key is in its final position. Break out
// of the current loop and return.
break;
}
}
}
private void HeapifyLastLeaf()
{
int i = m_count - 1;
while (i > 0)
{
int j = ((i + 1) / 2) - 1;
if (m_comparer.Compare(m_elements[i], m_elements[j]) > 0)
{
Swap(i, j);
i = j;
}
else
{
break;
}
}
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ToolStripRenderEventArgs.cs
- FontStretch.cs
- DataGridViewCellStateChangedEventArgs.cs
- ScrollableControl.cs
- ProtectedProviderSettings.cs
- ServiceDocumentFormatter.cs
- AbstractExpressions.cs
- BamlResourceDeserializer.cs
- PkcsMisc.cs
- SimpleTextLine.cs
- WebPartVerb.cs
- SimpleWorkerRequest.cs
- PassportPrincipal.cs
- ConfigurationFileMap.cs
- XmlWrappingReader.cs
- figurelength.cs
- DefaultPrintController.cs
- SafeViewOfFileHandle.cs
- FilterElement.cs
- RectangleGeometry.cs
- XmlSchemaAll.cs
- RegisteredExpandoAttribute.cs
- InheritanceService.cs
- SamlAction.cs
- EdmItemCollection.cs
- OracleSqlParser.cs
- CngUIPolicy.cs
- IApplicationTrustManager.cs
- StreamUpgradeProvider.cs
- SessionEndedEventArgs.cs
- TemplateColumn.cs
- Invariant.cs
- Splitter.cs
- StringKeyFrameCollection.cs
- DbSourceParameterCollection.cs
- LinkedResourceCollection.cs
- validationstate.cs
- ViewLoader.cs
- ExpressionVisitorHelpers.cs
- MemberRestriction.cs
- ControlAdapter.cs
- WebServiceHost.cs
- PeerReferralPolicy.cs
- ExpressionCopier.cs
- mansign.cs
- ReliableRequestSessionChannel.cs
- InfoCardKeyedHashAlgorithm.cs
- PassportAuthentication.cs
- RSAPKCS1SignatureDeformatter.cs
- BitmapData.cs
- TreeNodeStyleCollection.cs
- FrameAutomationPeer.cs
- ActiveXSite.cs
- ExtensionQuery.cs
- SyndicationDeserializer.cs
- ProtocolsConfigurationEntry.cs
- CurrencyWrapper.cs
- MonthChangedEventArgs.cs
- ExpandCollapseProviderWrapper.cs
- FlowDocumentPage.cs
- DeferredSelectedIndexReference.cs
- ConfigurationStrings.cs
- ContentElement.cs
- BamlBinaryReader.cs
- SafeNativeMethods.cs
- KnownTypes.cs
- AtlasWeb.Designer.cs
- CultureTable.cs
- EncodingTable.cs
- HwndStylusInputProvider.cs
- PersonalizationEntry.cs
- webproxy.cs
- ReadonlyMessageFilter.cs
- PackagePart.cs
- AttachedAnnotation.cs
- Itemizer.cs
- AlphabeticalEnumConverter.cs
- PolyBezierSegment.cs
- Cursor.cs
- TypeContext.cs
- ContentControl.cs
- InputReportEventArgs.cs
- ApplicationSettingsBase.cs
- ColorMatrix.cs
- LoginViewDesigner.cs
- EventListener.cs
- FixedSOMPage.cs
- CompositeDataBoundControl.cs
- PackWebRequest.cs
- _SecureChannel.cs
- ColorContext.cs
- DesignerCalendarAdapter.cs
- XmlReflectionMember.cs
- HttpPostedFileBase.cs
- BitmapEffect.cs
- RoutedEventConverter.cs
- GenericTypeParameterConverter.cs
- DrawingContextWalker.cs
- ListViewGroupConverter.cs
- Accessible.cs