Testing the reliability of the Python priority queue

Hearing of a problem with the PriorityQueue class in Python's Queue module, I wrote this short program to test the class.

The Python priority queue is modeled here by a list, which is sorted so as to match the queue's ascending order. The queue data structure differs from a list in having its size fixed at creation time, making possible a full() method, which lists do not have. Queues also differ from lists in that they can be blocked or have a timeout value applied to their methods, since they are intended for use with threads. Otherwise, lists have a much larger inventory of functionality.

In the this program, the two objects created are filled with random numbers, using both put() and get() so that the queue contracts as well as expands, and then subjected to four tests:

1. The queue should be full (meaning that full() returns True) after being created and populated.
2. The sizes of the objects are compared (using qsize() for the queue and len() for the list).
3. The objects are compared item by item (using get() for the queue and indexing for the list).
4. After all the values in the queue have been dequeued, it should in fact be empty, meaning that empty() returns True.

This test is repeated in an endless loop which can be terminated with ^C, after which the program reports the number of item-comparisons and errors found. Failure of either tests 1 or 4, however, will terminate the loop.

The user is offered the chance to supply the size of the queue and list, as well as the upper value of the range of random numbers (the lower value is 1). Default values are 10000 for both variables if the user does not enter values.

Note that blocking and timeout is not tested here. The put_nowait() and get_nowait() methods were tested manually but then removed from the code.

Conclusion: No problems have been found in Queue.PriorityQueue as of this writing.

Update, 20111130: I've more recently discussed a more interesting conclusion about this problem: see Lack of Stable Sort in Python's Priority Queue and Apparent Error in Python's Priority Queue.

[end]