// 第 3 周 – 自己实现的动态数组，以及 Go 切片（append）的工作原理
// 运行：go run ./w03/dynarray
package main

import "fmt"

// DynamicArray：容量成倍增长的数组。
type DynamicArray struct {
	data []int // 底层数组（len(data) 就是容量）
	size int
}

var copies int

func NewDynamicArray() *DynamicArray {
	return &DynamicArray{data: make([]int, 1)}
}

// Add 在末尾追加。满时分配两倍大小的数组 – 均摊 O(1)。
func (d *DynamicArray) Add(x int) {
	if d.size == len(d.data) {
		bigger := make([]int, 2*len(d.data))
		for i := 0; i < d.size; i++ {
			bigger[i] = d.data[i]
			copies++
		}
		d.data = bigger
	}
	d.data[d.size] = x
	d.size++
}

func (d *DynamicArray) Get(i int) int {
	if i < 0 || i >= d.size {
		panic(fmt.Sprintf("index: %d", i))
	}
	return d.data[i]
}

func (d *DynamicArray) Size() int     { return d.size }
func (d *DynamicArray) Capacity() int { return len(d.data) }

func main() {
	d := NewDynamicArray()
	for i := 1; i <= 9; i++ {
		d.Add(i * 10)
		fmt.Printf("Add(%d): size=%d capacity=%d\n", i*10, d.Size(), d.Capacity())
	}

	n := 1_000_000
	big := NewDynamicArray()
	copies = 0
	for i := 0; i < n; i++ {
		big.Add(i)
	}
	fmt.Printf("\nappending %d elements: %d copies (%.2f per element)\n", n, copies, float64(copies)/float64(n))

	// 内置的 append 也是这样做的：注意观察容量！
	fmt.Println("\ncapacities of append:")
	var s []int
	last := -1
	for i := 0; i < 2000; i++ {
		s = append(s, i)
		if cap(s) != last {
			fmt.Printf("  len=%4d cap=%4d\n", len(s), cap(s))
			last = cap(s)
		}
	}

	// 陷阱：共享底层数组
	arr := [6]int{10, 20, 30, 40, 50, 60}
	sl := arr[1:4] // len 3,cap 5
	sl[0] = 99
	fmt.Println("\nafter modifying arr[1:4], arr =", arr, " len =", len(sl), "cap =", cap(sl))
	sl = append(sl, 77) // 还有空间：它会覆盖 arr[4]!
	fmt.Println("after append(sl, 77), arr =", arr)
}