As we did with our original immutable queue, we’ll define dedicated implementations of IImmutablePriorityQueue<T> for handling empty and single item queues.

The implementation for an empty queue is as straightforward as you might expect:

public class EmptyImmutablePriorityQueue<T>
    : IImmutablePriorityQueue<T>
{
    private readonly Comparison<T> _comparer;

    internal EmptyImmutablePriorityQueue(Comparison<T> comparer)
    {
        _comparer = comparer 
            ?? throw new ArgumentNullException(nameof(comparer));
    }

Our constructor is marked internal because we want our consumers to use our factory methods to create instances.

    public T Head => throw new InvalidOperationException();
    public int Count => 0;
    public bool IsEmpty => true;

    public IImmutablePriorityQueue<T> Enqueue(T value)
        => new SingleItemImmutablePriorityQueue<T>(value, _comparer);

    public IImmutablePriorityQueue<T> Dequeue()
        => throw new InvalidOperationException();
}

Since the queue is empty, we throw an exception if someone tries to inspect our head element (that we don’t have), or if someone tries to dequeue from the empty queue. Alternatively, if we want to allow dequeing from an empty queue, we could return this from Dequeue().

Unlike our original immutable queue, we don’t cache a static empty queue for reuse - this is because each priority queue might have a different comparison rule used for ordering items.

The implementation of SingleItemImmutablePriorityQueue<T> is practically as simple:

public class SingleItemImmutablePriorityQueue<T>
    : IImmutablePriorityQueue<T>
{
    private readonly Comparison<T> _comparer;

    internal SingleItemImmutablePriorityQueue(
        T item, Comparison<T> comparer)
    {
        Head = item;
        _comparer = comparer;
    }

    public T Head { get; }
    public int Count => 1;
    public bool IsEmpty => false;

    public IImmutablePriorityQueue<T> Enqueue(T value)
        => new DualItemImmutablePriorityQueue<T>(value, this, _comparer);

    public IImmutablePriorityQueue<T> Dequeue()
        => new EmptyImmutablePriorityQueue<T>(_comparer);
}

When we Dequeue() from a single item queue, we return an empty queue; when we Enqueue() an item, we return a DualItemImmutablePriorityQueue<T>.

Next time, we’ll look at the implementation of DualItemImmutablePriorityQueue<T>, encountering our first application of queue invariants and using our comparison delegate for the first time.

About this series

An immutable implementation of a priority queue.

Posts in this series

Introducing the Priority Queue
Designing the External API
Dequeuing Values
Enqueuing Values
Simple Queues
Two Dual Item Queues
Creating Branching Nodes
Queue Testing
Prior post in this series:
Enqueuing Values
Next post in this series:
Two Dual Item Queues

Comments

blog comments powered by Disqus