As we did previously with our regular immutable queue, we should start by considering the design of our external interface - our API. How do we want our users to create and interact with our priority queue?
Let’s begin with an interface declaration to define how to interact with a priority queue once created:
You might observe that this is very close to the declaration of
IImmutableQueue that we’ve previously explored. The primary difference is the inclusion of
Count, which we need later on to keep our queue internally balanced.
To create an empty priority queue, we’ll follow the pattern already used by other immutable types in .NET and create a factory method:
Unlike some other immutable types, our empty queues need a little configuration in the form of a the
comparer parameter. This uses one of the standard .NET delegate types,
Comparison<T>, allowing users to pass a comparison function or delegate of their choice to control how the priority queue orders items.
For convenience of our users, we should supply some alternative approaches for users to specify the priority of each item. Doing this makes it easier for our consumers to get the effect they want.
If our user already has an implementation of
IComparer<T> that they want to use, we can use its
Compare method as the comparison delegate:
If the items going into the queue are already naturally ordered in the desired sequence (e.g. classes like int or string that already implement
IComparable<T>), we can create the delegate ourselves:
When there’s already a property on our items that can be used to order, such as when we’re ordering cars by total distance travelled, we should allow users to specify a key value to use:
Note how we’ve used a local function to make it easier to read the code; I think this is better than writing a complicated delegate directly within the
With these four ways to create an empty priority queue, it should be easy for our users to get started without having to jump through any nasty hoops. Of course, before that can happen, we need to implement the actual queue ourselves.