// Week 7 – A stack with a fixed-size array, and a general (generic) stack with a slice
// Run: go run ./w07/arraystack
package main

import (
	"errors"
	"fmt"
)

// ArrayStack: a fixed-capacity stack – exactly as in the pseudocode.
type ArrayStack struct {
	data []int
	top  int // index of the top element; -1 if empty
}

func NewArrayStack(capacity int) *ArrayStack {
	return &ArrayStack{data: make([]int, capacity), top: -1}
}

func (s *ArrayStack) IsEmpty() bool { return s.top == -1 }
func (s *ArrayStack) IsFull() bool  { return s.top == len(s.data)-1 }

// Push – O(1)
func (s *ArrayStack) Push(x int) error {
	if s.IsFull() {
		return errors.New("the stack is full (stack overflow)")
	}
	s.top++
	s.data[s.top] = x
	return nil
}

// Pop – O(1)
func (s *ArrayStack) Pop() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("the stack is empty (stack underflow)")
	}
	x := s.data[s.top]
	s.top--
	return x, nil
}

// Stack[T]: an unbounded stack of any element type (slice + append).
type Stack[T any] struct {
	items []T
}

func (s *Stack[T]) Push(x T)      { s.items = append(s.items, x) }
func (s *Stack[T]) IsEmpty() bool { return len(s.items) == 0 }
func (s *Stack[T]) Len() int      { return len(s.items) }

func (s *Stack[T]) Pop() T {
	n := len(s.items) - 1
	x := s.items[n]
	s.items = s.items[:n]
	return x
}

func (s *Stack[T]) Top() T { return s.items[len(s.items)-1] }

func main() {
	s := NewArrayStack(5)
	s.Push(15)
	s.Push(8)
	s.Push(42)
	fmt.Println("contents (from the bottom):", s.data[:s.top+1])
	x, _ := s.Pop()
	fmt.Println("Pop() =", x)

	for _, v := range []int{1, 2, 3, 4} {
		s.Push(v)
	}
	if err := s.Push(99); err != nil {
		fmt.Println("Error:", err)
	}
	fmt.Print("order of removal: ")
	for !s.IsEmpty() {
		v, _ := s.Pop()
		fmt.Print(v, " ")
	}
	fmt.Println()
	if _, err := s.Pop(); err != nil {
		fmt.Println("Error:", err)
	}

	// Generic stack of strings
	var g Stack[string]
	g.Push("a")
	g.Push("b")
	g.Push("c")
	fmt.Println("Stack[string]: Top =", g.Top(), ", Pop =", g.Pop(), ", Len =", g.Len())
}