// Week 3 – Our own dynamic array, and how the Go slice (append) works
// Run: go run ./w03/dynarray
package main

import "fmt"

// DynamicArray: an array whose capacity doubles.
type DynamicArray struct {
	data []int // the backing array (len(data) is the capacity)
	size int
}

var copies int

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

// Add appends at the end. When full, it allocates an array twice as large – amortized 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))

	// The built-in append does the same: watch the capacity!
	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)
		}
	}

	// Pitfall: shared backing array
	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) // there is still room: it overwrites arr[4]!
	fmt.Println("after append(sl, 77), arr =", arr)
}