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

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

type Node struct {
	Value      int
	Next, Prev *Node
}

var head, end *Node

func initSentinel(values ...int) {
	end = &Node{}
	head = end
	for _, v := range values {
		insertBefore(end, v)
	}
}

func insertBefore(p *Node, x int) {
	q := &Node{Value: p.Value, Next: p.Next}
	p.Value, p.Next = x, q
	if p == end {
		end = q
	}
}

func sentinelStr() string {
	var parts []string
	for p := head; p != end; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// F1. Maximum strázsás listában
func maxValue() int {
	m := math.MinInt
	for p := head; p != end; p = p.Next {
		m = max(m, p.Value)
	}
	return m
}

// F2. Előfordulások száma strázsás kereséssel
func countSentinel(x int) int {
	end.Value = x
	c := 0
	p := head
	for {
		for p.Value != x {
			p = p.Next
		}
		if p == end {
			return c
		}
		c++
		p = p.Next
	}
}

// F3. Páros elemek törlése a "másold a következőt" trükkel
func removeEven() {
	p := head
	for p != end {
		if p.Value%2 == 0 {
			q := p.Next
			p.Value, p.Next = q.Value, q.Next
			if q == end {
				end = p
			}
		} else {
			p = p.Next
		}
	}
}

// F4. Kétirányú lista palindrom-e?
func isPalindromeDoubly(a ...int) bool {
	var h, t *Node
	for _, v := range a {
		n := &Node{Value: v, Prev: t}
		if t != nil {
			t.Next = n
		} else {
			h = n
		}
		t = n
	}
	for h != t && t.Next != h {
		if h.Value != t.Value {
			return false
		}
		h, t = h.Next, t.Prev
	}
	return true
}

// F5. Ciklikus lista mérete
func circularSize(last *Node) int {
	if last == nil {
		return 0
	}
	c := 0
	for p := last.Next; ; {
		c++
		p = p.Next
		if p == last.Next {
			return c
		}
	}
}

func main() {
	initSentinel(4, 9, 2, 9, 7, 6)
	fmt.Println("F1. lista", sentinelStr(), ", max =", maxValue())
	fmt.Println("F2. countSentinel(9) =", countSentinel(9), ", countSentinel(5) =", countSentinel(5))
	removeEven()
	fmt.Println("F3. páros elemek törlése után:", sentinelStr())
	fmt.Println("F4. [1 2 3 2 1] palindrom?", isPalindromeDoubly(1, 2, 3, 2, 1), ", [1 2 2 3]?", isPalindromeDoubly(1, 2, 2, 3))
	a, b, c := &Node{Value: 1}, &Node{Value: 2}, &Node{Value: 3}
	a.Next, b.Next, c.Next = b, c, a
	fmt.Println("F5. ciklikus lista mérete:", circularSize(c))
}