GVSU CIS163 Project

GVList.java

package cis163.text_scrambler;

/**
 * Created by Hans Dulimarta on Fall 2015.
 */
public interface GVList<GVElement> {

    /**
     * Check if the list is empty
     * @return true/false
     */
    boolean isEmpty();

    /**
     * Verify is all items in this list are equal to all items in the other list
     * @param other the second list to compare this list with
     * @return true/false
     */
    boolean equals(GVList<GVElement> other);
    
    /**
     * How many items stored in the list
     * @return an the integer, the number of items in the list
     */
    int size();

    /**
     * Return the first item stored in the list
     *
     * @return the data contained in the first node
     * @throws IllegalStateException when the list is empty
     */
    GVElement front();

    /**
     * Return the first item stored in the list
     *
     * @return the data contained in the first node
     * @throws IllegalStateException when the list is empty
     */
    GVElement back();

    /**
     * Insert the provided item as the last (new item) in the list
     * @param item
     */
    void append (GVElement item);

    /**
     * Insert the provided item as the first (new item) in the list
     * @param item
     */
    void prepend (GVElement item);

    /**
     * Insert a new item (toInsert) after a given item (refItem)
     * @param toInsert the (new) item to insert into the list
     * @param refItem the reference item for the insertion
     * @throws IllegalStateException when the list is empty or the reference item
     *  is not in the list
     */
    void insertAfter (GVElement toInsert, GVElement refItem);

    /**
     * Remove the front item from the list
     * @return the item just removed
     * @throws IllegalStateException when the list is empty
     */
    GVElement removeFront();

    /**
     * Remove the last item from the list
     * @return the item just removed
     * @throws IllegalStateException when the list is empty
     */
    GVElement removeBack();

    /**
     * Remove the requested item from the list
     *
     * @param item the item to remove
     * @throws IllegalStateException when the list is empty or the requested
     * item is not in the list
     */
    void remove (GVElement item);

    /**
     * Remove all items from the list
     */
    void removeAll();

    /**
     * Make a duplicate copy of this list
     *
     * @return a new list that contains the same items (and order) as those
     *         in this list.
     */
    GVList<GVElement> makeCopy();
}

ListTester.java

package cis163.text_scrambler.test;

import cis163.text_scrambler.GVList;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;

import java.util.Random;
import java.util.Stack;

import static org.junit.Assert.*;

/**
 * Created by Hans Dulimarta (Fall 2015).
 */

public class ListTester {
    static class Box {
        public int content;
        public static int eqCount = 0;

        @Override
        public boolean equals(Object other) {
            Box w = (Box) other;
            eqCount++;
            return content == w.content;
        }
    }

    private static Random rnd;
    private static StringBuffer strBuff;
    private GVList<Integer> numList, nomList;
    private GVList<String> strList;
    private GVList<Character> chrList;
    private GVList<Box> boxList, booList;
    private GVList<GVList<Integer>> listOfLists;

    @BeforeClass
    public static void oneTimeSetup () {
        rnd = new Random();
        strBuff = new StringBuffer();
    }

    @Before
    public void preTestSetup() {
        fail ("You must uncomment the following 7 lines and rename XYZ");

        /* TODO rename XYZ with your own class that implements
         * the GVList interface */
//        numList = new XYZ<Integer>();
//        nomList = new XYZ<Integer>();
//        strList = new XYZ<String>();
//        chrList = new XYZ<Character>();
//        boxList = new XYZ<Box>();
//        booList = new XYZ<Box>();
//        listOfLists = new XYZ<GVList<Integer>>();
    }

    @Test
    public void defaultState() {
        assertTrue (numList.isEmpty());
        assertTrue (strList.isEmpty());
        assertTrue (chrList.isEmpty());
        assertTrue (boxList.isEmpty());

        assertEquals(0, numList.size());
        assertEquals(0, strList.size());
        assertEquals(0, chrList.size());
        assertEquals(0, boxList.size());
    }

    @Test
    public void frontOnEmptyListMustThrowException() {
        try {
            numList.front();
            strList.front();
            chrList.front();
            boxList.front();
            fail ("Invoking front() on an empty list must throw an exception");
        }
        catch (IllegalStateException e) {
            /* no code here */
        }
    }

    @Test
    public void backOnEmptyListMustThrowException() {
        try {
            numList.back();
            strList.back();
            chrList.back();
            boxList.back();
            fail ("Invoking back() on an empty list must throw an exception");
        }
        catch (IllegalStateException e) {
            /* no code here */
        }
    }

    @Test
    public void appendOnEmptyListMustUpdateHeadAndTail() {
        Integer val = rnd.nextInt();
        numList.append(val);
        assertFalse(numList.isEmpty());
        assertEquals(1, numList.size());
        assertEquals (val, numList.front());
        assertEquals (val, numList.back());

        Character ch = randomChar();
        chrList.append(ch);
        assertFalse(chrList.isEmpty());
        assertEquals(1, chrList.size());
        assertEquals (ch, chrList.front());
        assertEquals (ch, chrList.back());
    }

    @Test
    public void appendOnNonEmptyList() {
        Integer one, two;
        one = rnd.nextInt();
        two = rnd.nextInt();
        numList.append(one);
        numList.append(two);
        assertEquals (2, numList.size());
        assertEquals (one, numList.front());
        assertEquals (two, numList.back());
    }

    @Test
    public void appendOnBigList() {
        Integer one, two;
        final int NUMITEMS = 1000;
        one = rnd.nextInt();
        two = rnd.nextInt();
        numList.append(one);
        for (int k = 0; k < NUMITEMS; k++) {
            numList.append(k+1);
        }
        numList.append(two);
        assertEquals (2 + NUMITEMS, numList.size());
        assertEquals (one, numList.front());
        assertEquals (two, numList.back());
    }

    @Test
    public void prependOnNonEmptyList() {
        Integer one, two;
        one = rnd.nextInt();
        two = rnd.nextInt();
        numList.prepend(one);
        numList.prepend(two);
        assertEquals (2, numList.size());
        assertEquals (one, numList.back());
        assertEquals (two, numList.front());
    }

    @Test
    public void prependOnBigList() {
        Integer one, two;
        final int NUMITEMS = 1000;
        one = rnd.nextInt();
        two = rnd.nextInt();
        numList.prepend(one);
        for (int k = 0; k < NUMITEMS; k++) {
            numList.prepend(k+1);
        }
        numList.prepend(two);
        assertEquals (2 + NUMITEMS, numList.size());
        assertEquals (two, numList.front());
        assertEquals (one, numList.back());
    }

    @Test
    public void prependOnEmptyListMustUpdateHeadAndTail() {
        Integer val = rnd.nextInt();
        numList.prepend(val);
        assertFalse(numList.isEmpty());
        assertEquals(1, numList.size());
        assertEquals (val, numList.front());
        assertEquals (val, numList.back());

        String str = randomString(6);
        strList.prepend(str);
        assertFalse (strList.isEmpty());
        assertEquals(1, strList.size());
        assertEquals (str, strList.front());
        assertEquals (str, strList.back());
    }

    @Test
    public void insertAfterOnEmptyList () {
        try {
            numList.insertAfter(10, 60);
            strList.insertAfter("New string", "Ref string");
            chrList.insertAfter('Z','Y');
            fail ("insertAfter on an empty list must throw an exception");
        }
        catch (IllegalStateException e) {
            /* tests pass */
        }
    }

    @Test
    public void insertAfterOnOneItemListMustUpdateTail() {
        Integer one = rnd.nextInt();
        Integer two = one + 5;
        numList.append(one);
        numList.insertAfter(two, one);
        assertEquals(2, numList.size());
        assertEquals(one, numList.front());
        assertEquals(two, numList.back());
    }

    @Test
    public void insertAfterTailMustUpdateTail() {
        String one, two;
        final int NUMITEMS = 100;
        for (int k = 0; k < NUMITEMS; k++)
            strList.append(randomString(5));
        one = randomString(6);
        two = randomString(7);
        strList.append(one);
        assertEquals(one, strList.back());
        strList.insertAfter(two, one);
        assertEquals(two, strList.back());
    }

    @Test
    public void insertAfterMustCompareUsingEqual() {
        Box b;
        int N;
        N = rnd.nextInt(50) + 100;
        for (int k = 0; k < N; k++) {
            b = new Box();
            b.content = rnd.nextInt(500);
            boxList.append(b);
        }
        int val = 1000 + rnd.nextInt(500);
        Box b1 = new Box();
        b1.content = val;
        Box b2 = new Box();
        b2.content = val;
        boxList.append(b1);
        N = rnd.nextInt(50) + 100;
        for (int k = 0; k < N; k++) {
            b = new Box();
            b.content = rnd.nextInt(500);
            boxList.append(b);
        }
        Box.eqCount = 0;
        int oldSize = boxList.size();
        boxList.insertAfter(new Box(), b2);
        assertEquals(oldSize + 1, boxList.size());
        assertTrue (Box.eqCount > 0);
    }

    @Test (expected = IllegalStateException.class)
    public void insertAfterUnknownMustThrowException() {
        final int NUMITEMS = 500;
        for (int k = 0; k < NUMITEMS; k++)
            strList.append(randomString(5));

        strList.insertAfter("Test String", randomString(8));
    }

    @Test
    public void removeFrontOnEmptyListMustThrowException() {
        try {
            numList.removeFront();
            strList.removeFront();
            fail ("Forgot to throw IllegalStateException?");
        }
        catch (IllegalStateException e) {
            /* tests pass */
        }
    }

    @Test
    public void removeBackOnEmptyListMustThrowException() {
        try {
            chrList.removeBack();
            boxList.removeBack();
            fail ("Forgot to throw IllegalStateException?");
        }
        catch (IllegalStateException e) {
            /* tests pass */
        }
    }

    @Test
    public void removeFrontOnSingleItemMustUpdateTail() {
        String val = randomString(10);
        strList.append(val);
        String eval = strList.removeFront();
        assertEquals (0, strList.size());
        assertEquals(val, eval);
        try {
            strList.back();
            fail ("removeFront() on a single item must update tail");
        }
        catch (IllegalStateException e) {
            /* tests pass */
        }
    }

    @Test
    public void removeFrontOnBigList() {
        Stack<String> store = new Stack<String>();
        final int NUMITEMS = 500;
        for (int k = 0; k < NUMITEMS; k++) {
            String s = randomString(10);
            strList.prepend(s);
            store.push(s);
        }
        try {
            while (store.size() > 0) {
                String s = store.pop();
                String t = strList.removeFront();
                assertEquals(s, t);
            }
        }
        catch (Exception e) {
            fail ("Buggy implementation of prepend()");
        }
    }

    @Test (expected = IllegalStateException.class)
    public void removeUnknownMustThrowException() {
        final int NUMITEMS = 100;
        for (int k = 0; k < NUMITEMS; k++)
            strList.append(randomString(10));

        /* the following random string is not in the list */
        strList.remove(randomString(8));
    }

    @Test
    public void removeFirstItemMustUpdateHead() {
        final int NUMITEMS = 100;
        for (int k = 0; k < NUMITEMS; k++)
            strList.append("Test-" + k);
        strList.remove("Test-0");
        assertEquals ("Test-1", strList.front());
    }

    @Test
    public void removeBackOnBigList() {
        Stack<String> store = new Stack<String>();
        final int NUMITEMS = 500;
        for (int k = 0; k < NUMITEMS; k++) {
            String s = randomString(10);
            strList.append(s);
            store.push(s);
        }
        try {
            while (store.size() > 0) {
                String s = store.pop();
                String t = strList.removeBack();
                assertEquals(s, t);
            }
        }
        catch (Exception e) {
            fail ("Buggy implementation of prepend()");
        }
    }


    @Test (expected = IllegalStateException.class)
    public void removeOnEmptyListMustThrowException() {
        strList.remove("Test String");
    }

    @Test
    public void removeLastItemMustUpdateTail() {
        final int NUMITEMS = 100;
        for (int k = 0; k < NUMITEMS; k++)
            strList.prepend("Test-" + k);
        strList.remove("Test-0");
        assertEquals ("Test-1", strList.back());
    }

    @Test
    public void removeInteriorNode() {
        Stack<String> store = new Stack<String>();
        String s, toDel;
        for (int k = 0; k < 30; k++) {
            s = randomString(10);
            strList.append(s);
            store.push(s);
        }
        toDel = randomString(7);
        strList.append(toDel);
        for (int k = 0; k < 25; k++) {
            s = randomString(10);
            strList.append(s);
            store.push(s);
        }
        int oldSize = strList.size();
        strList.remove(toDel);
        assertEquals(oldSize - 1, strList.size());
        String t;
        while (store.size() > 0) {
            s = store.pop();
            t = strList.removeBack();
            assertEquals(s, t);
        }
        assertEquals (0, strList.size());
    }

    @Test
    public void removeAllMustResetAllAttributes() {
        for (int k = 0; k < 500; k++) {
            Box b = new Box();
            b.content = rnd.nextInt();
            boxList.append(b);
        }
        assertTrue (boxList.size() > 0);
        boxList.removeAll();
        assertEquals(0, boxList.size());
        assertTrue (boxList.isEmpty());
        try {
            boxList.front();
            boxList.back();
            fail ("Forgot to throw exception?");
        }
        catch (IllegalStateException e) {
            /* tests pass */
        }
    }

    @Test
    public void equalsMustCheckAllNodes() {
        final int NUMITEMS = 500;
        for (int k = 0; k < NUMITEMS; k++) {
            int val = rnd.nextInt();
            Box b1 = new Box();
            b1.content = val;
            Box b2 = new Box();
            b2.content = val;
            boxList.append(b1);
            booList.append(b2);
        }
        assertTrue (boxList.equals(booList));
        assertTrue (booList.equals(boxList));
        assertTrue (boxList.equals(boxList));
        assertTrue (booList.equals(booList));
        booList.removeBack();
        assertFalse(boxList.equals(booList));
    }

    @Test
    public void listOfListShouldWorkNaturally() {
        final int NUMITEMS = 100;
        for (int k = 0; k < NUMITEMS; k++) {
            numList.append(2*k);
            nomList.append(2*k + 1);
        }
        listOfLists.append(numList);
        listOfLists.append(nomList);

        GVList<Integer> evenValues = listOfLists.front();
        GVList<Integer> oddValues = listOfLists.back();

        while (evenValues.size() > 0) {
            int testVal = evenValues.removeFront();
            assertTrue (testVal % 2 == 0);
        }
        while (oddValues.size() > 0) {
            int testVal = oddValues.removeFront();
            assertTrue (testVal % 2 == 1);
        }
    }

    @Test
    public void duplicateCopyMustCreateNewNodes() {
        final int NUMITEMS = 100;
        Box b;
        for (int k = 0; k < NUMITEMS; k++) {
            b = new Box();
            b.content = rnd.nextInt();
            boxList.append(b);
        }
        GVList<Box> dup = boxList.makeCopy();
        assertEquals (boxList.size(), dup.size());
        while (boxList.size() > 0) {
            Box b1 = boxList.removeFront();
            Box b2 = dup.removeFront();
            assertTrue (b1.equals(b2));
            assertTrue (b2.equals(b1));
        }
        assertEquals (0, dup.size());
    }


    private char randomChar() {
        return (char) ('A' + rnd.nextInt(26));
    }

    private String randomString(int len) {
        strBuff.setLength(0);
        for (int k = 0; k < len; k++)
            strBuff.append(randomChar());
        return strBuff.toString();
    }
}