Immutability Matters
Enumerating Stacks

The immutable stack implementation we wrote in Immutable Stacks doesn’t provide consumers with an easy way to iterate through everything on the stack. We can (and should) remedy this by implementing IEnumerable<T>.

Add IEnumerable<T> to the interface declaration:

public interface IImmutableStack<T> : IEnumerable<T>
{
    // ... elided ...
}

Since IEnumerable<T> extends IEnumerable, we have two very slightly different implementations needed, one with a generic type parameter and one without:

public IEnumerator<T> GetEnumerator()
{
    return new EnumeratorOfImmutableStack<T>(this);
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Since we’re not actually interested in the bare IEnumerable being visible on our implementation classes, we’ll make that version an explicit interface implementation. Note also that we need to implement the interface on both SimpleImmutableStack and EmptyImmutableStack, though both implementations will be identical.

The class EnumeratorOfImmutableStack is our actual implementation of the enumerator. I chose this name because ImmutableStackEnumerator seemed ambiguous - would a reader recognised it as an “enumerator of an immutable stack” or as an “immutable enumerator of a stack”. Being more explicit seemed advisable, even though the class is an implementation detail.

internal class EnumeratorOfImmutableStack<T> : IEnumerator<T>
{
    // Reference to the remaining stack to traverse
    private IImmutableStack<T> _rest;

    // Reference to the stack we are traversing
    private readonly IImmutableStack<T> _stack;

    // Current item for processing
    public T Current { get; private set; }
    object IEnumerator.Current => Current;

    // Initialize a new enumerator
    public EnumeratorOfImmutableStack(IImmutableStack<T> stack)
    {
        _rest = stack;
        _stack = stack;
    }

    // Nothing to dispose
    public void Dispose() { }

    // Make the next item available as Current
    public bool MoveNext()
    {
        if (_rest.Empty)
        {
            return false;
        }

        Current = _rest.Peek;
        _rest = _rest.Discard();
        return true;
    }

    // Reset to start iteration again
    public void Reset()
    {
        _rest = _stack;
    }
}

Note that this implementation is pretty safe - once you’ve created the enumerator, it doesn’t matter what happens to the original stack. The immutability of the underlying stack gives us a high level of safety. Consider, for example, that we don’t need to snapshot a copy of the data to prevent it being modified, and we also don’t have to worry about getting the infamous “Collection was modified” exception. We can also hand off the enumeration to another thread without any concerns.

We need two implementatons for Current - one to satisfy the generic property from IEnumerable<T>, the other the non-generic property from IEnumerable. As before, we make the one from the older IEnumerable interface an explicit implementation.

The contract for IEnumerable<T> requires a call to MoveNext() before the value in Current is defined; prior to that, trying to read the property has undefined behaviour. I figure that means it’s ok to throw an exception if something goes wrong, so there are no safety checks here.

Supporting Reset() is optional, and it’s therefore seldom used. However, given it was easy and cheap to do, I don’t see a reason to leave it out. A variation that didn’t support Reset() wouldn’t need to keep a reference to the original stack in _stack.