// Data Structures – practical grade: Student registry
//
// Task: implement the functions marked with TODO using YOUR OWN data structure.
// The container/list package and map must NOT be used in the solution.
//
// Run (in this folder):  go run .
// At the end the program prints, level by level, which checks pass (OK) and which fail (FAIL).
package main

import (
	"fmt"
	"math"
	"math/rand"
	"strings"
	"time"
)

// ------------------------------------------------------------------
// Student (do NOT modify!)
// ------------------------------------------------------------------
type Student struct {
	ID    int
	Name  string
	Score int
}

func (s Student) String() string { return fmt.Sprintf("%d %s %d", s.ID, s.Name, s.Score) }

// ------------------------------------------------------------------
// Levels 1–3: singly linked list
// ------------------------------------------------------------------
type Node struct {
	Data *Student
	Next *Node
}

type StudentList struct {
	Head *Node // the first element; nil in an empty list
	// You may add further fields if needed (e.g. Tail, Size).
}

// Add – Level 1: a new student at the END of the list
func (l *StudentList) Add(s *Student) {
	panic("TODO")
}

// Size – Level 1: the number of students
func (l *StudentList) Size() int {
	panic("TODO")
}

// Find – Level 1: search by id; nil if not found
func (l *StudentList) Find(id int) *Student {
	panic("TODO")
}

// String – Level 1: e.g. "[1003 Li Wei 87, 1001 Wang Fang 92]"; empty list: "[]"
func (l *StudentList) String() string {
	panic("TODO")
}

// Remove – Level 2: deleting the student with the given id; true if there was one
func (l *StudentList) Remove(id int) bool {
	panic("TODO")
}

// AverageScore – Level 2: the average of the scores; 0 for an empty list
func (l *StudentList) AverageScore() float64 {
	panic("TODO")
}

// Best – Level 2: the student with the highest score (on a tie the one earlier in the list); nil for an empty list
func (l *StudentList) Best() *Student {
	panic("TODO")
}

// AddSortedByScore – Level 3: the list stays in DESCENDING order of score;
// on equal scores the new student goes BEHIND the ones already in the list (stable)
func (l *StudentList) AddSortedByScore(s *Student) {
	panic("TODO")
}

// Reverse – Level 3: reversing the list IN PLACE (without new nodes)
func (l *StudentList) Reverse() {
	panic("TODO")
}

// ------------------------------------------------------------------
// Level 4: binary search tree by id
// ------------------------------------------------------------------
type TreeNode struct {
	Data        *Student
	Left, Right *TreeNode
}

type StudentBST struct {
	Root *TreeNode
}

// You may write helper functions here.

// Insert – Level 4: insertion (key: ID); a duplicate id is not inserted
func (t *StudentBST) Insert(s *Student) {
	panic("TODO")
}

// Find – Level 4: search by id; nil if not found
func (t *StudentBST) Find(id int) *Student {
	panic("TODO")
}

// Height – Level 4: the height of the tree (empty tree: -1, one node: 0)
func (t *StudentBST) Height() int {
	panic("TODO")
}

// InorderIDs – Level 4: the ids in inorder, e.g. "[1001, 1002, 1003]"
func (t *StudentBST) InorderIDs() string {
	panic("TODO")
}

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

var okCount, failCount int

func check(what string, cond bool) {
	if cond {
		okCount++
		fmt.Println("  OK  ", what)
	} else {
		failCount++
		fmt.Println("  FAIL", what)
	}
}

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

// level runs the checks of one level; a TODO panic is treated as "not solved"
func level(title string, body func()) (passed bool) {
	fmt.Println(title)
	before := failCount
	defer func() {
		if r := recover(); r != nil {
			if r == "TODO" {
				fmt.Println("  ---  not solved yet")
			} else {
				failCount++
				fmt.Println("  FAIL panic:", r)
			}
			passed = false
		}
	}()
	body()
	return failCount == before
}

func main() {
	l1 := level("Level 1 (pass): Add, Size, Find, String", func() {
		var l StudentList
		check(`empty list: Size() == 0 and "[]"`, l.Size() == 0 && l.String() == "[]")
		for _, s := range sample() {
			l.Add(s)
		}
		check("after 5 students Size() == 5", l.Size() == 5)
		check("the order is the insertion order", l.String() ==
			"[1003 Li Wei 87, 1001 Wang Fang 92, 1005 Chen Jie 78, 1002 Zhang Min 92, 1004 Anna Kovács 65]")
		s := l.Find(1005)
		check("Find(1005) -> Chen Jie", s != nil && s.Name == "Chen Jie")
		check("Find(9999) -> nil", l.Find(9999) == nil)
	})

	l2 := l1 && level("Level 2 (satisfactory): Remove, AverageScore, Best", func() {
		var l StudentList
		check("empty list: AverageScore() == 0 and Best() == nil", l.AverageScore() == 0 && l.Best() == nil)
		for _, s := range 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) == nil", l.Size() == 4 && l.Find(1005) == nil)
		check("deleting the first element: Remove(1003)", l.Remove(1003) && strings.HasPrefix(l.String(), "[1001"))
		check("AverageScore() == 83.0", math.Abs(l.AverageScore()-83.0) < 1e-9)
		b := l.Best()
		check("Best() -> Wang Fang (on a tie the earlier one)", b != nil && b.Name == "Wang Fang")
	})

	l3 := l2 && level("Level 3 (good): AddSortedByScore, Reverse", func() {
		var l StudentList
		for _, s := range sample() {
			l.AddSortedByScore(s)
		}
		check("descending score, stable order", l.String() ==
			"[1001 Wang Fang 92, 1002 Zhang Min 92, 1003 Li Wei 87, 1005 Chen Jie 78, 1004 Anna Kovács 65]")
		l.AddSortedByScore(&Student{1006, "Liu Yang", 100})
		l.AddSortedByScore(&Student{1007, "Zhou Lan", 50})
		check("insertion at the beginning and at the end of the list", strings.HasPrefix(l.String(), "[1006") && strings.HasSuffix(l.String(), "Zhou Lan 50]"))
		l.Reverse()
		check("Reverse()", strings.HasPrefix(l.String(), "[1007 Zhou Lan 50, 1004") && strings.HasSuffix(l.String(), "1006 Liu Yang 100]"))
		var e StudentList
		e.Reverse()
		check("reversing an empty list", e.String() == "[]")
	})

	l4 := l3 && level("Level 4 (excellent): StudentBST – Insert, Find, Height, InorderIDs", func() {
		var t StudentBST
		check("empty tree: Height() == -1", t.Height() == -1)
		for _, s := range sample() {
			t.Insert(s)
		}
		t.Insert(&Student{1003, "Duplicate", 0})
		check("InorderIDs() sorted", t.InorderIDs() == "[1001, 1002, 1003, 1004, 1005]")
		check("Height() == 2", t.Height() == 2)
		f := t.Find(1004)
		check("Find(1004) -> Anna Kovács, Find(1) -> nil", f != nil && f.Name == "Anna Kovács" && t.Find(1) == nil)
		check("a duplicate id is not inserted", t.Find(1003).Name == "Li Wei")

		// Measurement: 20 000 students, 20 000 searches in a list and in a search tree
		rnd := rand.New(rand.NewSource(2026))
		var list StudentList
		var tree StudentBST
		n := 20_000
		ids := make([]int, n)
		for i := range ids {
			ids[i] = 100_000 + rnd.Intn(900_000)
			s := &Student{ids[i], fmt.Sprint("S", i), rnd.Intn(101)}
			list.Head = &Node{Data: s, Next: list.Head} // fast filling at the beginning
			tree.Insert(s)
		}
		t0 := time.Now()
		found1 := 0
		for _, id := range ids {
			if list.Find(id) != nil {
				found1++
			}
		}
		t1 := time.Now()
		found2 := 0
		for _, id := range ids {
			if tree.Find(id) != nil {
				found2++
			}
		}
		t2 := time.Now()
		fmt.Printf("  measurement: %d searches – list: %.1f ms, search tree: %.1f ms, tree height: %d\n",
			n, float64(t1.Sub(t0).Microseconds())/1000, float64(t2.Sub(t1).Microseconds())/1000, 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)
	})

	grade := "fail (1)"
	switch {
	case l4:
		grade = "excellent (5)"
	case l3:
		grade = "good (4)"
	case l2:
		grade = "satisfactory (3)"
	case l1:
		grade = "pass (2)"
	}
	fmt.Printf("\nPassed checks: %d, failed: %d\n", okCount, failCount)
	fmt.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)")
}