//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
// PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
using System;
using System.Text;
using System.Collections;
namespace Ilog.Language.Util
{
/**
* This implements a stack of objects, with a finite capacity. If
* pushing a new object runs over the capacity, room is made for it by
* discarding the oldest object in the stack (returning it as the
* return value of the overflowing Push). This class is
* useful as a ``forgetful'' stack which may memorize objects only up
* to a finite history.
*
* @version Last modified on Sat May 28 15:42:05 2005 by hak
* @author Hassan Aït-Kaci
* @copyright © 2000 ILOG, S.A.
*/
public class FiniteStack : Listable
{
/**
* Constructs a FiniteStack object.
*/
public FiniteStack ()
{
container = new object[capacity];
}
/**
* Constructs a FiniteStack object of specified capacity.
*/
public FiniteStack (int capacity)
{
container = new object[this.capacity=capacity+1]; // plus one for the free cell.
}
private object[] container; // the stack elements container
private int capacity = 21; // total number of assignable slots + 1 free cell
private int free = 0; // index of the free cell
private int latest = 0; // most recently assigned slot
private int oldest = 0; // least recently assigned slot
/**
* Returns the index preceding the specified index,
* modulo capacity.
*/
private int Prec (int index)
{
return (index+capacity-1)%capacity;
}
/**
* Returns the index following the specified index,
* modulo capacity.
*/
private int Succ (int index)
{
return (index+1)%capacity;
}
// NB: The stack is empty iff free==latest; otherwise, free==Succ(latest).
/**
* Returns true iff this FiniteStack is empty.
*/
public bool IsEmpty
{
get { return (latest == free); } // NB: could be (oldest == free) as well.
}
/**
* Returns the current total number of assignable slots.
*/
public int Capacity ()
{
return capacity-1; // minus one for the free cell.
}
/**
* Returns the current number of assigned slots.
*/
public int Count
{
get
{
if (IsEmpty)
return 0;
int size = latest-oldest+1;
return size >= 0 ? size : capacity+size;
}
}
/**
* Returns true iff this FiniteStack is full.
*/
public bool IsFull
{
get { return (free == Prec(oldest)); }
}
/**
* Erases all entries of this FiniteStack.
*/
public void Clear ()
{
while (!IsEmpty)
Pop();
oldest = latest = free = 0;
}
/**
* Returns the latest object pushed onto this FiniteStack
* without removing it, or null if it is empty.
*/
public object Peek ()
{
return Latest;
}
/**
* Returns the latest object pushed onto this FiniteStack
* without removing it, or null if it is empty.
*/
public object Latest
{
get { return IsEmpty ? null : container[latest]; }
}
/**
* Returns the oldest object of this FiniteStack without
* removing it, or null if it is empty.
*/
public object Oldest
{
get { return IsEmpty ? null : container[oldest]; }
}
/**
* Returns the index of the latest object in this stack, or
* -1 if the stack is empty.
*/
public int LatestIndex
{
get { return IsEmpty ? -1 : latest; }
}
/**
* Returns the index of the oldest object in this stack, or
* -1 if the stack is empty.
*/
public int OldestIndex
{
get { return IsEmpty ? -1 : oldest; }
}
/**
* Returns true iff the specified index is between that of the
* oldest and the latest, inclusively, modulo capacity.
*/
private bool IsValidIndex (int index)
{
if (IsEmpty || index < 0 || index >= capacity)
return false;
if (oldest <= latest)
return (oldest <= index && index <= latest);
return !(free < index && index < oldest);
}
/**
* Returns the object at the specified index where 0 is
* the index of the oldest element, and Count-1 that of
* the latest element.
*/
public object this [int index]
{
get
{
return container[(oldest+index)%capacity];
}
}
/**
* Removes and returns the latest object pushed onto this
* FiniteStack; returns null if it is empty.
*/
public object Pop ()
{
if (IsEmpty)
return null;
object value = container[latest];
container[latest] = null;
free = latest;
if (latest != oldest)
latest = Prec(latest);
return value;
}
/**
* Removes and returns the oldest object of this FiniteStack;
* returns null if it is empty.
*/
public object Drop ()
{
if (IsEmpty)
return null;
object value = container[oldest];
container[oldest] = null;
if (oldest == latest)
free = oldest;
else
oldest = Succ(oldest);
return value;
}
/**
* Pushes the specified object onto this FiniteStack. If
* the capacity is exceeded, removes and returns the oldest object
* in the stack. Otherwise, returns null.
*/
public object Push (object obj)
{
object spill = null;
if (IsFull)
{
spill = container[oldest];
oldest = Succ(oldest);
}
container[latest = free] = obj;
free = Succ(free);
return spill;
}
/**
* Sets the total number of assignable slots to the specified
* capacity. If the current number of assigned slots is larger
* than the specified capacity, slots older than the specified
* capacity are lost.
*/
public void SetCapacity (int capacity)
{
object[] container = new object[capacity+1]; // plus one for the free cell.
int size = Math.Min(Count,capacity);
int j = latest;
for (int i = size-1; i >= 0; i--)
{
container[i] = this.container[j];
j = Prec(j);
}
this.container = container;
this.capacity = capacity+1;
oldest = 0;
latest = size-1;
free = size;
}
/**
* Resizes this FiniteStack's container to the current
* number of assigned slots. If the stack is empty or full, then
* this does nothing.
*/
public void SetToSize ()
{
if (IsEmpty || IsFull)
return;
SetCapacity(Count);
}
/**
* Returns a string representation of this FiniteStack.
* The stack elements are listed from newest to oldest.
*/
public override string ToString ()
{
StringBuilder s = new StringBuilder("[");
string sep = "";
foreach (object elt in this)
{
s.Append(sep).Append(elt);
sep = ", ";
}
s.Append("]");
return s.ToString();
}
/**
* Returns an IEnumerator for this FiniteStack. The
* stack elements are visited from latest to oldest.
*/
public IEnumerator GetEnumerator ()
{
return new FiniteStackEnumerator(this);
}
/**
* This class implements an IEnumerator for a finite stack.
*/
private class FiniteStackEnumerator : IEnumerator
{
/**
* Constructs an enumerator for the specified finite stack.
*/
public FiniteStackEnumerator (FiniteStack stack)
{
this.stack = stack;
next = stack.latest;
}
/**
* The finite stack.
*/
private FiniteStack stack;
/**
* The next index to enumerate.
*/
private int next;
/**
* The current element being enumerated.
*/
private object current = null;
public object Current
{
get { return current; }
}
/**
* Advances to the next element, returning true if there is
* one, false otherwise.
*/
public bool MoveNext ()
{
if (next == stack.free || stack.container[next] == null)
return false;
current = stack.container[next];
next = stack.Prec(next);
return true;
}
/**
* Resets this enumerator to its beginning.
*/
public void Reset ()
{
next = stack.latest;
current = null;
}
}
}
}