// Data Structures – practical grade: Student registry
//
// Task: implement the methods marked with TODO using YOUR OWN data structure.
// The java.util collections (ArrayList, LinkedList, HashMap, TreeMap etc.) must NOT be used in the solution.
//
// Run:  java StudentRegistry.java
// At the end the program prints, level by level, which checks pass (OK) and which fail (FAIL).

public class StudentRegistry {

    // ------------------------------------------------------------------
    // Student (do NOT modify!)
    // ------------------------------------------------------------------
    static class Student {
        final int id;
        final String name;
        final int score;

        Student(int id, String name, int score) {
            this.id = id;
            this.name = name;
            this.score = score;
        }

        public String toString() { return id + " " + name + " " + score; }
    }

    // ------------------------------------------------------------------
    // Levels 1–3: singly linked list
    // ------------------------------------------------------------------
    static class StudentList {

        static class Node {
            Student data;
            Node next;
            Node(Student data, Node next) { this.data = data; this.next = next; }
        }

        Node head; // the first element; null in an empty list
        // You may add further fields if needed (e.g. tail, size).

        // Level 1: a new student at the END of the list
        void add(Student s) {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 1: the number of students
        int size() {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 1: search by id; null if there is no such student
        Student find(int id) {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 1: the text form of the list, e.g. "[1003 Li Wei 87, 1001 Wang Fang 92]"; empty list: "[]"
        public String toString() {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 2: deleting the student with the given id; true if there was one
        boolean remove(int id) {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 2: the average of the scores; 0 for an empty list
        double averageScore() {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 2: the student with the highest score (on a tie the one earlier in the list); null for an empty list
        Student best() {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 3: insertion so that the list stays in DESCENDING order of score;
        // on equal scores the new student goes BEHIND the ones already in the list (stable)
        void addSortedByScore(Student s) {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 3: reversing the list IN PLACE (without creating new nodes)
        void reverse() {
            throw new UnsupportedOperationException("TODO");
        }
    }

    // ------------------------------------------------------------------
    // Level 4: binary search tree by id
    // ------------------------------------------------------------------
    static class StudentBST {

        static class Node {
            Student data;
            Node left, right;
            Node(Student data) { this.data = data; }
        }

        Node root;

        // Level 4: insertion (key: id); if the id is already present, it is not inserted again
        void insert(Student s) {
            throw new UnsupportedOperationException("TODO");
        }

        // You may write helper methods here.

        // Level 4: search by id; null if not found
        Student find(int id) {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 4: the height of the tree (empty tree: -1, a single node: 0)
        int height() {
            throw new UnsupportedOperationException("TODO");
        }

        // Level 4: the ids in inorder, e.g. "[1001, 1002, 1003]"
        String inorderIds() {
            throw new UnsupportedOperationException("TODO");
        }
    }

    // ==================================================================
    // Checker program – do NOT modify!
    // ==================================================================

    static int ok, fail;

    static void check(String what, boolean cond) {
        if (cond) ok++;
        else fail++;
        System.out.println("  " + (cond ? "OK   " : "FAIL ") + what);
    }

    static Student[] sample() {
        return new Student[] {
                new Student(1003, "Li Wei", 87), new Student(1001, "Wang Fang", 92), new Student(1005, "Chen Jie", 78),
                new Student(1002, "Zhang Min", 92), new Student(1004, "Anna Kovács", 65) };
    }

    interface Level { void run(); }

    static boolean level(String title, Level body) {
        System.out.println(title);
        int failBefore = fail;
        try {
            body.run();
        } catch (UnsupportedOperationException e) {
            System.out.println("  ---  not solved yet");
            return false;
        } catch (RuntimeException e) {
            fail++;
            System.out.println("  FAIL exception: " + e);
            return false;
        }
        return fail == failBefore;
    }

    public static void main(String[] args) {
        boolean l1 = level("Level 1 (pass): add, size, find, toString", () -> {
            StudentList l = new StudentList();
            check("empty list: size() == 0 and \"[]\"", l.size() == 0 && l.toString().equals("[]"));
            for (Student s : sample()) l.add(s);
            check("after 5 students size() == 5", l.size() == 5);
            check("the order is the insertion order", l.toString().equals(
                    "[1003 Li Wei 87, 1001 Wang Fang 92, 1005 Chen Jie 78, 1002 Zhang Min 92, 1004 Anna Kovács 65]"));
            check("find(1005) -> Chen Jie", l.find(1005) != null && l.find(1005).name.equals("Chen Jie"));
            check("find(9999) -> null", l.find(9999) == null);
        });

        boolean l2 = l1 && level("Level 2 (satisfactory): remove, averageScore, best", () -> {
            StudentList l = new StudentList();
            check("empty list: averageScore() == 0 and best() == null", l.averageScore() == 0 && l.best() == null);
            for (Student s : sample()) l.add(s);
            check("remove(1005) true", l.remove(1005));
            check("remove(9999) false", !l.remove(9999));
            check("after deletion size() == 4 and find(1005) == null", l.size() == 4 && l.find(1005) == null);
            check("deleting the first element: remove(1003)", l.remove(1003) && l.toString().startsWith("[1001"));
            check("averageScore() == 83.0", Math.abs(l.averageScore() - 83.0) < 1e-9);
            check("best() -> Wang Fang (on a tie the earlier one)", l.best() != null && l.best().name.equals("Wang Fang"));
        });

        boolean l3 = l2 && level("Level 3 (good): addSortedByScore, reverse", () -> {
            StudentList l = new StudentList();
            for (Student s : sample()) l.addSortedByScore(s);
            check("descending score, stable order", l.toString().equals(
                    "[1001 Wang Fang 92, 1002 Zhang Min 92, 1003 Li Wei 87, 1005 Chen Jie 78, 1004 Anna Kovács 65]"));
            l.addSortedByScore(new Student(1006, "Liu Yang", 100));
            l.addSortedByScore(new Student(1007, "Zhou Lan", 50));
            check("insertion at the beginning and at the end of the list", l.toString().startsWith("[1006") && l.toString().endsWith("Zhou Lan 50]"));
            l.reverse();
            check("reverse()", l.toString().startsWith("[1007 Zhou Lan 50, 1004") && l.toString().endsWith("1006 Liu Yang 100]"));
            StudentList e = new StudentList();
            e.reverse();
            check("reversing an empty list", e.toString().equals("[]"));
        });

        boolean l4 = l3 && level("Level 4 (excellent): StudentBST – insert, find, height, inorderIds", () -> {
            StudentBST t = new StudentBST();
            check("empty tree: height() == -1", t.height() == -1);
            for (Student s : sample()) t.insert(s);
            t.insert(new Student(1003, "Duplicate", 0));
            check("inorderIds() sorted", t.inorderIds().equals("[1001, 1002, 1003, 1004, 1005]"));
            check("height() == 2", t.height() == 2);
            check("find(1004) -> Anna Kovács, find(1) -> null", t.find(1004) != null && t.find(1004).name.equals("Anna Kovács") && t.find(1) == null);
            check("a duplicate id is not inserted", t.find(1003).name.equals("Li Wei"));

            // Measurement: 20 000 students, 20 000 searches in a list and in a search tree
            java.util.Random rnd = new java.util.Random(2026);
            StudentList list = new StudentList();
            StudentBST tree = new StudentBST();
            int n = 20_000;
            int[] ids = new int[n];
            for (int i = 0; i < n; i++) {
                ids[i] = 100_000 + rnd.nextInt(900_000);
                Student s = new Student(ids[i], "S" + i, rnd.nextInt(101));
                list.head = new StudentList.Node(s, list.head); // fast filling at the beginning
                tree.insert(s);
            }
            long t0 = System.nanoTime();
            int found1 = 0;
            for (int id : ids) if (list.find(id) != null) found1++;
            long t1 = System.nanoTime();
            int found2 = 0;
            for (int id : ids) if (tree.find(id) != null) found2++;
            long t2 = System.nanoTime();
            System.out.printf("  measurement: %d searches – list: %.1f ms, search tree: %.1f ms, tree height: %d%n",
                    n, (t1 - t0) / 1e6, (t2 - t1) / 1e6, tree.height());
            check("both structures find every element", found1 == n && found2 == n);
            check("the height of the search tree is small (< 60)", tree.height() < 60);
        });

        String grade = l4 ? "excellent (5)" : l3 ? "good (4)" : l2 ? "satisfactory (3)" : l1 ? "pass (2)" : "fail (1)";
        System.out.println("\nPassed checks: " + ok + ", failed: " + fail);
        System.out.println("Level reached according to the automatic check: " + grade
                + "  (the final grade is set by the instructor based on the code and the oral explanation)");
    }
}