Immutable Priority Queues
Queue Testing

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.

[Property]
public void QueueAlwaysHasCorrectCount(string[] values)
{
    var queue = Create(values, StringComparer.OrdinalIgnoreCase);
    queue.Count.Should().Be(values.Length);
}

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.

Ok, passed 100 tests.

The supporting method Create() is used to make the queue:

private static IImmutablePriorityQueue<T> Create<T>(
    IEnumerable<T> values, Comparison<T> comparer)
{
    return values.Aggregate(
        (IImmutablePriorityQueue<T>)new EmptyImmutablePriorityQueue<T>(comparer),
        (queue, value) => queue.Enqueue(value));
}

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.

[Property]
public void QueueAlwaysReturnsCorrectNumberOfItems(string[] values)
{
    var queue = Create(values, StringComparer.OrdinalIgnoreCase);
    var list = ToList(queue);
    list.Should().HaveCount(values.Length);
}

Ok, passed 100 tests.

Again, there’s a helper method to review - ToList() takes a queue and extracts all of the items into a list.

private static IList<T> ToList<T>(IImmutablePriorityQueue<T> queue)
{
    var result = new List<T>(queue.Count);
    var remaining = queue;
    while (!remaining.IsEmpty)
    {
        result.Add(remaining.Head);
        remaining = remaining.Dequeue();
    }

    return result;
}

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.

[Property]
public void QueueAlwaysReturnsEverythingAdded(string[] values)
{
    var queue = Create(values, StringComparer.OrdinalIgnoreCase.Compare);
    var all = new HashSet<string>();
    while (!queue.IsEmpty)
    {
        all.Add(queue.Head);
        queue = queue.Dequeue();
    }

    foreach (var item in values)
    {
        all.Contains(item).Should().BeTrue();
    }
}

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.

Ok, passed 100 tests.

Now let’s verify that the items being removed from the head of the queue are priorised into the expected order:

[Property]
public void QueueReturnsExpectedItemsInOrder(NonEmptyArray<string> values)
{
    var queue = Create(values.Item, StringComparer.OrdinalIgnoreCase.Compare);
    var expected = values.Item.ToList();
    expected.Sort(StringComparer.OrdinalIgnoreCase.Compare);

    var actual = queue.ToList();
    actual.Should().ContainInOrder(expected);
}

The ContainInOrder() method from Fluent Assertions checks that all of the items included in the sequence expected occur in that order in the sequence actual.

This time we get a test failure:

FsCheck.Xunit.PropertyFailedException : 
Falsifiable, after 74 tests (59 shrinks) (StdGen (204443534,296524100)):
Original:
NonEmptyArray
  [|"x"; null; "e"; "_"; ""; "i"; ""; "s"; "&\014\004&\0287-OE\017Vxn\016"; null; ""; ""; "/";
    ""; ""; ""; null; ""; "0"; ""; ":"; ""; "Df"; ""; ""; ""; null; ""; "b"; "";
    "l"; ""; "v"; "QG"; "\000"; "["; ""; "e"; ""; "o"; null; "y"; ""; ""; ""; "\025";
    ""; ""; "K"; "`"; ":"; ""; ""; "X"; "k"; ""; ""; ""; "\127"; ""; null; ""|] (At least one control character has been escaped as a char code, e.g. \023)
Shrunk:
NonEmptyArray [|"K"; "k"; ""; ""|]

----
Expected collection {"", "", "K", "k"} to contain items {"", "", "k", "K"} in order,
but "K" (index 3) did not appear (in the right order).

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 k and K reversed 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.

By specifying 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.

Ok, passed 100 tests.

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.

[Property]
public void QueueAlwaysReturnsItemsInDecreasingOrder(NonEmptyArray<int> values)
{
    var queue = Create(values.Item, (left, right) => -left.CompareTo(right));
    var value = queue.Head;
    while (!queue.IsEmpty)
    {
        value.Should().BeGreaterOrEqualTo(queue.Head);
        value = queue.Head;
        queue = queue.Dequeue();
    }
}

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.

Ok, passed 100 tests.

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:

[Property]
public void QueueReturnsExpectedItemsInOrder(NonEmptyArray<string> values)
{
    var queue = Create(values.Item, StringComparer.OrdinalIgnoreCase.Compare);
    var expected = values.Item.ToList();
    expected.Sort(StringComparer.OrdinalIgnoreCase.Compare);

    var actual = queue.ToList();
    actual.Should().ContainInOrder(expected);
}

A much simpler fix is to change the assertion to use a different method from Fluent Assertions:

[Property]
public void QueueReturnsExpectedItemsInOrder(NonEmptyArray<string> values)
{
    var queue = Create(values.Item, StringComparer.OrdinalIgnoreCase.Compare);
    var expected = values.Item.ToList();
    expected.Sort(StringComparer.OrdinalIgnoreCase.Compare);

    var actual = queue.ToList();
    queue.Should().Equal(
        expected,
        StringComparer.OrdinalIgnoreCase.Equals);
}

The key to this fix is that now queue creation, list sorting, and sequence comparison are all using StringComparer.OrdinalIgnoreCase.