Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / NetFx40 / System.Activities.DurableInstancing / System / Activities / DurableInstancing / BinaryHeap.cs / 1305376 / BinaryHeap.cs
//---------------------------------------------------------------- // Copyright (c) Microsoft Corporation. All rights reserved. //--------------------------------------------------------------- namespace System.Activities.DurableInstancing { using System; using System.Collections.Generic; using System.Diagnostics.CodeAnalysis; using System.Runtime; sealed class BinaryHeapwhere TKey : IComparable { const int defaultCapacity = 128; readonly KeyValuePair EmptyItem = new KeyValuePair (); KeyValuePair [] items; int itemCount; public BinaryHeap() : this(defaultCapacity) { } public BinaryHeap(int capacity) { Fx.Assert(capacity > 0, "Capacity must be a positive value."); this.items = new KeyValuePair [capacity]; } public int Count { get { return this.itemCount; } } public bool IsEmpty { get { return this.itemCount == 0; } } public void Clear() { this.itemCount = 0; this.items = new KeyValuePair [defaultCapacity]; } public bool Enqueue(TKey key, TValue item) { if (this.itemCount == this.items.Length) { ResizeItemStore(this.items.Length * 2); } this.items[this.itemCount++] = new KeyValuePair (key, item); int position = this.BubbleUp(this.itemCount - 1); return (position == 0); } public KeyValuePair Dequeue() { return Dequeue(true); } KeyValuePair Dequeue(bool shrink) { Fx.Assert(this.itemCount > 0, "Cannot dequeue empty queue."); KeyValuePair result = items[0]; if (this.itemCount == 1) { this.itemCount = 0; this.items[0] = this.EmptyItem; } else { --this.itemCount; this.items[0] = this.items[itemCount]; this.items[itemCount] = this.EmptyItem; // Keep the structure of the heap valid. this.BubbleDown(0); } if (shrink) { ShrinkStore(); } return result; } public KeyValuePair Peek() { Fx.Assert(this.itemCount > 0, "Cannot peek at empty queue."); return this.items[0]; } [SuppressMessage(FxCop.Category.Design, "CA1006:DoNotNestGenericTypesInMemberSignatures", Justification="This is an internal only API.")] [SuppressMessage(FxCop.Category.MSInternal, "CA908:UseApprovedGenericsForPrecompiledAssemblies")] public ICollection > RemoveAll(Predicate > func) { ICollection > result = new List >(); for (int position = 0; position < this.itemCount; position++) { while (func(this.items[position]) && position < this.itemCount) { result.Add(this.items[position]); int lastItem = this.itemCount - 1; while (func(this.items[lastItem]) && position < lastItem) { result.Add(this.items[lastItem]); this.items[lastItem] = EmptyItem; --lastItem; } this.items[position] = this.items[lastItem]; this.items[lastItem] = EmptyItem; this.itemCount = lastItem; if (position < lastItem) { this.BubbleDown(this.BubbleUp(position)); } } } this.ShrinkStore(); return result; } void ShrinkStore() { // If we are under half capacity and above default capacity size down. if (this.items.Length > defaultCapacity && this.itemCount < (this.items.Length >> 1)) { int newSize = Math.Max( defaultCapacity, (((this.itemCount / defaultCapacity) + 1) * defaultCapacity)); this.ResizeItemStore(newSize); } } [SuppressMessage("Microsoft.MSInternal", "CA908:UseApprovedGenericsForPrecompiledAssemblies")] [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Justification = "This is an internal only API.")] public ICollection > TakeWhile(Predicate func) { ICollection > result = new List >(); while (!this.IsEmpty && func(this.Peek().Key)) { result.Add(this.Dequeue(false)); } ShrinkStore(); return result; } void ResizeItemStore(int newSize) { Fx.Assert(itemCount < newSize, "Shrinking now will lose data."); Fx.Assert(defaultCapacity <= newSize, "Can not shrink below the default capacity."); KeyValuePair [] temp = new KeyValuePair [newSize]; Array.Copy(this.items, 0, temp, 0, this.itemCount); this.items = temp; } void BubbleDown(int startIndex) { int currentPosition = startIndex; int swapPosition = startIndex; while (true) { int leftChildPosition = (currentPosition << 1) + 1; int rightChildPosition = leftChildPosition + 1; if (leftChildPosition < itemCount) { if (this.items[currentPosition].Key.CompareTo(this.items[leftChildPosition].Key) > 0) { swapPosition = leftChildPosition; } } else { break; } if (rightChildPosition < itemCount) { if (this.items[swapPosition].Key.CompareTo(this.items[rightChildPosition].Key) > 0) { swapPosition = rightChildPosition; } } if (currentPosition != swapPosition) { KeyValuePair temp = this.items[currentPosition]; this.items[currentPosition] = this.items[swapPosition]; this.items[swapPosition] = temp; } else { break; } currentPosition = swapPosition; } } int BubbleUp(int startIndex) { while (startIndex > 0) { int parent = (startIndex - 1) >> 1; if (this.items[parent].Key.CompareTo(this.items[startIndex].Key) > 0) { KeyValuePair temp = this.items[startIndex]; this.items[startIndex] = this.items[parent]; this.items[parent] = temp; } else { break; } startIndex = parent; } return startIndex; } } } // 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
- localization.cs
- PcmConverter.cs
- _LocalDataStoreMgr.cs
- SafePointer.cs
- TreeNodeMouseHoverEvent.cs
- ValueUtilsSmi.cs
- RangeValuePatternIdentifiers.cs
- AssertUtility.cs
- ParameterToken.cs
- WindowsTooltip.cs
- InfoCardKeyedHashAlgorithm.cs
- ProfessionalColorTable.cs
- MenuItemAutomationPeer.cs
- MetafileHeaderWmf.cs
- WebBrowsableAttribute.cs
- MemoryStream.cs
- RenamedEventArgs.cs
- Misc.cs
- FormatVersion.cs
- WindowsListViewItemCheckBox.cs
- Expression.cs
- PanelStyle.cs
- HttpListener.cs
- DataControlCommands.cs
- ProfileServiceManager.cs
- PatternMatcher.cs
- ThreadPool.cs
- ExpressionNormalizer.cs
- SolidColorBrush.cs
- SrgsRule.cs
- DispatchWrapper.cs
- FlowDocumentReaderAutomationPeer.cs
- LogWriteRestartAreaAsyncResult.cs
- DependencyObjectType.cs
- HWStack.cs
- CodeTypeMember.cs
- TreeWalkHelper.cs
- MimeTypeMapper.cs
- VisualStyleElement.cs
- FontCacheUtil.cs
- ResponseBodyWriter.cs
- SchemaContext.cs
- Attachment.cs
- FixedTextView.cs
- ToolStripItemDesigner.cs
- PrefixQName.cs
- KeyedHashAlgorithm.cs
- SqlProfileProvider.cs
- MouseEvent.cs
- PointKeyFrameCollection.cs
- HttpValueCollection.cs
- DesignerCategoryAttribute.cs
- AudioBase.cs
- RelationshipFixer.cs
- PathGeometry.cs
- StateItem.cs
- RotateTransform3D.cs
- DelimitedListTraceListener.cs
- Vector3DConverter.cs
- ObjectStateManagerMetadata.cs
- ServiceHttpHandlerFactory.cs
- TextEndOfLine.cs
- StyleBamlTreeBuilder.cs
- COM2ICategorizePropertiesHandler.cs
- FrameworkContentElement.cs
- HtmlTableRow.cs
- GcSettings.cs
- FormCollection.cs
- EdmTypeAttribute.cs
- TimeoutException.cs
- WinEventQueueItem.cs
- SafeFileMappingHandle.cs
- OrderingQueryOperator.cs
- TypeDependencyAttribute.cs
- DataGridViewCellLinkedList.cs
- HttpProfileGroupBase.cs
- OdbcReferenceCollection.cs
- DefaultAuthorizationContext.cs
- IPipelineRuntime.cs
- TimeZone.cs
- PointF.cs
- HttpConfigurationContext.cs
- AudioLevelUpdatedEventArgs.cs
- CodeDelegateInvokeExpression.cs
- InputQueueChannelAcceptor.cs
- TransformCollection.cs
- ListBindingConverter.cs
- NativeStructs.cs
- Journal.cs
- Array.cs
- InheritanceRules.cs
- SchemaNamespaceManager.cs
- ValidationHelper.cs
- EventLogPermissionEntry.cs
- ResponseBodyWriter.cs
- PlacementWorkspace.cs
- StrongBox.cs
- Page.cs
- PersonalizationEntry.cs
- ImageIndexConverter.cs