// 第 3 周 – 自己实现的动态数组（ArrayList 工作原理的核心）
// 运行：java DynamicArray.java
import java.util.ArrayList;

public class DynamicArray {
    private int[] data = new int[1];
    private int size = 0;
    static long copies = 0; // 总共复制了多少个元素

    // 在末尾追加。满时分配一个两倍大的数组。
    // 一次操作最坏是 O(n)，但平均（均摊）是 O(1)。
    void add(int x) {
        if (size == data.length) {
            int[] bigger = new int[2 * data.length];
            for (int i = 0; i < size; i++) {
                bigger[i] = data[i];
                copies++;
            }
            data = bigger;
        }
        data[size++] = x;
    }

    int get(int i) {
        if (i < 0 || i >= size) throw new IndexOutOfBoundsException("index: " + i);
        return data[i];
    }

    void set(int i, int x) {
        if (i < 0 || i >= size) throw new IndexOutOfBoundsException("index: " + i);
        data[i] = x;
    }

    int size() { return size; }
    int capacity() { return data.length; }

    public static void main(String[] args) {
        DynamicArray d = new DynamicArray();
        for (int i = 1; i <= 9; i++) {
            d.add(i * 10);
            System.out.printf("add(%d): size=%d capacity=%d%n", i * 10, d.size(), d.capacity());
        }

        int n = 1_000_000;
        DynamicArray big = new DynamicArray();
        copies = 0;
        for (int i = 0; i < n; i++) big.add(i);
        System.out.printf("%nappending %,d elements: %,d copies (%.2f per element)%n", n, copies, (double) copies / n);

        // 内置的版本：ArrayList（只能存放对象，所以用 Integer）
        ArrayList<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(7);
        list.add(1, 6);     // 插入 – O(n)
        list.remove(0);     // 按下标删除 – O(n)
        System.out.println("ArrayList: " + list + ", get(1) = " + list.get(1));
    }
}