CMSC 350 - Week2 discussion assignment

RootishArrayStack.java

/**
 * Most of the credit for this code goes to:
 * http://opendatastructures.org/ods-java/2_Array_Based_Lists.html
 * Code from opendatastructures.org is licensed under the Creative Commons
 * License. See:
 *   - http://opendatastructures.org/
 *   - https://creativecommons.org/licenses/by/2.5/ca/
 *
 * I wanted to include a proper copyright notice, but opendatastructures.org
 * does not post any such copyright notice (at least none that I could find).
 *
 * My major contribution to this is researching the generic stuff and
 * implementing `newArray`. In the guide at opendatastructures.org, `newArray`
 * is referenced all over the place, but I never saw any implementation
 * details--contrary to main public methods of this class, for which the guide
 * included complete, working code.
 *
 * Dynamically instantiating generic arrays turns out to be really tricky.
 * Who knew? :)
 * I got a lot of help from this thread, in order to implement `newArray`:
 * http://stackoverflow.com/questions/3403909/get-generic-type-of-class-at-runtime
 */

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;


public class RootishArrayStack <E> {

    protected List<E[]> blocks;
    private int size = 0;
    private final Class<E> type;

    /**
     * @param type - It turns out, dynamically creating generic arrays is very
     * tricky, so we need to explicitly pass in the runtime type, in addition
     * to a generic type parameter. For example, we must do this:
     * RootishArrayStack<String> ras = new RootishArrayStack<>(String.class);
     */
    public RootishArrayStack(Class <E> type) {
        this(10, type);
    }

    /**
     * @param initCapacity - Initial number of items which can potentially
     * be stored
     * @param type - It turns out, dynamically creating generic arrays is very
     * tricky, so we need to explicitly pass in the runtime type, in addition
     * to a generic type parameter. For example, we must do this:
     * RootishArrayStack<String> ras = new RootishArrayStack<>(String.class);
     */
    public RootishArrayStack(int initCapacity, Class<E> type) {
        this.type = type;
        if (initCapacity <= 0) {
            throw new RuntimeException("Initial capacity must be > 0");
        }
        // TODO: check for 0 or negative values

        // Calculate the number of total blocks, using our `i2b` helper function
        int highestIndex = initCapacity - 1;  // quantity to index: -1
        int numBlocks = i2b(highestIndex) + 1;  // index to quantity: +1

        blocks = new ArrayList<E[]>(numBlocks);
        // Initialize each block. The first block will have a size of 1,
        // the second block will have a size of 2, the third a size of 3,
        // and so on.
        for (int i = 0; i < numBlocks; i++) {  // quantity to index: -1
            @SuppressWarnings("unchecked")
            E[] arr = newArray(i + 1);
            blocks.add(arr);
        }
    }

    public int size() {
        return size;
    }

    protected static int i2b(int i) {
        double db = (-3.0 + Math.sqrt(9 + 8 * i)) / 2.0;
        int b = (int)Math.ceil(db);
        return b;
    }

    /**
     * Add a new block. The size of the new block should be equal to the size
     * of the previous block + 1.
     */
    private void grow() {
        blocks.add(newArray(blocks.size() + 1));
    }

    /**
     * Chop away unused blocks.
     */
    private void shrink() {
        int r = blocks.size();
        while (r > 0 && (r - 2) * (r - 1) / 2 >= size) {
            blocks.remove(blocks.size() - 1);
            r--;
        }
    }

    /**
     * Utility method for creating new arrays for the storage structure.
     */
    @SuppressWarnings("unchecked")
    private E[] newArray(int length) {
        return (E[]) Array.newInstance(type, length);
    }

    public void add(int i, E x) {
        if (i < 0 || i > size) {
            throw new IndexOutOfBoundsException();
        }
        int r = blocks.size();
        if (r * (r + 1)/2 < size + 1) {
            grow();
        }
        size++;
        // Shift values and make room for the new element:
        for (int j = size - 1; j > i; j--) {
            set(j, get(j-1));
        }
        set(i, x);
    }

    public E remove(int i) {
        if (i < 0 || i > size - 1) {
            throw new IndexOutOfBoundsException();
        }
        E x = get(i);
        for (int j = i; j < size - 1; j++) {
            set(j, get(j + 1));
        }
        size--;
        int r = blocks.size();
        if ((r - 2) * (r - 1) / 2 >= size) {
            shrink();
        }
        return x;
    }

    public E set(int i, E x) {
        if (i < 0 || i > size - 1) {
            throw new IndexOutOfBoundsException();
        }
        int b = i2b(i);
        int j = i - b * (b + 1) / 2;
        // We could technically just do this:
        // T y = get(i);
        // But this is faster (no redundant calculation of `b` and `j`):
        E y = blocks.get(b)[j];
        blocks.get(b)[j] = x;
        return y;
    }

    public E get(int i) {
        if (i < 0 || i > size - 1) {
            throw new IndexOutOfBoundsException();
        }
        int b = i2b(i);
        int j = i - b * (b + 1) / 2;
        return blocks.get(b)[j];
    }

    /**
     * Flatten the structure to a single array.
     */
    public E[] toArray() {
        E[] arr = newArray(size);
        for (int i = 0; i < size; i++) {
            arr[i] = get(i);
        }
        return arr;
    }
}

RootishArrayStackTest.java

import java.util.Arrays;


public class RootishArrayStackTest extends Testable {

    private RootishArrayStack<String> ras;
    @Override
    public void setUp() {
        ras = new RootishArrayStack<>(String.class);
    }
    @Test
    public void testConstructor() {
        // Test default capacity: 10
        assertEqual(ras.blocks.size(), 4);
        assertEqual(ras.blocks.get(0).length, 1);
        assertEqual(ras.blocks.get(1).length, 2);
        assertEqual(ras.blocks.get(2).length, 3);
        assertEqual(ras.blocks.get(3).length, 4);

        // Custom capacity: 3
        ras = new RootishArrayStack<>(3, String.class);
        assertEqual(ras.blocks.size(), 2);
        assertEqual(ras.blocks.get(0).length, 1);
        assertEqual(ras.blocks.get(1).length, 2);

        // Invalid capacity: 0
        try {
            ras = new RootishArrayStack<>(0, String.class);
            fail();
        }
        catch (RuntimeException e) {
            assertEqual("Initial capacity must be > 0", e.getMessage());
        }

        // Invalid capacity: -1
        try {
            ras = new RootishArrayStack<>(-1, String.class);
            fail();
        }
        catch (RuntimeException e) {
            assertEqual("Initial capacity must be > 0", e.getMessage());
        }
    }

    @Test
    public void testI2b() {
        int [] testCases = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        int [] bValues = {0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4};
        for (int i = 0; i < testCases.length; i++) {
            int testCase = testCases[i];
            int bValue = bValues[i];
            int b = RootishArrayStack.i2b(testCase);
            assertEqual(b, bValue);
        }
    }

    @Test
    public void testAdd_outOfBounds() {
        // negative index: -1
        try {
            ras.add(-1, "foo");
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        // index out of bounds: 1
        // (since size is still 0, regardless of capacity
        try {
            ras.add(1, "foo");
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }
    }

    @Test
    public void testAdd_append() {
        ras = new RootishArrayStack<>(4, String.class);
        ras.add(0, "foo");
        ras.add(1, "bar");
        ras.add(2, "baz");
        ras.add(3, "blarg");
        ras.add(4, "a");
        assertThat(Arrays.equals(
                ras.toArray(),
                new String [] {"foo", "bar", "baz", "blarg", "a"}));

        // Inspect the blocks:
        assertEqual(ras.blocks.size(), 3);
        assertThat(Arrays.equals(
                ras.blocks.get(0),
                new String[] {"foo"}));
        assertThat(Arrays.equals(
                ras.blocks.get(1),
                new String[] {"bar", "baz"}));
        assertThat(Arrays.equals(
                ras.blocks.get(2),
                new String[] {"blarg", "a", null}));

        // Test growth:
        ras.add(5, "b");
        assertThat(Arrays.equals(
                ras.blocks.get(2),
                new String[] {"blarg", "a", "b"}));
        // Block count still is the same, but now we're full.
        assertEqual(ras.blocks.size(), 3);
        ras.add(6, "c");
        // Block count has increased:
        assertEqual(ras.blocks.size(), 4);
        assertThat(Arrays.equals(
                ras.blocks.get(3),
                new String[] {"c", null, null, null}));
    }

    @Test
    public void testAdd_insert() {
        ras = new RootishArrayStack<>(3, String.class);
        ras.add(0, "foo");
        // Insert a value, which means we need to shift other values.
        ras.add(0, "bar");
        assertThat(Arrays.equals(
                ras.toArray(),
                new String[] {"bar", "foo"}));
    }

    @Test
    public void testSet() {
        ras.add(0, "foo");
        ras.add(1, "bar");
        assertThat(Arrays.equals(
                ras.toArray(),
                new String [] {"foo", "bar"}));
        ras.set(1, "baz");
        assertThat(Arrays.equals(
                ras.toArray(),
                new String [] {"foo", "baz"}));

    }

    @Test
    public void testSet_outOfBounds() {
        // Empty collection: index 0
        try {
            ras.set(0, "foo");
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        // Negative index: index -1
        try {
            ras.set(-1, "foo");
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        ras.add(0, "foo");
        // Non-empty collection: index 1
        try {
            ras.set(1, "foo");
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }
    }

    @Test
    public void testGet() {
        // Test boundary: 0 (with empty collection)
        try {
            ras.get(0);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        ras.add(0, "foo");
        assertEqual(ras.get(0), "foo");
        ras.add(0, "bar");
        assertEqual(ras.get(1), "foo");
        assertEqual(ras.get(0), "bar");

        // Test boundary: 2 (index out of range)
        try {
            ras.get(2);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }
        // Test boundary: -1
        try {
            ras.get(-1);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }
    }

    @Test
    public void testRemove() {
        ras = new RootishArrayStack<>(3, String.class);
        ras.add(0, "foo");
        ras.add(1, "bar");
        ras.add(2, "baz");

        // Sanity checks:
        assertEqual(ras.blocks.size(), 2);
        assertThat(Arrays.equals(
                ras.blocks.get(0),
                new String[] {"foo"}));
        assertThat(Arrays.equals(
                ras.blocks.get(1),
                new String[] {"bar", "baz"}));

        // Add one more element, collection should grow
        ras.add(3, "blarg");
        assertEqual(ras.blocks.size(), 3);
        assertThat(Arrays.equals(
                ras.blocks.get(2),
                new String[] {"blarg", null, null}));

        // - Remove element at index 1
        // - Test that the correct value is returned
        // - Everything should shift toward the left
        // - The collection will not shrink until we remove more elements
        String value = ras.remove(1);
        assertEqual(value, "bar");
        assertEqual(ras.blocks.size(), 3);
        assertThat(Arrays.equals(
                ras.blocks.get(0),
                new String[] {"foo"}));
        assertThat(Arrays.equals(
                ras.blocks.get(1),
                new String[] {"baz", "blarg"}));
        assertEqual(ras.size(), 3);

        // Remove more elements, to trigger shrinking:
        ras.remove(0);
        assertEqual(ras.blocks.size(), 3);
        ras.remove(1);
        assertEqual(ras.blocks.size(), 2);
        assertThat(Arrays.equals(
                ras.blocks.get(0),
                new String [] {"baz"}));
        assertThat(Arrays.equals(
                ras.blocks.get(1),
                // These "blarg" strings are still in memory...
                new String [] {"blarg", "blarg"}));
        // .. but they're not accessible
        try {
            ras.get(1);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

    }

    @Test
    public void testRemove_outOfBounds() {
        // Empty collection: index 0
        try {
            ras.remove(0);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        // Negative index: index -1
        try {
            ras.remove(-1);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }

        ras.add(0, "foo");
        // Non-empty collection: index 1
        try {
            ras.remove(1);
            fail();
        }
        catch (IndexOutOfBoundsException e) {
            // expected
        }
    }

    public static void main(String [] args) {
        new RootishArrayStackTest().runTests(true);
    }
}

Testable.java

/**
Copyright (c) 2015, Lars Butler

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
 */

import java.lang.annotation.Annotation;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

public class Testable {

    /**
     * Simple test annotation, to indicate that a method is a test method.
     */
    @Retention(RetentionPolicy.RUNTIME)
    public @interface Test {}

    public class TestItFailure extends RuntimeException {
        public TestItFailure() {}
        public TestItFailure(String message) {
            super(message);
        }
    }

    public void assertThat(boolean expr) throws TestItFailure {
        if (!expr) {
            throw new TestItFailure();
        }
    }

    public void assertEqual(Object a, Object b) throws TestItFailure {
        if (!a.equals(b)) {
            throw new TestItFailure(String.format(
                    "%s != %s",
                    a.toString(),
                    b.toString()));
        }
    }

    public void fail() {
        assertThat(false);
    }

    /**
     * Default `runTests` method; `verbose` defaults to false.
     * See below.
     */
    public void runTests() {
        runTests(false);
    }

    /**
     * 
     * @param verbose: if true, print stack traces of errors to stderr;
     * otherwise, just show "pass" or "fail" for each test.
     */
    public void runTests(boolean verbose) {
        try {
            int failures = doRunTests(verbose);
            if (failures > 0) {
                // If there are any failures, we should return
                // with a proper exit code indicating the failure.
                System.exit(1);
            }
        }
        catch (Exception e) {
            // Something unexpected happened.
            e.printStackTrace();
            System.exit(1);
        }
    }

    /**
     * Override in subclasses to specify custom setup commands for each test
     * method.
     */
    public void setUp() {}

    private int doRunTests(boolean verbose) throws IllegalAccessException, IllegalArgumentException {

        int testCount = 0;
        int passCount = 0;
        int failCount = 0;

        for (Method meth: this.getClass().getDeclaredMethods()) {
            // Check for `ATest` annotations, in order to find test methods.
            Annotation[] annots = meth.getAnnotationsByType(Testable.Test.class);
            if (annots.length > 0) {
                testCount++;
                boolean pass = true;
                try {
                    this.setUp();
                    meth.invoke(this);
                }
                catch (InvocationTargetException ex) {
                    if (verbose) {
                        System.err.println("Error in method: " + meth.getName());
                        ex.getTargetException().printStackTrace();
                    }
                    pass = false;
                }

                if (pass) {
                    passCount++;
                }
                else {
                    failCount++;
                }
                System.out.printf("%s: %s\n", meth.getName(), pass ? "pass": "fail");
            }
        }
        System.out.printf(
                "%d/%d tests ran successfully (failed: %d)\n",
                passCount,
                testCount,
                failCount);
        return failCount;
    }

}

Week2.java

/**
Copyright (c) 2015, Lars Butler

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
 */

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Parameter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;


public class Week2 {

    private static Map<String, Class []> getCommands() {
        Map<String, Class []> cmds = new HashMap<>();
        cmds.put("get", new Class [] {Integer.class});
        cmds.put("set", new Class [] {Integer.class, String.class});
        cmds.put("add", new Class [] {Integer.class, String.class});
        cmds.put("remove", new Class [] {Integer.class});
        cmds.put("toArray", new Class [] {});
        cmds.put("size", new Class [] {});
        return cmds;
    }
    public static final Map<String, Class []> COMMANDS = getCommands();

    public static void printHelp() {
        String [] helpText = {
                "Supported commands:",
                "",
                "  get INDEX",
                "    Get the value at the specified index",
                "  set INDEX VALUE",
                "    Set the element at INDEX to VALUE",
                "  add INDEX VALUE",
                "    Insert VALUE to the end of the specified INDEX",
                "  remove INDEX",
                "    Remove the item at INDEX from the array",
                "  toArray",
                "    Get the elements in the collection as an array",
                "  size",
                "    Get the size of the array (number of elements)",
                "  help | h",
                "    Show this help",
                "  quit | q",
                "    Exit the program",
        };
        for (String line: helpText) {
            System.out.println(line);
        }
    }

    /**
     * Get a method by name from an object.
     * NOTE: If there are two methods with the same name (and overloaded
     * signatures), the first one found will be returned. This is fine for HW1,
     * but would not necessarily be satisfactory for other uses.
     * @param o
     * @param name
     * @return
     */
    public static Method getMethodByName(Object o, String name) {
        Method [] meths = o.getClass().getMethods();
        for (Method m: meths) {
            if (m.getName().equals(name)) {
                return m;
            }
        }
        return null;
    }

    public static void ui() {
        final int arrayCap = 3;
        RootishArrayStack<String> array = new RootishArrayStack<>(arrayCap, String.class);
        System.out.printf("Welcome to the %s interactive shell!", array.getClass().getName());
        System.out.println();
        Scanner scanner = new Scanner(System.in);
        String input = "";
        System.out.printf("Initial array capacity: %d\n\n", arrayCap);
        printHelp();
        do {
            System.out.print("> ");

            input = scanner.nextLine();

            input = input.trim();
            if (input.equals("quit") || input.equals("q")) {
                System.exit(0);
            }
            else if (input.equals("help") || input.equals("h")) {
                printHelp();
                continue;
            }

            List<String> tokens = Arrays.asList(input.split("\\s+"));
            String command = tokens.get(0);
            Method cmdMeth = getMethodByName(array, command);
            if (cmdMeth == null) {
                System.out.printf("Unknown command: '%s'\n", command);
                printHelp();
                continue;
            }

            // Command found. Now we need to convert parameters.
            List<String> args = tokens.subList(1, tokens.size());
            int argsCount = args.size();
            Parameter [] params = cmdMeth.getParameters();
            if (argsCount != params.length) {
                // Wrong number of args.
                System.out.printf(
                        "Invalid number of arguments for command '%s'\n",
                        command);
                printHelp();
                continue;
            }

            // Correct number of arguments.
            // Now we need to convert the args.
            Class [] argTypes = COMMANDS.get(command);
            Object [] inputArgs = new Object[params.length];
            for (int i = 0; i < argTypes.length; i++) {
                Class c = argTypes[i];
                String a = args.get(i);
                if (c.getName().equals("java.lang.Integer")) {
                    inputArgs[i] = Integer.parseInt(a);
                }
                else {
                    // Assume it's a string
                    inputArgs[i] = a;
                }
            }
            try {
                Object ret = cmdMeth.invoke(array, inputArgs);
                if (ret != null) {
                    // If the return value is an array, print it nicely
                    if (ret instanceof Object[]) {
                        for (Object o: (Object[])ret) {
                            System.out.print(o.toString() + " ");
                        }
                        System.out.println();
                    }
                    else {
                        System.out.println(ret);
                    }
                }
            } catch (InvocationTargetException e) {
                e.getTargetException().printStackTrace();
            } catch (IllegalAccessException e) {
                e.printStackTrace();
            } catch (IllegalArgumentException e) {
                e.printStackTrace();
            }
        } while (!(
                input.toLowerCase() == "q"
                || input.toLowerCase() == "quit"));
    }

    public static void main(String[] args) {
        ui();
    }

}

Week2.txt

Week 2 discussion assignment
Lars Butler

Files included:
    Week2.java - Interactive text/shell UI for exercising RootishArrayStack functions
    RootishArrayStack.java - The main piece of this exercise
    RootishArrayStackTest.java - Unit tests for RootishArrayStack
    Testable.java - Lightweight unit testing library class, for running unit tests
    Week2-test-report1.png - Console output of program testing
    Week2-test-report2.png - Console output, continued
    Week2.txt - This file

For this task, I implemented the RootishArrayStack from
http://opendatastructures.org/ods-java/2_6_RootishArrayStack_Space.html. Most
of the code was given on this web page, but some of it I had to figure out
myself.

Most of the work here I did was to write the test code. The code in Week2.java
was adapted from code I submitted for `Homework 1`, so I didn't have to do much
with it this time around, except for adapt the command interface, fix a very
small bug, and add print capabilities for arrays (for the display of `toArray`).

To run the interactive program:

$ javac Week2.java
$ java Week2

Help text will be displayed to show you how to use it.

To run the test code and see a summarized test report:

$ javac RootishArrayStackTest.java
$ java RootishArrayStackTest

The test output should look like this:

testGet: pass
testI2b: pass
testSet: pass
testAdd_outOfBounds: pass
testConstructor: pass
testAdd_append: pass
testAdd_insert: pass
testSet_outOfBounds: pass
testRemove: pass
testRemove_outOfBounds: pass
10/10 tests ran successfully (failed: 0)

Week2.java is pretty messy; I plan to use it for future assignments, so I need
to take some time and clean it up.

-Lars