KeyedPriorityQueue.cs source code in C# .NET

                        Code:
                         / 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / WF / RunTime / KeyedPriorityQueue.cs / 1305376 / KeyedPriorityQueue.cs
                        
                        
                            // Copyright (c) Microsoft Corporation.  All rights reserved. 

using System;
using System.Diagnostics;
using System.Collections; 
using System.Collections.Generic;
using System.Collections.ObjectModel; 
 
namespace System.Workflow.Runtime
{ 
    internal sealed class KeyedPriorityQueueHeadChangedEventArgs : EventArgs where T : class
    {
        private T oldFirstElement;
        private T newFirstElement; 

        public KeyedPriorityQueueHeadChangedEventArgs(T oldFirstElement, T newFirstElement) 
        { 
            this.oldFirstElement = oldFirstElement;
            this.newFirstElement = newFirstElement; 
        }

        public T OldFirstElement { get { return oldFirstElement; } }
        public T NewFirstElement { get { return newFirstElement; } } 
    }
 
    ///  Combines the functionality of a dictionary and a heap-sorted priority queue. 
    /// Enqueue and Dequeue operations are O(log n), Peek is O(1) and Remove is O(n).
    /// Used by the SchedulerService classes to maintain an ordered list of running timers, etc. 
    /// Lesser priority values are higher priority.
    /// Key
    /// Value
    /// Priority 
    [Serializable]
    internal class KeyedPriorityQueue where V : class 
    { 
        private List> heap = new List>();
        private int size; 
        private Comparer priorityComparer = Comparer
.Default;
        private HeapNode placeHolder = default(HeapNode);

        public event EventHandler> FirstElementChanged; 

        public KeyedPriorityQueue() 
        { 
            heap.Add(default(HeapNode));       // Dummy zeroth element, heap is 1-based
        } 

        public void Enqueue(K key, V value, P priority)
        {
            V oldHead = size > 0 ? heap[1].Value : null; 
            int i = ++size;
            int parent = i / 2; 
            if (i == heap.Count) 
                heap.Add(placeHolder);
            while (i > 1 && IsHigher(priority, heap[parent].Priority)) 
            {
                heap[i] = heap[parent];
                i = parent;
                parent = i / 2; 
            }
            heap[i] = new HeapNode(key, value, priority); 
            V newHead = heap[1].Value; 
            if (!newHead.Equals(oldHead))
            { 
                RaiseHeadChangedEvent(oldHead, newHead);
            }
        }
 
        public V Dequeue()
        { 
            V oldHead = (size < 1) ? null : DequeueImpl(); 
            V newHead = (size < 1) ? null : heap[1].Value;
            RaiseHeadChangedEvent(null, newHead); 
            return oldHead;
        }

        private V DequeueImpl() 
        {
            Debug.Assert(size > 0, "Queue Underflow"); 
            V oldHead = heap[1].Value; 
            heap[1] = heap[size];
            heap[size--] = placeHolder; 
            Heapify(1);
            return oldHead;
        }
 

        public V Remove(K key) 
        { 
            if (size < 1)
                return null; 

            V oldHead = heap[1].Value;
            for (int i = 1; i <= size; i++)
            { 
                if (heap[i].Key.Equals(key))
                { 
                    V retval = heap[i].Value; 
                    Swap(i, size);
                    heap[size--] = placeHolder; 
                    Heapify(i);
                    V newHead = heap[1].Value;
                    if (!oldHead.Equals(newHead))
                    { 
                        RaiseHeadChangedEvent(oldHead, newHead);
                    } 
                    return retval; 
                }
            } 
            return null;
        }

        public V Peek() 
        {
            return (size < 1) ? null : heap[1].Value; 
        } 

        public int Count 
        {
            get { return size; }
        }
 
        public V FindByPriority(P priority, Predicate match)
        { 
            return size < 1 ? null : Search(priority, 1, match); 
        }
 
        public ReadOnlyCollection Values
        {
            get
            { 
                List values = new List();
                for (int i = 1; i <= size; i++) 
                { 
                    values.Add(heap[i].Value);
                } 
                return new ReadOnlyCollection(values);
            }
        }
 
        public ReadOnlyCollection Keys
        { 
            get 
            {
                List keys = new List(); 
                for (int i = 1; i <= size; i++)
                {
                    keys.Add(heap[i].Key);
                } 
                return new ReadOnlyCollection(keys);
            } 
        } 

        public void Clear() 
        {
            heap.Clear();
            size = 0;
        } 

        private void RaiseHeadChangedEvent(V oldHead, V newHead) 
        { 
            if (oldHead != newHead)
            { 
                EventHandler> fec = FirstElementChanged;
                if (fec != null)
                    fec(this, new KeyedPriorityQueueHeadChangedEventArgs(oldHead, newHead));
            } 
        }
 
        private V Search(P priority, int i, Predicate match) 
        {
            Debug.Assert(i >= 1 || i <= size, "Index out of range: i = " + i + ", size = " + size); 

            V value = null;
            if (IsHigher(heap[i].Priority, priority))
            { 
                if (match(heap[i].Value))
                    value = heap[i].Value; 
                int left = 2 * i; 
                int right = left + 1;
                if (value == null && left <= size) 
                    value = Search(priority, left, match);
                if (value == null && right <= size)
                    value = Search(priority, right, match);
            } 
            return value;
        } 
 
        private void Heapify(int i)
        { 
            Debug.Assert(i >= 1 || i <= size, "Index out of range: i = " + i + ", size = " + size);

            int left = 2 * i;
            int right = left + 1; 
            int highest = i;
            if (left <= size && IsHigher(heap[left].Priority, heap[i].Priority)) 
                highest = left; 
            if (right <= size && IsHigher(heap[right].Priority, heap[highest].Priority))
                highest = right; 
            if (highest != i)
            {
                Swap(i, highest);
                Heapify(highest); 
            }
 
        } 

        private void Swap(int i, int j) 
        {
            Debug.Assert(i >= 1 || j >= 1 || i <= size || j <= size, "Index out of range: i = " + i + ", j = " + j + ", size = " + size);

            HeapNode temp = heap[i]; 
            heap[i] = heap[j];
            heap[j] = temp; 
        } 

        protected virtual bool IsHigher(P p1, P p2) 
        {
            return (priorityComparer.Compare(p1, p2) < 1);
        }
 
        [Serializable]
        private struct HeapNode 
        { 
            public KK Key;
            public VV Value; 
            public PP Priority;

            public HeapNode(KK key, VV value, PP priority)
            { 
                Key = key;
                Value = value; 
                Priority = priority; 
            }
        } 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
KeyedPriorityQueue.cs source code in C# .NET

Source code for the .NET framework in C#

Code:

Link Menu
