/*==
== 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
}
}