DSTest.java

Description

This describes several randomized tests that are to be run on data structures of different sorts. This can be safely ignored by the ones completing the exercise, until it is time to test.

Every test starts with an empty data structure, and adds several items to it.

Testing with DSTest

The following tests are provided by DSTest.

runLinkedListTestSuite(ILinkedList<Integer>)

This should be called if you have written a linked list that follows the ILinkedList interface.

There are several components:

getIterator(ILinkedList<Integer>)

This gets an iterator for the data structure and checks for each i from 0 … size() - 1 whether get(i) is the same as the i^th element iterated.

sortedSame(ILinkedList<Integer)

This uses the asList() method, and sorts both lists. Then, it checks that for each i, both lists have the same element for get(i).

first0(ILinkedList<Integer>)

This checks that getFirst() = = get(0).

lastSize(ILinkedList<Integer>)

This checks that getLast() = = get(size() - 1).

runQueueSuite(IQueue<Integer>)

This is used to test queues. It runs the enqueue_in_order() function. Note that this should be preferred, for various reasons.

enqueue_in_order(IQueue<Integer>)

This tests that the queue has a First In First Out (FIFO) strategy. It does this by keeping track of what items it puts in when, and then when they come out.

runPriorityQueueSuite(IQueue<Integer>)

This is used to test priority queues. It runs the enqueue_in_order_priority() function. Note that this should be preferred, for various reasons.

enqueue_in_order_priority(IQueue<Integer>)

This ensures that, no matter the order added to the queue, an element that is less than another doesn’t show up before one greater.

runGenericQueueSuite(IQueue<Integer>)

Called by both queue suites, this calls the dequeue_iterate() function, which should be passed by both queues and priority queues.

dequeue_iterate(IQueue<Integer>)

This tests that the i^th element dequeued is also the i^th element iterated with an iterator.