package defects.xen.unit;

import java.util.*;

/**
 * Unit tests for xen-0001: credit2 balance_load O(V²) VCPU swap-search.
 */
public class Xen0001Test {

    static int passed = 0;
    static int failed = 0;

    static void assertTrue(String label, boolean condition) {
        if (condition) {
            System.out.println("  PASS: " + label);
            passed++;
        } else {
            System.out.println("  FAIL: " + label);
            failed++;
        }
    }

    public static void main(String[] args) {
        System.out.println("xen-0001 unit tests");
        System.out.println("=".repeat(50));

        testDefectiveIsQuadratic();
        testFixedIsLinear();
        testBothFindSameWinner();
        testNoMigratable();
        testSingleVcpu();
        testLoadRatioAbove50x();

        System.out.println();
        System.out.printf("Result: %d passed, %d failed%n", passed, failed);
        if (failed > 0) System.exit(1);
    }

    static void testDefectiveIsQuadratic() {
        System.out.println("\n--- testDefectiveIsQuadratic ---");
        Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad d =
            new Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad();

        int v1 = 10, v2 = 20;
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> l1 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v1, 100, false);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> o1 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v1, 50, false);
        d.findBestSwap(l1, o1,
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(l1),
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(o1));
        int ops1 = d.comparisons;

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> l2 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v2, 100, false);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> o2 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v2, 50, false);
        d.findBestSwap(l2, o2,
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(l2),
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(o2));
        int ops2 = d.comparisons;

        // Doubling V should roughly quadruple ops
        double ratio = (double) ops2 / ops1;
        assertTrue("Defective ops grows quadratically (ratio ≈ 4×): " + ratio,
            ratio >= 3.5 && ratio <= 4.5);
    }

    static void testFixedIsLinear() {
        System.out.println("\n--- testFixedIsLinear ---");
        Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad f =
            new Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad();

        int v1 = 50, v2 = 100;
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> l1 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v1, 100, true);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> o1 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v1, 50, true);
        f.findBestSwap(l1, o1,
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(l1),
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(o1));
        int ops1 = f.comparisons;

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> l2 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v2, 100, true);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> o2 =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v2, 50, true);
        f.findBestSwap(l2, o2,
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(l2),
            Xen0001CreditBalanceLoadAlgorithm.totalLoad(o2));
        int ops2 = f.comparisons;

        // Fixed ops should be O(1) or at most O(V) — not O(V²)
        assertTrue("Fixed ops does not grow quadratically (ops1=" + ops1 + " ops2=" + ops2 + ")",
            ops2 <= ops1 * 4); // generous bound: well below V² ratio of 4
        assertTrue("Fixed ops is bounded (ops1 <= 4): " + ops1, ops1 <= 4);
        assertTrue("Fixed ops is bounded (ops2 <= 4): " + ops2, ops2 <= 4);
    }

    static void testBothFindSameWinner() {
        System.out.println("\n--- testBothFindSameWinner ---");
        // Imbalanced runqueues: lrqd very heavy, orqd light
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lrqd = new ArrayList<>();
        lrqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(1, 1000, true));
        lrqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(2, 500, true));
        lrqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(3, 200, false));

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> orqd = new ArrayList<>();
        orqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(10, 100, true));
        orqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(11, 50, true));

        long lLoad = 1700, oLoad = 150;

        Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad def =
            new Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad();
        Xen0001CreditBalanceLoadAlgorithm.SwapPair defPair =
            def.findBestSwap(lrqd, orqd, lLoad, oLoad);

        // Sorted descending by avgload for fixed
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lrqdS = new ArrayList<>(lrqd);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> orqdS = new ArrayList<>(orqd);
        lrqdS.sort((a, b) -> Long.compare(b.avgload, a.avgload));
        orqdS.sort((a, b) -> Long.compare(b.avgload, a.avgload));

        Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad fix =
            new Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad();
        Xen0001CreditBalanceLoadAlgorithm.SwapPair fixPair =
            fix.findBestSwap(lrqdS, orqdS, lLoad, oLoad);

        assertTrue("Both defective and fixed find a swap pair",
            defPair != null && fixPair != null);
        // Both should choose the heaviest push (id=1, load=1000)
        assertTrue("Both push the heaviest VCPU (id=1)",
            defPair != null && defPair.push.id == 1 &&
            fixPair != null && fixPair.push.id == 1);
    }

    static void testNoMigratable() {
        System.out.println("\n--- testNoMigratable ---");
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lrqd = new ArrayList<>();
        lrqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(1, 500, false));
        lrqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(2, 300, false));

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> orqd = new ArrayList<>();
        orqd.add(new Xen0001CreditBalanceLoadAlgorithm.Vcpu(10, 100, false));

        Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad def =
            new Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad();
        Xen0001CreditBalanceLoadAlgorithm.SwapPair defPair =
            def.findBestSwap(lrqd, orqd, 800, 100);

        assertTrue("No swap when no VCPUs are migratable (defective): pair=null",
            defPair == null);

        Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad fix =
            new Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad();
        Xen0001CreditBalanceLoadAlgorithm.SwapPair fixPair =
            fix.findBestSwap(lrqd, orqd, 800, 100);
        assertTrue("No swap when no VCPUs are migratable (fixed): pair=null",
            fixPair == null);
    }

    static void testSingleVcpu() {
        System.out.println("\n--- testSingleVcpu ---");
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lrqd = List.of(
            new Xen0001CreditBalanceLoadAlgorithm.Vcpu(1, 200, true));
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> orqd = List.of(
            new Xen0001CreditBalanceLoadAlgorithm.Vcpu(2, 50, true));

        Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad def =
            new Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad();
        def.findBestSwap(lrqd, orqd, 200, 50);
        assertTrue("Single VCPU: defective comparisons=1", def.comparisons == 1);

        Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad fix =
            new Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad();
        fix.findBestSwap(lrqd, orqd, 200, 50);
        assertTrue("Single VCPU: fixed comparisons <= 2", fix.comparisons <= 2);
    }

    static void testLoadRatioAbove50x() {
        System.out.println("\n--- testLoadRatioAbove50x (V=100) ---");
        int v = 100;
        Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad def =
            new Xen0001CreditBalanceLoadAlgorithm.DefectiveBalanceLoad();
        Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad fix =
            new Xen0001CreditBalanceLoadAlgorithm.FixedBalanceLoad();

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lrqd =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v, 100, false);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> orqd =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v, 50, false);
        long lLoad = Xen0001CreditBalanceLoadAlgorithm.totalLoad(lrqd);
        long oLoad = Xen0001CreditBalanceLoadAlgorithm.totalLoad(orqd);

        def.findBestSwap(lrqd, orqd, lLoad, oLoad);

        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> lS =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v, 100, true);
        List<Xen0001CreditBalanceLoadAlgorithm.Vcpu> oS =
            Xen0001CreditBalanceLoadAlgorithm.buildSvcList(v, 50, true);
        fix.findBestSwap(lS, oS, lLoad, oLoad);

        double ratio = (double) def.comparisons / Math.max(fix.comparisons, 1);
        System.out.printf("  defective=%d, fixed=%d, ratio=%.1f×%n",
            def.comparisons, fix.comparisons, ratio);
        assertTrue("Op-count ratio >= 50× at V=100: " + ratio, ratio >= 50.0);
    }
}