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
- DBProviderConfigurationHandler.cs
- InputScopeConverter.cs
- SafeBitVector32.cs
- TagPrefixAttribute.cs
- SourceChangedEventArgs.cs
- BmpBitmapEncoder.cs
- HtmlShimManager.cs
- WorkflowViewService.cs
- Site.cs
- DataStreamFromComStream.cs
- ResourceProviderFactory.cs
- DataPagerField.cs
- Stack.cs
- ObjectPersistData.cs
- SoapInteropTypes.cs
- unsafenativemethodsother.cs
- __ConsoleStream.cs
- AssociationTypeEmitter.cs
- CreateUserWizard.cs
- AuthenticationManager.cs
- HttpContext.cs
- XamlClipboardData.cs
- ObjectAssociationEndMapping.cs
- BaseCodeDomTreeGenerator.cs
- DockProviderWrapper.cs
- PrimaryKeyTypeConverter.cs
- RIPEMD160.cs
- COM2FontConverter.cs
- ControlParser.cs
- BamlLocalizationDictionary.cs
- SwitchLevelAttribute.cs
- InstalledVoice.cs
- ServiceOperationHelpers.cs
- controlskin.cs
- CheckBoxBaseAdapter.cs
- XmlSchemaExternal.cs
- XamlReaderConstants.cs
- OutputChannel.cs
- LazyTextWriterCreator.cs
- AnimationClockResource.cs
- _ListenerRequestStream.cs
- CoTaskMemHandle.cs
- SortKey.cs
- DefaultHttpHandler.cs
- ObjectView.cs
- InternalSafeNativeMethods.cs
- EntityStoreSchemaGenerator.cs
- WebBrowser.cs
- WebServiceData.cs
- WeakReferenceKey.cs
- DPCustomTypeDescriptor.cs
- TextWriter.cs
- _UncName.cs
- HandlerBase.cs
- HtmlProps.cs
- DataGridViewSelectedRowCollection.cs
- GridView.cs
- DataQuery.cs
- XmlSignatureProperties.cs
- SqlEnums.cs
- ProxyGenerator.cs
- ScrollEventArgs.cs
- CatalogPartCollection.cs
- WCFModelStrings.Designer.cs
- SystemParameters.cs
- BuildResultCache.cs
- TranslateTransform3D.cs
- RtfToXamlReader.cs
- ImportDesigner.xaml.cs
- ControllableStoryboardAction.cs
- DataGridViewCellMouseEventArgs.cs
- XmlNamespaceMappingCollection.cs
- coordinator.cs
- DataRecord.cs
- ReadWriteSpinLock.cs
- NamespaceQuery.cs
- Operand.cs
- SqlDataSourceCache.cs
- XmlCharacterData.cs
- MenuItem.cs
- SafeNativeMethods.cs
- ServiceModelPerformanceCounters.cs
- XhtmlMobileTextWriter.cs
- ReferenceEqualityComparer.cs
- BuildProviderUtils.cs
- XamlWriterExtensions.cs
- DbConnectionOptions.cs
- invalidudtexception.cs
- EntityWrapperFactory.cs
- Condition.cs
- PixelFormats.cs
- ApplicationInfo.cs
- SeparatorAutomationPeer.cs
- SharedConnectionWorkflowTransactionService.cs
- BinaryReader.cs
- ConfigXmlComment.cs
- AssemblyCache.cs
- MachineSettingsSection.cs
- BuilderPropertyEntry.cs
- Int16Converter.cs