import java.util.*;

public class DemonstrasiAmortized {
    // List int sederhana dengan array internal yang bertumbuh dua kali lipat.
    static class DaftarInt {
        int[] data;
        int ukuran = 0;
        long jumlahSalin = 0;
        long elemenTersalin = 0;

        DaftarInt(int kapasitasAwal) {
            data = new int[kapasitasAwal];
        }

        void tambah(int nilai) {
            if (ukuran == data.length) {
                jumlahSalin++;
                elemenTersalin += ukuran;
                data = Arrays.copyOf(data, data.length * 2);
            }
            data[ukuran++] = nilai;
        }
    }

    public static void main(String[] args) {
        int total = 100_000;

        DaftarInt tumbuh = new DaftarInt(4);
        for (int i = 0; i < total; i++) {
            tumbuh.tambah(i);
        }
        System.out.println("Kapasitas awal 4 (bertumbuh sendiri):");
        System.out.println("  elemen ditambahkan : " + total);
        System.out.println("  operasi salin array: " + tumbuh.jumlahSalin);
        System.out.println("  elemen tersalin     : " + tumbuh.elemenTersalin);
        System.out.printf("  rata-rata salin per tambah: %.2f%n",
                (double) tumbuh.elemenTersalin / total);

        DaftarInt siap = new DaftarInt(131_072);
        for (int i = 0; i < total; i++) {
            siap.tambah(i);
        }
        System.out.println("Kapasitas awal 131072 (dihitung di muka):");
        System.out.println("  operasi salin array: " + siap.jumlahSalin);
        System.out.println("  elemen tersalin     : " + siap.elemenTersalin);
    }
}