// 10. hét – Kétirányú láncolt lista Go nyelven
// Futtatás: go run ./h10/doublylist
package main

import (
	"container/list"
	"fmt"
	"strings"
)

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

type DoublyList struct {
	Head, Tail *Node
	Size       int
}

func (l *DoublyList) InsertFirst(x int) {
	n := &Node{Value: x, Next: l.Head}
	if l.Head != nil {
		l.Head.Prev = n
	} else {
		l.Tail = n
	}
	l.Head = n
	l.Size++
}

func (l *DoublyList) InsertLast(x int) {
	n := &Node{Value: x, Prev: l.Tail}
	if l.Tail != nil {
		l.Tail.Next = n
	} else {
		l.Head = n
	}
	l.Tail = n
	l.Size++
}

func (l *DoublyList) InsertAfter(p *Node, x int) {
	if p == l.Tail {
		l.InsertLast(x)
		return
	}
	n := &Node{Value: x, Prev: p, Next: p.Next}
	p.Next.Prev = n
	p.Next = n
	l.Size++
}

// Remove – O(1): mindkét szomszédot ismerjük
func (l *DoublyList) Remove(p *Node) {
	if p.Prev != nil {
		p.Prev.Next = p.Next
	} else {
		l.Head = p.Next
	}
	if p.Next != nil {
		p.Next.Prev = p.Prev
	} else {
		l.Tail = p.Prev
	}
	l.Size--
}

func (l *DoublyList) Find(x int) *Node {
	for p := l.Head; p != nil; p = p.Next {
		if p.Value == x {
			return p
		}
	}
	return nil
}

func (l *DoublyList) Forward() string {
	var parts []string
	for p := l.Head; p != nil; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " <-> ") + "]"
}

func (l *DoublyList) Backward() string {
	var parts []string
	for p := l.Tail; p != nil; p = p.Prev {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " <-> ") + "]"
}

func main() {
	var l DoublyList
	l.InsertLast(2)
	l.InsertLast(3)
	l.InsertFirst(1)
	l.InsertLast(5)
	fmt.Println("előre:     ", l.Forward())
	fmt.Println("visszafelé:", l.Backward())
	l.InsertAfter(l.Find(3), 4)
	fmt.Println("InsertAfter(3, 4):", l.Forward())
	l.Remove(l.Find(3))
	fmt.Println("Remove(3):        ", l.Forward())
	l.Remove(l.Tail)
	fmt.Println("Remove(Tail):     ", l.Forward(), ", Size =", l.Size)

	// A Go container/list csomagja kétirányú (strázsás, ciklikus) lista
	gl := list.New()
	gl.PushBack("b")
	gl.PushBack("c")
	gl.PushFront("a")
	fmt.Print("container/list: ")
	for e := gl.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println()
}