PriorityQueue.cs

Go to the documentation of this file.

/*
 PriorityQueue.cs - C# implementation of a binary min-heap based generic priority queue.

 Copyright (C) 2012   Peter Graf

 This file is part of PBL - The Program Base Library.
 PBL is free software.

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 For more information on the Program Base Library or Peter Graf,
 please see: https://www.mission-base.com/.

 $Log: PriorityQueue.cs,v $
 Revision 1.3  2012/12/11 00:44:32  peter
 Added documentation comments.

 Revision 1.2  2012/12/09 02:40:28  peter
 Better exception handling

 Revision 1.1  2012/12/09 01:19:23  peter
 Initial Version

 */

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.Diagnostics;

namespace Com.Mission_Base.Pbl
{
    [Serializable]
    [ComVisible(false)]
    [DebuggerDisplay("Count = {Count}")]
    public class PriorityQueue<T> : List<T>, IList<T> where T : IComparable<T>
    {
        private readonly object _lock;
        private readonly IComparer<T> _comparer;

        #region Heap handling

        private int CompareItems(T left, T right)
        {
            if (_comparer == null)
            {
                if (left == null)
                {
                    if (right == null)
                    {
                        return 0;
                    }
                    return -1;
                }
                return left.CompareTo(right);
            }
            return _comparer.Compare(left, right);
        }

        private int LastParentIndex
        {
            // For zero based arrays all elements with an index bigger
            // than 'Count / 2 - 1' do not have any children
            get
            {
                return Count / 2 - 1;
            }
        }

        private void EnsureHeapConditionDownward(int index)
        {
            int lastParentIndex = LastParentIndex;
            if (index <= lastParentIndex)
            {
                var entry = base[index];

                // As long as the entry has at least one child
                //
                while (index <= lastParentIndex)
                {
                    // For zero based arrays the left child is at '2 * index + 1'
                    //
                    int childIndex = 2 * index + 1;

                    var child = base[childIndex];

                    // If the entry also has a right child, the smaller child
                    // needs to be considered for the swap
                    //
                    if (childIndex < Count - 1)
                    {
                        // The right child is next to the left child in the array
                        //
                        int rightChildIndex = childIndex + 1;
                        var rightChild = base[rightChildIndex];

                        if (CompareItems(rightChild, child) < 0)
                        {
                            // Use the right child for the swap
                            //
                            child = rightChild;
                            childIndex = rightChildIndex;
                        }
                    }

                    if (CompareItems(entry, child) <= 0)
                    {
                        // The heap condition is fulfilled for the entry
                        //
                        return;
                    }

                    // Do the swap with the child
                    //
                    base[childIndex] = entry;
                    base[index] = child;

                    index = childIndex;
                }
            }

            // The entry does not have any children, therefore
            // the heap condition is fulfilled for the entry
        }

        private int EnsureHeapConditionUpward(int index)
        {
            if (index > 0)
            {
                var entry = base[index];

                // As long as the entry is not the top of the heap
                //
                while (index > 0)
                {
                    // For zero based arrays the parent index is '( index - 1 ) / 2'
                    //
                    int parentIndex = (index - 1) / 2;
                    var parent = this[parentIndex];

                    if (CompareItems(entry, parent) >= 0)
                    {
                        // The heap condition is fulfilled for the entry
                        //
                        return index;
                    }

                    // Do the swap with the parent
                    //
                    base[parentIndex] = entry;
                    base[index] = parent;

                    index = parentIndex;
                }
            }

            // The entry is the top of the heap
            //
            return index;
        }

        public void EnsureHeapCondition(int index)
        {
            int rc = EnsureHeapConditionUpward(index);
            if (rc == index)
            {
                EnsureHeapConditionDownward(index);
            }
        }

        public void EnsureHeapCondition()
        {
            // The heap condition is always fulfilled for entries without children,
            // therefore 'bottom-up heap construction' only needs to look
            // at elements that do have children
            //
            for (int index = LastParentIndex; index >= 0; index--)
            {
                EnsureHeapConditionDownward(index);
            }
        }

        private void HeapRemoveAt(int index)
        {
            if (index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException(string.Format("Index {0} is less than 0, or index is equal to or greater than priority queue count {1}.", index, Count));
            }
            else if (index == Count - 1)
            {
                base.RemoveAt(index);
                return;
            }

            // Remove the last entry in the list
            //
            base[index] = base[Count - 1];
            base.RemoveAt(Count - 1);

            if (Count > 1)
            {
                // Copying the values might have violated the heap condition
                // at position index, it needs to ensured
                //
                EnsureHeapCondition(index);
            }
        }
        #endregion

        #region Constructors

        public PriorityQueue()
        {
            _lock = new object();
        }

        public PriorityQueue(IEnumerable<T> enumerable)
            : base(enumerable)
        {
            _lock = new object();
            EnsureHeapCondition();
        }

        public PriorityQueue(Int32 capacity)
            : base(capacity)
        {
            _lock = new object();
        }

        public PriorityQueue(IComparer<T> comparer)
        {
            _comparer = comparer;
            _lock = new object();
        }

        public PriorityQueue(IEnumerable<T> enumerable, IComparer<T> comparer)
            : base(enumerable)
        {
            _comparer = comparer;
            _lock = new object();
            EnsureHeapCondition();
        }

        public PriorityQueue(Int32 capacity, IComparer<T> comparer)
            : base(capacity)
        {
            _comparer = comparer;
            _lock = new object();
        }
        #endregion

        #region Queue methods

        public void Enqueue(T item)
        {
            base.Add(item);
            EnsureHeapConditionUpward(Count - 1);
        }

        public T Dequeue()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("The priority queue is empty.");
            }
            var result = base[0];
            HeapRemoveAt(0);
            return result;
        }

        public T Peek()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("The priority queue is empty.");
            }
            return base[0];
        }
        #endregion

        #region List methods


        public new T this[int index]
        {
            get { return base[index]; }
            set
            {
                base[index] = value;
                EnsureHeapCondition(index);
            }
        }

        public new void Add(T item)
        {
            Enqueue(item);
        }

        public new void AddRange(IEnumerable<T> collection)
        {
            base.AddRange(collection);
            EnsureHeapCondition();
        }

        public new void Insert(int index, T item)
        {
            Enqueue(item);
        }

        public new void InsertRange(int index, IEnumerable<T> collection)
        {
            base.InsertRange(index, collection);
            EnsureHeapCondition();
        }

        public new void RemoveAt(int index)
        {
            HeapRemoveAt(index);
        }

        public new bool Remove(T item)
        {
            int index = IndexOf(item);
            if (index < 0)
            {
                return false;
            }
            HeapRemoveAt(index);
            return true;
        }

        public new int RemoveAll(Predicate<T> match)
        {
            var result = base.RemoveAll(match);
            if (result > 0)
            {
                EnsureHeapCondition();
            }
            return result;
        }

        public new void RemoveRange(int index, int count)
        {
            base.RemoveRange(index, count);
            if (index > LastParentIndex)
            {
                EnsureHeapCondition();
            }
        }

        public new void Reverse()
        {
            if (Count > 1)
            {
                throw new InvalidOperationException("A priority queue cannot be reversed.");
            }
        }

        public new void Reverse(int index, int count)
        {
            if (index > LastParentIndex)
            {
                throw new InvalidOperationException("A priority queue cannot be partially reversed.");
            }
            base.Reverse(index, count);
        }

        public new void Sort()
        {
            if (Count > 1)
            {
                if (_comparer != null)
                {
                    base.Sort(_comparer);
                }
                else
                {
                    base.Sort();
                }
            }
        }

        public new void Sort(IComparer<T> comparer)
        {
            if (Count > 1)
            {
                if (!ReferenceEquals(comparer, _comparer))
                {
                    throw new InvalidOperationException("A priority queue cannot be sorted with a comparer other than the one specified for the priority queue.");
                }
                base.Sort(_comparer);
            }
        }

        public new void Sort(int index, int count, IComparer<T> comparer)
        {
            if (Count > 1)
            {
                if (!ReferenceEquals(comparer, _comparer) || index != 0 || count != Count)
                {
                    throw new InvalidOperationException("A priority queue cannot be partially sorted.");
                }
                base.Sort(index, count, _comparer);
            }
        }

        public new void Sort(Comparison<T> comparison)
        {
            if (Count > 1)
            {
                throw new InvalidOperationException("A priority queue cannot be sorted with a comparison.");
            }
        }
        #endregion

        #region Misc

        public object SyncRoot
        {
            get { return _lock; }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public IComparer<T> Comparer { get { return _comparer; } }

        #endregion
    }
}