Tip:
Highlight text to annotate it
X
...is investigate in more detail random testing of a specific API,
and that's the bounded queue that we've already looked at a couple times in this class.
So let's take a minute and review the code for the bounded queue.
So what the queue is is an abstract data type. It's providing several methods.
So for example, we have a constructor, an empty call full.
Enqueue adds something, dequeue removes something,
and checkRep is our assertion checker that does sanity checking
over the internal state of the queue.
So now let's look at the simple test routine that I wrote.
What it does is it creates a queue of 2 elements, adds some stuff to it,
asserts that the proper values are returned,
and removes those things from the queue,
again asserting that the proper things were returned.
And notice also that we're calling checkRep after every queue operation.
So this is a non-random test for the queue.
What I'd like to do now is, using the Udacity API, write a random tester for the queue.
So let's just talk about this a little bit--how should it work?
It's clear that the random test, like the deterministic test here,
is going to need to start off by creating a queue.
It's also clear that after performing any queue operation,
the random test should call checkRep.
The thing that's not clear is how do we decide what API function to call,
and how do we know whether the result is correct?
One thing you can do is randomly call functions in the queue's API
with random arguments and just keep asserting checkRep and not really care what comes out.
That is to say, you can just randomly invoke queue operations in a loop
and wait for checkRep to fail.
On the other hand, it's not that hard to do better.
The first thing is we know how many elements the queue holds,
and we also know whether any particular addition
or removal from the queue succeeds or fails.
And so it's pretty easy using an integer to keep track of how many elements
are currently used in the queue.
And what we'd like to do in that case is assert that any enqueue operation
to a non-full queue succeeds and any enqueue operation to a full queue fails.
Similarly, any dequeue operation from an empty queue needs to fail,
as we see a little bit below,
and any dequeue operation from a non-empty queue should succeed.
So the third thing you can do--and you don't need to do this to pass the quiz,
but it's something that would be nice--
is actually keep track of what values should be coming out of dequeue operations.
And so let's just take a minute to see what that would look like.
The bounded queue that you're testing is based on a Python array,
but it turns out that it's really easy to emulate the operation of that queue
using native Python data structures.
So basically, if you wanted to do this, what you would do is you would declare a Python list
that's initially empty, and every time I want to enqueue something in our bounded queue
we also append it to the list.
We have to be a little bit more careful than this
because if the enqueueing of an item fails, we don't want to append sums to our list.
Similarly, when we dequeue something for the bounded queue,
if the dequeue operation succeeds, we want to issue l.pop(0).
The way this works is when something gets appended to a list,
it gets appended at the end, and l.pop(0) takes something off the beginning.
So basically, we're emulating a queue using native Python data structures,
and our emulated queue isn't going to be as fast as the native queue
which is based on the array, but that doesn't matter for testing purposes.
And so if we do these kind of operations and we do them in a random testing loop
and we insert the appropriate checkReps,
then we can build really a quite effective random tester for the bounded queue
using not that many lines of code.
So what I'd like you to do now is go to the API and write a small random tester for the queue.