// 10. hét – Strázsás lista: Fej az első elemre, Vég a strázsára mutat; üres lista: Fej = Vég.
// Futtatás: go run ./h10/sentinellist
package main

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

type Node struct {
	Value int
	Next  *Node
}

type SentinelList struct {
	Head, End *Node
}

// NewSentinelList: egyetlen strázsa elem, Fej = Vég
func NewSentinelList() *SentinelList {
	s := &Node{}
	return &SentinelList{Head: s, End: s}
}

func (l *SentinelList) IsEmpty() bool { return l.Head == l.End }

func (l *SentinelList) String() string {
	var parts []string
	for p := l.Head; p != l.End; p = p.Next { // a strázsáig, nem nil-ig!
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// Search: strázsás keresés – a ciklusnak egyetlen feltétele van
func (l *SentinelList) Search(x int) *Node {
	l.End.Value = x
	p := l.Head
	for p.Value != x {
		p = p.Next
	}
	if p == l.End {
		return nil
	}
	return p
}

// InsertBefore: beszúrás p ELÉ – O(1) (p tartalmát q-ba másoljuk, p-be az új adat)
func (l *SentinelList) InsertBefore(p *Node, x int) {
	q := &Node{Value: p.Value, Next: p.Next}
	p.Value = x
	p.Next = q
	if p == l.End {
		l.End = q
	}
}

func (l *SentinelList) InsertLast(x int)  { l.InsertBefore(l.End, x) }
func (l *SentinelList) InsertFirst(x int) { l.InsertBefore(l.Head, x) }

// Delete: p törlése – O(1) (a következő elem tartalmát p-be másoljuk)
func (l *SentinelList) Delete(p *Node) {
	if p == l.End {
		panic("a strázsa nem törölhető")
	}
	q := p.Next
	p.Value = q.Value
	p.Next = q.Next
	if q == l.End {
		l.End = p
	}
}

func (l *SentinelList) Clear() { l.Head = l.End }

// InsertSorted: az első nagyobb elem elé – speciális esetek nélkül
func (l *SentinelList) InsertSorted(x int) {
	l.End.Value = math.MaxInt
	p := l.Head
	for p.Value < x {
		p = p.Next
	}
	l.InsertBefore(p, x)
}

func main() {
	l := NewSentinelList()
	fmt.Println("üres:", l)
	l.InsertLast(3)
	l.InsertLast(9)
	l.InsertLast(4)
	l.InsertFirst(1)
	fmt.Println("InsertLast 3, 9, 4; InsertFirst 1:", l)
	fmt.Println("Search(9) talált?", l.Search(9) != nil, ", Search(7) talált?", l.Search(7) != nil)
	l.InsertBefore(l.Search(9), 8)
	fmt.Println("InsertBefore(9, 8):", l)
	l.Delete(l.Search(4))
	fmt.Println("Delete(4):", l)
	l.Delete(l.Search(1))
	fmt.Println("Delete(1):", l)

	s := NewSentinelList()
	for _, x := range []int{5, 2, 8, 1, 9, 3} {
		s.InsertSorted(x)
	}
	fmt.Println("rendezett beszúrással:", s)
	s.Clear()
	fmt.Println("Clear után üres?", s.IsEmpty())
}