import java.util.*;

/**
 * CWE-407 simulation: TiDB updateDroppingPartitionInfo O(P*D) partition name lookup.
 *
 * tidb-0001: slices.Contains(partLowerNames, oldDefs[i].Name.L) inside
 *            for i := range oldDefs => O(P*D).
 *            Fix: map[string]struct{} for O(1) lookup => O(P+D).
 */
public class TidbTest {

    // --- Defective: linear scan per partition definition ---
    static List<String> updateDroppingPartitionDefective(
            List<String> oldDefNames, List<String> partLowerNames) {
        List<String> newDefs = new ArrayList<>();
        List<String> droppingDefs = new ArrayList<>();
        // "consider using a map to probe partLowerNames if too many partLowerNames"
        for (String defName : oldDefNames) {
            boolean found = partLowerNames.contains(defName); // O(D) per call
            if (found) {
                droppingDefs.add(defName);
            } else {
                newDefs.add(defName);
            }
        }
        return newDefs;
    }

    // --- Fixed: hash set for O(1) lookup ---
    static List<String> updateDroppingPartitionFixed(
            List<String> oldDefNames, List<String> partLowerNames) {
        Set<String> nameSet = new HashSet<>(partLowerNames); // O(D)
        List<String> newDefs = new ArrayList<>();
        List<String> droppingDefs = new ArrayList<>();
        for (String defName : oldDefNames) {
            if (nameSet.contains(defName)) { // O(1)
                droppingDefs.add(defName);
            } else {
                newDefs.add(defName);
            }
        }
        return newDefs;
    }

    // --- Correctness ---
    static void testCorrectness() {
        List<String> oldDefs = Arrays.asList("p0", "p1", "p2", "p3", "p4");
        List<String> dropping = Arrays.asList("p1", "p3");

        List<String> resultDefective = updateDroppingPartitionDefective(oldDefs, dropping);
        List<String> resultFixed = updateDroppingPartitionFixed(oldDefs, dropping);

        assert resultDefective.equals(Arrays.asList("p0", "p2", "p4"))
            : "Defective correctness failed: " + resultDefective;
        assert resultFixed.equals(Arrays.asList("p0", "p2", "p4"))
            : "Fixed correctness failed: " + resultFixed;
        assert resultDefective.equals(resultFixed)
            : "Results differ";
        System.out.println("PASS correctness");
    }

    // --- Performance ---
    static void testPerformance() {
        int P = 8192;  // max partitions in TiDB
        int D = 500;   // dropping half

        List<String> oldDefs = new ArrayList<>(P);
        for (int i = 0; i < P; i++) {
            oldDefs.add("partition_" + i);
        }
        List<String> dropping = new ArrayList<>(D);
        for (int i = 0; i < D; i++) {
            dropping.add("partition_" + (i * (P / D)));
        }

        // Warm up
        for (int w = 0; w < 3; w++) {
            updateDroppingPartitionDefective(oldDefs, dropping);
            updateDroppingPartitionFixed(oldDefs, dropping);
        }

        int iterations = 200;

        long startDefective = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            updateDroppingPartitionDefective(oldDefs, dropping);
        }
        long defectiveNs = System.nanoTime() - startDefective;

        long startFixed = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            updateDroppingPartitionFixed(oldDefs, dropping);
        }
        long fixedNs = System.nanoTime() - startFixed;

        double ratio = (double) defectiveNs / fixedNs;

        System.out.printf("tidb-0001 updateDroppingPartitionInfo P=%d D=%d%n", P, D);
        System.out.printf("  defective: %,d ns%n", defectiveNs);
        System.out.printf("  fixed:     %,d ns%n", fixedNs);
        System.out.printf("  ratio:     %.1fx%n", ratio);

        assert ratio > 5.0
            : "Expected significant speedup, got only " + ratio + "x";
        System.out.println("PASS performance (ratio=" + String.format("%.1f", ratio) + "x)");
    }

    public static void main(String[] args) {
        testCorrectness();
        testPerformance();
        System.out.println("ALL TESTS PASSED");
    }
}