import java.util.*;

/**
 * Models pidgin-0001: libpurple/privacy.c
 *
 * add_all_buddies_to_permit_list() ensures every buddy on our buddy list is
 * also on the permit (allow) list. It iterates all B buddies and for each
 * calls g_slist_find_custom(account->permit, name, g_utf8_collate), scanning
 * our permit GSList linearly: O(B * P) where P = permit list size (grows to B).
 * Total: O(B^2) for B buddies all on our ALLOW_BUDDYLIST privacy mode.
 *
 * Fix: before our buddy loop, snapshot account->permit into a GHashTable for
 * O(1) membership tests. Our while loop becomes O(B) total.
 */
public class PidginPrivacyTest {

    // --- Defective model: GSList linear scan per buddy ---
    static long addAllBuddiesDefective(List<String> buddies) {
        List<String> permit = new ArrayList<>();
        long ops = 0;
        for (String buddy : buddies) {
            // simulate g_slist_find_custom scan of permit list
            boolean found = false;
            for (String p : permit) {   // O(P)
                ops++;
                if (p.equals(buddy)) { found = true; break; }
            }
            if (!found) permit.add(buddy);
        }
        return ops;
    }

    // --- Fixed model: GHashTable snapshot for O(1) lookup ---
    static long addAllBuddiesFixed(List<String> buddies) {
        Set<String> permitSet = new HashSet<>(); // snapshot of existing permit
        List<String> permit = new ArrayList<>();
        long ops = 0;
        for (String buddy : buddies) {
            ops++; // O(1) hash lookup
            if (!permitSet.contains(buddy)) {
                permitSet.add(buddy);
                permit.add(buddy);
            }
        }
        return ops;
    }

    static List<String> generateBuddies(int n) {
        List<String> buddies = new ArrayList<>();
        for (int i = 0; i < n; i++)
            buddies.add("buddy" + i + "@example.com");
        return buddies;
    }

    public static void main(String[] args) {
        System.out.println("pidgin-0001: add_all_buddies_to_permit_list O(B^2) vs O(B)");
        System.out.println("============================================================");

        int[] sizes = {50, 100, 200, 500, 1000, 2000};

        for (int n : sizes) {
            List<String> buddies = generateBuddies(n);

            long tDefStart = System.nanoTime();
            long opsDefective = addAllBuddiesDefective(new ArrayList<>(buddies));
            long tDefEnd = System.nanoTime();

            long tFixStart = System.nanoTime();
            long opsFixed = addAllBuddiesFixed(new ArrayList<>(buddies));
            long tFixEnd = System.nanoTime();

            long timeDefective = tDefEnd - tDefStart;
            long timeFixed = tFixEnd - tFixStart;
            double ratio = (double) opsDefective / opsFixed;

            System.out.printf("B=%4d: defective=%8d ops (%6.3f ms) | fixed=%6d ops (%6.3f ms) | ratio=%.1fx%n",
                n,
                opsDefective, timeDefective / 1_000_000.0,
                opsFixed, timeFixed / 1_000_000.0,
                ratio);
        }

        // Correctness: both models produce same permit list
        List<String> test = Arrays.asList("alice@x.com", "bob@x.com", "alice@x.com", "carol@x.com");

        Set<String> defSeen = new LinkedHashSet<>();
        for (String b : test) defSeen.add(b);

        Set<String> fixSeen = new HashSet<>();
        List<String> fixPermit = new ArrayList<>();
        for (String b : test) { if (fixSeen.add(b)) fixPermit.add(b); }

        assert new ArrayList<>(defSeen).equals(fixPermit)
            : "Mismatch: " + defSeen + " vs " + fixPermit;
        System.out.println("\nCorrectness: PASS");

        // Verify ratio at B=1000
        List<String> bigBuddies = generateBuddies(1000);
        long bigDef = addAllBuddiesDefective(new ArrayList<>(bigBuddies));
        long bigFix = addAllBuddiesFixed(new ArrayList<>(bigBuddies));
        double bigRatio = (double) bigDef / bigFix;
        assert bigRatio > 200 : "Expected >200x at B=1000, got " + bigRatio;
        System.out.printf("Speedup at B=1000: %.0fx -- PASS%n", bigRatio);
    }
}