// Week 8 – Circular queue (ring buffer) in Go
// Run: go run ./w08/circularqueue
package main

import (
	"errors"
	"fmt"
)

type CircularQueue struct {
	data  []int
	front int // index of the first element
	rear  int // index of the last element
	count int
}

func NewCircularQueue(capacity int) *CircularQueue {
	return &CircularQueue{data: make([]int, capacity), rear: -1}
}

func (q *CircularQueue) IsEmpty() bool { return q.count == 0 }
func (q *CircularQueue) IsFull() bool  { return q.count == len(q.data) }

// Enqueue – O(1)
func (q *CircularQueue) Enqueue(x int) error {
	if q.IsFull() {
		return errors.New("the queue is full")
	}
	q.rear = (q.rear + 1) % len(q.data)
	q.data[q.rear] = x
	q.count++
	return nil
}

// Dequeue – O(1)
func (q *CircularQueue) Dequeue() (int, error) {
	if q.IsEmpty() {
		return 0, errors.New("the queue is empty")
	}
	x := q.data[q.front]
	q.front = (q.front + 1) % len(q.data)
	q.count--
	return x, nil
}

func (q *CircularQueue) String() string {
	s := "[front] "
	for i := 0; i < q.count; i++ {
		s += fmt.Sprint(q.data[(q.front+i)%len(q.data)], " ")
	}
	return s + fmt.Sprintf("[rear]  (front=%d, rear=%d, count=%d)", q.front, q.rear, q.count)
}

func main() {
	q := NewCircularQueue(5)
	for x := 1; x <= 5; x++ {
		q.Enqueue(x * 10)
	}
	fmt.Println("5 × enqueue: ", q)
	if err := q.Enqueue(60); err != nil {
		fmt.Println("Error:", err)
	}
	a, _ := q.Dequeue()
	b, _ := q.Dequeue()
	fmt.Println("Dequeue() =", a, ", Dequeue() =", b)
	q.Enqueue(60)
	q.Enqueue(70) // rear wraps around
	fmt.Println("2 × enqueue: ", q)

	fmt.Print("emptying (FIFO): ")
	for !q.IsEmpty() {
		x, _ := q.Dequeue()
		fmt.Print(x, " ")
	}
	fmt.Println()

	// A simple queue with a slice: s = append(s, x) and s = s[1:]
	// (s[1:] does not free the beginning, but append copies to a new array from time to time)
	s := []string{}
	s = append(s, "Li", "Wang", "Chen")
	first := s[0]
	s = s[1:]
	fmt.Println("slice queue: removed =", first, ", remaining =", s)
}