Immutable Priority Queues
The Problem with Equality

Did you spot the problem with the implementation of queue equality that we developed last time? As with the other bug we’ve encountered, this one stems from the comparison function we use.

If you use a strict priority function (one that always orders items, never considering them equal), everything works perfectly well - two queues containing the same items and using the same priority function will be return all the items in strictly the same order.

But if the priority function only specifies a partial ordering, things can go awry with our equality definition.

A partial ordering is when you have some items that have the same priority as each other. When this happens, we’re saying that the order of these items does not matter and the code is free to return the items in any sequence at all.

We’ve seen this before, when we had a priority queue of strings - an IImmutablePriorityQueue<string> that was defined using StringComparer.OrdinalIgnoreCase.

Should we consider two queues equal, if they contain the same set of items, prioritized by the same ordering function, but they happen to return two of items with equal priority in a different order to each other?

I think we should.

But how do we compare these queues?

The key is to accept that items with the same priority to appear in any order and accommodate that in as we work through comparing pairs of items.

Let’s look at an example, comparing two case-insensitive alphabetical queues with the following items:

Initial State:

Both queue heads are identical, so we dequeue from both queues.

State after step 1:

The queue heads are not identical, but they have equal priority, so they might have exact matches to come. We stash them aside, and then dequeue from both queues.

State after step 2:

Again, the queue heads are not identical, but they have equal priority. We check to see if either queue head matches a stashed value from the other queue. The head of the left head is in our right stash, so we dequeue from the left queue and remove that value from our right stash.

State after step 3:

Our queue heads are now identical, so we dequeue from both queues. Our stashes remain the same.

State after step 4:

Our queue heads are not identical, but they have equal priority, so we check to see if either queue head matches a stashed value from the other queue. This time, we find that the head of our right queue is in the left stash, so we can dequeue from the right queue and remove it from the left stash.

State after step 5:

Both queues have an identical head, so we dequeue from both - and both queues are now empty.

Since both our stashes are also empty, we know that every item found a match in the other queue, and we can consider the queues equal.

Phew!

Here’s the implementation - it’s a bit long, but should be relatively straightforward to read.

public bool Equals(IImmutablePriorityQueue<T> other)
{
    // Can't be equal if `other` is null, or a different size, or a different type
    if (other is null 
        || Count != other.Count
        || GetType() != other.GetType())
    {
        return false;
    }

    // Can't be equal if the rule for prioritization is different
    var branch = (BranchingImmutablePriorityQueue<T>) other;
    if (!Equals(_comparer, branch._comparer))
    {
        return false;
    }

    IImmutablePriorityQueue<T> left = this;
    IImmutablePriorityQueue<T> right = branch;
    var leftStash = new List<T>();
    var rightStash = new List<T>();

    while (!left.IsEmpty && !right.IsEmpty)
    {
        // If both queue heads are equal, move on
        if (Equals(left.Head, right.Head))
        {
            left = left.Dequeue();
            right = right.Dequeue();
            continue;
        }

        // If the head of the left queue is in our right stash, move on
        if (rightStash.Contains(left.Head))
        {
            rightStash.Remove(left.Head);
            left = left.Dequeue();
            continue;
        }

        // If the head of the right queue is in our left stash
        if (leftStash.Contains(right.Head))
        {
            leftStash.Remove(right.Head);
            right = right.Dequeue();
            continue;
        }

        // If queue heads have different priority, not equal
        if (_comparer(left.Head, right.Head) != 0)
        {
            return false;
        }

        // queue heads are different, but have the same priority
        // stash them both and continue
        leftStash.Add(left.Head);
        rightStash.Add(right.Head);
        left = left.Dequeue();
        right = right.Dequeue();
    }

    // Equal if we've found matches for everything in both queues
    // and our stashes are empty (no outstanding matches)
    return left.IsEmpty
           && right.IsEmpty
           && leftStash.Count == 0
           && rightStash.Count == 0;
}

I had to desk check this approach several times before I convinced myself that it would work. After implementation, I turned each of those desk checks into a unit tests.