Skip to content

Instantly share code, notes, and snippets.

@grnde
Last active March 6, 2020 21:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save grnde/a35359f963348c9b8873b491e2d863d1 to your computer and use it in GitHub Desktop.
Save grnde/a35359f963348c9b8873b491e2d863d1 to your computer and use it in GitHub Desktop.
My current implementation of a stack that forgets the oldest element if the maximum capacity is reached.
/// <summary>
/// Represents a fixed size last-in-first-out (LIFO) collection of instances of the same specified type.
/// Removes the oldest element when the stack reaches the maximum capacity.
/// </summary>
/// <typeparam name="T">Specifies the type of elements in the stack.</typeparam>
public partial class CircularStack<T> : IEnumerable<T>
{
/// <summary>
/// Holds the stack elements.
/// </summary>
private T[] elements;
/// <summary>
/// Points always at the next to use index in the <see cref="elements"/> array.
/// Equals <see cref="tail"/> if stack is full or empty.
/// </summary>
private Index head;
/// <summary>
/// Points always at the last used index in the <see cref="elements"/> array.
/// Equals <see cref="head"/> if stack is full or empty.
/// </summary>
private Index tail;
/// <summary>
/// Flag to determine if stack is full. Is updated on each <see cref="Push"/> and <see cref="Pop"/> call.
/// </summary>
private bool full = false;
/// <summary>
/// Defines the minimum capacity of the stack.
/// </summary>
private const int MIN_CAPACITY = 1;
/// <summary>
/// When resizing the <see cref="elements">element</see> array this value defines the growth or shrink value.
/// </summary>
private const int CHUNK_SIZE = 4;
/// <summary>
/// Each call that changes the stack increments the version. If the stack is changed while enumeration,
/// the enumerator will throw an exception.
/// </summary>
private uint version = 0;
/// <summary>
/// Initializes a new instance of the stack class that is empty and has the specified maximal capacity.
/// </summary>
/// <param name="capacity">The maximum number of elements that the stack can contain.</param>
public CircularStack(int capacity)
{
if(capacity < MIN_CAPACITY)
throw new ArgumentOutOfRangeException(nameof(capacity), capacity, $"{nameof(capacity)} is less than '{MIN_CAPACITY}'.");
Capacity = capacity;
elements = new T[Math.Min(Capacity, CHUNK_SIZE)];
head = new Index(Capacity);
tail = new Index(Capacity);
}
/// <summary>
/// Pushes an <paramref name="element"/> at the top of the stack.
/// If the max <see cref="Capacity">capacity</see> is reached, the oldest element
/// is removed from the stack.
/// </summary>
public void Push(T element)
{
elements[head++] = element;
if(full)
tail++;
full = head == tail;
EnsureCapacity();
IncrementVersion();
}
private void EnsureCapacity()
{
if(Size == Capacity)
return;
if(Size > head)
return;
Array.Resize(ref elements, Math.Min(Capacity, Size + CHUNK_SIZE));
}
private void IncrementVersion()
=> version = unchecked(version + 1);
/// <summary>
/// Removes the last <see cref="Push">pushed</see> element from the stack and returns it.
/// </summary>
/// <returns>The last <see cref="Push">pushed</see> element.</returns>
/// <exception cref="InvalidOperationException">Thrown if the stack is empty.</exception>
public T Pop()
{
if(IsEmpty())
throw new InvalidOperationException();
T element = elements[--head];
elements[head] = default;
full = false;
IncrementVersion();
return element;
}
/// <summary>
/// Determines whether an element is in the stack.
/// </summary>
/// <param name="element">The object to locate in the stack. Can be <see langword="null"/></param>
/// <returns><see langword="true"/>, if the object is found in the stack; otherwise <see langword="false"/></returns>
public bool Contains(T element)
{
Index index = tail;
Func<bool> containsElement = element == null
? new Func<bool>(() => elements[index] == null)
: new Func<bool>(() => elements[index]?.Equals(element) ?? false);
for(int elementsToCompare = Count(); elementsToCompare > 0; index++, elementsToCompare--)
if(containsElement())
return true;
return false;
}
/// <summary>
/// Checks if the stack is empty.
/// </summary>
public bool IsEmpty()
=> !full && head == tail;
/// <summary>
/// Checks if the stack is full.
/// </summary>
public bool IsFull()
=> full;
/// <summary>
/// Calculates the number of elements currently stored in the stack.
/// </summary>
public int Count()
{
if(full)
return Capacity;
return head >= tail
? head - tail
: Capacity + head - tail;
}
/// <summary>
/// Removes all elements from the stack.
/// </summary>
public void Clear()
{
Array.Clear(elements, 0, Count());
head = tail;
full = false;
IncrementVersion();
}
/// <summary>
/// Trims the size of the stack if the current size is greater 4,
/// it's fill level is less then 90 percent
/// and the new size is at least 10 percent less then the current.
/// </summary>
public void TrimExcess()
{
const double TRIMEXCESS_LEVEL_LIMIT = 0.9;
if(Size <= CHUNK_SIZE)
return;
int elementCount = Count();
if((double)elementCount / (double)Size > TRIMEXCESS_LEVEL_LIMIT)
return;
var newSize = Math.Min(Size, (elementCount + CHUNK_SIZE) - ((elementCount + CHUNK_SIZE) % CHUNK_SIZE));
if((double)newSize / (double)Size > TRIMEXCESS_LEVEL_LIMIT)
return;
var newElements = new T[newSize];
if(head < tail)
{
Array.Copy(elements, tail, newElements, destinationIndex: 0, Size - tail);
Array.Copy(elements, sourceIndex: 0, newElements, Size - tail, head);
}
else
Array.Copy(elements, tail, newElements, 0, elementCount);
tail = new Index(Capacity);
head = tail.Add(elementCount);
elements = newElements;
IncrementVersion();
}
/// <summary>
/// The defined maximum of elements the stack can hold.
/// </summary>
public int Capacity { get; }
/// <summary>
/// Represents the current maximum of elements the stack can hold.
/// Increases with the <see cref="Count">element count</see>
/// until the defined <see cref="Capacity">capacity</see> is reached.
/// </summary>
public int Size => elements.Length;
}
public partial class CircularStack<T>
{
IEnumerator<T> IEnumerable<T>.GetEnumerator()
=> new Enumerator(this);
IEnumerator IEnumerable.GetEnumerator()
=> new Enumerator(this);
/// <summary>
/// Implements <see cref="IEnumerator{T}"/> for a <see cref="CircularStack{T}"/>.
/// </summary>
private class Enumerator : IEnumerator<T>
{
/// <summary>
/// The <see cref="CircularStack{T}"/> to enumerate.
/// </summary>
private readonly CircularStack<T> stack;
/// <summary>
/// The version of the <see cref="CircularStack{T}"/> at the <see cref="Enumerator"/> initialization.
/// </summary>
private readonly uint version;
/// <summary>
/// Flag that indicates if the enumeration can't move next.
/// </summary>
private bool done;
/// <summary>
/// Index of the start element to enumerate.
/// </summary>
Index tail;
/// <summary>
/// Index of the last element to enumerate.
/// </summary>
Index head;
/// <summary>
/// Initializes a new instance of the <see cref="Enumerator"/> class.
/// </summary>
/// <param name="stack">The <see cref="CircularStack{T}"/> to enumerate.</param>
public Enumerator(CircularStack<T> stack)
{
this.stack = stack ?? throw new ArgumentNullException(nameof(stack));
this.version = stack.version;
Reset();
}
public void Reset()
{
if(version != stack.version)
throw new InvalidOperationException();
done = stack.IsEmpty();
head = stack.head;
tail = stack.tail;
Current = default;
}
public bool MoveNext()
{
if(version != stack.version)
throw new InvalidOperationException();
if(done)
return false;
Current = stack.elements[tail++];
done = head == tail;
return true;
}
public void Dispose() => Current = default;
public T Current { get; private set; }
object IEnumerator.Current => Current;
}
}
public partial class CircularStack<T>
{
/// <summary>
/// Defines an index for a circular array access.
/// </summary>
[DebuggerDisplay("Index = {index}")]
private struct Index
{
/// <summary>
/// Current index value.
/// </summary>
private int index;
/// <summary>
/// Represents the total number of elements in an array.
/// </summary>
private readonly int lenght;
/// <summary>
/// Initializes a new instance of the <see cref="Index"/> class that current value is zero and has a specified length.
/// </summary>
/// <param name="length">The length of the represented array.</param>
public Index(int length)
: this(0, length)
{ }
/// <summary>
/// Initializes a new instance of the <see cref="Index"/> class with a current value and has a specified length.
/// </summary>
/// <param name="index">Start value of the <see cref="Index"/> class.</param>
/// <param name="length">The length of the represented array.</param>
/// <exception cref="ArgumentOutOfRangeException">Thrown when <paramref name="length"/> is less or equals zero.</exception>
/// <exception cref="ArgumentOutOfRangeException">Thrown when <paramref name="index"/> is greater or equals <paramref name="length"/>.</exception>
private Index(int index, int length)
{
if(length <= 0)
throw new ArgumentOutOfRangeException(nameof(length), length, $"{nameof(length)} is less or equals zero.");
if(index >= length)
throw new ArgumentOutOfRangeException(nameof(index), index, $"{nameof(index)} is greater or equals {nameof(length)}.");
this.lenght = length;
this.index = index;
}
public Index Add(int count)
=> new Index((this.index + count) % this.lenght, this.lenght);
/// <summary>
/// Defines the increment operator of the <see cref="Index"/>. If the upper bound is exceeded, the value
/// is set to zero.
/// </summary>
public static Index operator ++(Index item)
=> item.Add(1);
/// <summary>
/// Defines the decrement operator of the <see cref="Index"/>. If the lower bound is exceeded, the value
/// is set to the upper index value.
/// </summary>
public static Index operator --(Index value)
{
int index = value.index - 1;
if(index < 0)
index += value.lenght;
return new Index(index, value.lenght);
}
public static implicit operator int(Index index)
=> index.index;
public static bool operator ==(Index a, Index b)
=> a.index == b.index;
public static bool operator !=(Index a, Index b)
=> a.index != b.index;
public static bool operator >(Index a, Index b)
=> a.index > b.index;
public static bool operator <(Index a, Index b)
=> a.index < b.index;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment