import java.lang.reflect.Field; import java.util.ArrayList; import java.util.Random; import java.util.TreeSet; /** * Lab 06 tester. * * javac *.java * java Lab06Tester * * Runs every check and keeps going after a failure, then prints a summary. * A method that still has its "not written yet" line is reported as SKIP, so * you can run this after every task. * * Besides calling your methods, it looks INSIDE your tree: it reads the fields * root, key, value, left, and right from the provided BSTMap.java, so keep * those names. */ public class Lab06Tester { 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 checkEquals(Object expected, Object got, String message) { if (expected == null ? got == null : expected.equals(got)) { check(true, message); } else { fail(message + "\n should be: " + expected + "\n yours: " + got); } } 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 volatile boolean timedOut = false; /** Runs one section; a missing method is a SKIP, a crash or a hang is a FAIL. */ private static void runSection(Runnable section) { final Throwable[] thrown = new Throwable[1]; Thread worker = new Thread(null, () -> { try { section.run(); } catch (Throwable e) { thrown[0] = e; } }, "section", 1 << 24); 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."); timedOut = true; } else if (thrown[0] instanceof UnsupportedOperationException) { skip(thrown[0].getMessage() + ". The rest of this section waits until you write it."); } else if (thrown[0] instanceof StackOverflowError) { fail("this section stopped: your recursion never ended (StackOverflowError)." + "\n Does your helper stop when cur is null, and does every call" + "\n move down to cur.left or cur.right?"); } else if (thrown[0] instanceof NullPointerException) { fail("this section stopped early because your code threw " + thrown[0] + "\n Does each helper check for an empty subtree (cur == null)" + "\n before it reads cur.key? Lecture's search checks root==null first" + "\n (L23, slide 92)."); } 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 the tree // ------------------------------------------------------------------ private static String fieldProblem = null; private static Object field(Object object, String name) { try { Field f = object.getClass().getDeclaredField(name); f.setAccessible(true); return f.get(object); } catch (ReflectiveOperationException e) { throw new IllegalStateException("can't read field " + name); } } private static Object root(BSTMap map) { return field(map, "root"); } /** Number of nodes reachable from the root (stops at 100000 in case of a loop). */ private static int countNodes(Object node) { if (node == null) { return 0; } return 1 + countNodes(field(node, "left")) + countNodes(field(node, "right")); } /** Levels below and including node: an empty tree has 0. */ private static int levels(Object node) { if (node == null) { return 0; } return 1 + Math.max(levels(field(node, "left")), levels(field(node, "right"))); } /** The keys level by level, for example "level 0: dog | level 1: bee fox". */ private static String shape(Object root) { ArrayList rows = new ArrayList<>(); addKeys(root, 0, rows); String result = ""; for (int i = 0; i < rows.size(); i++) { result += (i == 0 ? "" : " | ") + "level " + i + ": " + rows.get(i); } return result; } private static void addKeys(Object node, int level, ArrayList rows) { if (node == null) { return; } while (rows.size() <= level) { rows.add(""); } rows.set(level, (rows.get(level) + " " + field(node, "key")).trim()); addKeys(field(node, "left"), level + 1, rows); addKeys(field(node, "right"), level + 1, rows); } /** Returns null if every left key is smaller and every right key larger, or a description. */ @SuppressWarnings({"unchecked", "rawtypes"}) private static String orderProblem(Object node, Comparable low, Comparable high) { if (node == null) { return null; } Comparable key = (Comparable) field(node, "key"); if (low != null && key.compareTo(low) <= 0) { return "\n " + key + " is in the RIGHT subtree of " + low + ", but " + key + " comes before " + low + ", so it belongs on the LEFT"; } if (high != null && key.compareTo(high) >= 0) { return "\n " + key + " is in the LEFT subtree of " + high + ", but " + key + " comes after " + high + ", so it belongs on the RIGHT"; } String left = orderProblem(field(node, "left"), low, key); return left != null ? left : orderProblem(field(node, "right"), key, high); } /** The node holding key (found by the tester's own search), or null. */ @SuppressWarnings({"unchecked", "rawtypes"}) private static Object nodeFor(Object node, Comparable key) { while (node != null) { int c = key.compareTo(field(node, "key")); if (c == 0) { return node; } node = field(node, c < 0 ? "left" : "right"); } return null; } // Lecture's tree uses the keys 15 8 17 3 10 16 20. These words have the same // alphabetical order, so they build the same tree: ant=3, bee=8, cat=10, // dog=15, eel=16, fox=17, gnu=20. Each word's value is its lecture number. private static final String[] WORDS = {"dog", "bee", "fox", "ant", "cat", "eel", "gnu"}; private static final int[] NUMBERS = {15, 8, 17, 3, 10, 16, 20}; private static final String LECTURE_SHAPE = "level 0: dog | level 1: bee fox | level 2: ant cat eel gnu"; /** Lecture's tree, built from the words in lecture's order. */ private static BSTMap lectureTree() { BSTMap map = new BSTMap<>(); for (int i = 0; i < WORDS.length; i++) { map.put(WORDS[i], NUMBERS[i]); } return map; } /** The seven words in alphabetical order, which makes a chain. */ private static BSTMap sortedTree() { BSTMap map = new BSTMap<>(); String[] sorted = {"ant", "bee", "cat", "dog", "eel", "fox", "gnu"}; for (int i = 0; i < sorted.length; i++) { map.put(sorted[i], i + 1); } return map; } /** A different String object holding the same letters as word. */ private static String copyOf(String word) { return new String(word); } // ------------------------------------------------------------------ // Sections // ------------------------------------------------------------------ private static void setupSection() { section("Task 1: the provided BSTMap"); System.out.println(" Makes an empty map and looks inside it."); BSTMap map = new BSTMap<>(); try { check(root(map) == null, "new BSTMap(): an empty map, so root is null"); } catch (IllegalStateException e) { fieldProblem = "BSTMap needs a field named root (as in the provided file)"; fail(fieldProblem); return; } System.out.println(" (The tester can see inside your tree through root, key, value, left, right.)"); } private static void putSection() { section("Task 2: put (your find and insert)"); System.out.println(" Puts dog 15, bee 8, fox 17, ant 3, cat 10, eel 16, gnu 20 (lecture's tree,"); System.out.println(" in words), then looks inside the tree to see where each word went."); BSTMap map = new BSTMap<>(); boolean allNull = true; for (int i = 0; i < WORDS.length; i++) { if (map.put(WORDS[i], NUMBERS[i]) != null) { allNull = false; } } check(allNull, "put(\"dog\", 15) and the other 6 puts return null: each word is NEW,\n" + " so there is no old value to return"); checkEquals(7, countNodes(root(map)), "7 different words make 7 nodes in the tree"); String lectureShape = shape(root(map)); checkEquals(LECTURE_SHAPE, lectureShape, "each word is in the same place as lecture's number: dog at the top (where 15 was),\n" + " bee and fox below it, ant cat eel gnu at the bottom (L22, slides 21-39)"); if (!LECTURE_SHAPE.equals(lectureShape)) { System.out.println(" Compare your insert with lecture's insert_Recursive (L23, slide 47)."); } String order = orderProblem(root(map), null, null); check(order == null, "every word left of a node comes earlier in the alphabet, every word right of it later" + (order == null ? "" : ": " + order)); Integer oldCat = map.put("cat", 99); checkEquals(10, oldCat, "put(\"cat\", 99): cat is already in the map, so put returns cat's OLD value, 10"); if (!Integer.valueOf(10).equals(oldCat) && LECTURE_SHAPE.equals(lectureShape)) { System.out.println(" insert builds the right tree, but find did not find \"cat\". Check which" + "\n way find turns: lecture's root.key > key (L23, slide 92) means OUR key" + "\n is smaller, which is key.compareTo(cur.key) < 0. The sign flips."); } checkEquals(7, countNodes(root(map)), "put(\"cat\", 99) changes cat's node; it does not add an 8th node"); Object cat = nodeFor(root(map), "cat"); checkEquals(99, cat == null ? null : field(cat, "value"), "after put(\"cat\", 99), cat's node holds the new value, 99"); check(map.put("hen", null) == null && countNodes(root(map)) == 7, "put(\"hen\", null): a map never stores null, so nothing is added"); checkEquals("level 0: ant | level 1: bee | level 2: cat | level 3: dog | level 4: eel" + " | level 5: fox | level 6: gnu", shape(root(sortedTree())), "put ant, bee, cat, dog, eel, fox, gnu (alphabetical order): each word goes to the RIGHT\n" + " of the one before, so the tree is a chain, 7 levels deep (L22, slides 41-45)"); // Equal keys that are different objects. With ==, these look different. BSTMap words = new BSTMap<>(); words.put("cat", 1); Integer oldWord = words.put(copyOf("cat"), 2); Object only = nodeFor(root(words), "cat"); boolean same = countNodes(root(words)) == 1 && Integer.valueOf(1).equals(oldWord) && only != null && Integer.valueOf(2).equals(field(only, "value")); check(same, "put(\"cat\", 1), then put cat again from a different String object: it is the\n" + " SAME key, so the value is replaced and the tree still has 1 node" + (same ? "" : "\n Compare keys with compareTo, never ==. Lecture's search uses ==" + "\n (L23, slide 90) because its keys are ints; for Strings, == only checks" + "\n whether they are the same object, and words read from a file never are.")); Random random = new Random(231); BSTMap randomMap = new BSTMap<>(); TreeSet distinct = new TreeSet<>(); for (int i = 0; i < 300; i++) { String key = "w" + random.nextInt(1000); randomMap.put(key, i); distinct.add(key); } String randomOrder = orderProblem(root(randomMap), null, null); check(randomOrder == null && countNodes(root(randomMap)) == distinct.size(), "300 puts of random words: one node per different word, all in alphabetical order" + (randomOrder == null ? "" : ": " + randomOrder)); } private static void getSection() { section("Task 4: get, containsKey, size, clear"); System.out.println(" Uses lecture's tree in words (dog 15, bee 8, fox 17, ant 3, cat 10, eel 16, gnu 20)."); BSTMap empty = new BSTMap<>(); checkEquals(null, empty.get("dog"), "get(\"dog\") on an empty map: nothing to find, so null"); BSTMap map = lectureTree(); boolean found = true; for (int i = 0; i < WORDS.length; i++) { if (!Integer.valueOf(NUMBERS[i]).equals(map.get(WORDS[i]))) { found = false; } } check(found, "get(\"dog\") gives 15, get(\"ant\") gives 3, ... every word gives its number"); check(map.get("cow") == null && map.get("aardvark") == null && map.get("zebra") == null, "get(\"cow\"), get(\"aardvark\"), get(\"zebra\"): not in the map, so null\n" + " (cow falls between cat and dog; aardvark before every word; zebra after)"); checkEquals(17, map.get(copyOf("fox")), "get(\"fox\") with fox in a different String object still finds 17"); check(map.containsKey("eel"), "containsKey(\"eel\"): eel is in the map, so true"); check(!map.containsKey("cow"), "containsKey(\"cow\"): cow is not in the map, so false"); checkEquals(0, empty.size(), "size() of a new map: 0 words"); checkEquals(7, map.size(), "size() after putting 7 different words: 7"); map.put("cat", 99); map.put("ant", null); checkEquals(7, map.size(), "size() after put(\"cat\", 99) and put(\"ant\", null): still 7, no new words"); map.clear(); check(map.size() == 0 && root(map) == null, "after clear(): size() is 0 and root is null"); check(map.get("dog") == null && !map.containsKey("dog"), "after clear(): get(\"dog\") is null; the old words are gone"); map.put("yak", 4); check(map.size() == 1 && Integer.valueOf(4).equals(map.get("yak")), "after clear(), put(\"yak\", 4) works: size() 1, get(\"yak\") 4"); } private static void traversalSection() { section("Task 5: keySet and values"); System.out.println(" In-order traversal (L24, slide 4) lists the words in alphabetical order."); BSTMap map = lectureTree(); checkEquals("[ant, bee, cat, dog, eel, fox, gnu]", "" + map.keySet(), "keySet() of lecture's tree: the 7 words in alphabetical order"); checkEquals("[3, 8, 10, 15, 16, 17, 20]", "" + map.values(), "values(): each word's number, in the same order as keySet()"); BSTMap empty = new BSTMap<>(); check(empty.keySet().isEmpty() && empty.values().isEmpty(), "keySet() and values() of an empty map: empty lists []"); BSTMap words = new BSTMap<>(); String[] tiny = {"it", "was", "the", "best", "of", "times", "it", "was", "the", "worst", "of", "times"}; for (String word : tiny) { Integer count = words.get(word); words.put(word, count == null ? 1 : count + 1); } checkEquals("[best, it, of, the, times, was, worst]", "" + words.keySet(), "counting \"it was the best of times it was the worst of times\":\n" + " keySet() lists each different word once, alphabetically"); checkEquals("[1, 2, 2, 2, 2, 2, 1]", "" + words.values(), "values() gives each word's count, lined up with keySet(): best 1, it 2, ..."); } private static void maxDepthSection() { section("Task 6: maxDepth"); System.out.println(" maxDepth counts LEVELS: the most nodes get may visit to find one word."); BSTMap map = new BSTMap<>(); int empty = map.maxDepth(); map.put("dog", 15); int one = map.maxDepth(); int lecture = lectureTree().maxDepth(); boolean edges = empty == -1 || (one == 0 && lecture == 2); checkEquals(0, empty, "maxDepth() of an empty map: 0 levels"); checkEquals(1, one, "maxDepth() with just dog: 1 level"); checkEquals(3, lecture, "maxDepth() of lecture's tree (dog / bee fox / ant cat eel gnu): 3 levels"); if (edges) { System.out.println(" Hint: you computed lecture's HEIGHT, which counts edges (L22, slide 4)." + "\n maxDepth counts LEVELS, which is height + 1. An empty tree has 0 levels."); } checkEquals(7, sortedTree().maxDepth(), "maxDepth() after putting the 7 words in alphabetical order: a chain, 7 levels"); Random random = new Random(7); BSTMap randomMap = new BSTMap<>(); for (int i = 0; i < 300; i++) { randomMap.put("w" + random.nextInt(1000), i); } checkEquals(levels(root(randomMap)), randomMap.maxDepth(), "maxDepth() after 300 random words: matches the tester's own count of levels"); } public static void main(String[] args) { System.out.println("Lab 06 Tester"); runSection(Lab06Tester::setupSection); if (fieldProblem != null) { System.out.println("\n The tester can't look inside your tree. Use the provided BSTMap.java."); } else { Runnable[] sections = { Lab06Tester::putSection, Lab06Tester::getSection, Lab06Tester::traversalSection, Lab06Tester::maxDepthSection }; 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 && skipped == 0) { System.out.println("All checks passed."); } else if (failed == 0) { System.out.println("No failures so far. Each SKIP is a method you haven't written yet."); } else { System.out.println("Fix the first FAIL above first; later failures are often caused by it."); } System.exit(failed == 0 ? 0 : 1); } }