// Adatszerkezetek – gyakorlati jegy: Hallgatói nyilvántartás
//
// Feladat: a TODO-val jelölt függvények megvalósítása SAJÁT adatszerkezettel.
// A container/list csomag és a map a megoldásban NEM használható.
//
// Futtatás (ebben a mappában):  go run .
// A program a végén szintenként kiírja, mely ellenőrzések sikeresek (OK) és melyek nem (HIBA).
package main

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

// ------------------------------------------------------------------
// Hallgató (NE módosítsd!)
// ------------------------------------------------------------------
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. szint: egyirányú láncolt lista
// ------------------------------------------------------------------
type Node struct {
	Data *Student
	Next *Node
}

type StudentList struct {
	Head *Node // az első elem; üres listában nil
	// Szükség esetén további mezőket is felvehetsz (pl. Tail, Size).
}

// Add – 1. szint: új hallgató a lista VÉGÉRE
func (l *StudentList) Add(s *Student) {
	panic("TODO")
}

// Size – 1. szint: a hallgatók száma
func (l *StudentList) Size() int {
	panic("TODO")
}

// Find – 1. szint: keresés azonosító szerint; nil, ha nincs
func (l *StudentList) Find(id int) *Student {
	panic("TODO")
}

// String – 1. szint: pl. "[1003 Li Wei 87, 1001 Wang Fang 92]"; üres lista: "[]"
func (l *StudentList) String() string {
	panic("TODO")
}

// Remove – 2. szint: a megadott azonosítójú hallgató törlése; igaz, ha volt ilyen
func (l *StudentList) Remove(id int) bool {
	panic("TODO")
}

// AverageScore – 2. szint: a pontszámok átlaga; üres listánál 0
func (l *StudentList) AverageScore() float64 {
	panic("TODO")
}

// Best – 2. szint: a legnagyobb pontszámú hallgató (egyenlőségnél a listában előbb álló); üres listánál nil
func (l *StudentList) Best() *Student {
	panic("TODO")
}

// AddSortedByScore – 3. szint: a lista pontszám szerint CSÖKKENŐ sorrendű marad;
// egyenlő pontszámnál az új hallgató a már bent lévők MÖGÉ kerül (stabil)
func (l *StudentList) AddSortedByScore(s *Student) {
	panic("TODO")
}

// Reverse – 3. szint: a lista megfordítása HELYBEN (új csomópontok nélkül)
func (l *StudentList) Reverse() {
	panic("TODO")
}

// ------------------------------------------------------------------
// 4. szint: bináris keresőfa az azonosító szerint
// ------------------------------------------------------------------
type TreeNode struct {
	Data        *Student
	Left, Right *TreeNode
}

type StudentBST struct {
	Root *TreeNode
}

// Ide írhatsz segédfüggvényeket.

// Insert – 4. szint: beszúrás (kulcs: ID); ismétlődő azonosítót nem szúrunk be
func (t *StudentBST) Insert(s *Student) {
	panic("TODO")
}

// Find – 4. szint: keresés azonosító szerint; nil, ha nincs
func (t *StudentBST) Find(id int) *Student {
	panic("TODO")
}

// Height – 4. szint: a fa magassága (üres fa: -1, egy csomópont: 0)
func (t *StudentBST) Height() int {
	panic("TODO")
}

// InorderIDs – 4. szint: az azonosítók inorder sorrendben, pl. "[1001, 1002, 1003]"
func (t *StudentBST) InorderIDs() string {
	panic("TODO")
}

// ==================================================================
// Ellenőrző program – NE módosítsd!
// ==================================================================

var okCount, failCount int

func check(what string, cond bool) {
	if cond {
		okCount++
		fmt.Println("  OK  ", what)
	} else {
		failCount++
		fmt.Println("  HIBA", 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 egy szint ellenőrzését futtatja; a TODO-pánikot "nincs megoldva"-ként kezeli
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("  ---  még nincs megoldva")
			} else {
				failCount++
				fmt.Println("  HIBA pánik:", r)
			}
			passed = false
		}
	}()
	body()
	return failCount == before
}

func main() {
	l1 := level("1. szint (elégséges): Add, Size, Find, String", func() {
		var l StudentList
		check(`üres lista: Size() == 0 és "[]"`, l.Size() == 0 && l.String() == "[]")
		for _, s := range sample() {
			l.Add(s)
		}
		check("5 hallgató után Size() == 5", l.Size() == 5)
		check("a sorrend a beszúrás sorrendje", 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("2. szint (közepes): Remove, AverageScore, Best", func() {
		var l StudentList
		check("üres lista: AverageScore() == 0 és Best() == nil", l.AverageScore() == 0 && l.Best() == nil)
		for _, s := range sample() {
			l.Add(s)
		}
		check("Remove(1005) igaz", l.Remove(1005))
		check("Remove(9999) hamis", !l.Remove(9999))
		check("törlés után Size() == 4 és Find(1005) == nil", l.Size() == 4 && l.Find(1005) == nil)
		check("az első elem törlése: 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 (egyenlőségnél az előbb álló)", b != nil && b.Name == "Wang Fang")
	})

	l3 := l2 && level("3. szint (jó): AddSortedByScore, Reverse", func() {
		var l StudentList
		for _, s := range sample() {
			l.AddSortedByScore(s)
		}
		check("csökkenő pontszám, stabil sorrend", 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("beszúrás a lista elejére és végére", 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("üres lista megfordítása", e.String() == "[]")
	})

	l4 := l3 && level("4. szint (jeles): StudentBST – Insert, Find, Height, InorderIDs", func() {
		var t StudentBST
		check("üres fa: Height() == -1", t.Height() == -1)
		for _, s := range sample() {
			t.Insert(s)
		}
		t.Insert(&Student{1003, "Másolat", 0})
		check("InorderIDs() rendezett", 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("ismétlődő azonosítót nem szúr be", t.Find(1003).Name == "Li Wei")

		// Mérés: 20 000 hallgató, 20 000 keresés listában és keresőfában
		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("H", i), rnd.Intn(101)}
			list.Head = &Node{Data: s, Next: list.Head} // gyors feltöltés az elejére
			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("  mérés: %d keresés – lista: %.1f ms, keresőfa: %.1f ms, fa magassága: %d\n",
			n, float64(t1.Sub(t0).Microseconds())/1000, float64(t2.Sub(t1).Microseconds())/1000, tree.Height())
		check("mindkét szerkezet minden elemet megtalál", found1 == n && found2 == n)
		check("a keresőfa magassága kicsi (< 60)", tree.Height() < 60)
	})

	grade := "elégtelen (1)"
	switch {
	case l4:
		grade = "jeles (5)"
	case l3:
		grade = "jó (4)"
	case l2:
		grade = "közepes (3)"
	case l1:
		grade = "elégséges (2)"
	}
	fmt.Printf("\nSikeres ellenőrzések: %d, hibás: %d\n", okCount, failCount)
	fmt.Println("Az automatikus ellenőrzés alapján elért szint:", grade,
		" (a végső jegyet az oktató állapítja meg a kód és a szóbeli magyarázat alapján)")
}