// 9. hét – A gyakorlati feladatok megoldásai
// Futtatás: go run ./h09/exercises
package main

import (
	"fmt"
	"math"
	"strings"
)

type Node struct {
	Value int
	Next  *Node
}

func fromSlice(a ...int) *Node {
	var h *Node
	for i := len(a) - 1; i >= 0; i-- {
		h = &Node{a[i], h}
	}
	return h
}

func str(h *Node) string {
	var parts []string
	for p := h; p != nil; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// F1. Összeg és maximum
func sumAndMax(h *Node) (int, int) {
	sum, mx := 0, math.MinInt
	for p := h; p != nil; p = p.Next {
		sum += p.Value
		mx = max(mx, p.Value)
	}
	return sum, mx
}

// F2. Az i-edik elem – O(i)
func get(h *Node, i int) (int, bool) {
	p := h
	for k := 0; k < i && p != nil; k++ {
		p = p.Next
	}
	if p == nil {
		return 0, false
	}
	return p.Value, true
}

// F3. Előfordulások száma
func count(h *Node, x int) int {
	c := 0
	for p := h; p != nil; p = p.Next {
		if p.Value == x {
			c++
		}
	}
	return c
}

// F4. Megfordítás helyben
func reverse(h *Node) *Node {
	var prev *Node
	for p := h; p != nil; {
		next := p.Next
		p.Next = prev
		prev, p = p, next
	}
	return prev
}

// F5. Összes x törlése
func removeAll(h *Node, x int) *Node {
	for h != nil && h.Value == x {
		h = h.Next
	}
	if h == nil {
		return nil
	}
	for p := h; p.Next != nil; {
		if p.Next.Value == x {
			p.Next = p.Next.Next
		} else {
			p = p.Next
		}
	}
	return h
}

// F6. Középső elem (nyúl és teknős)
func middle(h *Node) int {
	slow, fast := h, h
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	return slow.Value
}

// F7. Rendezett beszúrás
func insertSorted(h *Node, x int) *Node {
	if h == nil || x <= h.Value {
		return &Node{x, h}
	}
	p := h
	for p.Next != nil && p.Next.Value < x {
		p = p.Next
	}
	p.Next = &Node{x, p.Next}
	return h
}

func main() {
	h := fromSlice(4, 9, 2, 9, 7)
	s, m := sumAndMax(h)
	fmt.Println("F1. lista", str(h), ": összeg =", s, ", max =", m)
	v, ok := get(h, 3)
	_, ok2 := get(h, 10)
	fmt.Println("F2. get(3) =", v, ok, ", get(10) létezik?", ok2)
	fmt.Println("F3. count(9) =", count(h, 9))
	fmt.Println("F4. reverse =", str(reverse(fromSlice(1, 2, 3, 4, 5))))
	fmt.Println("F5. removeAll(9) =", str(removeAll(fromSlice(9, 4, 9, 9, 2, 9), 9)))
	fmt.Println("F6. middle([1..5]) =", middle(fromSlice(1, 2, 3, 4, 5)), ", middle([1..6]) =", middle(fromSlice(1, 2, 3, 4, 5, 6)))
	var sl *Node
	for _, x := range []int{5, 2, 8, 1, 9, 3} {
		sl = insertSorted(sl, x)
	}
	fmt.Println("F7. rendezett beszúrással:", str(sl))
}