SemiMutableStack.cs

/// <summary>
/// A hybrid immutable-mutable stack. It is an immutable chain with a regular mutable stack appended at the tail.
/// Each immutable chain can point to a parent chain of the same kind.
/// You can push and pop to the mutable part like a regular stack without allocating new instances.
/// You can also get an immutable snapshot at any time.
/// Getting a snapshot collapses the current mutable part and allocates the immutable chain appended to the current chain.
/// Popping from an immutable chain just returns the parent and doesn't allocate.
/// You can continue pushing and popping on every immutable instance,
/// but this only affects the mutable part, the immutable part doesn't change.
/// </summary>
/// <remarks>This is useful when traversing a tree, where you need to store the parent chain only for some nodes.
/// You avoid allocating immutable chains for subtrees that don't need it. For a node that needs it, the current
/// mutable stack is collapsed, and the immutable chain is materialized and stored. Once an immutable chain is stored,
/// its mutable stack continues to be utilized for further traversal, until another node collapses it again.
/// The same mutable stack instance is passed around and reused during traversal.
/// This data structure is deliberately not thread-safe and will break horribly with any concurrent use.
/// It is also only designed to push to the latest instance, as the mutable instance is reused
/// to avoid allocating it for every new snapshot.
/// </remarks>
public class SemiMutableStack<T>
{
    public T Value { get; set; }
    public SemiMutableStack<T> Parent { get; set; }

    protected List<T> Mutable { get; set; }

    public SemiMutableStack(T value = default, SemiMutableStack<T> parent = null)
    {
        Value = value;
        Parent = parent;
    }

    public void Push(T value)
    {
        Mutable ??= [];
        Mutable.Add(value);
    }

    public SemiMutableStack<T> Pop()
    {
        var mutable = Mutable;
        int count = mutable?.Count ?? 0;
        if (count > 0)
        {
            mutable.RemoveAt(count - 1);
            return this;
        }

        if (Parent != null)
        {
            // if the parent doesn't have a mutable instance, reuse the current one
            // since we likely no longer need it.
            if (Parent.Mutable == null)
            {
                Parent.Mutable = Mutable;
            }

            // Release our mutable stack because it's unlikely this instance will be pushed to again
            Mutable = null;
            return Parent;
        }

        throw new InvalidOperationException("Attempted to Pop from an empty stack");
    }

    public SemiMutableStack<T> GetImmutableSnapshot()
    {
        var current = this;

        var mutable = Mutable;
        if (mutable != null)
        {
            for (int i = 0; i < mutable.Count; i++)
            {
                var item = mutable[i];
                current = Create(item, current);
            }

            Mutable.Clear();
            Mutable = null;

            // Pass the current mutable instance to the new immutable one for reuse
            current.Mutable = mutable;
        }

        return current;
    }

    protected virtual SemiMutableStack<T> Create(T item, SemiMutableStack<T> parent)
    {
        return new SemiMutableStack<T>(item, parent);
    }
}