package unit;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

/**
 * zookeeper-0001: PrepRequestProcessor.removeDuplicates — ArrayList.contains() O(n²)
 * vs LinkedHashSet O(n).
 *
 * Standalone unit test — no JUnit required.
 * Compile: javac -d . ZooKeeperAclDedupTest.java
 * Run:     java unit.ZooKeeperAclDedupTest
 *
 * ACL is modelled as a plain String (scheme:id:perms) — sufficient to demonstrate
 * the algorithmic complexity without the Thrift dependency.
 */
public class ZooKeeperAclDedupTest {

    static long slowOps;
    static long fastOps;

    /**
     * Slow: mirrors PrepRequestProcessor.removeDuplicates() — ArrayList accumulator.
     * retval.contains() scans the growing list for each of n ACLs → O(n²).
     */
    static List<String> slowRemoveDuplicates(List<String> acls) {
        slowOps = 0;
        List<String> retval = new ArrayList<>(acls.size());
        for (String acl : acls) {
            slowOps++;                          // outer loop entry
            boolean found = false;
            for (String existing : retval) {    // ArrayList.contains() scan — O(n)
                slowOps++;
                if (existing.equals(acl)) { found = true; break; }
            }
            if (!found) retval.add(acl);
        }
        return retval;
    }

    /**
     * Fast: patched — LinkedHashSet for O(1) contains/add, preserves order.
     */
    static List<String> fastRemoveDuplicates(List<String> acls) {
        fastOps = 0;
        LinkedHashSet<String> seen = new LinkedHashSet<>(acls.size() * 2);
        for (String acl : acls) {
            fastOps++;   // O(1) hash add
            seen.add(acl);
        }
        return new ArrayList<>(seen);
    }

    static void run(int n, int dupFraction, int expectedNx) {
        // Build ACL list: n unique entries + n*dupFraction duplicates interleaved
        List<String> acls = new ArrayList<>();
        for (int i = 0; i < n; i++) acls.add("world:anyone:" + i);
        for (int d = 0; d < dupFraction; d++) {
            for (int i = 0; i < n; i++) acls.add("world:anyone:" + i);
        }

        List<String> slowResult = slowRemoveDuplicates(acls);
        List<String> fastResult = fastRemoveDuplicates(acls);

        boolean resultsMatch = slowResult.equals(fastResult);
        boolean quadraticWorse = slowOps > fastOps * expectedNx;

        System.out.printf("n=%-4d dups=%-2dx  slow=%7d  fast=%5d  ratio=%5.1fx  match=%b  PASS=%b%n",
            n, dupFraction, slowOps, fastOps, (double) slowOps / fastOps, resultsMatch,
            resultsMatch && quadraticWorse);

        if (!resultsMatch || !quadraticWorse) {
            throw new AssertionError(
                "FAIL n=" + n + " resultsMatch=" + resultsMatch +
                " slowOps=" + slowOps + " fastOps=" + fastOps +
                " needed ratio>" + expectedNx);
        }
    }

    public static void main(String[] args) {
        System.out.println("=== zookeeper-0001: ACL removeDuplicates O(n^2) vs O(n) ===");
        run(50,  2, 5);
        run(200, 2, 15);
        run(500, 2, 30);
        System.out.println("3/3 PASS");
    }
}