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. /// ///internal class FixedMaxHeap { 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. /// ///internal class FixedMaxHeap { 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
- BrushConverter.cs
- EnumConverter.cs
- Compiler.cs
- ErrorFormatter.cs
- XmlIlTypeHelper.cs
- DATA_BLOB.cs
- Group.cs
- FileNotFoundException.cs
- Calendar.cs
- XPathNodeList.cs
- SoapExtensionReflector.cs
- DrawingCollection.cs
- RectConverter.cs
- TextParagraphView.cs
- Timer.cs
- ImageSource.cs
- ViewKeyConstraint.cs
- ManagementObjectSearcher.cs
- FormViewUpdateEventArgs.cs
- MailMessageEventArgs.cs
- ImageList.cs
- SplineKeyFrames.cs
- FlowDocumentScrollViewerAutomationPeer.cs
- SqlDataReaderSmi.cs
- DiscoveryClientBindingElement.cs
- ProgressBarBrushConverter.cs
- DisplayNameAttribute.cs
- ISFTagAndGuidCache.cs
- SharedStatics.cs
- CLRBindingWorker.cs
- HtmlInputControl.cs
- HttpRequestTraceRecord.cs
- TreeBuilder.cs
- WebPartExportVerb.cs
- TypedDatasetGenerator.cs
- SiteMapNodeCollection.cs
- XmlValidatingReaderImpl.cs
- TreeNodeMouseHoverEvent.cs
- CodeIdentifiers.cs
- codemethodreferenceexpression.cs
- Process.cs
- CqlIdentifiers.cs
- AddInIpcChannel.cs
- QueryProcessor.cs
- SystemInformation.cs
- InternalConfigSettingsFactory.cs
- XmlSerializationGeneratedCode.cs
- embossbitmapeffect.cs
- UnlockCardRequest.cs
- RepeaterItemCollection.cs
- TrimSurroundingWhitespaceAttribute.cs
- WebPartCollection.cs
- EndpointDiscoveryMetadataCD1.cs
- SecurityTokenSpecification.cs
- WindowsRegion.cs
- LocalizedNameDescriptionPair.cs
- StoreContentChangedEventArgs.cs
- PageParser.cs
- TreeNodeConverter.cs
- ObjectDataSource.cs
- DocumentPageView.cs
- cookie.cs
- EraserBehavior.cs
- ModelVisual3D.cs
- Content.cs
- CustomTypeDescriptor.cs
- MeasureData.cs
- SafeNativeMethodsCLR.cs
- ReplacementText.cs
- ProfilePropertySettings.cs
- WindowsToolbarItemAsMenuItem.cs
- ThicknessAnimation.cs
- TemplateColumn.cs
- UIElement3D.cs
- ScrollChrome.cs
- IpcManager.cs
- CodeGeneratorOptions.cs
- InternalSafeNativeMethods.cs
- PolyQuadraticBezierSegment.cs
- ViewValidator.cs
- SerTrace.cs
- HTMLTextWriter.cs
- DynamicValidatorEventArgs.cs
- FormViewInsertedEventArgs.cs
- Duration.cs
- basecomparevalidator.cs
- HttpDebugHandler.cs
- DrawingAttributeSerializer.cs
- SkipStoryboardToFill.cs
- PropertyDescriptor.cs
- DesigntimeLicenseContext.cs
- Point.cs
- ViewStateModeByIdAttribute.cs
- FragmentNavigationEventArgs.cs
- TreeViewHitTestInfo.cs
- UnsupportedPolicyOptionsException.cs
- ExtensionMethods.cs
- CodeDirectionExpression.cs
- LoginCancelEventArgs.cs
- ScrollProviderWrapper.cs