As is always important, we need to implement hashing and equality. But what does equality mean for a queue?
Perhaps the most straightforward approach would be to use structural equality - two queues are equal if they have exactly the same items and internal structure. This would be simple to implement, but would it be correct?
Consider these two queues …
Both queues contain the same set of integer values, with the same priority rule. The only difference is the order that items were added to the queue.
From our perspective, looking at the internal structure of these queues, they clearly look different.
But to a consumer, both queues will return the same items in the same order. Either one could be used and the behaviour of the consuming code would be unchanged.
Our definition of equal needs to be based on external characteristics only.
The implementation process starts by adding to our interface:
EmptyImmutableQueue<T>, the implementation is almost trivia. We start with the specific implementation required by our interface, then override
object.Equals() to delegate appropriately.
Since the priority configured for each queue might be different, we need to check that the two
_comparer values are also equal.
When we have exactly one item in our queue (in
SingleItemImmutablePriorityQueue<T>), the code is also pretty simple.
I’ll leave the implementation for
DualItemImmutablePriorityQueue<T> as an exercise.
BranchingImmutablePriorityQueue<T>, we can build on the pieces already in place to write a fairly simple implementation:
Count first so that we can exit early if the queues are different sizes. If the queues are the same size, we use
SequenceEqual to see if both queues contain the same items in the same order.
You can probably see now why we covered queue enumeration earlier in this series.
Except for the bug. Can you identify the problem?