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:
Our constructor is marked internal because we want our consumers to use our factory methods to create instances.
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
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:
Dequeue() from a single item queue, we return an empty queue; when we
Enqueue() an item, we return a
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.