Collections Data Structure C#

/*==
== Copyright : BlueCurve (c)
== Licence   : Gnu/GPL v2.x
== Author    : Teddy Albina
== Email     : bluecurveteam@gmail.com
== Web site  : http://www.codeplex.com/BlueCurve
*/
using System;
using BlueCurve.Search.Common;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization.Formatters.Binary;
using System.IO;
namespace BlueCurve.Search.Common.PriorityQueue
{
    /// 
    /// Struct définissant un PriorityQueueItem
    /// 

    /// Clef
    /// Valeur
    [Serializable]
    public struct PriorityQueueItem
    {
        private TValue _value;
        public TValue Value
        {
            get { return _value; }
            set { _value = value; }
        }
        private TPriority _priority;
        public TPriority Priority
        {
            get { return _priority; }
            set { _priority = value; }
        }
        internal PriorityQueueItem(TValue val, TPriority pri)
        {
            this._value = val;
            this._priority = pri;
        }
    }
    /// 
    /// Fournit une implémentation de priorityQueue
    /// 

    /// Type de clef
    /// Type de valeur
    [Serializable]
    public class PriorityQueue : ICollection , IEnumerable>
    {
        /// 
        /// This features enable the priority queue to increment automaticaly
        /// the priority of the item
        /// 

        private PriorityQueueItem[] items;
        /// 
        /// Default capacity of the queue
        /// 

        private const Int32 DefaultCapacity = 1024;
        /// 
        /// Capacity of the queue
        /// 

        private Int32 capacity;
        /// 
        /// Numbers of items in the queue
        /// 

        private Int32 numItems;
        /// 
        /// Comparison delegate
        /// 

        private Comparison compareFunc;
        /// 
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the default initial capacity, and uses the default IComparer.
        /// 

        public PriorityQueue()
            : this(DefaultCapacity, Comparer.Default)
        {
        }
        public PriorityQueue(Int32 initialCapacity)
            : this(initialCapacity, Comparer.Default)
        {
        }
        public PriorityQueue(IComparer comparer)
            : this(DefaultCapacity, comparer)
        {
        }
        public PriorityQueue(int initialCapacity, IComparer comparer)
        {
            Init(initialCapacity, new Comparison(comparer.Compare));
        }
        public PriorityQueue(Comparison comparison)
            : this(DefaultCapacity, comparison)
        {
        }
        public PriorityQueue(int initialCapacity, Comparison comparison)
        {
            Init(initialCapacity, comparison);
        }
        private void Init(int initialCapacity, Comparison comparison)
        {
            numItems = 0;
            compareFunc = comparison;
            SetCapacity(initialCapacity);
        }
        public int Count
        {
            get { return numItems; }
        }
        public int Capacity
        {
            get { return items.Length; }
            set { SetCapacity(value); }
        }
        private void SetCapacity(int newCapacity)
        {
            int newCap = newCapacity;
            if (newCap < DefaultCapacity)
                newCap = DefaultCapacity;
            // throw exception if newCapacity < NumItems
            if (newCap < numItems)
                throw new ArgumentOutOfRangeException("newCapacity", "New capacity is less than Count");
            this.capacity = newCap;
            if (items == null)
            {
                items = new PriorityQueueItem[newCap];
                return;
            }
            // Resize the array.
            Array.Resize>(ref items, newCap);
        }
        public void Enqueue(PriorityQueueItem newItem)
        {
            if (numItems == capacity)
            {
                // need to increase capacity
                // grow by 50 percent
                SetCapacity((3 * Capacity) / 2);
            }
            int i = numItems;
            ++numItems;
            while ((i > 0) && (compareFunc(items[(i - 1) / 2].Priority, newItem.Priority) < 0))
            {
                items[i] = items[(i - 1) / 2];
                i = (i - 1) / 2;
            }
            items[i] = newItem;
        }
        /// 
        /// Permet d'ajouter des elements dans la pile
        /// 

        /// Clef
        /// Priorité
        public void Enqueue(TValue value, TPriority priority)
        {
            Enqueue(new PriorityQueueItem(value, priority));
        }
        /// 
        /// Permet de supprimer un intervale de la file d'attente
        /// 

        /// début de l'intervalle
        /// PriorityQueueItem
        private PriorityQueueItem RemoveAt(Int32 index)
        {
            PriorityQueueItem o = items[index];
            --numItems;
            // move the last item to fill the hole
            PriorityQueueItem tmp = items[numItems];
            // If you forget to clear this, you have a potential memory leak.
            items[numItems] = default(PriorityQueueItem);
            if (numItems > 0 && index != numItems)
            {
                // If the new item is greater than its parent, bubble up.
                int i = index;
                int parent = (i - 1) / 2;
                while (compareFunc(tmp.Priority, items[parent].Priority) > 0)
                {
                    items[i] = items[parent];
                    i = parent;
                    parent = (i - 1) / 2;
                }
                // if i == index, then we didn't move the item up
                if (i == index)
                {
                    // bubble down ...
                    while (i < (numItems) / 2)
                    {
                        int j = (2 * i) + 1;
                        if ((j < numItems - 1) && (compareFunc(items[j].Priority, items[j + 1].Priority) < 0))
                            ++j;
                        if (compareFunc(items[j].Priority, tmp.Priority) <= 0)
                            break;
                        items[i] = items[j];
                        i = j;
                    }
                }
                // Be sure to store the item in its place.
                items[i] = tmp;
            }
            return o;
        }
        /// 
        /// Vérifie que les données de la pile sont cohérentes
        /// 

        /// bool
        public bool VerifyQueue()
        {
            int i = 0;
            while (i < numItems / 2)
            {
                int leftChild = (2 * i) + 1;
                int rightChild = leftChild + 1;
                if (compareFunc(items[i].Priority, items[leftChild].Priority) < 0)
                    return false;
                if (rightChild < numItems && compareFunc(items[i].Priority, items[rightChild].Priority) < 0)
                    return false;
                ++i;
            }
            return true;
        }
        /// 
        /// Permet d'obtenir un élement
        /// 

        /// PriorityQueueItem
        public PriorityQueueItem Dequeue()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return RemoveAt(0);
        }
        /// 
        /// Removes the item with the specified value from the queue.
        /// The passed equality comparison is used.
        /// 

        /// The item to be removed.
        /// An object that implements the IEqualityComparer interface
        /// for the type of item in the collection.
        public void Remove(TValue item, IEqualityComparer comparer)
        {
            // need to find the PriorityQueueItem that has the Data value of o
            for (int index = 0; index < numItems; ++index)
            {
                if (comparer.Equals(item, items[index].Value))
                {
                    RemoveAt(index);
                    return;
                }
            }
            throw new ApplicationException("The specified itemm is not in the queue.");
        }
        /// 
        /// Removes the item with the specified value from the queue.
        /// The default type comparison function is used.
        /// 

        /// The item to be removed.
        public void Remove(TValue item)
        {
            Remove(item, EqualityComparer.Default);
        }
        /// 
        /// Permet d'obtenir le premier élement de la pile
        /// 

        /// PriorityQueueItem
        public PriorityQueueItem Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return items[0];
        }
        /// 
        /// Permet de vider la pile
        /// 

        public void Clear()
        {
            for (int i = 0; i < numItems; ++i)
            {
                items[i] = default(PriorityQueueItem);
            }
            numItems = 0;
            TrimExcess();
        }
        /// 
        /// Set the capacity to the actual number of items, if the current
        /// number of items is less than 90 percent of the current capacity.
        /// 

        public void TrimExcess()
        {
            if (numItems < (float)0.9 * capacity)
            {
                SetCapacity(numItems);
            }
        }
        /// 
        /// Permet de savoir si un élement existe dans la pile
        /// 

        /// element a tester
        /// bool
        public bool Contains(TValue o)
        {
            foreach (PriorityQueueItem x in items)
            {
                if (x.Value.Equals(o))
                    return true;
            }
            return false;
        }
        /// 
        /// Permet d'obtenir la priorité d'un element
        /// 

        /// element dont on veut la priorité
        /// TPriority
        public TPriority GetPriority(TValue key)
        {
            foreach (PriorityQueueItem x in items)
            {
                if (x.Value.Equals(key))
                    return x.Priority;
            }
            return default(TPriority);
        }
        /// 
        /// Permet de changer la priorité d'un élément
        /// 

        /// élement dont on veut changer la priorité
        /// nouvelle prioritée
        /// bool
        public bool SetPriority(TValue key, TPriority priority)
        {
            for (int i = 0; i < items.Length; i++)
            {
                PriorityQueueItem x = items[i];
                if (x.Value.Equals(key))
                {
                    Console.WriteLine(x.Value);
                    items[i].Priority = priority;
                    return true;
                }  
            }
            return false;
        }
        /// 
        /// Permet de copier les élements de la pile dans un PriorityQueueItem
        /// 

        /// PriorityQueueItem
        /// index de l'array a copier
        public void CopyTo(PriorityQueueItem[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex is less than 0.");
            if (array.Rank > 1)
                throw new ArgumentException("array is multidimensional.");
            if (numItems == 0)
                return;
            if (arrayIndex >= array.Length)
                throw new ArgumentException("arrayIndex is equal to or greater than the length of the array.");
            if (numItems > (array.Length - arrayIndex))
                throw new ArgumentException("The number of elements in the source ICollection is greater than the available space from arrayIndex to the end of the destination array.");
            for (int i = 0; i < numItems; i++)
            {
                array[arrayIndex + i] = items[i];
            }
        }
        #region ICollection Members
        /// 
        /// Permet de copier a partir d'un Array
        /// 

        /// pile source
        /// index source
        public void CopyTo(Array array, int index)
        {
            this.CopyTo((PriorityQueueItem[])array, index);
        }
        public bool IsSynchronized
        {
            get { return false; }
        }
        public object SyncRoot
        {
            get { return items.SyncRoot; }
        }
        #endregion
        #region IEnumerable> Members
        
        /// 
        /// Enumérateur de la pile
        /// 

        /// IEnumerator
        public IEnumerator> GetEnumerator()
        {
            for (int i = 0; i < numItems; i++)
            {
                yield return items[i];
            }
        }
        #endregion
        #region IEnumerable Members
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        #endregion
        #region 'Save'
        /// 
        /// Permet de sauvegarder la pile
        /// 

        /// bool
        public bool Save ()
        {
            try
            {
                using (Stream stream = File.Open("QueuePriority.bin", FileMode.Create, FileAccess.Write, FileShare.None))
                {
                    BinaryFormatter formatter = new BinaryFormatter();
                    formatter.Serialize(stream, items);
                    stream.Close();
                    stream.Dispose();
                }
                return true;
            }
            catch
            {
                return false;
            }
        }
        /// 
        /// Permet de restaures la pile de priorité
        /// 

        /// 
        public bool Reload()
        {
            PriorityQueueItem[] temp;
            try
            {
                using (Stream stream = File.Open("QueuePriority.bin", FileMode.Open, FileAccess.Read, FileShare.None))
                {
                    BinaryFormatter formatter = new BinaryFormatter();
                    temp = (PriorityQueueItem[])formatter.Deserialize(stream);
                    stream.Close();
                    stream.Dispose();
                }
                if (temp.Length > 0)
                    items = (PriorityQueueItem[])temp.Clone();
                return true;
            }
            catch
            {
                return false;
            }
        }          
        #endregion
    }
}