// You can edit this code!
// Click here and start typing.
package main

import "fmt"

type Node[T any] struct {
	Value T
	Next  *Node[T]
}

type LinkedList[T any] struct {
	Head  *Node[T]
	Tail  *Node[T]
	Count int
}

func (l *LinkedList[T]) AddHead(n *Node[T]) {
	n.Next = l.Head
	l.Head = n
	l.Count++
	if l.Count == 1 {
		l.Tail = l.Head
	}
}

func (l *LinkedList[T]) RemoveHead() {
	if l.Count == 0 {
		return
	}
	l.Head = l.Head.Next
	l.Count--
}

func (l *LinkedList[T]) AddTail(n *Node[T]) {
	if l.Count == 0 {
		l.Head = n
		l.Tail = n
	} else {
		l.Tail.Next = n
	}
	l.Tail = n
	l.Count++
}

func (l *LinkedList[T]) RemoveTail() {
	if l.Count == 0 {
		return
	}
	if l.Count == 1 {
		l.Head = nil
		l.Tail = nil
	} else {
		node := l.TraverseUntil(func(n *Node[T]) bool {
			return n.Next == l.Tail
		})
		node.Next = nil
		l.Tail = node
	}
	l.Count--
}

func (l *LinkedList[T]) TraverseUntil(pred func(n *Node[T]) bool) *Node[T] {
	current := l.Head
	for !pred(current) {
		current = current.Next
	}
	return current
}

func (l *LinkedList[T]) Print() {
	fmt.Printf("%d: ", l.Count)
	print(l.Head)
}

func print[T any](node *Node[T]) {
	for node != nil {
		fmt.Printf("%v --> ", node.Value)
		node = node.Next
	}
	fmt.Println()
}

func main() {
	tail := Node[int]{Value: 4}
	scnd := Node[int]{Value: 3, Next: &tail}
	frst := Node[int]{Value: 2, Next: &scnd}
	head := Node[int]{Value: 1, Next: &frst}
	//print(&head)

	// swap frst & scnd
	frst.Next = &tail
	scnd.Next = &frst
	head.Next = &scnd
	//print(&head)

	fmt.Println("Adding to Head")
	l := LinkedList[int]{}
	l.AddHead(&Node[int]{Value: 4})
	l.Print()
	l.AddHead(&Node[int]{Value: 3})
	l.Print()
	l.AddHead(&Node[int]{Value: 2})
	l.Print()
	l.AddHead(&Node[int]{Value: 1})
	l.Print()

	fmt.Println()

	fmt.Println("Adding to Tail")
	l2 := LinkedList[int]{}
	l2.AddTail(&Node[int]{Value: 1})
	l2.Print()
	l2.AddTail(&Node[int]{Value: 2})
	l2.Print()
	l2.AddTail(&Node[int]{Value: 3})
	l2.Print()
	l2.AddTail(&Node[int]{Value: 4})
	l2.Print()

	fmt.Println()

	fmt.Println("Removing from Head")
	l.Print()
	l.RemoveHead()
	l.Print()
	l.RemoveHead()
	l.Print()
	l.RemoveHead()
	l.Print()
	l.RemoveHead()
	l.Print()

	fmt.Println()

	fmt.Println("Removing from Tail")
	l2.Print()
	l2.RemoveTail()
	l2.Print()
	l2.RemoveTail()
	l2.Print()
	l2.RemoveTail()
	l2.Print()
	l2.RemoveTail()
	l2.Print()
}