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
- ReturnEventArgs.cs
- ObjectItemCollection.cs
- InternalMappingException.cs
- TimeSpanConverter.cs
- AutomationPatternInfo.cs
- prefixendpointaddressmessagefilter.cs
- SpotLight.cs
- TransformProviderWrapper.cs
- CollectionsUtil.cs
- COAUTHINFO.cs
- XmlBinaryWriterSession.cs
- AndMessageFilterTable.cs
- ProtocolException.cs
- DataServices.cs
- FirstQueryOperator.cs
- GeneralTransform3DCollection.cs
- TransformBlockRequest.cs
- DbConnectionStringBuilder.cs
- _DomainName.cs
- ServiceDebugBehavior.cs
- Int16Animation.cs
- GenericPrincipal.cs
- InternalConfigHost.cs
- PolyQuadraticBezierSegmentFigureLogic.cs
- StringSorter.cs
- DataQuery.cs
- XmlLinkedNode.cs
- MatrixCamera.cs
- storepermissionattribute.cs
- GlyphInfoList.cs
- Line.cs
- dataprotectionpermission.cs
- XmlCharType.cs
- HyperLink.cs
- VariableReference.cs
- SequenceDesigner.xaml.cs
- SmtpSection.cs
- BamlRecordHelper.cs
- XsltSettings.cs
- XmlToDatasetMap.cs
- TextModifierScope.cs
- HandlerFactoryWrapper.cs
- JsonEnumDataContract.cs
- CookielessHelper.cs
- Events.cs
- SslStreamSecurityBindingElement.cs
- PostBackTrigger.cs
- SignalGate.cs
- URLIdentityPermission.cs
- MarginsConverter.cs
- FileDialog.cs
- IndexedWhereQueryOperator.cs
- HitTestDrawingContextWalker.cs
- FontCollection.cs
- ReferencedAssembly.cs
- DesignTimeResourceProviderFactoryAttribute.cs
- securitycriticaldataformultiplegetandset.cs
- loginstatus.cs
- FormViewDeletedEventArgs.cs
- recordstatescratchpad.cs
- InputMethodStateChangeEventArgs.cs
- HtmlElementCollection.cs
- PropertyToken.cs
- BinaryMessageFormatter.cs
- MenuCommandService.cs
- VectorKeyFrameCollection.cs
- SqlMethodCallConverter.cs
- SmiSettersStream.cs
- ListArgumentProvider.cs
- ADRoleFactory.cs
- StandardCommands.cs
- CngProvider.cs
- LZCodec.cs
- EntityProviderFactory.cs
- FloaterParagraph.cs
- DbConnectionHelper.cs
- GlyphingCache.cs
- MenuItemBinding.cs
- PropertyEmitterBase.cs
- DocumentDesigner.cs
- FreezableCollection.cs
- PipelineModuleStepContainer.cs
- ContextStaticAttribute.cs
- DictionaryKeyPropertyAttribute.cs
- PackageStore.cs
- EntityDataSourceSelectedEventArgs.cs
- MetadataCache.cs
- BufferBuilder.cs
- QueryContinueDragEventArgs.cs
- Context.cs
- DoubleCollectionConverter.cs
- DocumentXPathNavigator.cs
- ContainsRowNumberChecker.cs
- DetailsViewModeEventArgs.cs
- ItemsPanelTemplate.cs
- NamedPipeProcessProtocolHandler.cs
- Pair.cs
- DataListItemCollection.cs
- DetailsViewCommandEventArgs.cs
- MatrixKeyFrameCollection.cs