// 数据结构 – 上机考试：学生信息管理
//
// 任务：用你自己实现的数据结构完成标有 TODO 的函数。
// 解答中不得使用 container/list 包和 map。
//
// 运行（在本文件夹中）：go run .
// 最后程序按级别输出哪些检查通过（OK），哪些失败（FAIL）。
package main

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

// ------------------------------------------------------------------
// 学生（不要修改！）
// ------------------------------------------------------------------
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) }

// ------------------------------------------------------------------
// 第 1–3 级：单链表
// ------------------------------------------------------------------
type Node struct {
	Data *Student
	Next *Node
}

type StudentList struct {
	Head *Node // 第一个结点；空链表中为 nil
	// 如有需要，可以增加其他字段（例如 Tail、Size）。
}

// Add – 第 1 级：新学生加到链表的末尾
func (l *StudentList) Add(s *Student) {
	// >>> SOLUTION
	n := &Node{Data: s}
	if l.Head == nil {
		l.Head = n
		return
	}
	p := l.Head
	for p.Next != nil {
		p = p.Next
	}
	p.Next = n
	// <<< SOLUTION
}

// Size – 第 1 级：学生人数
func (l *StudentList) Size() int {
	// >>> SOLUTION
	c := 0
	for p := l.Head; p != nil; p = p.Next {
		c++
	}
	return c
	// <<< SOLUTION
}

// Find – 第 1 级：按学号查找；找不到时为 nil
func (l *StudentList) Find(id int) *Student {
	// >>> SOLUTION
	for p := l.Head; p != nil; p = p.Next {
		if p.Data.ID == id {
			return p.Data
		}
	}
	return nil
	// <<< SOLUTION
}

// String – 第 1 级：例如 "[1003 Li Wei 87, 1001 Wang Fang 92]"；空链表："[]"
func (l *StudentList) String() string {
	// >>> SOLUTION
	var parts []string
	for p := l.Head; p != nil; p = p.Next {
		parts = append(parts, p.Data.String())
	}
	return "[" + strings.Join(parts, ", ") + "]"
	// <<< SOLUTION
}

// Remove – 第 2 级：删除给定学号的学生；如果有这个学生则返回 true
func (l *StudentList) Remove(id int) bool {
	// >>> SOLUTION
	var prev *Node
	p := l.Head
	for p != nil && p.Data.ID != id {
		prev, p = p, p.Next
	}
	if p == nil {
		return false
	}
	if prev == nil {
		l.Head = p.Next
	} else {
		prev.Next = p.Next
	}
	return true
	// <<< SOLUTION
}

// AverageScore – 第 2 级：分数的平均值；空链表为 0
func (l *StudentList) AverageScore() float64 {
	// >>> SOLUTION
	n, sum := 0, 0
	for p := l.Head; p != nil; p = p.Next {
		n++
		sum += p.Data.Score
	}
	if n == 0 {
		return 0
	}
	return float64(sum) / float64(n)
	// <<< SOLUTION
}

// Best – 第 2 级：分数最高的学生（并列时取链表中靠前的）；空链表为 nil
func (l *StudentList) Best() *Student {
	// >>> SOLUTION
	var b *Student
	for p := l.Head; p != nil; p = p.Next {
		if b == nil || p.Data.Score > b.Score {
			b = p.Data
		}
	}
	return b
	// <<< SOLUTION
}

// AddSortedByScore – 第 3 级：链表保持按分数降序排列；
// 分数相同时，新学生排在已有学生的后面（稳定）
func (l *StudentList) AddSortedByScore(s *Student) {
	// >>> SOLUTION
	if l.Head == nil || s.Score > l.Head.Data.Score {
		l.Head = &Node{Data: s, Next: l.Head}
		return
	}
	p := l.Head
	for p.Next != nil && p.Next.Data.Score >= s.Score {
		p = p.Next
	}
	p.Next = &Node{Data: s, Next: p.Next}
	// <<< SOLUTION
}

// Reverse – 第 3 级：原地逆置链表（不创建新结点）
func (l *StudentList) Reverse() {
	// >>> SOLUTION
	var prev *Node
	for p := l.Head; p != nil; {
		next := p.Next
		p.Next = prev
		prev, p = p, next
	}
	l.Head = prev
	// <<< SOLUTION
}

// ------------------------------------------------------------------
// 第 4 级：按学号组织的二叉搜索树
// ------------------------------------------------------------------
type TreeNode struct {
	Data        *Student
	Left, Right *TreeNode
}

type StudentBST struct {
	Root *TreeNode
}

// >>> SOLUTION
func insertNode(p *TreeNode, s *Student) *TreeNode {
	if p == nil {
		return &TreeNode{Data: s}
	}
	if s.ID < p.Data.ID {
		p.Left = insertNode(p.Left, s)
	} else if s.ID > p.Data.ID {
		p.Right = insertNode(p.Right, s)
	}
	return p
}

func heightOf(p *TreeNode) int {
	if p == nil {
		return -1
	}
	return 1 + max(heightOf(p.Left), heightOf(p.Right))
}

func inorderIDs(p *TreeNode, out *[]string) {
	if p == nil {
		return
	}
	inorderIDs(p.Left, out)
	*out = append(*out, fmt.Sprint(p.Data.ID))
	inorderIDs(p.Right, out)
}

// <<< SOLUTION

// Insert – 第 4 级：插入（键：ID）；重复的学号不插入
func (t *StudentBST) Insert(s *Student) {
	// >>> SOLUTION
	t.Root = insertNode(t.Root, s)
	// <<< SOLUTION
}

// Find – 第 4 级：按学号查找；找不到时为 nil
func (t *StudentBST) Find(id int) *Student {
	// >>> SOLUTION
	p := t.Root
	for p != nil && p.Data.ID != id {
		if id < p.Data.ID {
			p = p.Left
		} else {
			p = p.Right
		}
	}
	if p == nil {
		return nil
	}
	return p.Data
	// <<< SOLUTION
}

// Height – 第 4 级：树的高度（空树：-1，一个结点：0）
func (t *StudentBST) Height() int {
	// >>> SOLUTION
	return heightOf(t.Root)
	// <<< SOLUTION
}

// InorderIDs – 第 4 级：按中序排列的学号，例如 "[1001, 1002, 1003]"
func (t *StudentBST) InorderIDs() string {
	// >>> SOLUTION
	var out []string
	inorderIDs(t.Root, &out)
	return "[" + strings.Join(out, ", ") + "]"
	// <<< SOLUTION
}

// ==================================================================
// 检查程序 – 不要修改！
// ==================================================================

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 运行一个级别的检查；TODO 引起的 panic 视为“尚未解答”
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")

		// 测量：20 000 个学生，在链表和二叉搜索树中各查找 20 000 次
		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} // 在表头快速填充
			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)")
}