junit - (homeworkish) unit test a class with random behavior without being able to mock the RNG -

junit - (homeworkish) unit test a class with random behavior without being able to mock the RNG -

i'm working through coursera's algorithms, part course. have create randomizedqueue next api:

public class randomizedqueue<item> implements iterable<item> { public randomizedqueue() // build empty randomized queue public boolean isempty() // queue empty? public int size() // homecoming number of items on queue public void enqueue(item item) // add together item public item dequeue() // delete , homecoming random item public item sample() // homecoming (but not delete) random item public iterator<item> iterator() // homecoming independent iterator on items in random order public static void main(string[] args) // unit testing }

question: if can't create mock rng pass construction (because i'm not allowed alter api) , don't want test private methods, how test random behavior of structure?

what i've tried

i've tried thinking results i'd expect probabilistic problem. so, example, i'll run next pseudocode test 10,000 times:

create new randomizedqueue enqueue 100 items (e.g. integers 0 - 99) deque 1 item

then can test frequency each of 100 items dequed within confidence interval (based on binomial distribution).

some might phone call cheating, beg differ.

the point of unit testing verify behavior of system. such, if test going useful @ all, must deterministic. otherwise you'll false negatives, deteriorating integrity of test. ("oh, it's ok if test fails. happens sometimes...")

with in mind, what if didn't have restriction couldn't modify api? if had druthers, how implement , test class? create that implementation first. can design class deterministic.

after have working , tested class, implement randomizedqueue<item> as adapter class.

example

consider next setup:

public interface randomnumbergenerator { int getrandomint(); } // identical randomizedqueue<t>, except takes randomnumbergenerator dependency public class myrandomizedqueue<item> implements iterable<item> { public myrandomizedqueue(randomnumbergenerator generator) { ... }

your tests provide sut false randomnumbergenerator , have finish command on expected outcome of method be.

in actual randomizedqueue<t> implementation, instantiate tested class real randomnumbergenerator implementation (e.g., 1 uses java.util.random), store fellow member variable, , forwards method calls along it. like:

public item dequeue() { homecoming innerqueue.dequeue(); }

unit-testing junit junit4