import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * Kalkulator shallow size, retained size, dan pohon dominator atas graf
 * objek model dengan ukuran byte tetap. Semua angka hasil penelusuran
 * graf murni, bukan statistik GC sungguhan.
 */
public class UkurRetensi {

    static final Map<String, Simpul> simpul = new LinkedHashMap<>();

    static final class Simpul {
        final String nama;
        final int shallow;
        final List<Simpul> keluar = new ArrayList<>();

        Simpul(String nama, int shallow) {
            this.nama = nama;
            this.shallow = shallow;
        }

        void rujuk(Simpul s) {
            keluar.add(s);
        }
    }

    public static void main(String[] args) {
        bangunGraf();
        Simpul akar = simpul.get("Aplikasi");
        int totalHeap = ukuranTerjangkau(akar, null);

        System.out.println("== Peta referensi (ukuran model, byte) ==");
        for (Simpul s : simpul.values()) {
            if (!s.keluar.isEmpty()) {
                List<String> tujuan = new ArrayList<>();
                for (Simpul k : s.keluar) {
                    tujuan.add(k.nama);
                }
                System.out.println(s.nama + " -> " + String.join(", ", tujuan));
            }
        }
        System.out.println("Total heap model = " + totalHeap + " byte");
        System.out.println();
        System.out.println("== Shallow vs retained ==");
        System.out.printf("%-16s %8s %9s%n", "node", "shallow", "retained");
        Map<String, Integer> masuk = hitungIndegree();
        for (Simpul s : simpul.values()) {
            int retained = totalHeap - ukuranTerjangkau(akar, s);
            String tanda = masuk.get(s.nama) >= 2 ? "  <- dibagikan" : "";
            System.out.printf("%-16s %8d %9d%s%n", s.nama, s.shallow, retained, tanda);
        }
        System.out.println();
        System.out.println("== Pohon dominator (retained) ==");
        Map<String, Integer> petaRetained = new LinkedHashMap<>();
        for (Simpul s : simpul.values()) {
            petaRetained.put(s.nama, totalHeap - ukuranTerjangkau(akar, s));
        }
        Map<String, List<Simpul>> anak = pohonDominator(akar);
        cetakPohon(akar, anak, petaRetained, 0);
        System.out.println();
        System.out.println("== Catatan pembacaan ==");
        for (String n : List.of("ProfilBudi", "KeranjangBudi", "CachePengguna")) {
            Simpul s = simpul.get(n);
            int retained = totalHeap - ukuranTerjangkau(akar, s);
            int ikutBebas = retained - s.shallow;
            System.out.println(n + ": retained " + retained + " = shallow " + s.shallow
                + " + " + ikutBebas + " milik objek yang ikut bebas");
        }
    }

    static void bangunGraf() {
        Simpul aplikasi = buat("Aplikasi", 16);
        Simpul konfigurasi = buat("Konfigurasi", 48);
        Simpul cache = buat("CachePengguna", 40);
        Simpul budi = buat("PenggunaBudi", 32);
        Simpul siti = buat("PenggunaSiti", 32);
        Simpul profilBudi = buat("ProfilBudi", 56);
        Simpul profilSiti = buat("ProfilSiti", 56);
        Simpul logAudit = buat("LogAudit", 64);
        Simpul sesi = buat("SesiAktif", 24);
        Simpul keranjang = buat("KeranjangBudi", 32);
        Simpul item1 = buat("ItemBarang-1", 24);
        Simpul item2 = buat("ItemBarang-2", 24);
        Simpul item3 = buat("ItemBarang-3", 24);

        aplikasi.rujuk(konfigurasi);
        aplikasi.rujuk(cache);
        aplikasi.rujuk(logAudit);
        aplikasi.rujuk(sesi);
        cache.rujuk(budi);
        cache.rujuk(siti);
        budi.rujuk(profilBudi);
        siti.rujuk(profilSiti);
        logAudit.rujuk(profilBudi); // ProfilBudi dibagikan dua pemilik
        sesi.rujuk(keranjang);
        keranjang.rujuk(budi);      // PenggunaBudi punya dua jalur dari akar
        keranjang.rujuk(item1);
        keranjang.rujuk(item2);
        keranjang.rujuk(item3);
    }

    static Simpul buat(String nama, int shallow) {
        Simpul s = new Simpul(nama, shallow);
        simpul.put(nama, s);
        return s;
    }

    // Jumlah byte objek yang masih terjangkau dari akar setelah 'dihapus' dilepas
    static int ukuranTerjangkau(Simpul akar, Simpul dihapus) {
        if (dihapus == akar) {
            return 0; // melepas akar = seluruh heap bebas
        }
        Map<String, Boolean> dikunjungi = new LinkedHashMap<>();
        Deque<Simpul> tumpukan = new ArrayDeque<>();
        tumpukan.push(akar);
        dikunjungi.put(akar.nama, true);
        int total = 0;
        while (!tumpukan.isEmpty()) {
            Simpul s = tumpukan.pop();
            total += s.shallow;
            for (Simpul k : s.keluar) {
                if (k != dihapus && !dikunjungi.containsKey(k.nama)) {
                    dikunjungi.put(k.nama, true);
                    tumpukan.push(k);
                }
            }
        }
        return total;
    }

    static Map<String, Integer> hitungIndegree() {
        Map<String, Integer> masuk = new LinkedHashMap<>();
        for (Simpul s : simpul.values()) {
            masuk.putIfAbsent(s.nama, 0);
            for (Simpul k : s.keluar) {
                masuk.merge(k.nama, 1, Integer::sum);
            }
        }
        return masuk;
    }

    static Map<String, List<Simpul>> pohonDominator(Simpul akar) {
        // Dominator d: melepas d membuat node n tak terjangkau.
        // Immediate dominator = dominator terdalam (terdekat ke n).
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Deque<Simpul> antrean = new ArrayDeque<>();
        jarak.put(akar.nama, 0);
        antrean.add(akar);
        while (!antrean.isEmpty()) {
            Simpul s = antrean.poll();
            for (Simpul k : s.keluar) {
                if (!jarak.containsKey(k.nama)) {
                    jarak.put(k.nama, jarak.get(s.nama) + 1);
                    antrean.add(k);
                }
            }
        }
        Map<String, List<Simpul>> anak = new LinkedHashMap<>();
        for (Simpul n : simpul.values()) {
            if (n == akar) {
                continue;
            }
            Simpul idom = akar;
            for (Simpul d : simpul.values()) {
                if (d == n || d == akar) {
                    continue;
                }
                boolean nHilang = ukuranTerjangkauNode(akar, d, n);
                if (nHilang && jarak.get(d.nama) > jarak.get(idom.nama)) {
                    idom = d;
                }
            }
            anak.computeIfAbsent(idom.nama, k -> new ArrayList<>()).add(n);
        }
        return anak;
    }

    // Apakah node 'dicari' tak terjangkau dari akar setelah 'dihapus' dilepas?
    static boolean ukuranTerjangkauNode(Simpul akar, Simpul dihapus, Simpul dicari) {
        Map<String, Boolean> dikunjungi = new LinkedHashMap<>();
        Deque<Simpul> tumpukan = new ArrayDeque<>();
        tumpukan.push(akar);
        dikunjungi.put(akar.nama, true);
        while (!tumpukan.isEmpty()) {
            Simpul s = tumpukan.pop();
            if (s == dicari) {
                return false;
            }
            for (Simpul k : s.keluar) {
                if (k != dihapus && !dikunjungi.containsKey(k.nama)) {
                    dikunjungi.put(k.nama, true);
                    tumpukan.push(k);
                }
            }
        }
        return true;
    }

    static void cetakPohon(Simpul s, Map<String, List<Simpul>> anak,
                           Map<String, Integer> retained, int kedalaman) {
        System.out.println("  ".repeat(kedalaman) + s.nama + " (" + retained.get(s.nama) + ")");
        for (Simpul a : anak.getOrDefault(s.nama, List.of())) {
            cetakPohon(a, anak, retained, kedalaman + 1);
        }
    }
}