/* * file name: LinkedListTester.java * purpose: Guided tester for CS231 Lab 3 (LinkedList). * * How to run (no -ea flag needed): * javac LinkedList.java LinkedListTester.java * java LinkedListTester runs the tasks in order and stops at the * first task that still needs work * java LinkedListTester 7 runs only Task 7 * * You do not need to edit this file. It will not crash if your code throws * an exception or gets stuck in a loop - it reports what happened and where. */ import java.lang.reflect.Constructor; import java.lang.reflect.Field; import java.lang.reflect.Method; import java.lang.reflect.Modifier; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Objects; public class LinkedListTester { private static final int CHECKPOINT_TASK = 6; private static final long TIME_LIMIT_MS = 3000; // ================================================================== // The tasks, in order. Each matches a task on the Lab 3 page. // ================================================================== private static List buildTasks() { List tasks = new ArrayList<>(); tasks.add(new Task(1, "Node, fields, constructor, size(), isEmpty()", LinkedListTester::task1)); tasks.add(new Task(2, "add(T item) and toString()", LinkedListTester::task2)); tasks.add(new Task(3, "get(int index)", LinkedListTester::task3)); tasks.add(new Task(4, "add(int index, T item)", LinkedListTester::task4)); tasks.add(new Task(5, "contains(Object o)", LinkedListTester::task5)); tasks.add(new Task(6, "remove() and clear()", LinkedListTester::task6)); tasks.add(new Task(7, "remove(int index)", LinkedListTester::task7)); tasks.add(new Task(8, "equals(Object o)", LinkedListTester::task8)); tasks.add(new Task(9, "LLIterator and iterator()", LinkedListTester::task9)); return tasks; } // ------------------------------------------------------------------ // TASK 1 // ------------------------------------------------------------------ private static void task1() throws Throwable { // --- structure of Node --- Class nodeClass = findNested(LinkedList.class, "Node"); check("LinkedList contains a nested class named Node", nodeClass != null, "Keep the class named exactly Node inside LinkedList."); if (nodeClass == null) { return; } check("Node is private", Modifier.isPrivate(nodeClass.getModifiers()), "Code outside LinkedList should never see Nodes. Declare it: private class Node"); Field nextField = findFieldOfType(nodeClass, nodeClass); check("Node has a field of type Node (next)", nextField != null, "Node needs a field like: private Node next;"); Field dataField = findFieldOfType(nodeClass, Object.class); check("Node has a field of type T to hold its item", dataField != null, "Declare a field like: private T data; (Inside LinkedList, Node can use T.)"); // --- behavior of Node (reached through reflection, since Node is private) --- LinkedList outer = new LinkedList(); Constructor ctor = nodeClass.getDeclaredConstructors()[0]; ctor.setAccessible(true); Object nodeA = ctor.newInstance(outer, "apple"); Object nodeB = ctor.newInstance(outer, "banana"); Method getData = nodeClass.getDeclaredMethod("getData"); Method getNext = nodeClass.getDeclaredMethod("getNext"); Method setNext = nodeClass.getDeclaredMethod("setNext", nodeClass); getData.setAccessible(true); getNext.setAccessible(true); setNext.setAccessible(true); checkEquals("new Node(\"apple\").getData()", "apple", getData.invoke(nodeA), "The Node constructor should store item in your data field, and getData() should return it."); checkEquals("new Node(\"apple\").getNext()", null, getNext.invoke(nodeA), "A brand-new Node has no next Node yet: next should be null."); setNext.invoke(nodeA, nodeB); check("after a.setNext(b), a.getNext() returns b", getNext.invoke(nodeA) == nodeB, "setNext(n) should store n in next; getNext() should return next."); // --- LinkedList fields --- check("LinkedList has a field of type Node (head)", findFieldOfType(LinkedList.class, nodeClass) != null, "Keep the field: private Node head;"); // --- empty list behavior --- LinkedList ll = new LinkedList(); check("new LinkedList() is not null", ll != null, ""); checkEquals("size() of a new list", 0, ll.size(), "A new list holds zero items."); checkEquals("isEmpty() of a new list", true, ll.isEmpty(), "isEmpty() should return true when size is 0."); } // ------------------------------------------------------------------ // TASK 2 // ------------------------------------------------------------------ private static void task2() throws Throwable { LinkedList empty = new LinkedList(); checkEquals("toString() of an empty list", "[]", empty.toString(), "An empty list prints as [] (brackets with nothing between them)."); LinkedList one = new LinkedList(); one.add(7); checkEquals("size() after add(7)", 1, one.size(), "add(item) must increase size by 1."); checkEquals("isEmpty() after add(7)", false, one.isEmpty(), "isEmpty() should be false once the list holds an item."); checkEquals("toString() after add(7)", "[7]", one.toString(), "One item prints as [7] - no comma."); LinkedList ll = new LinkedList(); for (int i = 0; i < 5; i++) { ll.add(i); } checkEquals("size() after add(0), add(1), ... add(4)", 5, ll.size(), "Each call to add(item) must increase size by 1."); checkEquals("toString() after add(0), add(1), ... add(4)", "[4, 3, 2, 1, 0]", ll.toString(), "add(item) inserts at the FRONT, so the last item added is printed first.\n" + "If you see only one number, head may not be moving to the new Node.\n" + "If you see a trailing comma, only put \", \" between items."); LinkedList words = new LinkedList(); words.add("c"); words.add("b"); words.add("a"); checkEquals("LinkedList: add(\"c\"), add(\"b\"), add(\"a\") then toString()", "[a, b, c]", words.toString(), "Your list should work for any type T, not only Integer."); } // ------------------------------------------------------------------ // TASK 3 // ------------------------------------------------------------------ private static void task3() throws Throwable { LinkedList ll = new LinkedList(); for (int i = 0; i < 5; i++) { ll.add(4 - i); // list is [0, 1, 2, 3, 4] } String desc = " on the list [0, 1, 2, 3, 4]"; checkEquals("get(0)" + desc, 0, ll.get(0), "get(0) is the item in the head Node."); checkEquals("get(1)" + desc, 1, ll.get(1), "To reach index 1, step forward from head one time."); checkEquals("get(3)" + desc, 3, ll.get(3), "Check your loop bounds: to reach index i, step forward exactly i times."); checkEquals("get(4)" + desc + " (the last item)", 4, ll.get(4), "If this crashed, your loop may step one Node too far (past the end)."); checkEquals("size() is unchanged after calling get()", 5, ll.size(), "get() should only look at the list, never change it."); checkEquals("get(1) still returns the same item when called again", 1, ll.get(1), "get() must not move head. Use a separate 'current' reference to walk."); LinkedList words = new LinkedList(); words.add("z"); words.add("y"); words.add("x"); checkEquals("LinkedList [x, y, z]: get(2)", "z", words.get(2), ""); } // ------------------------------------------------------------------ // TASK 4 // ------------------------------------------------------------------ private static void task4() throws Throwable { LinkedList empty = new LinkedList(); empty.add(0, 9); checkEquals("add(0, 9) on an empty list, then size()", 1, empty.size(), "Inserting at index 0 is the same as add(item)."); checkEquals("add(0, 9) on an empty list, then get(0)", 9, empty.get(0), ""); LinkedList end = new LinkedList(); end.add(2); end.add(1); // [1, 2] end.add(2, 3); // at the end checkEquals("[1, 2] then add(2, 3) (insert at the end): toString()", "[1, 2, 3]", end.toString(), "index == size() means 'insert after the last item'. Walk to the Node at index - 1."); checkEquals("[1, 2] then add(2, 3): size()", 3, end.size(), "add(index, item) must increase size."); LinkedList ll = new LinkedList(); ll.add(0, 1); ll.add(1, 4); ll.add(1, 2); ll.add(0, 0); ll.add(4, 5); ll.add(3, 3); String steps = "add(0,1), add(1,4), add(1,2), add(0,0), add(4,5), add(3,3)"; checkEquals("size() after " + steps, 6, ll.size(), "Every add(index, item) must increase size by 1 - including the index-0 case."); checkEquals("toString() after " + steps, "[0, 1, 2, 3, 4, 5]", ll.toString(), "Walk to the Node BEFORE the insertion point (index - 1).\n" + "Then: newNode.setNext(before.getNext()); before.setNext(newNode);\n" + "Doing those two steps in the other order loses the rest of the list."); boolean allMatch = true; for (int i = 0; i < 6; i++) { if (!Objects.equals(i, ll.get(i))) { allMatch = false; } } check("get(i) == i for every i in that list", allMatch, ""); LinkedList words = new LinkedList(); words.add(0, "b"); words.add(0, "a"); words.add(2, "d"); words.add(2, "c"); words.add("start"); checkEquals("add(0,\"b\"), add(0,\"a\"), add(2,\"d\"), add(2,\"c\"), add(\"start\")", "[start, a, b, c, d]", words.toString(), "After inserting with add(index, item), add(item) should still put items at the front."); } // ------------------------------------------------------------------ // TASK 5 // ------------------------------------------------------------------ private static void task5() throws Throwable { LinkedList ll = new LinkedList(); for (int i = 0; i < 3; i++) { ll.add(2 * i); // [4, 2, 0] } checkEquals("[4, 2, 0].contains(0) (last item)", true, ll.contains(0), "Make sure your loop checks the LAST Node, too."); checkEquals("[4, 2, 0].contains(4) (first item)", true, ll.contains(4), "Make sure your loop checks the head Node."); checkEquals("[4, 2, 0].contains(3)", false, ll.contains(3), "Return false only after checking every Node."); checkEquals("empty list .contains(1)", false, new LinkedList().contains(1), "An empty list contains nothing (and must not crash)."); LinkedList fruit = new LinkedList(); fruit.add("pear"); fruit.add("apple"); String sameLetters = new String("pear"); // equal text, but a different object checkEquals("contains(new String(\"pear\")) on [apple, pear]", true, fruit.contains(sameLetters), "Use item.equals(o), not ==. Here the two Strings have the same letters but are\n" + "different objects in memory, so == says false while .equals says true."); LinkedList big = new LinkedList(); big.add(Integer.valueOf(1000)); checkEquals("contains(1000) where 1000 was stored as a different Integer object", true, big.contains(Integer.valueOf(1000)), "Use .equals(), not ==, when comparing objects."); checkEquals("[apple, pear].contains(null)", false, fruit.contains(null), "Call item.equals(o) (item is never null here), not o.equals(item)."); checkEquals("size() unchanged after contains()", 2, fruit.size(), "contains() must not change the list."); } // ------------------------------------------------------------------ // TASK 6 // ------------------------------------------------------------------ private static void task6() throws Throwable { LinkedList ll = new LinkedList(); for (int i = 0; i < 5; i++) { ll.add(4 - i); // [0, 1, 2, 3, 4] } checkEquals("first remove() on [0, 1, 2, 3, 4]", 0, ll.remove(), "remove() returns the item that was in the head Node."); checkEquals("second remove()", 1, ll.remove(), "After removing, head must move to the next Node."); checkEquals("size() after two removes", 3, ll.size(), "remove() must decrease size by 1."); checkEquals("toString() after two removes", "[2, 3, 4]", ll.toString(), ""); ll.remove(); ll.remove(); ll.remove(); checkEquals("after removing every item: isEmpty()", true, ll.isEmpty(), ""); checkEquals("after removing every item: toString()", "[]", ll.toString(), "When the last Node is removed, head should become null."); checkEquals("remove() on an empty list returns", null, ll.remove(), "If the list is empty, return null instead of crashing (check head == null first)."); checkEquals("size() after remove() on an empty list", 0, ll.size(), "Removing from an empty list must not make size negative."); ll.add(42); checkEquals("add(42) after emptying the list: toString()", "[42]", ll.toString(), "The list should be fully usable after it becomes empty."); LinkedList words = new LinkedList(); words.add("c"); words.add("b"); words.add("a"); words.clear(); checkEquals("clear(): size()", 0, words.size(), "clear() resets the fields of an empty list."); checkEquals("clear(): isEmpty()", true, words.isEmpty(), ""); checkEquals("clear(): toString()", "[]", words.toString(), "After clear(), head should be null."); words.add("new"); checkEquals("add(\"new\") after clear(): toString()", "[new]", words.toString(), ""); } // ------------------------------------------------------------------ // TASK 7 // ------------------------------------------------------------------ private static void task7() throws Throwable { LinkedList ll = new LinkedList(); for (int i = 0; i < 8; i++) { ll.add(7 - i); // [0, 1, 2, 3, 4, 5, 6, 7] } checkEquals("remove(0) on [0, 1, 2, 3, 4, 5, 6, 7]", 0, ll.remove(0), "Index 0 is a special case - which method already removes the head?"); checkEquals("then remove(3) on [1, 2, 3, 4, 5, 6, 7]", 4, ll.remove(3), "Walk to the Node BEFORE the one to remove (index - 1), then make it skip over it."); checkEquals("then remove(5) on [1, 2, 3, 5, 6, 7] (the last item)", 7, ll.remove(5), "Removing the last Node: the Node before it should end up with next == null."); checkEquals("size() after three removes", 5, ll.size(), "remove(index) must decrease size."); checkEquals("toString() after three removes", "[1, 2, 3, 5, 6]", ll.toString(), ""); LinkedList words = new LinkedList(); words.add("c"); words.add("b"); words.add("a"); // [a, b, c] words.remove(2); words.add(2, "z"); checkEquals("[a, b, c]: remove(2), then add(2, \"z\")", "[a, b, z]", words.toString(), "After removing the last item, the list must still end correctly."); LinkedList single = new LinkedList(); single.add("only"); checkEquals("remove(0) on a one-item list returns", "only", single.remove(0), ""); checkEquals("then isEmpty()", true, single.isEmpty(), ""); } // ------------------------------------------------------------------ // TASK 8 // ------------------------------------------------------------------ private static void task8() throws Throwable { LinkedList list1 = new LinkedList(); LinkedList list2 = new LinkedList(); LinkedList list3 = new LinkedList(); LinkedList list4 = new LinkedList(); for (int i = 0; i < 3; i++) { list1.add(i); list2.add(i); list3.add(i); list4.add(i); } list3.add(4); list4.add(5); // list1 = list2 = [2, 1, 0]; list3 = [4, 2, 1, 0]; list4 = [5, 2, 1, 0] checkEquals("[2, 1, 0] equals [2, 1, 0]", true, list1.equals(list2), "Two different list objects with equal items in the same order are equal."); checkEquals("[2, 1, 0] equals [4, 2, 1, 0]", false, list2.equals(list3), "Lists of different sizes are never equal."); checkEquals("[4, 2, 1, 0] equals [2, 1, 0]", false, list3.equals(list2), "Lists of different sizes are never equal (check in both directions)."); checkEquals("[4, 2, 1, 0] equals [5, 2, 1, 0]", false, list3.equals(list4), "Same size is not enough - compare every pair of items."); checkEquals("[5, 2, 1, 0] equals \"Hello\"", false, list4.equals("Hello"), "If o is not a LinkedList, return false (use instanceof)."); checkEquals("[5, 2, 1, 0] equals null", false, list4.equals(null), "null is not a LinkedList, so the answer is false."); checkEquals("empty list equals empty list", true, new LinkedList().equals(new LinkedList()), ""); checkEquals("a list equals itself", true, list1.equals(list1), ""); checkEquals("size() of both lists unchanged after equals()", "3 and 3", list1.size() + " and " + list2.size(), "equals() must not change either list. Walk with separate references; don't call remove()."); LinkedList a = new LinkedList(); LinkedList b = new LinkedList(); a.add(new String("hi")); b.add(new String("hi")); checkEquals("[hi] equals [hi] (different String objects with the same letters)", true, a.equals(b), "Compare items with .equals(), not ==."); } // ------------------------------------------------------------------ // TASK 9 // ------------------------------------------------------------------ private static void task9() throws Throwable { LinkedList ll = new LinkedList(); ll.add(0, 1); ll.add(1, 4); ll.add(1, 2); ll.add(0, 0); ll.add(4, 5); ll.add(3, 3); // [0, 1, 2, 3, 4, 5] Iterator it = ll.iterator(); check("iterator() returns an Iterator (not null)", it != null, "iterator() should return new LLIterator(this.head);"); if (it == null) { return; } checkEquals("hasNext() on a fresh iterator of [0, 1, 2, 3, 4, 5]", true, it.hasNext(), "hasNext() is true when the iterator's Node field is not null.\n" + "Did the LLIterator constructor store the head it was given?"); checkEquals("first next()", 0, it.next(), "next() returns the item in the current Node..."); checkEquals("second next()", 1, it.next(), "...and then moves the iterator's Node forward."); StringBuilder seen = new StringBuilder(); int count = 0; for (Integer value : ll) { if (count > 0) { seen.append(", "); } seen.append(value); count++; if (count > 50) { break; // protects against an iterator that never ends } } checkEquals("for-each loop over [0, 1, 2, 3, 4, 5] visits", "0, 1, 2, 3, 4, 5", seen.toString(), "hasNext() must become false after the last item has been returned by next()."); int emptyCount = 0; for (Integer value : new LinkedList()) { emptyCount++; } checkEquals("for-each loop over an empty list runs this many times", 0, emptyCount, "For an empty list, hasNext() should be false right away."); LinkedList words = new LinkedList(); words.add("c"); words.add("b"); words.add("a"); int pairs = 0; for (String x : words) { for (String y : words) { pairs++; } } checkEquals("nested for-each loops over a 3-item list (two independent iterators)", 9, pairs, "Each call to iterator() must return a NEW LLIterator with its own position.\n" + "Store the position in the LLIterator, never by moving the list's head."); checkEquals("size() unchanged after iterating", 3, words.size(), "Iterating must not change the list."); checkEquals("toString() unchanged after iterating", "[a, b, c]", words.toString(), ""); } // ================================================================== // Tester machinery - you do not need to read below this line. // ================================================================== @FunctionalInterface private interface TaskBody { void run() throws Throwable; } private static class Task { final int number; final String title; final TaskBody body; Task(int number, String title, TaskBody body) { this.number = number; this.title = title; this.body = body; } } private enum Result { PASS, FAIL, CRASH, TIMEOUT } private static int passed; private static int failed; private static void check(String description, boolean ok, String hint) { if (ok) { passed++; System.out.println(" [PASS] " + description); } else { failed++; System.out.println(" [FAIL] " + description); printHint(hint); } } private static void checkEquals(String description, Object expected, Object actual, String hint) { if (Objects.equals(expected, actual)) { passed++; System.out.println(" [PASS] " + description + " -> " + show(actual)); } else { failed++; System.out.println(" [FAIL] " + description); System.out.println(" expected: " + show(expected)); System.out.println(" got: " + show(actual)); printHint(hint); } } private static String show(Object o) { if (o instanceof String) { return "\"" + o + "\""; } return String.valueOf(o); } private static void printHint(String hint) { if (hint == null || hint.isEmpty()) { return; } String[] lines = hint.split("\n"); System.out.println(" hint: " + lines[0]); for (int i = 1; i < lines.length; i++) { System.out.println(" " + lines[i]); } } private static Class findNested(Class outer, String simpleName) { for (Class c : outer.getDeclaredClasses()) { if (c.getSimpleName().equals(simpleName)) { return c; } } return null; } private static Field findFieldOfType(Class owner, Class type) { for (Field f : owner.getDeclaredFields()) { if (f.getType() == type && !f.isSynthetic()) { return f; } } return null; } private static boolean isStudentFrame(StackTraceElement e) { String c = e.getClassName(); return c.equals("LinkedList") || c.startsWith("LinkedList$"); } private static void reportCrash(Throwable e) { if (e instanceof java.lang.reflect.InvocationTargetException && e.getCause() != null) { e = e.getCause(); } System.out.println(); System.out.println(" [CRASH] Your code threw " + e.getClass().getName()); if (e.getMessage() != null) { System.out.println(" message: " + e.getMessage()); } int shown = 0; for (StackTraceElement frame : e.getStackTrace()) { if (isStudentFrame(frame) && shown < 3) { System.out.println(" at: " + frame.getClassName().replace('$', '.') + "." + frame.getMethodName() + " (" + frame.getFileName() + " line " + frame.getLineNumber() + ")"); shown++; } } if (e instanceof NullPointerException) { printHint("A NullPointerException means a method was called on a reference that is null.\n" + "In a linked list this usually means walking past the last Node, or using head\n" + "when the list is empty. Draw the list and trace your loop by hand."); } else if (e instanceof StackOverflowError) { printHint("A method keeps calling itself forever. Check whether a method calls itself by\n" + "accident (for example, toString() building a String with \"\" + this)."); } else if (e instanceof ClassCastException) { printHint("A value was cast to the wrong type. Check your casts in equals()."); } } private static Result runTask(Task t) { passed = 0; failed = 0; System.out.println(); System.out.println("------------------------------------------------------------"); System.out.println(" Task " + t.number + " - " + t.title); System.out.println("------------------------------------------------------------"); final Throwable[] error = new Throwable[1]; Thread worker = new Thread(() -> { try { t.body.run(); } catch (Throwable e) { error[0] = e; } }); worker.setDaemon(true); worker.start(); try { worker.join(TIME_LIMIT_MS); } catch (InterruptedException ignored) { } if (worker.isAlive()) { System.out.println(); System.out.println(" [TIMEOUT] Task " + t.number + " did not finish within " + (TIME_LIMIT_MS / 1000) + " seconds."); printHint("This almost always means an infinite loop. In a while loop that walks the list,\n" + "make sure the loop variable moves forward every time: current = current.getNext();\n" + "Also check that a Node never ends up pointing to itself."); return Result.TIMEOUT; } if (error[0] != null) { reportCrash(error[0]); return Result.CRASH; } System.out.println(); System.out.println(" " + passed + " checks passed, " + failed + " failed."); return failed == 0 ? Result.PASS : Result.FAIL; } private static void banner(String... lines) { System.out.println(); System.out.println("============================================================"); for (String line : lines) { System.out.println(" " + line); } System.out.println("============================================================"); } public static void main(String[] args) { List tasks = buildTasks(); banner("CS231 Lab 3 - LinkedList Tester", "Tasks run in order. The tester stops at the first task that needs work.", "Tip: run a single task with java LinkedListTester "); if (args.length > 0) { int which; try { which = Integer.parseInt(args[0]); } catch (NumberFormatException e) { System.out.println("Please give a task number from 1 to " + tasks.size() + "."); return; } if (which < 1 || which > tasks.size()) { System.out.println("Please give a task number from 1 to " + tasks.size() + "."); return; } Result r = runTask(tasks.get(which - 1)); System.out.println(); System.out.println(r == Result.PASS ? "Task " + which + " is complete." : "Task " + which + " still needs work."); System.exit(0); } int completed = 0; for (Task t : tasks) { Result r = runTask(t); if (r != Result.PASS) { banner("Task " + t.number + " still needs work. (" + completed + " of " + tasks.size() + " tasks complete)", "Read the [FAIL] / [CRASH] messages above, experiment in main(),", "fix LinkedList.java, recompile, and run the tester again."); System.exit(0); } completed++; System.out.println(" Task " + t.number + " complete."); if (t.number == CHECKPOINT_TASK) { banner("LAB CHECKPOINT REACHED!", "add, get, contains and remove work. Call a TA or instructor over", "and show them this output - then keep going with Task 7."); } } banner("All " + tasks.size() + " Lab 3 tasks complete!", "Your LinkedList is ready for Project 3.", "Copy LinkedList.java into your Projects/Project3 folder."); System.exit(0); } }