PriorityQueue.cs

Go to the documentation of this file.

using System;
using System.Collections;

namespace BenTools.Data
{
    public interface IPriorityQueue : ICollection, ICloneable, IList
    {
        int Push(object O);
        object Pop();
        object Peek();
        void Update(int i);
    }
    public class BinaryPriorityQueue : IPriorityQueue, ICollection, ICloneable, IList
    {
        protected ArrayList InnerList = new ArrayList();
        protected IComparer Comparer;

        #region contructors
        public BinaryPriorityQueue() : this(System.Collections.Comparer.Default)
        {}
        public BinaryPriorityQueue(IComparer c)
        {
            Comparer = c;
        }
        public BinaryPriorityQueue(int C) : this(System.Collections.Comparer.Default,C)
        {}
        public BinaryPriorityQueue(IComparer c, int Capacity)
        {
            Comparer = c;
            InnerList.Capacity = Capacity;
        }

        protected BinaryPriorityQueue(ArrayList Core, IComparer Comp, bool Copy)
        {
            if(Copy)
                InnerList = Core.Clone() as ArrayList;
            else
                InnerList = Core;
            Comparer = Comp;
        }

        #endregion
        protected void SwitchElements(int i, int j)
        {
            object h = InnerList[i];
            InnerList[i] = InnerList[j];
            InnerList[j] = h;
        }

        protected virtual int OnCompare(int i, int j)
        {
            return Comparer.Compare(InnerList[i],InnerList[j]);
        }

        #region public methods
        public int Push(object O)
        {
            int p = InnerList.Count,p2;
            InnerList.Add(O); // E[p] = O
            do
            {
                if(p==0)
                    break;
                p2 = (p-1)/2;
                if(OnCompare(p,p2)<0)
                {
                    SwitchElements(p,p2);
                    p = p2;
                }
                else
                    break;
            }while(true);
            return p;
        }

        public object Pop()
        {
            object result = InnerList[0];
            int p = 0,p1,p2,pn;
            InnerList[0] = InnerList[InnerList.Count-1];
            InnerList.RemoveAt(InnerList.Count-1);
            do
            {
                pn = p;
                p1 = 2*p+1;
                p2 = 2*p+2;
                if(InnerList.Count>p1 && OnCompare(p,p1)>0) // links kleiner
                    p = p1;
                if(InnerList.Count>p2 && OnCompare(p,p2)>0) // rechts noch kleiner
                    p = p2;
                
                if(p==pn)
                    break;
                SwitchElements(p,pn);
            }while(true);
            return result;
        }

        public void Update(int i)
        {
            int p = i,pn;
            int p1,p2;
            do  // aufsteigen
            {
                if(p==0)
                    break;
                p2 = (p-1)/2;
                if(OnCompare(p,p2)<0)
                {
                    SwitchElements(p,p2);
                    p = p2;
                }
                else
                    break;
            }while(true);
            if(p<i)
                return;
            do     // absteigen
            {
                pn = p;
                p1 = 2*p+1;
                p2 = 2*p+2;
                if(InnerList.Count>p1 && OnCompare(p,p1)>0) // links kleiner
                    p = p1;
                if(InnerList.Count>p2 && OnCompare(p,p2)>0) // rechts noch kleiner
                    p = p2;
                
                if(p==pn)
                    break;
                SwitchElements(p,pn);
            }while(true);
        }

        public object Peek()
        {
            if(InnerList.Count>0)
                return InnerList[0];
            return null;
        }

        public bool Contains(object value)
        {
            return InnerList.Contains(value);
        }

        public void Clear()
        {
            InnerList.Clear();
        }

        public int Count
        {
            get
            {
                return InnerList.Count;
            }
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return InnerList.GetEnumerator();
        }

        public void CopyTo(Array array, int index)
        {
            InnerList.CopyTo(array,index);
        }

        public object Clone()
        {
            return new BinaryPriorityQueue(InnerList,Comparer,true);    
        }

        public bool IsSynchronized
        {
            get
            {
                return InnerList.IsSynchronized;
            }
        }

        public object SyncRoot
        {
            get
            {
                return this;
            }
        }
        #endregion
        #region explicit implementation
        bool IList.IsReadOnly
        {
            get
            {
                return false;
            }
        }

        object IList.this[int index]
        {
            get
            {
                return InnerList[index];
            }
            set
            {
                InnerList[index] = value;
                Update(index);
            }
        }

        int IList.Add(object o)
        {
            return Push(o);
        }

        void IList.RemoveAt(int index)
        {
            throw new NotSupportedException();
        }

        void IList.Insert(int index, object value)
        {
            throw new NotSupportedException();
        }

        void IList.Remove(object value)
        {
            throw new NotSupportedException();
        }

        int IList.IndexOf(object value)
        {
            throw new NotSupportedException();
        }

        bool IList.IsFixedSize
        {
            get
            {
                return false;
            }
        }

        public static BinaryPriorityQueue Syncronized(BinaryPriorityQueue P)
        {
            return new BinaryPriorityQueue(ArrayList.Synchronized(P.InnerList),P.Comparer,false);
        }
        public static BinaryPriorityQueue ReadOnly(BinaryPriorityQueue P)
        {
            return new BinaryPriorityQueue(ArrayList.ReadOnly(P.InnerList),P.Comparer,false);
        }
        #endregion
    }
}