import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.Random;
import java.util.TreeMap;

/**
 * Project 06 tester (week 1).
 *
 *   javac *.java
 *   java Project06Tester
 *
 * 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.
 * Keep tiny.txt from Lab 06 in this folder: Task 3 counts its words.
 */
public class Project06Tester {

    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 (Objects.equals(expected, 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:"
                + "\n         a while loop whose condition never becomes false, or a recursive call"
                + "\n         that never moves down the tree.");
            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 && ("" + thrown[0]).contains("intValue")) {
            fail("this section stopped early because your code threw " + thrown[0]
                + "\n         A null was used as a number. get returns null for a word that isn't in"
                + "\n         the map: check for null first (getCount should return 0 for such a word).");
        } 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) before it"
                + "\n         reads cur.key? Lecture's delete checks root == null first (L24, slide 112).");
        } else if (thrown[0] instanceof IndexOutOfBoundsException && ("" + thrown[0]).contains("-1")) {
            fail("this section stopped early because your code threw " + thrown[0]
                + "\n         best was still -1: no word was left to choose, but the loop asked for"
                + "\n         one anyway. Stop when a pass through the words finds nothing.");
        } 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 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");
    }

    private static int countNodes(Object node) {
        if (node == null) {
            return 0;
        }
        return 1 + countNodes(field(node, "left")) + countNodes(field(node, "right"));
    }

    /** The keys level by level, for example "level 0: dog | level 1: bee fox". */
    private static String shape(Object root) {
        ArrayList<String> 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.isEmpty() ? "(empty tree)" : result;
    }

    private static void addKeys(Object node, int level, ArrayList<String> 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 the tree is in alphabetical order, or a description of the first problem. */
    private static String orderProblem(Object node, String low, String high) {
        if (node == null) {
            return null;
        }
        String key = (String) field(node, "key");
        if (low != null && key.compareTo(low) <= 0) {
            return key + " is in the RIGHT subtree of " + low + ", but comes before it";
        }
        if (high != null && key.compareTo(high) >= 0) {
            return key + " is in the LEFT subtree of " + high + ", but comes after it";
        }
        String left = orderProblem(field(node, "left"), low, key);
        return left != null ? left : orderProblem(field(node, "right"), key, high);
    }

    /** Lecture's tree in words: dog 15, bee 8, fox 17, ant 3, cat 10, eel 16, gnu 20. */
    private static BSTMap<String, Integer> lectureTree() {
        String[] words = {"dog", "bee", "fox", "ant", "cat", "eel", "gnu"};
        int[] numbers = {15, 8, 17, 3, 10, 16, 20};
        BSTMap<String, Integer> map = new BSTMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], numbers[i]);
        }
        return map;
    }

    private static ArrayList<String> list(String... words) {
        return new ArrayList<String>(Arrays.asList(words));
    }

    // ------------------------------------------------------------------
    // Task 1: remove
    // ------------------------------------------------------------------

    private static void removeSection() {
        section("Task 1: remove (your delete and minNode)");
        System.out.println("  Starts from lecture's tree in words:  level 0: dog | level 1: bee fox | level 2: ant cat eel gnu");
        BSTMap<String, Integer> map = lectureTree();

        checkEquals(3, map.remove("ant"), "remove(\"ant\"): ant is a LEAF (case 1); remove returns its value, 3");
        checkEquals("level 0: dog | level 1: bee fox | level 2: cat eel gnu", shape(root(map)),
            "after removing ant, the leaf is simply gone");
        checkEquals(6, map.size(), "size() after removing ant: 6");

        checkEquals(8, map.remove("bee"), "remove(\"bee\"): bee now has ONE child, cat (case 2); returns 8");
        checkEquals("level 0: dog | level 1: cat fox | level 2: eel gnu", shape(root(map)),
            "after removing bee, its only child cat moves up into bee's place");

        map = lectureTree();
        map.remove("gnu");
        checkEquals(17, map.remove("fox"), "remove(\"gnu\") then remove(\"fox\"): fox now has only a LEFT child, eel (case 2)");
        checkEquals("level 0: dog | level 1: bee eel | level 2: ant cat", shape(root(map)),
            "after removing fox, its only child eel moves up into fox's place");

        map = lectureTree();
        checkEquals(17, map.remove("fox"), "remove(\"fox\"): fox has TWO children, eel and gnu (case 3); returns 17");
        checkEquals("level 0: dog | level 1: bee gnu | level 2: ant cat eel", shape(root(map)),
            "after removing fox, the smallest word in fox's right subtree (gnu) takes fox's place\n"
            + "         (L24, slide 112: copy the smallest, then delete it from the right subtree)");

        map = lectureTree();
        checkEquals(15, map.remove("dog"), "remove(\"dog\"): removing the ROOT, which has two children; returns 15");
        checkEquals("level 0: eel | level 1: bee fox | level 2: ant cat gnu", shape(root(map)),
            "after removing dog, the smallest word in its right subtree (eel) becomes the root");
        checkEquals(16, map.get("eel"), "eel's VALUE moved with its key: get(\"eel\") is still 16");
        checkEquals(6, map.size(), "size() after removing the root: 6");

        String before = shape(root(map));
        checkEquals(null, map.remove("cow"), "remove(\"cow\"): cow is not in the map, so remove returns null");
        check(map.size() == 6 && before.equals(shape(root(map))), "remove(\"cow\") leaves the size and the tree unchanged");

        BSTMap<String, Integer> empty = new BSTMap<>();
        checkEquals(null, empty.remove("dog"), "remove(\"dog\") on an empty map: null, and nothing breaks");

        BSTMap<String, Integer> one = new BSTMap<>();
        one.put("yak", 1);
        one.remove("yak");
        check(root(one) == null && one.size() == 0, "removing the only word: root is null and size() is 0");
        one.put("emu", 2);
        check(one.size() == 1 && Integer.valueOf(2).equals(one.get("emu")), "the map works again after it was emptied");

        Random random = new Random(231);
        BSTMap<String, Integer> mine = new BSTMap<>();
        TreeMap<String, Integer> javas = new TreeMap<>();
        String problem = null;
        for (int step = 0; step < 20000 && problem == null; step++) {
            String key = "w" + random.nextInt(300);
            int op = random.nextInt(3);
            Integer a;
            Integer b;
            String what;
            if (op == 0) {
                a = mine.put(key, step);
                b = javas.put(key, step);
                what = "put(\"" + key + "\", " + step + ")";
            } else if (op == 1) {
                a = mine.remove(key);
                b = javas.remove(key);
                what = "remove(\"" + key + "\")";
            } else {
                a = mine.get(key);
                b = javas.get(key);
                what = "get(\"" + key + "\")";
            }
            String order = orderProblem(root(mine), null, null);
            if (!Objects.equals(a, b)) {
                problem = "call " + (step + 1) + ", " + what + ", returned " + a + " but should return " + b;
            } else if (mine.size() != javas.size()) {
                problem = "after call " + (step + 1) + ", " + what + ", size() is " + mine.size()
                    + " but should be " + javas.size();
            } else if (order != null) {
                problem = "after call " + (step + 1) + ", " + what + ", the tree is out of order: " + order;
            }
        }
        check(problem == null, "20,000 random put, get, and remove calls give the same answers as Java's own"
            + "\n         sorted map, and the tree stays in alphabetical order"
            + (problem == null ? "" : "\n         first problem: " + problem));
    }

    // ------------------------------------------------------------------
    // Task 3: buildMap and getCount
    // ------------------------------------------------------------------

    private static void countSection() {
        section("Task 3: buildMap and getCount");
        System.out.println("  Counts \"it was the best of times it was the worst of times\" (12 words).");
        WordCounter wc = new WordCounter();
        wc.buildMap(list("it", "was", "the", "best", "of", "times", "it", "was", "the", "worst", "of", "times"));
        checkEquals(12, wc.totalWordCount(), "totalWordCount(): 12 words, repeats included");
        checkEquals(7, wc.uniqueWordCount(), "uniqueWordCount(): 7 different words");
        checkEquals(2, wc.getCount("it"), "getCount(\"it\"): it appears 2 times");
        checkEquals(1, wc.getCount("best"), "getCount(\"best\"): best appears 1 time");
        checkEquals(0, wc.getCount("cow"), "getCount(\"cow\"): cow never appears, so 0 (not null)");

        wc.buildMap(list("it", "was", "the", "age", "of", "wisdom"));
        checkEquals(18, wc.totalWordCount(), "a second buildMap with 6 more words ADDS to the counts: 18 words");
        checkEquals(3, wc.getCount("it"), "getCount(\"it\") after the second buildMap: 2 + 1 = 3");
        checkEquals(9, wc.uniqueWordCount(), "uniqueWordCount(): 7 + 2 new words (age, wisdom) = 9");

        WordCounter tiny = new WordCounter();
        ArrayList<String> words = tiny.readWords("tiny.txt");
        if (words.isEmpty()) {
            skip("tiny.txt is missing or empty. Copy it from Lab 06 into this folder.");
            return;
        }
        tiny.buildMap(words);
        check(tiny.totalWordCount() == 60 && tiny.uniqueWordCount() == 20,
            "tiny.txt: 60 words, 20 different (yours: " + tiny.totalWordCount() + " words, "
            + tiny.uniqueWordCount() + " different)");
    }

    // ------------------------------------------------------------------
    // Task 4: topWords
    // ------------------------------------------------------------------

    private static WordCounter tinyCounter() {
        WordCounter wc = new WordCounter();
        wc.buildMap(list(
            "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst", "of", "times",
            "it", "was", "the", "age", "of", "wisdom", "it", "was", "the", "age", "of", "foolishness",
            "it", "was", "the", "epoch", "of", "belief", "it", "was", "the", "epoch", "of", "incredulity",
            "it", "was", "the", "season", "of", "light", "it", "was", "the", "season", "of", "darkness",
            "it", "was", "the", "spring", "of", "hope", "it", "was", "the", "winter", "of", "despair"));
        return wc;
    }

    private static void topSection() {
        section("Task 4: topWords");
        System.out.println("  Counts the 60 words of tiny.txt: it, of, the, was 10 times each; age, epoch,");
        System.out.println("  season, times 2 times each; 12 other words once each.");
        WordCounter wc = tinyCounter();
        checkEquals(list("it", "of", "the"), wc.topWords(3),
            "topWords(3): it, of, the, was are tied at 10, so the first three in the alphabet");
        checkEquals(list("it", "of", "the", "was", "age", "epoch"), wc.topWords(6),
            "topWords(6): the four 10s, then the first two of the words with count 2");
        checkEquals(list(), wc.topWords(0), "topWords(0): an empty list");
        ArrayList<String> all = wc.topWords(100);
        check(all.size() == 20 && new java.util.HashSet<String>(all).size() == 20,
            "topWords(100) when there are only 20 different words: all 20, each once (yours: "
            + all.size() + " words)");
        checkEquals(list("wisdom", "worst"), slice(all, 18, 20),
            "the words that appear once come last, in alphabetical order, so the list ends wisdom, worst");
        checkEquals(list(), new WordCounter().topWords(5), "topWords(5) on an empty WordCounter: an empty list");
    }

    private static ArrayList<String> slice(ArrayList<String> words, int from, int to) {
        ArrayList<String> result = new ArrayList<String>();
        for (int i = from; i < to && i < words.size(); i++) {
            result.add(words.get(i));
        }
        return result;
    }

    // ------------------------------------------------------------------
    // Task 5: topWordsNotIn
    // ------------------------------------------------------------------

    private static void notInSection() {
        section("Task 5: topWordsNotIn");
        System.out.println("  this = tiny.txt's 60 words; other = \"it was the age of times\".");
        WordCounter wc = tinyCounter();
        WordCounter other = new WordCounter();
        other.buildMap(list("it", "was", "the", "age", "of", "times"));
        checkEquals(list("epoch", "season", "belief", "best"), wc.topWordsNotIn(other, 4),
            "topWordsNotIn(other, 4): skips it, was, the, age, of, times (other has them);\n"
            + "         then epoch and season (2 each), then belief and best (1 each, alphabetical)");
        ArrayList<String> all = wc.topWordsNotIn(other, 100);
        checkEquals(14, all.size(), "topWordsNotIn(other, 100): only 14 words are missing from other, so 14");
        check(!all.contains("it") && !all.contains("times"), "no word that other contains is in the list");
        checkEquals(wc.topWords(5), wc.topWordsNotIn(new WordCounter(), 5),
            "if other is empty, every word counts: the same as topWords(5)");
        checkEquals(list(), wc.topWordsNotIn(wc, 5), "a text compared with ITSELF: every word is in the other, so an empty list");
    }

    public static void main(String[] args) {
        System.out.println("Project 06 Tester (week 1)");
        Runnable[] sections = { Project06Tester::removeSection, Project06Tester::countSection,
            Project06Tester::topSection, Project06Tester::notInSection };
        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);
    }
}
