import java.io.ByteArrayOutputStream; import java.io.PrintStream; import java.lang.reflect.Field; import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; /** * Lab 05 tester. * * javac *.java * java Lab05Tester * * Runs every check and keeps going after a failure, then prints a summary. * Besides interface behavior, it looks INSIDE your LinkedList: after each * operation it checks that head, tail, and size agree with the actual nodes. * For that it needs fields named head and tail (any capitalization). * * Passing every check does not guarantee full credit. You still need your own * expected-versus-got tests, your hand traces, and your explanations. */ public class Lab05Tester { private static int passed = 0, failed = 0, skipped = 0; private static void check(boolean condition, String message) { if (condition) { passed++; System.out.println(" [PASS] " + message); } else { failed++; System.out.println(" [FAIL] " + message); } } private static void fail(String message) { failed++; System.out.println(" [FAIL] " + message); } private static void skip(String message) { skipped++; System.out.println(" [SKIP] " + message); } private static final int SECONDS = 10; private static final String LOOP_HINT = "\n a next link that points back into the list, or a loop that never reaches null."; private static volatile boolean timedOut = false; /** Runs one section; reports a FAIL instead of hanging if it never finishes. */ private static void runSection(Runnable section) { final Throwable[] thrown = new Throwable[1]; Thread worker = new Thread(() -> { try { section.run(); } catch (Throwable e) { thrown[0] = e; } }); worker.setDaemon(true); worker.start(); try { worker.join(SECONDS * 1000L); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } if (worker.isAlive()) { fail("this section did not finish in " + SECONDS + " seconds. Look for an infinite loop:" + LOOP_HINT); timedOut = true; } else if (thrown[0] != null) { fail("this section stopped early because your code threw " + thrown[0]); } } private static void section(String title) { System.out.println(); System.out.println("== " + title + " =="); } // ------------------------------------------------------------------ // Looking inside LinkedList: head, tail, and the nodes' next links // ------------------------------------------------------------------ private static Field headField, tailField, nextField; private static String pointerSetupProblem = null; private static void findPointerFields() { for (Field f : LinkedList.class.getDeclaredFields()) { String name = f.getName().toLowerCase(); if (name.equals("head")) headField = f; if (name.equals("tail")) tailField = f; } if (headField == null || tailField == null) { pointerSetupProblem = "LinkedList needs fields named head and tail for pointer checks" + " (found head: " + (headField != null) + ", tail: " + (tailField != null) + ")"; return; } if (headField.getType() != tailField.getType()) { pointerSetupProblem = "head and tail should have the same node type"; return; } Class nodeType = headField.getType(); for (Field f : nodeType.getDeclaredFields()) { if (f.getType() == nodeType) nextField = f; } if (nextField == null) { pointerSetupProblem = "could not find the node's next field (a field of type " + nodeType.getSimpleName() + " inside " + nodeType.getSimpleName() + ")"; return; } headField.setAccessible(true); tailField.setAccessible(true); nextField.setAccessible(true); } /** Returns a description of what is wrong with head/tail/size, or null if all is well. */ private static String structureProblem(LinkedList list) { try { Object head = headField.get(list); Object tail = tailField.get(list); int size = list.size(); if (size == 0) { if (head != null && tail != null) return "size is 0 but head and tail are not null"; if (head != null) return "size is 0 but head is not null"; if (tail != null) return "size is 0 but tail is not null (it still points at a removed node)"; return null; } if (size < 0) return "size is negative"; if (head == null) return "size is " + size + " but head is null"; if (tail == null) return "size is " + size + " but tail is null"; int count = 1; Object last = head; Object next = nextField.get(last); while (next != null && count <= size) { last = next; count++; next = nextField.get(last); } if (count > size) return "more nodes are reachable from head than size() reports (" + size + ")"; if (count < size) return "size() is " + size + " but only " + count + " nodes are reachable from head"; if (last != tail) return "tail does not point to the last node reachable from head"; if (size == 1 && head != tail) return "one item, but head and tail are different nodes"; return null; } catch (IllegalAccessException e) { return "could not read the fields: " + e; } } private static void checkStructure(LinkedList list, String when) { if (pointerSetupProblem != null) return; // reported once at the start String problem = structureProblem(list); if (problem == null) check(true, "pointers correct " + when); else fail("pointers wrong " + when + ": " + problem); } // ------------------------------------------------------------------ // Sections // ------------------------------------------------------------------ private static void stackSection() { section("Task 1 and 3: Stack behavior and pointers"); LinkedList list = new LinkedList(); Stack s = list; check(s.size() == 0 && s.pop() == null && s.peek() == null, "empty stack: size 0, pop and peek return null"); checkStructure(list, "on a new list and after an empty pop"); s.push("A"); check(s.peek().equals("A") && s.size() == 1, "push A: peek A, size 1"); checkStructure(list, "after push A (first node is also the last)"); s.push("B"); s.push("C"); check(s.peek().equals("C") && s.size() == 3, "push B, C: peek C, size 3"); checkStructure(list, "after push B, C (tail should still be A)"); check("C".equals(s.pop()) && "B".equals(s.pop()), "LIFO: pop C then B"); checkStructure(list, "after popping back to one item"); check("A".equals(s.pop()) && s.size() == 0, "pop A: size 0"); checkStructure(list, "after popping the last item (tail must be cleared)"); check(s.pop() == null && s.size() == 0, "pop on empty: null, size still 0"); checkStructure(list, "after pop on empty"); s.push("D"); checkStructure(list, "after pushing onto a stack that had been emptied"); s.peek(); check(s.size() == 1, "peek does not change size"); LinkedList cycle = new LinkedList(); Stack again = cycle; boolean ok = true; String structure = null; for (int i = 0; i < 20 && ok; i++) { again.push(i); if (structure == null && pointerSetupProblem == null) structure = structureProblem(cycle); ok = again.peek() == i && again.size() == 1 && again.pop() == i && again.size() == 0 && again.peek() == null; if (structure == null && pointerSetupProblem == null) structure = structureProblem(cycle); } check(ok, "20 push/pop cycles through empty"); if (pointerSetupProblem == null) { if (structure == null) check(true, "pointers correct throughout push/pop cycles"); else fail("pointers wrong during push/pop cycles: " + structure); } } private static void queueSection() { section("Task 4: Queue behavior and pointers"); LinkedList list = new LinkedList(); Queue q = list; check(q.size() == 0 && q.poll() == null && q.peek() == null, "empty queue: size 0, poll and peek return null"); checkStructure(list, "on a new queue and after an empty poll"); q.offer("A"); check("A".equals(q.peek()) && q.size() == 1, "offer A: peek A, size 1"); checkStructure(list, "after offering to an empty queue"); q.offer("B"); q.offer("C"); check("A".equals(q.peek()) && q.size() == 3, "offer B, C: peek still A, size 3"); checkStructure(list, "after offer B, C (tail should be C)"); check("A".equals(q.poll()), "FIFO: poll A"); q.offer("D"); checkStructure(list, "after poll then offer"); check("B".equals(q.poll()) && "C".equals(q.poll()) && "D".equals(q.poll()), "interleaved FIFO: poll B, C, D"); check(q.size() == 0, "size 0 after polling everything"); checkStructure(list, "after polling the last item (tail must be cleared)"); q.offer("E"); checkStructure(list, "after offering to a queue that had been emptied"); check("E".equals(q.poll()) && q.poll() == null, "poll E, then null"); LinkedList cycle = new LinkedList(); Queue again = cycle; boolean ok = true; String structure = null; for (int i = 0; i < 20 && ok; i++) { again.offer(i); if (structure == null && pointerSetupProblem == null) structure = structureProblem(cycle); ok = again.poll() == i && again.size() == 0; if (structure == null && pointerSetupProblem == null) structure = structureProblem(cycle); } check(ok && again.poll() == null && again.peek() == null, "20 offer/poll cycles through empty"); if (pointerSetupProblem == null) { if (structure == null) check(true, "pointers correct throughout offer/poll cycles"); else fail("pointers wrong during offer/poll cycles: " + structure); } LinkedList big = new LinkedList(); for (int i = 0; i < 1000; i++) big.offer(i); boolean order = true; for (int i = 0; i < 1000; i++) if (big.poll() != i) order = false; check(order && big.size() == 0, "1000 offers then 1000 polls come out in order"); } /** Calls a list method by reflection; returns null if the method does not exist. */ private static Method method(String name, Class... params) { try { return LinkedList.class.getMethod(name, params); } catch (NoSuchMethodException e) { return null; } } private static String drain(Queue q) { StringBuilder sb = new StringBuilder(); String item; while ((item = q.poll()) != null) sb.append(item); return sb.toString(); } private static void listMethodSection() { section("Task 3: your other list methods keep tail correct"); if (pointerSetupProblem != null) { skip("needs head and tail fields (see above)"); return; } Method addAt = method("add", int.class, Object.class); Method removeAt = method("remove", int.class); Method clear = method("clear"); try { if (addAt == null) { skip("no add(int index, T item) method found; test your own insert-by-index method in main"); } else { LinkedList list = new LinkedList(); addAt.invoke(list, 0, "A"); checkStructure(list, "after add(0, A) on an empty list"); list.offer("B"); addAt.invoke(list, 2, "C"); checkStructure(list, "after add(size, C) appends at the end"); list.offer("D"); addAt.invoke(list, 1, "x"); checkStructure(list, "after add(1, x) in the middle"); check("AxBCD".equals(drain(list)), "add by index then offer: items in order A x B C D"); } if (removeAt == null) { skip("no remove(int index) method found; test your own remove-by-index method in main"); } else { LinkedList list = new LinkedList(); list.offer("A"); list.offer("B"); list.offer("C"); removeAt.invoke(list, 2); checkStructure(list, "after remove(size - 1) removes the last node"); list.offer("D"); check("ABD".equals(drain(list)), "remove last by index then offer: A B D"); list.offer("E"); removeAt.invoke(list, 0); checkStructure(list, "after remove(0) on a one-item list"); } if (clear == null) { skip("no clear() method found"); } else { LinkedList list = new LinkedList(); list.offer("A"); list.offer("B"); clear.invoke(list); checkStructure(list, "after clear()"); list.offer("C"); checkStructure(list, "after clear() then offer"); check("C".equals(list.peek()) && list.size() == 1, "clear then offer: only C remains"); } } catch (InvocationTargetException e) { fail("a list method threw " + e.getCause()); } catch (IllegalAccessException e) { fail("could not call a list method: " + e); } } private static void mazeSection() { section("Task 5: Maze and Cell"); Maze m = new Maze(3, 5, 0); check(m.getRows() == 3 && m.getCols() == 5, "rectangular dimensions"); check(m.getNeighbors(m.get(0, 0)).size() == 2, "corner has 2 neighbors"); int[][] expected = { { 0, 2 }, { 2, 2 }, { 1, 3 }, { 1, 1 } }; int i = 0; boolean ordered = true; for (Cell c : m.getNeighbors(m.get(1, 2))) { if (i >= 4 || c != m.get(expected[i][0], expected[i][1])) ordered = false; i++; } check(ordered && i == 4, "interior neighbors: up, down, right, left, and the maze's own Cells"); m.get(1, 3).setType(CellType.OBSTACLE); check(m.getNeighbors(m.get(1, 2)).size() == 3, "obstacles are not neighbors"); m.get(2, 4).setPrev(m.get(2, 4)); check(m.countVisitedCells() == 1, "discovery count includes the last column"); m.reset(); check(m.countVisitedCells() == 0 && m.get(1, 3).getType() == CellType.OBSTACLE, "reset clears prev but keeps obstacles"); int cells = 0; for (Cell c : m) cells++; check(cells == 15, "iterating over the maze visits all 15 cells"); } private static String capture(Runnable code) { PrintStream original = System.out; ByteArrayOutputStream buffer = new ByteArrayOutputStream(); System.setOut(new PrintStream(buffer)); try { code.run(); } finally { System.setOut(original); } return buffer.toString().trim(); } /** The order line only; the grid printed after it is for students to read. */ private static String firstLine(String output) { int end = output.indexOf('\n'); return (end < 0 ? output : output.substring(0, end)).trim(); } private static void frontierOrderSection() { section("Task 6: frontier order (MazePractice)"); // A different grid from the hand trace, so this does not give the trace away. final Maze m = new Maze(2, 4, 0); try { String stack = firstLine(capture(() -> MazePractice.printStackOrder(m, m.get(0, 0), 8))); String expectStack = "Stack order: (0,0) (0,1) (0,2) (0,3) (1,3) (1,2) (1,1) (1,0)"; if (stack.equals(expectStack)) check(true, "printStackOrder on a 2x4 grid from (0,0)"); else fail("printStackOrder on a 2x4 grid from (0,0) (it uses your Stack and Maze)" + "\n expected: " + expectStack + "\n got: " + stack); String queue = firstLine(capture(() -> MazePractice.printQueueOrder(m, m.get(0, 0), 8))); if (queue.isEmpty()) { fail("printQueueOrder printed nothing; complete it in MazePractice.java"); } else if (queue.equals("Queue order: (0,0) (1,0) (0,1) (1,1) (0,2) (1,2) (0,3) (1,3)")) { check(true, "printQueueOrder on a 2x4 grid from (0,0)"); } else { fail("printQueueOrder on a 2x4 grid from (0,0) gave the wrong order" + "\n got: " + queue + "\n Trace it by hand: a queue removes the OLDEST discovered cell first."); } } catch (RuntimeException e) { fail("MazePractice threw " + e); } } public static void main(String[] args) { System.out.println("Lab 05 Tester"); findPointerFields(); if (pointerSetupProblem != null) { System.out.println(); skip(pointerSetupProblem); System.out.println(" Pointer checks are skipped. Rename your fields, or check head and tail by hand."); } Runnable[] sections = { Lab05Tester::stackSection, Lab05Tester::queueSection, Lab05Tester::listMethodSection, Lab05Tester::mazeSection, Lab05Tester::frontierOrderSection }; for (Runnable section : sections) { if (timedOut) break; runSection(section); } if (timedOut) System.out.println("\n Stopped after a section timed out; fix that first, then run again."); System.out.println(); System.out.println("Summary: " + passed + " passed, " + failed + " failed, " + skipped + " skipped."); if (failed == 0) { System.out.println("All checks passed. Also show your own tests, traces, and explanations."); } else { System.out.println("Fix the first FAIL above first; later failures are often caused by it."); } System.exit(failed == 0 ? 0 : 1); // also ends any stuck section } }