// 第 8 周 – 实践课练习的参考答案
// 运行：go run ./w08/exercises
package main

import (
	"fmt"
	"strings"
)

// 练习中使用的、用切片实现的简单泛型队列
type Queue[T any] struct{ items []T }

func (q *Queue[T]) Enqueue(x T) { q.items = append(q.items, x) }
func (q *Queue[T]) Dequeue() T {
	x := q.items[0]
	q.items = q.items[1:]
	return x
}
func (q *Queue[T]) Peek() T     { return q.items[0] }
func (q *Queue[T]) Len() int    { return len(q.items) }
func (q *Queue[T]) Empty() bool { return len(q.items) == 0 }

// E1. 旧试卷中的代码阅读题
func fibonacciQueue(n int) {
	var q Queue[int]
	q.Enqueue(0)
	q.Enqueue(1)
	for i := 0; i < n; i++ {
		a := q.Dequeue()
		fmt.Print(a, " ")
		b := q.Peek()
		q.Enqueue(a + b)
	}
	fmt.Println()
}

// E2. 约瑟夫问题
func josephus(n, k int) int {
	var q Queue[int]
	for i := 1; i <= n; i++ {
		q.Enqueue(i)
	}
	fmt.Print("order of elimination: ")
	for q.Len() > 1 {
		for i := 1; i < k; i++ {
			q.Enqueue(q.Dequeue())
		}
		fmt.Print(q.Dequeue(), " ")
	}
	return q.Dequeue()
}

// E3. 时间片轮转调度
func roundRobin(names []string, burst []int, quantum int) {
	var q Queue[int]
	left := append([]int(nil), burst...)
	for i := range names {
		q.Enqueue(i)
	}
	time := 0
	for !q.Empty() {
		p := q.Dequeue()
		run := min(quantum, left[p])
		time += run
		left[p] -= run
		if left[p] > 0 {
			q.Enqueue(p)
		} else {
			fmt.Printf("%s done (t=%d)  ", names[p], time)
		}
	}
	fmt.Println()
}

// E4. 用栈把队列逆序
func reverse(q *Queue[int]) {
	var st []int
	for !q.Empty() {
		st = append(st, q.Dequeue())
	}
	for len(st) > 0 {
		q.Enqueue(st[len(st)-1])
		st = st[:len(st)-1]
	}
}

// E5. 代码阅读：字母 = 入队，'*' = 出队并输出
func trace(ops string) string {
	var q Queue[rune]
	var out strings.Builder
	for _, c := range ops {
		switch c {
		case ' ':
		case '*':
			out.WriteRune(q.Dequeue())
		default:
			q.Enqueue(c)
		}
	}
	return out.String()
}

// E6. 滑动平均
func movingAverage(data []int, k int) {
	var w Queue[int]
	sum := 0
	for _, x := range data {
		w.Enqueue(x)
		sum += x
		if w.Len() > k {
			sum -= w.Dequeue()
		}
		fmt.Printf("%.1f ", float64(sum)/float64(w.Len()))
	}
	fmt.Println()
}

func main() {
	fmt.Print("E1. ")
	fibonacciQueue(10)
	fmt.Print("E2. ")
	fmt.Println("-> survivor:", josephus(7, 3))
	fmt.Print("E3. ")
	roundRobin([]string{"P1", "P2", "P3"}, []int{5, 2, 4}, 2)
	q := &Queue[int]{items: []int{1, 2, 3, 4}}
	reverse(q)
	fmt.Println("E4. reverse([1 2 3 4]) =", q.items)
	fmt.Println(`E5. trace("D A T * A * S * T R * U C * T") =`, trace("D A T * A * S * T R * U C * T"))
	fmt.Print("E6. moving average (k=3): ")
	movingAverage([]int{10, 20, 30, 40, 50, 60}, 3)
}