Immutability Matters
Enumeration of Queues

We previously enabled enumeration of our immutable stacks - we should do the same for our immutable queues. Unfortunately, it’s a bit more complicated this time around. (For those looking to the solution to the puzzle posed at the end of my earlier post, you’ll need to wait until next time - but read to the end of this post for a clue.)

To begin, we’ll modify our base interface to extend IEnumerable<T>.

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

We could take the same approach as we did earlier, creating a custom implementation of IEnumerator<T> and hooking it up to our queue. The implementation would look like this:

public class NaiiveEnumeratorOfImmutableQueue<T> : IEnumerator<T>
{
    // A reference to the queue we are enumerating
    private readonly IImmutableQueue<T> _queue;

    // Our current cursor position working through the queue
    private IImmutableQueue<T> _cursor;

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

    // Initialize a new enumerator
    public NaiiveEnumeratorOfImmutableQueue(
        IImmutableQueue<T> queue)
    {
        _queue = queue;
        _cursor = queue;
    }

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

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

        Current = _cursor.Head;
        _cursor = _cursor.Dequeue();
        return true;
    }

    // Reset to start iteration again
    public void Reset()
    {
        _cursor = _queue;
    }
}

This approach gives us a simple way to enumerate across the content of any implementation of IImmutableQueue<T>. I have the unit tests to prove that it works (more on those in a later post).

But there’s a real problem with this approach, one that didn’t affect us when we implemented enumeration for immutable stacks.

When we .Discard() the top item from an IImmutableStack<T>, our implementations always return an existing instance. There is no heap allocation going on. However, when we .Dequeue() the head item from an IImmutableQueue<T>, our current implementation returns a new instance representing the smaller queue. This means that every step of enumeration we do with this implementation is going to generate debris on our object heap, forcing the garbage collector to do more work, cleaning up after us more often. This may also promote other objects into higher generations of the heap, slowing their collection when they are eventually discarded.

Fortunately, there’s a much better way - for each kind of IImmutableQueue<T> to implement it’s own enumerator, in the same way as our stack .Reverse() method.

Enumeration of an EmptyImmutableQueue<T> is trivial:

// Return an enumerator for the items in this queue
public IEnumerator<T> GetEnumerator()
{
    yield break;
}

Enumeration of a SimpleImmutableQueue<T> is a little more complex, but not overly so. We need to return:

• The Head of the queue; then
• Each of the items in _outbound; then
• Each of the items in _inbound in reverse order.

// Return an enumerator for the items in this queue
public IEnumerator<T> GetEnumerator()
{
    yield return Head;

    foreach(var item in _outbound)
    {
        yield return item;
    }

    foreach(var item in _inbound.Reverse())
    {
        yield return item;
    }
}

This has a much lower object creation rate, leaving much less debris on our object heap and requiring garbage collection to happen much less frequently.

Is it perfect?

No, it’s not - it has a nasty flaw waiting to bite. Something that might not be discovered with test workloads, but only when production gets busy. In fact, this is the very same issue that I mentioned in my earlier post, talking about why the implementation of SimpleImmutableQueue<T> was unsuitable for production use. Have you solved that puzzle yet?