Unit testing of a shuffle method on a list

Question

Consider the following class:

public class Deck {
    private final Queue<Card> queue = new LinkedList<>();

    public Deck() { }

    public Deck(final Collection<Card> cards) {
        Objects.requireNonNull(cards);
        queue.addAll(cards);
    }

    public void add(final Card card) {
        Objects.requireNonNull(card);
        queue.add(card);
    }

    public void addAll(final Collection<Card> cards) {
        Objects.requireNonNull(cards);
        queue.addAll(cards);
    }

    public void shuffle() {
        Collections.shuffle((List<Card>)queue);
    }

    public Card take() {
        return queue.remove();
    }
}

How would I unit test the shuffle() method? I am using JUnit 4 for testing.

I have the following options:

1. Test shuffle() to see that it does not generate an exception.
2. Test shuffle() and check if the deck actually gets shuffled.

Example pseudocode of option 2:

while notShuffled
    create new Deck
    take cards and check if they are shuffled

The only culprit here is that when executing a test written for option 2 (which also inheritly includes option 1), if the shuffling does not work as intended, then the code execution will never stop.

How would I solve this issue? Is it possibly to limit the execution time in JUnit tests?

Answer 1

Currently, your class is tightly coupled with the Collections.shuffle function. Static functions are notorious for making things more difficult to test. (On top of that, there's no point in you testing Collections.shuffle; presumably, it works correctly.)

In order to address this, you can introduce a seam in your class for this shuffling functionality. This is done by extracting the shuffle function into a role (represented by an interface). For example:

public interface ICardShuffler {
    void shuffle(List<Card> cards);
}

Then, your Deck class can be configured to keep a reference to an instance of some implementation of this interface, and invoke it when necessary:

public class Deck {
    private final Queue<Card> queue = new LinkedList<>();

    private ICardShuffler cardShuffler;

    public Deck(ICardShuffler cardShuffler) {
        this.cardShuffler = cardShuffler;
    }
    ...
    public void shuffle() {
        cardShuffler.shuffle((List<Card>)queue);
    }
    ...

This allows your unit test to use a test double, like a mock object, to verify that the expected behavior occurs (i.e., that shuffle invokes shuffle on the provided ICardShuffler).

Finally, you can move the current functionality into an implementation of this interface:

public class CollectionsCardShuffler implements ICardShuffler {
    public void shuffle(List<Card> cards) {
        Collections.shuffle(cards);
    }
}

Note: In addition to facilitating testing, this seam also allows you to implement new methods of shuffling without having to modify any of the code in Deck.

Answer 2

I don't understand your pseudocode... why use a while loop? Just call shuffle on a deck. If an exception is thrown, test fails. If the deck is in the same order, test fails. Do you need more than that?

Answer 3

You could also write your own class CollectionsHelper and use that instead of Collections.

public class CollectionsHelper {
    private CollectionsHelper(){}
    private static boolean isTest = false;
    private static int n = 0;
    public static void shuffle(List<?> l){
        if(!isTest) Collections.shuffle(l);
        else Collections.shuffle(l, new Random(n));
    }
    public static void setTest(){
        isTest = true;
        n = 0;
    }
    public static boolean isTest(){
        return isTest;
    }
    public static void setSeedForTest(int seed){
        n = seed;
    }
}

At the beginning of each test you can call CollectionsHelper.setTest() to use the deterministic shuffle. Your class would look like:

public class Deck {
    private final Queue<Card> queue = new LinkedList<>();

    public Deck() { }

    public Deck(final Collection<Card> cards) {
        Objects.requireNonNull(cards);
        queue.addAll(cards);
    }

    public void add(final Card card) {
        Objects.requireNonNull(card);
        queue.add(card);
    }

    public void addAll(final Collection<Card> cards) {
        Objects.requireNonNull(cards);
        queue.addAll(cards);
    }

    public void shuffle() {
        CollectionsHelper.shuffle((List<Card>)queue);
    }

    public Card take() {
        return queue.remove();
    }
}

Answer 4

I would do something like the following:

• First, I would make the Deck class implement Iterator<Card>.
• Second, I would make the Deck class immutable after the first call to shuffle or take. ie. don't allow the addition of cards.

Then I would do something like this...

 static List<List<Card>> previousDecks = new ArrayList<>();
 static List<Card> inputList = createListOfCards();

 static{
      privousDecks.add(inputList);
 }

 @Test
 public void testShuffle(){
    Deck deck = new Deck(inputList);
    deck.shuffle();

    List<Card> shuffled = new ArrayList<>();
    Iterators.addAll(shuffled, deck);

    assertThat(shuffled, 
       IsIterableContainingInAnyOrder.containsInAnyOrder(inputList));

    for (List<Card> previouslySeen : previousDecks){
        assertThat(shuffled,
            CoreMatchers.not(
            IsIterableContainingInOrder.contains(previouslySeen )));
    }
    previousDecks.add(shuffled);
 }

I would then find a way of running testShuffle multiple times to ensure that the shuffle does not produce the same result each time. This can be done multiple ways. Here is an example.

As an FYI, I am using Hamcrest and Guava here.

Iterators

Hamcrest