using System;
using System.Collections;
namespace KillerInstinct.AI{
/// <summary>
/// The Heap allows to maintain a list sorted as long as needed.
/// If no IComparer interface has been provided at construction, then the list expects the Objects to implement IComparer.
/// If the list is not sorted it behaves like an ordinary list.
/// When sorted, the list's "Add" method will put new objects at the right place.
/// As well the "Contains" and "IndexOf" methods will perform a binary search.
/// </summary>
public class Heap : IList, ICloneable
{
#region Private Members
private ArrayList FList;
private IComparer FComparer = null;
private bool FUseObjectsComparison;
#endregion
#region Constructors
/// <summary>
/// Default constructor.
/// Since no IComparer is provided here, added objects must implement the IComparer interface.
/// </summary>
public Heap()
{
InitProperties(null, 0);
}
/// <summary>
/// Constructor.
/// Since no IComparer is provided, added objects must implement the IComparer interface.
/// </summary>
/// <param name="Capacity">Capacity of the list (<see cref="ArrayList.Capacity">ArrayList.Capacity</see>)</param>
public Heap(int Capacity)
{
InitProperties(null, Capacity);
}
/// <summary>
/// Constructor.
/// </summary>
/// <param name="Comparer">Will be used to compare added elements for sort and search operations.</param>
public Heap(IComparer Comparer)
{
InitProperties(Comparer, 0);
}
/// <summary>
/// Constructor.
/// </summary>
/// <param name="Comparer">Will be used to compare added elements for sort and search operations.</param>
/// <param name="Capacity">Capacity of the list (<see cref="ArrayList.Capacity">ArrayList.Capacity</see>)</param>
public Heap(IComparer Comparer, int Capacity)
{
InitProperties(Comparer, Capacity);
}
#endregion
#region Properties
/// <summary>
/// If set to true, it will not be possible to add an object to the list if its value is already in the list.
/// </summary>
public bool AddDuplicates
{
set
{
FAddDuplicates = value;
}
get
{
return FAddDuplicates;
}
}
private bool FAddDuplicates;
/// <summary>
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public int Capacity
{
get
{
return FList.Capacity;
}
set
{
FList.Capacity = value;
}
}
#endregion
#region IList Members
/// <summary>
/// IList implementation.
/// Gets object's value at a specified index.
/// The set operation is impossible on a Heap.
/// </summary>
/// <exception cref="ArgumentOutOfRangeException">Index is less than zero or Index is greater than Count.</exception>
/// <exception cref="InvalidOperationException">[] operator cannot be used to set a value on a Heap.</exception>
public object this[int Index]
{
get
{
if(Index >= FList.Count || Index < 0)
throw new ArgumentOutOfRangeException("Index is less than zero or Index is greater than Count.");
return FList[Index];
}
set
{
throw new InvalidOperationException("[] operator cannot be used to set a value in a Heap.");
}
}
/// <summary>
/// IList implementation.
/// Adds the object at the right place.
/// </summary>
/// <param name="O">The object to add.</param>
/// <returns>The index where the object has been added.</returns>
/// <exception cref="ArgumentException">The Heap is set to use object's IComparable interface, and the specifed object does not implement this interface.</exception>
public int Add(object O)
{
int Return = -1;
if (ObjectIsCompliant(O))
{
int Index = IndexOf(O);
int NewIndex = Index>=0 ? Index : -Index-1;
if (NewIndex>=Count) FList.Add(O);
else FList.Insert(NewIndex, O);
Return = NewIndex;
}
return Return;
}
/// <summary>
/// IList implementation.
/// Search for a specified object in the list.
/// If the list is sorted, a <see cref="ArrayList.BinarySearch">BinarySearch</see> is performed using IComparer interface.
/// Else the <see cref="Equals">Object.Equals</see> implementation is used.
/// </summary>
/// <param name="O">The object to look for</param>
/// <returns>true if the object is in the list, otherwise false.</returns>
public bool Contains(object O)
{
return FList.BinarySearch(O, FComparer)>=0;
}
/// <summary>
/// IList implementation.
/// Returns the index of the specified object in the list.
/// If the list is sorted, a <see cref="ArrayList.BinarySearch">BinarySearch</see> is performed using IComparer interface.
/// Else the <see cref="Equals">Object.Equals</see> implementation of objects is used.
/// </summary>
/// <param name="O">The object to locate.</param>
/// <returns>
/// If the object has been found, a positive integer corresponding to its position.
/// If the objects has not been found, a negative integer which is the bitwise complement of the index of the next element.
/// </returns>
public int IndexOf(object O)
{
int Result = -1;
Result = FList.BinarySearch(O, FComparer);
while(Result>0 && FList[Result-1].Equals(O))
Result--;
return Result;
}
/// <summary>
/// IList implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public bool IsFixedSize
{
get
{
return FList.IsFixedSize ;
}
}
/// <summary>
/// IList implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public bool IsReadOnly
{
get
{
return FList.IsReadOnly;
}
}
/// <summary>
/// IList implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public void Clear()
{
FList.Clear();
}
/// <summary>
/// IList implementation.
/// Cannot be used on a Heap.
/// </summary>
/// <param name="Index">The index before which the object must be added.</param>
/// <param name="O">The object to add.</param>
/// <exception cref="InvalidOperationException">Insert method cannot be called on a Heap.</exception>
public void Insert(int Index, object O)
{
throw new InvalidOperationException("Insert method cannot be called on a Heap.");
}
/// <summary>
/// IList implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
/// <param name="Value">The object whose value must be removed if found in the list.</param>
public void Remove(object Value)
{
FList.Remove(Value);
}
/// <summary>
/// IList implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
/// <param name="Index">Index of object to remove.</param>
public void RemoveAt(int Index)
{
FList.RemoveAt(Index);
}
#endregion
#region IList.ICollection Members
/// <summary>
/// IList.ICollection implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(Array array, int arrayIndex) { FList.CopyTo(array, arrayIndex); }
/// <summary>
/// IList.ICollection implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public int Count { get { return FList.Count; } }
/// <summary>
/// IList.ICollection implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public bool IsSynchronized { get { return FList.IsSynchronized; } }
/// <summary>
/// IList.ICollection implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
public object SyncRoot { get { return FList.SyncRoot; } }
#endregion
#region IList.IEnumerable Members
/// <summary>
/// IList.IEnumerable implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
/// <returns>Enumerator on the list.</returns>
public IEnumerator GetEnumerator()
{
return FList.GetEnumerator();
}
#endregion
#region IClonable Members
/// <summary>
/// ICloneable implementation.
/// Idem <see cref="ArrayList">ArrayList</see>
/// </summary>
/// <returns>Cloned object.</returns>
public object Clone()
{
Heap Clone = new Heap(FComparer, FList.Capacity);
Clone.FList = (ArrayList)FList.Clone();
Clone.FAddDuplicates = FAddDuplicates;
return Clone;
}
#endregion
#region Delegate Members
/// <summary>
/// Defines an equality for two objects
/// </summary>
public delegate bool Equality(object Object1, object Object2);
#endregion
#region Overridden Members
/// <summary>
/// Object.ToString() override.
/// Build a string to represent the list.
/// </summary>
/// <returns>The string refecting the list.</returns>
public override string ToString()
{
string OutString = "{";
for (int i=0; i<FList.Count; i++)
OutString += FList[i].ToString() + (i != FList.Count-1 ? "; " : "}");
return OutString;
}
/// <summary>
/// Object.Equals() override.
/// </summary>
/// <returns>true if object is equal to this, otherwise false.</returns>
public override bool Equals(object Object)
{
Heap SL = (Heap)Object;
if ( SL.Count!=Count )
return false;
for (int i=0; i<Count; i++)
if ( !SL[i].Equals(this[i]) )
return false;
return true;
}
/// <summary>
/// Object.GetHashCode() override.
/// </summary>
/// <returns>Hash code for this.</returns>
public override int GetHashCode()
{
return FList.GetHashCode();
}
#endregion
#region Public Members
/// <summary>
/// Idem IndexOf(object), but starting at a specified position in the list
/// </summary>
/// <param name="Object">The object to locate.</param>
/// <param name="Start">The index for start position.</param>
/// <returns></returns>
public int IndexOf(object Object, int Start)
{
int Result = -1;
Result = FList.BinarySearch(Start, FList.Count-Start, Object, FComparer);
while(Result > Start && FList[Result-1].Equals(Object))
Result--;
return Result;
}
/// <summary>
/// Idem IndexOf(object), but with a specified equality function
/// </summary>
/// <param name="Object">The object to locate.</param>
/// <param name="AreEqual">Equality function to use for the search.</param>
/// <returns></returns>
public int IndexOf(object Object, Equality AreEqual)
{
for (int i=0; i<FList.Count; i++)
if ( AreEqual(FList[i], Object) ) return i;
return -1;
}
/// <summary>
/// Idem IndexOf(object), but with a start index and a specified equality function
/// </summary>
/// <param name="Object">The object to locate.</param>
/// <param name="Start">The index for start position.</param>
/// <param name="AreEqual">Equality function to use for the search.</param>
/// <returns></returns>
public int IndexOf(object Object, int Start, Equality AreEqual)
{
if ( Start<0 || Start>=FList.Count ) throw new ArgumentException("Start index must belong to [0; Count-1].");
for (int i=Start; i<FList.Count; i++)
if ( AreEqual(FList[i], Object) ) return i;
return -1;
}
/// <summary>
/// The objects will be added at the right place.
/// </summary>
/// <param name="C">The object to add.</param>
/// <returns>The index where the object has been added.</returns>
/// <exception cref="ArgumentException">The Heap is set to use object's IComparable interface, and the specifed object does not implement this interface.</exception>
public void AddRange(ICollection C)
{
foreach(object Object in C)
Add(Object);
}
/// <summary>
/// Cannot be called on a Heap.
/// </summary>
/// <param name="Index">The index before which the objects must be added.</param>
/// <param name="C">The object to add.</param>
/// <exception cref="InvalidOperationException">Insert cannot be called on a Heap.</exception>
public void InsertRange(int Index, ICollection C)
{
throw new InvalidOperationException("Insert cannot be called on a Heap.");
}
/// <summary>
/// Limits the number of occurrences of a specified value.
/// Same values are equals according to the Equals() method of objects in the list.
/// The first occurrences encountered are kept.
/// </summary>
/// <param name="Value">Value whose occurrences number must be limited.</param>
/// <param name="NumberToKeep">Number of occurrences to keep</param>
public void LimitOccurrences(object Value, int NumberToKeep)
{
if(Value == null)
throw new ArgumentNullException("Value");
int Pos = 0;
while((Pos = IndexOf(Value, Pos)) >= 0)
{
if(NumberToKeep <= 0)
FList.RemoveAt(Pos);
else
{
Pos++;
NumberToKeep--;
}
if(FComparer.Compare(FList[Pos],Value) > 0 )
break;
}
}
/// <summary>
/// Removes all duplicates in the list.
/// Each value encountered will have only one representant.
/// </summary>
public void RemoveDuplicates()
{
int PosIt;
PosIt = 0;
while(PosIt < Count-1)
{
if(FComparer.Compare(this[PosIt],this[PosIt+1]) == 0 )
RemoveAt(PosIt);
else
PosIt++;
}
}
/// <summary>
/// Returns the object of the list whose value is minimum
/// </summary>
/// <returns>The minimum object in the list</returns>
public int IndexOfMin()
{
int RetInt = -1;
if (FList.Count > 0)
{
RetInt = 0;
object RetObj = FList[0];
}
return RetInt;
}
/// <summary>
/// Returns the object of the list whose value is maximum
/// </summary>
/// <returns>The maximum object in the list</returns>
public int IndexOfMax()
{
int RetInt = -1;
if(FList.Count > 0)
{
RetInt = FList.Count-1;
object RetObj = FList[FList.Count-1];
}
return RetInt;
}
/// <summary>
/// Returns the topmost object on the list and removes it from the list
/// </summary>
/// <returns>Returns the topmost object on the list</returns>
public object Pop()
{
if(FList.Count == 0)
throw new InvalidOperationException("The heap is empty.");
object Object = FList[Count-1];
FList.RemoveAt(Count-1);
return(Object);
}
/// <summary>
/// Pushes an object on list. It will be inserted at the right spot.
/// </summary>
/// <param name="Object">Object to add to the list</param>
/// <returns></returns>
public int Push(object Object)
{
return(Add(Object));
}
#endregion
#region Private Members
private bool ObjectIsCompliant(object Object)
{
if(FUseObjectsComparison && !(Object is IComparable))
throw new ArgumentException("The Heap is set to use the IComparable interface of objects, and the object to add does not implement the IComparable interface.");
if(!FAddDuplicates && Contains(Object))
return false;
return true;
}
private class Comparison : IComparer
{
public int Compare(object Object1, object Object2)
{
IComparable C = Object1 as IComparable;
return C.CompareTo(Object2);
}
}
private void InitProperties(IComparer Comparer, int Capacity)
{
if(Comparer != null)
{
FComparer = Comparer;
FUseObjectsComparison = false;
}
else
{
FComparer = new Comparison();
FUseObjectsComparison = true;
}
FList = Capacity > 0 ? new ArrayList(Capacity) : new ArrayList();
FAddDuplicates = true;
}
#endregion
}
}
|