// Week 3 – Array operations: insertion, deletion, reversal, rotation
// Run: go run ./w03/arrayops
package main

import "fmt"

// insert inserts at index pos; the array contains n elements. Shifts right from the back – 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 deletes at index pos: shifts left from the front – 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 in place, with two indexes – 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 by k positions, with three reversals – O(n), O(1) space.
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)

	// The same with slices, more concisely (behind the scenes it is still O(n) shifting)
	s := []int{5, 8, 13, 21, 34}
	s = append(s[:2], append([]int{99}, s[2:]...)...) // insertion
	s = append(s[:1], s[2:]...)                       // deletion
	fmt.Println("with slices:   ", s)
}