// Week 11 – Stack and queue with a linked list (generic), with a common interface
// Run: go run ./w11/linkedstackqueue
package main

import (
	"errors"
	"fmt"
	"strings"
)

type Stack[T any] interface {
	Push(x T)
	Pop() (T, error)
	IsEmpty() bool
}

type node[T any] struct {
	value T
	next  *node[T]
}

// LinkedStack: the top is the beginning of the list – O(1)
type LinkedStack[T any] struct{ top *node[T] }

func (s *LinkedStack[T]) Push(x T) { s.top = &node[T]{x, s.top} }

func (s *LinkedStack[T]) Pop() (T, error) {
	var zero T
	if s.top == nil {
		return zero, errors.New("empty stack")
	}
	x := s.top.value
	s.top = s.top.next
	return x, nil
}

func (s *LinkedStack[T]) IsEmpty() bool { return s.top == nil }

// SliceStack: the same interface with a slice (week 7)
type SliceStack[T any] struct{ items []T }

func (s *SliceStack[T]) Push(x T) { s.items = append(s.items, x) }
func (s *SliceStack[T]) Pop() (T, error) {
	var zero T
	if len(s.items) == 0 {
		return zero, errors.New("empty stack")
	}
	x := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return x, nil
}
func (s *SliceStack[T]) IsEmpty() bool { return len(s.items) == 0 }

// LinkedQueue: removal from the beginning, insertion at the end – O(1)
type LinkedQueue[T any] struct {
	front, rear *node[T]
}

func (q *LinkedQueue[T]) Enqueue(x T) {
	n := &node[T]{value: x}
	if q.rear == nil {
		q.front = n
	} else {
		q.rear.next = n
	}
	q.rear = n
}

func (q *LinkedQueue[T]) Dequeue() (T, error) {
	var zero T
	if q.front == nil {
		return zero, errors.New("empty queue")
	}
	x := q.front.value
	q.front = q.front.next
	if q.front == nil {
		q.rear = nil // it became empty
	}
	return x, nil
}

func (q *LinkedQueue[T]) IsEmpty() bool { return q.front == nil }

// reverse knows only the interface
func reverse(s string, st Stack[rune]) string {
	for _, c := range s {
		st.Push(c)
	}
	var sb strings.Builder
	for !st.IsEmpty() {
		c, _ := st.Pop()
		sb.WriteRune(c)
	}
	return sb.String()
}

func main() {
	fmt.Println("reverse with a linked stack:", reverse("数据结构", &LinkedStack[rune]{}))
	fmt.Println("reverse with a slice stack: ", reverse("数据结构", &SliceStack[rune]{}))

	var q LinkedQueue[string]
	q.Enqueue("Li")
	q.Enqueue("Wang")
	q.Enqueue("Chen")
	x, _ := q.Dequeue()
	q.Enqueue("Anna")
	fmt.Print("queue: Dequeue = ", x, ", remaining: ")
	for !q.IsEmpty() {
		v, _ := q.Dequeue()
		fmt.Print(v, " ")
	}
	fmt.Println()
}