Testing a Priority Queue

I ran into an interesting testing problem this week. I needed to create a custom Priority Queue data structure which supported O(1) lookups and O(lg n) random access removes (as opposed to a regular dequeue operation) and O(lg n) random access modifies in addition to the standard enqueue and dequeue. This turned out to be a very tricky little problem. During development it was clear that I needed a pretty serious suite of test cases. My first approach was to use a classical test case input, test case expected result. But there were just too many things to test. I realized that a Priority Queue has very well-defined state definitions and that I could use that fact to write efficient test suites. Recall that a Priority Queue is similar to a regular queue but that each item in a priority queue has some priority level associated with the item. Whenever an item is enqueued, the queue is rearranged so that the item with the highest priority is at the front of the queue. When a item is dequeued, it is always the first item, which is the one with the highest priority. Anyway, my test suite ended up being quite small but was very effective. It was something like this:
for (int i = 0; i < 500000; ++i) // 500,000 test cases
  generate a random operation code
  if code = enqueue
    generate a new random item
    enqueue it
    check the state of the priority queue
  if code = dequeue
    dequeue the priority queue
    check the state of the priority queue
  etc. for remove, contains, and modify
The key is that I could check the internal state of the queue. For example, I iterated through the queue to check that the front value was the smallest, and that my internal data structures (lookup arrays and indexes) were consistent, and so on. I’m not sure what the moral is. Maybe that the approach I’ve described is very effective for testing highly structured custom data structures.
This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.