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:

Left | "alpha", "beta", "Beta", "BETA", "gamma" |
---|---|

Right | "alpha", "Beta", "BETA", "beta", "gamma" |

Initial State:

Left.Head | Right.Head |
---|---|

"alpha" | "alpha" |

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

State after step 1:

Left.Head | Right.Head |
---|---|

"beta" | "Beta" |

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:

Left.Head | Right.Head | Left Stash | Right Stash |
---|---|---|---|

"Beta" | "BETA" | "beta" | "Beta" |

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:

Left.Head | Right.Head | Left Stash | Right Stash |
---|---|---|---|

"BETA" | "BETA" | "beta" | - |

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

State after step 4:

Left.Head | Right.Head | Left Stash | Right Stash |
---|---|---|---|

"gamma" | "beta" | "beta" | - |

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:

Left.Head | Right.Head | Left Stash | Right Stash |
---|---|---|---|

"gamma" | "gamma" | - | - |

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.

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.

## Comments

blog comments powered by Disqus