// 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) {
            // >>> SOLUTION
            Node n = new Node(s, null);
            if (head == null) {
                head = n;
                return;
            }
            Node p = head;
            while (p.next != null) p = p.next;
            p.next = n;
            // <<< SOLUTION
        }

        // Level 1: the number of students
        int size() {
            // >>> SOLUTION
            int c = 0;
            for (Node p = head; p != null; p = p.next) c++;
            return c;
            // <<< SOLUTION
        }

        // Level 1: search by id; null if there is no such student
        Student find(int id) {
            // >>> SOLUTION
            for (Node p = head; p != null; p = p.next) if (p.data.id == id) return p.data;
            return null;
            // <<< SOLUTION
        }

        // Level 1: the text form of the list, e.g. "[1003 Li Wei 87, 1001 Wang Fang 92]"; empty list: "[]"
        public String toString() {
            // >>> SOLUTION
            StringBuilder sb = new StringBuilder("[");
            for (Node p = head; p != null; p = p.next) {
                sb.append(p.data);
                if (p.next != null) sb.append(", ");
            }
            return sb.append("]").toString();
            // <<< SOLUTION
        }

        // Level 2: deleting the student with the given id; true if there was one
        boolean remove(int id) {
            // >>> SOLUTION
            Node prev = null, p = head;
            while (p != null && p.data.id != id) {
                prev = p;
                p = p.next;
            }
            if (p == null) return false;
            if (prev == null) head = p.next;
            else prev.next = p.next;
            return true;
            // <<< SOLUTION
        }

        // Level 2: the average of the scores; 0 for an empty list
        double averageScore() {
            // >>> SOLUTION
            int n = 0, sum = 0;
            for (Node p = head; p != null; p = p.next) {
                n++;
                sum += p.data.score;
            }
            return n == 0 ? 0 : (double) sum / n;
            // <<< SOLUTION
        }

        // Level 2: the student with the highest score (on a tie the one earlier in the list); null for an empty list
        Student best() {
            // >>> SOLUTION
            Student b = null;
            for (Node p = head; p != null; p = p.next) if (b == null || p.data.score > b.score) b = p.data;
            return b;
            // <<< SOLUTION
        }

        // 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) {
            // >>> SOLUTION
            if (head == null || s.score > head.data.score) {
                head = new Node(s, head);
                return;
            }
            Node p = head;
            while (p.next != null && p.next.data.score >= s.score) p = p.next;
            p.next = new Node(s, p.next);
            // <<< SOLUTION
        }

        // Level 3: reversing the list IN PLACE (without creating new nodes)
        void reverse() {
            // >>> SOLUTION
            Node prev = null, p = head;
            while (p != null) {
                Node next = p.next;
                p.next = prev;
                prev = p;
                p = next;
            }
            head = prev;
            // <<< SOLUTION
        }
    }

    // ------------------------------------------------------------------
    // 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) {
            // >>> SOLUTION
            root = insert(root, s);
            // <<< SOLUTION
        }

        // >>> SOLUTION
        private Node insert(Node p, Student s) {
            if (p == null) return new Node(s);
            if (s.id < p.data.id) p.left = insert(p.left, s);
            else if (s.id > p.data.id) p.right = insert(p.right, s);
            return p;
        }

        private int height(Node p) { return p == null ? -1 : 1 + Math.max(height(p.left), height(p.right)); }

        private void inorder(Node p, StringBuilder sb) {
            if (p == null) return;
            inorder(p.left, sb);
            if (sb.length() > 1) sb.append(", ");
            sb.append(p.data.id);
            inorder(p.right, sb);
        }
        // <<< SOLUTION

        // Level 4: search by id; null if not found
        Student find(int id) {
            // >>> SOLUTION
            Node p = root;
            while (p != null && p.data.id != id) p = (id < p.data.id) ? p.left : p.right;
            return p == null ? null : p.data;
            // <<< SOLUTION
        }

        // Level 4: the height of the tree (empty tree: -1, a single node: 0)
        int height() {
            // >>> SOLUTION
            return height(root);
            // <<< SOLUTION
        }

        // Level 4: the ids in inorder, e.g. "[1001, 1002, 1003]"
        String inorderIds() {
            // >>> SOLUTION
            StringBuilder sb = new StringBuilder("[");
            inorder(root, sb);
            return sb.append("]").toString();
            // <<< SOLUTION
        }
    }

    // ==================================================================
    // 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)");
    }
}