// 第 3 周 – 数组操作：插入、删除、逆置、循环移位
// 运行：go run ./w03/arrayops
package main

import "fmt"

// insert 在下标 pos 处插入；数组中有 n 个元素。从后往前右移 – O(n)。
func insert(a []int, n, pos, x int) int {
	if n == len(a) {
		panic("the array is full")
	}
	for i := n - 1; i >= pos; i-- {
		a[i+1] = a[i]
	}
	a[pos] = x
	return n + 1
}

// deleteAt 删除下标 pos 处的元素：从前往后左移 – O(n)。
func deleteAt(a []int, n, pos int) int {
	for i := pos; i < n-1; i++ {
		a[i] = a[i+1]
	}
	a[n-1] = 0
	return n - 1
}

// reverse 用两个下标原地逆置 – O(n)。
func reverse(a []int) {
	for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
		a[i], a[j] = a[j], a[i]
	}
}

// rotateLeft 循环左移 k 位，三次逆置 – O(n),O(1) 空间。
func rotateLeft(a []int, k int) {
	k %= len(a)
	reverse(a[:k])
	reverse(a[k:])
	reverse(a)
}

func main() {
	a := make([]int, 6)
	n := copy(a, []int{5, 8, 13, 21, 34})
	fmt.Println("initially:     ", a, "n =", n)

	n = insert(a, n, 2, 99)
	fmt.Println("insert(2, 99): ", a, "n =", n)

	n = deleteAt(a, n, 1)
	fmt.Println("delete(1):     ", a, "n =", n)

	r := []int{1, 2, 3, 4, 5}
	reverse(r)
	fmt.Println("reverse:       ", r)

	q := []int{1, 2, 3, 4, 5}
	rotateLeft(q, 2)
	fmt.Println("rotateLeft(2): ", q)

	// 用切片写得更简洁（底层仍然是 O(n) 的移动）
	s := []int{5, 8, 13, 21, 34}
	s = append(s[:2], append([]int{99}, s[2:]...)...) // 插入
	s = append(s[:1], s[2:]...)                       // 删除
	fmt.Println("with slices:   ", s)
}