Immutable Priority Queues
Queue Enumeration

Sometimes our users might want to do something odd - like iterate the content of a queue without going to the hassle of dequeuing items one at a time. Fortunately, it’s not hard for us to support this.

We start by modifying our interface to indicate that we support enumeration:

public interface IImmutablePriorityQueue<T> : IEnumerable<T>

Perhaps the simplest implementation is to just take care of doing the dequeuing on behalf of the user. We need separate implementations for each kind of immutable priority queue.

For an empty queue, we need an enumerator that returns no items:

public IEnumerator<T> GetEnumerator()
{
    yield break;
}

It’s worth highlighting that our return type here is IEnumerator<T>, not IEnumerable<T>. The later is far more commonly used, but the former is supported is well. This is one of the little things that reflects the care with which features are added to the C# language.

A single item queue is just as simple:

public IEnumerator<T> GetEnumerator()
{
    yield return Head;
}

… and a dual item queue not much different …

public IEnumerator<T> GetEnumerator()
{
    yield return Head;
    yield return _rest;
}

… it’s only when we look at the branching queue that the implementation becomes anything non-trivial …

public IEnumerator<T> GetEnumerator()
{
    IImmutablePriorityQueue<T> queue = this;
    while (!queue.IsEmpty)
    {
        yield return queue.Head;
        queue = queue.Dequeue();
    }
}

Testing that these implementations work as expected, we can write a simple property test:

[Property]
public void EnumerationReturnsExpectedItemsInOrder(NonEmptyArray<string> values)
{
    var queue = Create(values.Item, StringComparer.OrdinalIgnoreCase.Compare);
    var expected = values.Item.ToList();
    expected.Sort(StringComparer.OrdinalIgnoreCase.Compare);

    queue.Should().Equal(
        expected,
        StringComparer.OrdinalIgnoreCase.Equals);
}

This is very similar to the earlier test QueueReturnsExpectedItemsInOrder, but without the overhead of separately extracting the items from the queue into a staging area before checking.