Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Base / MS / Internal / PriorityQueue.cs / 1305600 / PriorityQueue.cs
using System; using System.Collections.Generic; using System.Diagnostics; namespace System.Windows.Threading { internal class PriorityQueue{ public PriorityQueue() { // Build the collection of priority chains. _priorityChains = new SortedList >(); // NOTE: should be Priority _cacheReusableChains = new Stack >(10); _head = _tail = null; _count = 0; } // NOTE: not used // public int Count {get{return _count;}} public DispatcherPriority MaxPriority // NOTE: should be Priority { get { int count = _priorityChains.Count; if(count > 0) { return (DispatcherPriority) _priorityChains.Keys[count - 1]; } else { return DispatcherPriority.Invalid; // NOTE: should be Priority.Invalid; } } } public PriorityItem Enqueue(DispatcherPriority priority, T data) // NOTE: should be Priority { // Find the existing chain for this priority, or create a new one // if one does not exist. PriorityChain chain = GetChain(priority); // Wrap the item in a PriorityItem so we can put it in our // linked list. PriorityItem priorityItem = new PriorityItem (data); // Step 1: Append this to the end of the "sequential" linked list. InsertItemInSequentialChain(priorityItem, _tail); // Step 2: Append the item into the priority chain. InsertItemInPriorityChain(priorityItem, chain, chain.Tail); return priorityItem; } public T Dequeue() { // Get the max-priority chain. int count = _priorityChains.Count; if(count > 0) { PriorityChain chain = _priorityChains.Values[count - 1]; Debug.Assert(chain != null, "PriorityQueue.Dequeue: a chain should exist."); PriorityItem item = chain.Head; Debug.Assert(item != null, "PriorityQueue.Dequeue: a priority item should exist."); RemoveItem(item); return item.Data; } else { throw new InvalidOperationException(); } } public T Peek() { T data = default(T); // Get the max-priority chain. int count = _priorityChains.Count; if(count > 0) { PriorityChain chain = _priorityChains.Values[count - 1]; Debug.Assert(chain != null, "PriorityQueue.Peek: a chain should exist."); PriorityItem item = chain.Head; Debug.Assert(item != null, "PriorityQueue.Peek: a priority item should exist."); data = item.Data; } return data; } public void RemoveItem(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItem: invalid item."); Debug.Assert(item.Chain != null, "PriorityQueue.RemoveItem: a chain should exist."); PriorityChain chain = item.Chain; // Step 1: Remove the item from its priority chain. RemoveItemFromPriorityChain(item); // Step 2: Remove the item from the sequential chain. RemoveItemFromSequentialChain(item); // Note: we do not clean up empty chains on purpose to reduce churn. } public void ChangeItemPriority(PriorityItem item, DispatcherPriority priority) // NOTE: should be Priority { // Remove the item from its current priority and insert it into // the new priority chain. Note that this does not change the // sequential ordering. // Step 1: Remove the item from the priority chain. RemoveItemFromPriorityChain(item); // Step 2: Insert the item into the new priority chain. // Find the existing chain for this priority, or create a new one // if one does not exist. PriorityChain chain = GetChain(priority); InsertItemInPriorityChain(item, chain); } private PriorityChain GetChain(DispatcherPriority priority) // NOTE: should be Priority { PriorityChain chain = null; int count = _priorityChains.Count; if(count > 0) { if(priority == (DispatcherPriority) _priorityChains.Keys[0]) { chain = _priorityChains.Values[0]; } else if(priority == (DispatcherPriority) _priorityChains.Keys[count - 1]) { chain = _priorityChains.Values[count - 1]; } else if((priority > (DispatcherPriority) _priorityChains.Keys[0]) && (priority < (DispatcherPriority) _priorityChains.Keys[count - 1])) { _priorityChains.TryGetValue((int)priority, out chain); } } if(chain == null) { if(_cacheReusableChains.Count > 0) { chain = _cacheReusableChains.Pop(); chain.Priority = priority; } else { chain = new PriorityChain (priority); } _priorityChains.Add((int)priority, chain); } return chain; } private void InsertItemInPriorityChain(PriorityItem item, PriorityChain chain) { // Scan along the sequential chain, in the previous direction, // looking for an item that is already in the new chain. We will // insert ourselves after the item we found. We can short-circuit // this search if the new chain is empty. if(chain.Head == null) { Debug.Assert(chain.Tail == null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should be null."); InsertItemInPriorityChain(item, chain, null); } else { Debug.Assert(chain.Tail != null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should not be null."); PriorityItem after = null; // Search backwards along the sequential chain looking for an // item already in this list. for(after = item.SequentialPrev; after != null; after = after.SequentialPrev) { if(after.Chain == chain) { break; } } InsertItemInPriorityChain(item, chain, after); } } internal void InsertItemInPriorityChain(PriorityItem item, PriorityChain chain, PriorityItem after) { Debug.Assert(chain != null, "PriorityQueue.InsertItemInPriorityChain: a chain must be provided."); Debug.Assert(item.Chain == null && item.PriorityPrev == null && item.PriorityNext == null, "PriorityQueue.InsertItemInPriorityChain: item must not already be in a priority chain."); item.Chain = chain; if(after == null) { // Note: passing null for after means insert at the head. if(chain.Head != null) { Debug.Assert(chain.Tail != null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should not be null."); chain.Head.PriorityPrev = item; item.PriorityNext = chain.Head; chain.Head = item; } else { Debug.Assert(chain.Tail == null, "PriorityQueue.InsertItemInPriorityChain: both the head and the tail should be null."); chain.Head = chain.Tail = item; } } else { item.PriorityPrev = after; if(after.PriorityNext != null) { item.PriorityNext = after.PriorityNext; after.PriorityNext.PriorityPrev = item; after.PriorityNext = item; } else { Debug.Assert(item.Chain.Tail == after, "PriorityQueue.InsertItemInPriorityChain: the chain's tail should be the item we are inserting after."); after.PriorityNext = item; chain.Tail = item; } } chain.Count++; } private void RemoveItemFromPriorityChain(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItemFromPriorityChain: invalid item."); Debug.Assert(item.Chain != null, "PriorityQueue.RemoveItemFromPriorityChain: a chain should exist."); // Step 1: Fix up the previous link if(item.PriorityPrev != null) { Debug.Assert(item.Chain.Head != item, "PriorityQueue.RemoveItemFromPriorityChain: the head should not point to this item."); item.PriorityPrev.PriorityNext = item.PriorityNext; } else { Debug.Assert(item.Chain.Head == item, "PriorityQueue.RemoveItemFromPriorityChain: the head should point to this item."); item.Chain.Head = item.PriorityNext; } // Step 2: Fix up the next link if(item.PriorityNext != null) { Debug.Assert(item.Chain.Tail != item, "PriorityQueue.RemoveItemFromPriorityChain: the tail should not point to this item."); item.PriorityNext.PriorityPrev = item.PriorityPrev; } else { Debug.Assert(item.Chain.Tail == item, "PriorityQueue.RemoveItemFromPriorityChain: the tail should point to this item."); item.Chain.Tail = item.PriorityPrev; } // Step 3: cleanup item.PriorityPrev = item.PriorityNext = null; item.Chain.Count--; if(item.Chain.Count == 0) { if(item.Chain.Priority == (DispatcherPriority) _priorityChains.Keys[_priorityChains.Count - 1]) { _priorityChains.RemoveAt(_priorityChains.Count - 1); } else { _priorityChains.Remove((int) item.Chain.Priority); } if(_cacheReusableChains.Count < 10) { item.Chain.Priority = DispatcherPriority.Invalid; // NOTE: should be Priority.Invalid _cacheReusableChains.Push(item.Chain); } } item.Chain = null; } internal void InsertItemInSequentialChain(PriorityItem item, PriorityItem after) { Debug.Assert(item.SequentialPrev == null && item.SequentialNext == null, "PriorityQueue.InsertItemInSequentialChain: item must not already be in the sequential chain."); if(after == null) { // Note: passing null for after means insert at the head. if(_head != null) { Debug.Assert(_tail != null, "PriorityQueue.InsertItemInSequentialChain: both the head and the tail should not be null."); _head.SequentialPrev = item; item.SequentialNext = _head; _head = item; } else { Debug.Assert(_tail == null, "PriorityQueue.InsertItemInSequentialChain: both the head and the tail should be null."); _head = _tail = item; } } else { item.SequentialPrev = after; if(after.SequentialNext != null) { item.SequentialNext = after.SequentialNext; after.SequentialNext.SequentialPrev = item; after.SequentialNext = item; } else { Debug.Assert(_tail == after, "PriorityQueue.InsertItemInSequentialChain: the tail should be the item we are inserting after."); after.SequentialNext = item; _tail = item; } } _count++; } private void RemoveItemFromSequentialChain(PriorityItem item) { Debug.Assert(item != null, "PriorityQueue.RemoveItemFromSequentialChain: invalid item."); // Step 1: Fix up the previous link if(item.SequentialPrev != null) { Debug.Assert(_head != item, "PriorityQueue.RemoveItemFromSequentialChain: the head should not point to this item."); item.SequentialPrev.SequentialNext = item.SequentialNext; } else { Debug.Assert(_head == item, "PriorityQueue.RemoveItemFromSequentialChain: the head should point to this item."); _head = item.SequentialNext; } // Step 2: Fix up the next link if(item.SequentialNext != null) { Debug.Assert(_tail != item, "PriorityQueue.RemoveItemFromSequentialChain: the tail should not point to this item."); item.SequentialNext.SequentialPrev = item.SequentialPrev; } else { Debug.Assert(_tail == item, "PriorityQueue.RemoveItemFromSequentialChain: the tail should point to this item."); _tail = item.SequentialPrev; } // Step 3: cleanup item.SequentialPrev = item.SequentialNext = null; _count--; } // Priority chains... private SortedList > _priorityChains; // NOTE: should be Priority private Stack > _cacheReusableChains; // Sequential chain... private PriorityItem _head; private PriorityItem _tail; private int _count; } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- TypeDescriptor.cs
- GridViewRowPresenterBase.cs
- Vector3DCollectionConverter.cs
- KeyGesture.cs
- GeneratedContractType.cs
- DoubleAnimationUsingPath.cs
- PenThread.cs
- XmlAutoDetectWriter.cs
- __Error.cs
- PrintDialog.cs
- invalidudtexception.cs
- MonthCalendar.cs
- AsyncDataRequest.cs
- SqlDataReaderSmi.cs
- NamespaceInfo.cs
- ServiceHost.cs
- GeneratedView.cs
- SourceFileBuildProvider.cs
- ComboBoxHelper.cs
- CustomTrackingQuery.cs
- KernelTypeValidation.cs
- ObjectListCommandEventArgs.cs
- StylusCaptureWithinProperty.cs
- TypeReference.cs
- Interlocked.cs
- Helper.cs
- DataIdProcessor.cs
- MenuItem.cs
- Int32CAMarshaler.cs
- TextCompositionEventArgs.cs
- PingOptions.cs
- BaseTemplateBuildProvider.cs
- PenCursorManager.cs
- SubMenuStyleCollection.cs
- DeviceContext2.cs
- PersonalizationProviderCollection.cs
- HTMLTagNameToTypeMapper.cs
- DataGridViewSelectedColumnCollection.cs
- DBBindings.cs
- GPPOINT.cs
- ClusterRegistryConfigurationProvider.cs
- IntSecurity.cs
- GuidelineCollection.cs
- WindowsGraphicsCacheManager.cs
- MetaTableHelper.cs
- JavaScriptSerializer.cs
- AttributeCollection.cs
- SafeFileMapViewHandle.cs
- EventNotify.cs
- Freezable.cs
- TextServicesContext.cs
- FrameworkTextComposition.cs
- OutOfProcStateClientManager.cs
- ToolStripItemBehavior.cs
- FontInfo.cs
- BindingsCollection.cs
- TextRange.cs
- _HeaderInfo.cs
- UIHelper.cs
- FilterException.cs
- Convert.cs
- AutomationIdentifier.cs
- DefaultObjectSerializer.cs
- PerformanceCounterNameAttribute.cs
- ValueHandle.cs
- ConfigXmlCDataSection.cs
- InvalidOperationException.cs
- UpDownBase.cs
- PolygonHotSpot.cs
- DelegateHelpers.Generated.cs
- ObjectCache.cs
- KeyedCollection.cs
- PagerSettings.cs
- RegexWriter.cs
- PathFigure.cs
- CaretElement.cs
- BindableTemplateBuilder.cs
- ObfuscateAssemblyAttribute.cs
- WebControlAdapter.cs
- SiteMap.cs
- ResolveMatchesApril2005.cs
- Quad.cs
- BidirectionalDictionary.cs
- CodeMemberProperty.cs
- MenuItemBindingCollection.cs
- SamlSecurityToken.cs
- DetailsViewInsertEventArgs.cs
- BaseCollection.cs
- GetWinFXPath.cs
- MenuAdapter.cs
- RegexStringValidatorAttribute.cs
- SignedPkcs7.cs
- HostingPreferredMapPath.cs
- SubtreeProcessor.cs
- ObsoleteAttribute.cs
- MetadataItemEmitter.cs
- FormViewPagerRow.cs
- TreeNodeCollection.cs
- ToolboxService.cs
- SplineQuaternionKeyFrame.cs