It’s vital that our priority queue returns items in the correct order, so we should write some unit tests to ensure that items are returned in the order desired. Fortunately, we can test this fairly easy using property tests.
Property Testing is an approach to testing based on the idea of declaratively stating the characteristics (or properties) that a system should have and then generating a bunch of random test cases to verify that the properties hold. For .NET developers, the FsCheck project provides great support.
The first property we’re going to check is that the queue contains the right number of items.
This test accepts an array of string values that we use to create a priority queue; we then verify that the queue has the expected number of items. Courtesy of the
[Property] attribute at the top, FsCheck will generate 100 random arrays of strings and check that the test passes with every one.
The supporting method
Create() is used to make the queue:
The next property of our priority queues that we want to verify is that we always get the expected number of items out of a queue.
Again, there’s a helper method to review -
ToList() takes a queue and extracts all of the items into a list.
Having verified that the right number of items go into a queue and then come back out again, let’s verify that all of the items that went in actually came back out.
Note that the test checks that every string in
values is present in the set of values extracted from the queue; it’s easy to write tests like this the wrong way around (like I did the first time) and thus not end up testing what you think you’re testing.
Now let’s verify that the items being removed from the head of the queue are priorised into the expected order:
ContainInOrder() method from Fluent Assertions checks that all of the items included in the sequence
expected occur in that order in the sequence
This time we get a test failure:
This is really useful.
Let’s break down the message piece by piece.
- FsCheck was able to fail the property on the 74th test sample that it tried. You can see from the text shown that it created a challenging set of strings as sample data.
- Once it found a failing test case, it was able to shrink the sample data 59 times, finding a simple four item array that reproduced the same problem.
- At the end, the test report shows us both four element sequences and we can see that one has
Kreversed by comparison with the other.
I must confess, it took me way too long to track down the source of the problem. I reviewed most of the code and wrote a heap of individual unit tests to verify assumptions before I finally saw the actual issue.
That was a facepalm moment.
StringComparer.OrdinalIgnoreCase.Compare when creating the queue and when sorting the list, I’ve said that letter case should be ignored … meaning that ‘k’ and ‘K’ are equal … but when I compare the two sequences, I’m not using the same rule.
Since there’s no overload of
ContainInOrder() that allows me to pass a comparison rule, the easy fix was to modify queue creation and sorting to use
StringComparer.Ordinal.Compare instead - and now all the tests pass.
Another way to check that the priority queue returns items in the correct sequence is to check that adjacent items removed from the queue are in the expected order. This requires a pairwise check, working through the sequence comparing each pair of adjacent values.
This time around, we run the test with a sequence of integer values. We work through the queue, checking that each item we remove from the head of the queue is greater or equal to the item left behind.
Property tests aren’t the right solution for testing every part of your system, but for some things - like the behaviour of a priority queue - they’re a very good solution indeed.
Update Monday, 10 December …
A friend of mine showed me a simpler way to solve the failing test discussed above.
Here’s the failing test code:
A much simpler fix is to change the assertion to use a different method from Fluent Assertions:
The key to this fix is that now queue creation, list sorting, and sequence comparison are all using