Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / wpf / src / Base / MS / Internal / PriorityQueue.cs / 1 / 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. 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
- DataBoundLiteralControl.cs
- UnmanagedMemoryAccessor.cs
- GridViewRowCollection.cs
- TextDpi.cs
- FormsAuthenticationUser.cs
- MaskDesignerDialog.cs
- PageBuildProvider.cs
- DocumentXmlWriter.cs
- CharKeyFrameCollection.cs
- WebBrowserUriTypeConverter.cs
- HitTestWithPointDrawingContextWalker.cs
- TextSchema.cs
- DocumentOrderQuery.cs
- SapiInterop.cs
- MdiWindowListItemConverter.cs
- CacheVirtualItemsEvent.cs
- KeyedHashAlgorithm.cs
- StyleSheetDesigner.cs
- FileDialogPermission.cs
- ClientSettings.cs
- WindowsEditBox.cs
- Padding.cs
- cookie.cs
- MULTI_QI.cs
- DataRecord.cs
- XmlQueryCardinality.cs
- compensatingcollection.cs
- InertiaRotationBehavior.cs
- DbDataReader.cs
- XmlElementAttributes.cs
- Rotation3D.cs
- NetworkInterface.cs
- StoreContentChangedEventArgs.cs
- CodeTypeParameter.cs
- CodePageUtils.cs
- ZipIOLocalFileHeader.cs
- EnumMember.cs
- SQLByte.cs
- Version.cs
- WebSysDescriptionAttribute.cs
- DetailsViewUpdateEventArgs.cs
- DataSetUtil.cs
- OutputCacheProfile.cs
- FontFamily.cs
- FontWeight.cs
- CodeStatement.cs
- XamlPointCollectionSerializer.cs
- ForwardPositionQuery.cs
- StreamWriter.cs
- AnchoredBlock.cs
- DataStorage.cs
- SqlStatistics.cs
- followingquery.cs
- OperatingSystem.cs
- IsolatedStoragePermission.cs
- GenericAuthenticationEventArgs.cs
- ErrorCodes.cs
- PlainXmlSerializer.cs
- SmiContextFactory.cs
- SamlAuthorityBinding.cs
- AnnotationObservableCollection.cs
- CharacterMetricsDictionary.cs
- ProjectionCamera.cs
- XsdDateTime.cs
- SourceElementsCollection.cs
- SchemaMerger.cs
- ProtocolProfile.cs
- OleDbStruct.cs
- RelationalExpressions.cs
- _NetworkingPerfCounters.cs
- RelAssertionDirectKeyIdentifierClause.cs
- SoapSchemaExporter.cs
- DispatcherFrame.cs
- CodeExporter.cs
- BuiltInPermissionSets.cs
- ParameterBuilder.cs
- validationstate.cs
- MediaContextNotificationWindow.cs
- IdentityManager.cs
- HierarchicalDataBoundControl.cs
- CompareInfo.cs
- Int32Rect.cs
- designeractionlistschangedeventargs.cs
- MLangCodePageEncoding.cs
- SqlBuffer.cs
- DefaultPropertyAttribute.cs
- ImageDrawing.cs
- CapabilitiesUse.cs
- TableRow.cs
- Exceptions.cs
- ChildTable.cs
- ColumnMapProcessor.cs
- EncryptionUtility.cs
- HMACSHA256.cs
- ContextMenuAutomationPeer.cs
- ClientOperationFormatterProvider.cs
- PropertyGridView.cs
- FixedSOMLineRanges.cs
- TakeQueryOptionExpression.cs
- HttpServerUtilityWrapper.cs