Last active
March 6, 2020 21:28
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// <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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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