Immutable Priority Queues
Queue Equality

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:

public interface IImmutablePriorityQueue<T> : 
    IEnumerable<T>, 
    IEquatable<IImmutablePriorityQueue<T>>

For our EmptyImmutableQueue<T>, the implementation is almost trivia. We start with the specific implementation required by our interface, then override object.Equals() to delegate appropriately.

public bool Equals(IImmutablePriorityQueue<T> other)
{
    if (other is EmptyImmutablePriorityQueue<T> empty)
    {
        return _comparer.Equals(empty._comparer);
    }

    return false;
}

public override bool Equals(object obj)
    => obj is IImmutablePriorityQueue<T> queue
       && Equals(queue);

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.

public bool Equals(IImmutablePriorityQueue<T> other)
{
    if (other is SingleItemImmutablePriorityQueue<T> single)
    {
        return Equals(Head, single.Head)
               && Equals(_comparer, single._comparer);
    }

    return false;
}

public override bool Equals(object obj)
    => obj is IImmutablePriorityQueue<T> queue
       && Equals(queue);

I’ll leave the implementation for DualItemImmutablePriorityQueue<T> as an exercise.

For BranchingImmutablePriorityQueue<T>, we can build on the pieces already in place to write a fairly simple implementation:

public bool Equals(IImmutablePriorityQueue<T> other)
{
    if (other is BranchingImmutablePriorityQueue<T> branch)
    {
        return Count == branch.Count
               && _comparer.Equals(branch._comparer)
               && this.SequenceEqual(branch);
    }

    return false;
}

public override bool Equals(object obj)
    => obj is IImmutablePriorityQueue<T> queue
       && Equals(queue);

We check 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.

All done.

Except for the bug. Can you identify the problem?