Suite of automated tests for the Unsorted implementation of the LinkedList ADT.

UnsortedLinkedListTest.java

package it.pm.algorithms;

import it.pm.algorithms.impl.UnsortedLinkedList;
import java.util.Random;
import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Automated Unit Tests for the {@link UnsortedLinkedList} implementation.
 *
 * @author Paolo Maresca <plo.maresca@gmail.com>
 */
public class UnsortedLinkedListTest
{

    private UnsortedLinkedList list;

    public UnsortedLinkedListTest() {}

    @Before
    public void setUp() { list = new UnsortedLinkedList(); }

    @After
    public void tearDown() {}


    @Test
    public void iterativeReverse()
    {
        list.insert(0);
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        String serialized = list.printIterative();
        Assert.assertEquals("5 4 3 2 1 0 ", serialized);
        list.iterativeReverse();
        String reversed = list.printIterative();
        Assert.assertEquals("0 1 2 3 4 5 ", reversed);
        list.iterativeReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
    }

    @Test
    public void recursiveReverse()
    {
        list.insert(0);
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        String serialized = list.printIterative();
        Assert.assertEquals("5 4 3 2 1 0 ", serialized);
        list.recursiveReverse();
        String reversed = list.printIterative();
        Assert.assertEquals("0 1 2 3 4 5 ", reversed);
        list.recursiveReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
    }

    @Test
    public void recursiveReverseRandomItems()
    {
        Random rand = new Random();
        for(int i = 0; i < 100; i++)
            list.insert(rand.nextInt(10000));

        String serialized = list.printIterative();
        list.iterativeReverse();
        String reversed = list.printIterative();
        list.iterativeReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
    }

    @Test
    public void iterativeReverseRandomItems()
    {
        Random rand = new Random();
        for(int i = 0; i < 100; i++)
            list.insert(rand.nextInt(10000));

        String serialized = list.printIterative();
        list.recursiveReverse();
        String reversed = list.printIterative();
        list.recursiveReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
    }

    @Test
    public void iterativeReverseCornerCases()
    {
        // empty list
        String serialized = list.printIterative();
        list.iterativeReverse();
        String reversed = list.printIterative();
        Assert.assertEquals(serialized, reversed);
        Assert.assertEquals("", serialized);
        Assert.assertEquals("", reversed);
        list.iterativeReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("", reReversed);

        // one element in the list
        list.insert(1);
        serialized = list.printIterative();
        list.iterativeReverse();
        reversed = list.printIterative();
        Assert.assertEquals(serialized, reversed);
        Assert.assertEquals("1 ", serialized);
        Assert.assertEquals("1 ", reversed);
        list.iterativeReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("1 ", reReversed);

        // two elements in the list
        list.insert(2);
        serialized = list.printIterative();
        list.iterativeReverse();
        reversed = list.printIterative();
        Assert.assertEquals("2 1 ", serialized);
        Assert.assertEquals("1 2 ", reversed);
        list.iterativeReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("2 1 ", reReversed);

        // three elements in the list
        list.insert(3);
        serialized = list.printIterative();
        list.iterativeReverse();
        reversed = list.printIterative();
        Assert.assertEquals("3 2 1 ", serialized);
        Assert.assertEquals("1 2 3 ", reversed);
        list.iterativeReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("3 2 1 ", reReversed);
    }

    @Test
    public void recursiveReverseCornerCases()
    {
        // empty list
        String serialized = list.printIterative();
        list.recursiveReverse();
        String reversed = list.printIterative();
        Assert.assertEquals(serialized, reversed);
        Assert.assertEquals("", serialized);
        Assert.assertEquals("", reversed);
        list.recursiveReverse();
        String reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("", reReversed);

        // one element in the list
        list.insert(1);
        serialized = list.printIterative();
        list.recursiveReverse();
        reversed = list.printIterative();
        Assert.assertEquals(serialized, reversed);
        Assert.assertEquals("1 ", serialized);
        Assert.assertEquals("1 ", reversed);
        list.recursiveReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("1 ", reReversed);

        // two elements in the list
        list.insert(2);
        serialized = list.printIterative();
        list.recursiveReverse();
        reversed = list.printIterative();
        Assert.assertEquals("2 1 ", serialized);
        Assert.assertEquals("1 2 ", reversed);
        list.recursiveReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("2 1 ", reReversed);

        // three elements in the list
        list.insert(3);
        serialized = list.printIterative();
        list.recursiveReverse();
        reversed = list.printIterative();
        Assert.assertEquals("3 2 1 ", serialized);
        Assert.assertEquals("1 2 3 ", reversed);
        list.recursiveReverse();
        reReversed = list.printIterative();
        Assert.assertEquals(serialized, reReversed);
        Assert.assertEquals("3 2 1 ", reReversed);
    }

    @Test
    public void testPrint()
    {
        String printed = list.printRecursive();
        Assert.assertEquals("", printed);
        list.insert(4);
        list.insert(11);
        printed = list.printRecursive();
        Assert.assertEquals("11 4 ", printed);
    }

    @Test
    public void testSearch()
    {
        // empty list
        LinkedList.Node found = list.search(1);
        Assert.assertNull(found);

        // filled list
        list.insert(4);
        list.insert(11);
        list.insert(1);
        list.insert(5);
        list.insert(7);
        String printed = list.printRecursive();
        Assert.assertEquals("7 5 1 11 4 ", printed);
        found = list.search(5);
        Assert.assertNotNull(found);
        Assert.assertEquals(5, (int) found.value);
        found = list.search(1);
        Assert.assertNotNull(found);
        Assert.assertEquals(1, (int) found.value);

        // non-existing element
        found = list.search(77);
        Assert.assertNull(found);
    }

    @Test
    public void testDelete()
    {
        // empty list
        LinkedList.Node deleted = list.delete(5);
        Assert.assertNull(deleted);

        // fille list
        list.insert(4);
        list.insert(11);
        list.insert(1);
        list.insert(5);
        list.insert(7);
        deleted = list.delete(5);
        Assert.assertNotNull(deleted);
        Assert.assertEquals(5, (int) deleted.value);
        String printed = list.printRecursive();
        Assert.assertEquals("7 1 11 4 ", printed);
        deleted = list.delete(4);
        Assert.assertNotNull(deleted);
        Assert.assertEquals(4, (int) deleted.value);
        printed = list.printRecursive();
        Assert.assertEquals("7 1 11 ", printed);
        deleted = list.delete(1);
        Assert.assertNotNull(deleted);
        Assert.assertEquals(1, (int) deleted.value);
        printed = list.printRecursive();
        Assert.assertEquals("7 11 ", printed);
        deleted = list.delete(7);
        Assert.assertNotNull(deleted);
        Assert.assertEquals(7, (int) deleted.value);
        printed = list.printRecursive();
        Assert.assertEquals("11 ", printed);
        deleted = list.delete(11);
        Assert.assertNotNull(deleted);
        Assert.assertEquals(11, (int) deleted.value);
        printed = list.printRecursive();
        Assert.assertEquals("", printed);

        // non-existing element in the list
        deleted = list.delete(77);
        Assert.assertNull(deleted);
    }


    @Test
    public void testMin()
    {
        list.insert(4);
        list.insert(11);
        list.insert(1);
        list.insert(5);
        list.insert(7);
        Integer min = (Integer) list.min();
        Assert.assertNotNull(min);
        Assert.assertEquals(new Integer(1), min);
    }

    @Test
    public void testMax()
    {
        list.insert(4);
        list.insert(11);
        list.insert(1);
        list.insert(5);
        list.insert(7);
        Integer max = (Integer) list.max();
        Assert.assertNotNull(max);
        Assert.assertEquals(new Integer(11), max);
    }

    @Test
    public void printIterative()
    {
        // empty list
        String serialized = list.printIterative();
        Assert.assertEquals("", serialized);

        // filled list
        list.insert(4);
        list.insert(11);
        list.insert(1);
        list.insert(5);
        list.insert(7);
        serialized = list.printIterative();
        Assert.assertEquals("7 5 1 11 4 ", serialized);
    }

}