import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ResolusiDependensi {

    record Modul(String nama, String versi, List<String> butuh) {}

    // Graf contoh: aplikasi bergantung pada tiga modul; web dan data
    // sama-sama menyeret versi umum yang lebih baru secara transitif.
    static final List<Modul> GRAF = List.of(
            new Modul("aplikasi", "1.0", List.of("umum:1.0", "web:2.0", "data:1.2")),
            new Modul("web", "2.0", List.of("umum:1.1", "inti:1.0")),
            new Modul("data", "1.2", List.of("umum:1.1")),
            new Modul("umum", "1.0", List.of()),
            new Modul("umum", "1.1", List.of()),
            new Modul("inti", "1.0", List.of()));

    public static void main(String[] args) {
        System.out.println("Graf dependensi:");
        for (Modul m : GRAF) {
            String anak = m.butuh().isEmpty() ? " (tanpa dependensi)" : " -> " + m.butuh();
            System.out.println("  " + m.nama() + " " + m.versi() + anak);
        }
        System.out.println();
        System.out.println("Model Maven (definisi terdekat menang):");
        System.out.println("  " + resolusiTerdekat());
        System.out.println("Model Gradle (versi terbaru menang):");
        System.out.println("  " + resolusiTerbaru());
    }

    // Penelusuran melebar dari dependensi langsung: nama yang terlihat
    // lebih dulu menang, meniru aturan "nearest definition wins" Maven.
    static Map<String, String> resolusiTerdekat() {
        Map<String, String> terpilih = new TreeMap<>();
        Deque<Modul> antrean = new ArrayDeque<>();
        for (String ref : cari("aplikasi", "1.0").butuh()) {
            antrean.add(cari(ref));
        }
        while (!antrean.isEmpty()) {
            Modul m = antrean.poll();
            if (!terpilih.containsKey(m.nama())) {
                terpilih.put(m.nama(), m.versi());
                for (String ref : m.butuh()) {
                    antrean.add(cari(ref));
                }
            }
        }
        return terpilih;
    }

    // Bandingkan semua versi yang muncul di graf, pilih yang tertinggi —
    // meniru penyelesaian konflik versi Gradle yang memilih versi terbaru.
    static Map<String, String> resolusiTerbaru() {
        Map<String, String> terpilih = new TreeMap<>();
        for (Modul m : GRAF) {
            if (m.nama().equals("aplikasi")) {
                continue;
            }
            terpilih.merge(m.nama(), m.versi(),
                    (lama, baru) -> bandingkanVersi(baru, lama) > 0 ? baru : lama);
        }
        return terpilih;
    }

    static Modul cari(String namaVersi) {
        String[] bagian = namaVersi.split(":");
        return cari(bagian[0], bagian[1]);
    }

    static Modul cari(String nama, String versi) {
        for (Modul m : GRAF) {
            if (m.nama().equals(nama) && m.versi().equals(versi)) {
                return m;
            }
        }
        throw new IllegalArgumentException("Modul tidak ada: " + nama + ":" + versi);
    }

    // Bandingkan dua string versi sederhana "mayor.minor".
    static int bandingkanVersi(String a, String b) {
        String[] sa = a.split("\\.");
        String[] sb = b.split("\\.");
        int panjang = Math.max(sa.length, sb.length);
        for (int i = 0; i < panjang; i++) {
            int ka = i < sa.length ? Integer.parseInt(sa[i]) : 0;
            int kb = i < sb.length ? Integer.parseInt(sb[i]) : 0;
            if (ka != kb) {
                return Integer.compare(ka, kb);
            }
        }
        return 0;
    }
}