package unit;

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

/**
 * hadoop-0001: PendingReconstructionBlocks.PendingBlockInfo.incrementReplicas()
 * uses ArrayList.contains() O(n) inside a for loop — O(n*m) total.
 *
 * Standalone unit test — no JUnit required.
 * Compile: javac -d . HadoopPendingReconstructionTest.java
 * Run:     java -ea unit.HadoopPendingReconstructionTest
 */
public class HadoopPendingReconstructionTest {

    static long slowOps;
    static long fastOps;

    /**
     * Simulates PendingBlockInfo.incrementReplicas() with ArrayList.
     * For each newTarget, ArrayList.contains() scans all existing targets: O(n).
     * Total for m newTargets with n existing: O(m*n).
     */
    static List<String> slowIncrementReplicas(List<String> existingTargets, List<String> newTargets) {
        slowOps = 0;
        List<String> targets = new ArrayList<>(existingTargets);
        for (String newTarget : newTargets) {
            slowOps++;  // loop entry
            for (String existing : targets) {  // ArrayList.contains() scan
                slowOps++;
                if (existing.equals(newTarget)) break;
            }
            if (!targets.contains(newTarget)) {
                targets.add(newTarget);
            }
        }
        return targets;
    }

    /**
     * Patched: LinkedHashSet.add() is O(1) amortised.
     * Total for m newTargets: O(m).
     */
    static List<String> fastIncrementReplicas(List<String> existingTargets, List<String> newTargets) {
        fastOps = 0;
        LinkedHashSet<String> targets = new LinkedHashSet<>(existingTargets);
        for (String newTarget : newTargets) {
            fastOps++;  // O(1) hash add
            targets.add(newTarget);
        }
        return new ArrayList<>(targets);
    }

    static void run(int nExisting, int mNew, int expectedRatio) {
        // Build existing targets (all unique)
        List<String> existing = new ArrayList<>();
        for (int i = 0; i < nExisting; i++) existing.add("dn-" + i);

        // newTargets: half duplicates, half new
        List<String> newTargets = new ArrayList<>();
        for (int i = 0; i < mNew / 2; i++) newTargets.add("dn-" + i);           // duplicates
        for (int i = nExisting; i < nExisting + mNew / 2; i++) newTargets.add("dn-" + i); // new

        List<String> slowResult = slowIncrementReplicas(existing, newTargets);
        List<String> fastResult = fastIncrementReplicas(existing, newTargets);

        boolean resultsMatch = slowResult.equals(fastResult);
        boolean quadraticWorse = slowOps > fastOps * expectedRatio;
        boolean pass = resultsMatch && quadraticWorse;

        System.out.printf("n=%-4d m=%-4d  slow=%6d  fast=%4d  ratio=%5.1fx  match=%b  PASS=%b%n",
            nExisting, mNew, slowOps, fastOps, (double) slowOps / fastOps, resultsMatch, pass);

        if (!pass) {
            throw new AssertionError(
                "FAIL n=" + nExisting + " m=" + mNew +
                " resultsMatch=" + resultsMatch +
                " slowOps=" + slowOps + " fastOps=" + fastOps +
                " needed ratio>" + expectedRatio);
        }
    }

    public static void main(String[] args) {
        System.out.println("=== hadoop-0001: PendingReconstructionBlocks.incrementReplicas() O(n*m) vs O(m) ===");
        run(50,  50,  5);
        run(200, 100, 20);
        run(500, 200, 50);
        System.out.println("3/3 PASS");
    }
}