Saturday 17 November 2018
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.
Comments
blog comments powered by Disqus