import java.util.*;

/**
 * CWE-407 unit test for digikam-0002: GPS marker tiler image ID dedup
 * QList<qlonglong>::contains() during tile splitting: O(I^2) per tile.
 *
 * Simulates splitting a parent tile with I geotagged images into child tiles,
 * where each image insertion checks the growing child list for duplicates.
 */
public class DigikamGPSTilerDedupTest {

    // --- DEFECTIVE: List contains for dedup ---
    static List<Long> splitTileDefective(long[] imageIds, int[] childIndices, int numChildren) {
        @SuppressWarnings("unchecked")
        List<Long>[] children = new List[numChildren];
        for (int i = 0; i < numChildren; i++) {
            children[i] = new ArrayList<>();
        }

        for (int i = 0; i < imageIds.length; i++) {
            long id = imageIds[i];
            int childIdx = childIndices[i];
            List<Long> child = children[childIdx];
            if (!child.contains(id)) {  // O(N) per check
                child.add(id);
            }
        }

        // Return largest child for verification
        List<Long> largest = children[0];
        for (List<Long> c : children) {
            if (c.size() > largest.size()) largest = c;
        }
        return largest;
    }

    // --- PATCHED: Set + List for dedup ---
    static List<Long> splitTilePatched(long[] imageIds, int[] childIndices, int numChildren) {
        @SuppressWarnings("unchecked")
        List<Long>[] children = new List[numChildren];
        @SuppressWarnings("unchecked")
        Set<Long>[] childSets = new Set[numChildren];
        for (int i = 0; i < numChildren; i++) {
            children[i] = new ArrayList<>();
            childSets[i] = new HashSet<>();
        }

        for (int i = 0; i < imageIds.length; i++) {
            long id = imageIds[i];
            int childIdx = childIndices[i];
            if (!childSets[childIdx].contains(id)) {  // O(1) per check
                childSets[childIdx].add(id);
                children[childIdx].add(id);
            }
        }

        List<Long> largest = children[0];
        for (List<Long> c : children) {
            if (c.size() > largest.size()) largest = c;
        }
        return largest;
    }

    public static void main(String[] args) {
        int I = 5000;  // images in parent tile (e.g., geotagged photos in a city)
        int numChildren = 4;  // quadtree children

        Random rng = new Random(42);
        long[] imageIds = new long[I];
        int[] childIndices = new int[I];
        for (int i = 0; i < I; i++) {
            imageIds[i] = i;  // unique IDs
            childIndices[i] = rng.nextInt(numChildren);
        }
        // Add duplicates (simulating re-processing)
        long[] allIds = new long[I * 2];
        int[] allChildren = new int[I * 2];
        System.arraycopy(imageIds, 0, allIds, 0, I);
        System.arraycopy(childIndices, 0, allChildren, 0, I);
        System.arraycopy(imageIds, 0, allIds, I, I);
        System.arraycopy(childIndices, 0, allChildren, I, I);

        // Warm up
        for (int w = 0; w < 3; w++) {
            splitTileDefective(allIds, allChildren, numChildren);
            splitTilePatched(allIds, allChildren, numChildren);
        }

        // Benchmark defective
        int iterations = 50;
        long startDef = System.nanoTime();
        List<Long> resultDef = null;
        for (int i = 0; i < iterations; i++) {
            resultDef = splitTileDefective(allIds, allChildren, numChildren);
        }
        long defectiveNs = System.nanoTime() - startDef;

        // Benchmark patched
        long startPat = System.nanoTime();
        List<Long> resultPat = null;
        for (int i = 0; i < iterations; i++) {
            resultPat = splitTilePatched(allIds, allChildren, numChildren);
        }
        long patchedNs = System.nanoTime() - startPat;

        double ratio = (double) defectiveNs / patchedNs;

        System.out.println("digikam-0002: GPS marker tiler image ID dedup");
        System.out.println("I=" + I + " images per tile, " + numChildren + " children");
        System.out.println("Defective largest child: " + resultDef.size() + "  Patched: " + resultPat.size());
        System.out.printf("Defective: %.3f ms%n", defectiveNs / 1e6);
        System.out.printf("Patched:   %.3f ms%n", patchedNs / 1e6);
        System.out.printf("Ratio:     %.1fx%n", ratio);

        assert resultDef.size() == resultPat.size() : "Sizes must match!";

        boolean pass = ratio > 2.0;
        System.out.println(pass ? "PASS" : "FAIL");
        if (!pass) System.exit(1);
    }
}