package unit;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Objects;

/**
 * CWE-407 unit test: elasticsearch-004
 * IndexGraveyard.containsIndex — List<Tombstone> linear scan called per-index
 * inside DanglingIndicesState loop → O(I × T).
 *
 * Slow path: for (Tombstone t : tombstones) { if t.equals(index) ... } — O(T) per call.
 * Fast path: HashSet<Index>.contains() — O(1) per call.
 *
 * Compile: javac -d . IndexGraveyardDanglingContains.java
 * Run:     java -ea unit.IndexGraveyardDanglingContains
 */
public class IndexGraveyardDanglingContains {

    /** Minimal stand-in for an Index (name + uuid). */
    static final class Index {
        final String name;
        final String uuid;

        Index(String name, String uuid) {
            this.name = name;
            this.uuid = uuid;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Index)) return false;
            Index other = (Index) o;
            return name.equals(other.name) && uuid.equals(other.uuid);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, uuid);
        }
    }

    /** Minimal stand-in for a Tombstone. */
    static final class Tombstone {
        final Index index;
        Tombstone(Index index) { this.index = index; }
        Index getIndex() { return index; }
    }

    // ---- Slow path: List-based linear scan per call (O(T)) ----

    static boolean slowContainsIndex(List<Tombstone> tombstones, Index index) {
        for (Tombstone tombstone : tombstones) {
            if (tombstone.getIndex().equals(index)) {
                return true;
            }
        }
        return false;
    }

    /** Simulates DanglingIndicesState with slow O(I×T) behaviour. */
    static long slowFindDanglingIndices(List<Index> diskIndices, List<Tombstone> tombstones) {
        long ops = 0;
        List<Index> dangling = new ArrayList<>();
        for (Index index : diskIndices) {
            for (Tombstone t : tombstones) {   // counts each tombstone comparison
                ops++;
                if (t.getIndex().equals(index)) break;
            }
            if (!slowContainsIndex(tombstones, index)) {
                dangling.add(index);
            }
        }
        return ops;
    }

    // ---- Fast path: HashSet O(1) membership test ----

    static long fastFindDanglingIndices(List<Index> diskIndices, List<Tombstone> tombstones) {
        long ops = 0;
        // Build set once: O(T)
        Set<Index> graveyardSet = new HashSet<>(tombstones.size() * 2);
        for (Tombstone t : tombstones) {
            graveyardSet.add(t.getIndex());
            ops++;
        }
        // Check each disk index: O(1) per check
        List<Index> dangling = new ArrayList<>();
        for (Index index : diskIndices) {
            ops++;   // O(1) hash lookup
            if (!graveyardSet.contains(index)) {
                dangling.add(index);
            }
        }
        return ops;
    }

    // ---- Correctness check ----

    static List<Index> slowResult(List<Index> diskIndices, List<Tombstone> tombstones) {
        List<Index> dangling = new ArrayList<>();
        for (Index index : diskIndices) {
            if (!slowContainsIndex(tombstones, index)) {
                dangling.add(index);
            }
        }
        return dangling;
    }

    static List<Index> fastResult(List<Index> diskIndices, List<Tombstone> tombstones) {
        Set<Index> graveyardSet = new HashSet<>();
        for (Tombstone t : tombstones) graveyardSet.add(t.getIndex());
        List<Index> dangling = new ArrayList<>();
        for (Index index : diskIndices) {
            if (!graveyardSet.contains(index)) dangling.add(index);
        }
        return dangling;
    }

    public static void main(String[] args) {
        int passed = 0;

        // ---- Test 1: correctness at small scale ----
        {
            List<Tombstone> tombstones = new ArrayList<>();
            List<Index> diskIndices = new ArrayList<>();
            // 10 tombstones, 20 disk indices — 5 overlap
            for (int i = 0; i < 10; i++) {
                tombstones.add(new Tombstone(new Index("idx-" + i, "uuid-" + i)));
            }
            for (int i = 0; i < 20; i++) {
                diskIndices.add(new Index("idx-" + i, "uuid-" + i));
            }
            List<Index> slow = slowResult(diskIndices, tombstones);
            List<Index> fast = fastResult(diskIndices, tombstones);
            assert slow.size() == fast.size()
                : "FAIL: slow=" + slow.size() + " fast=" + fast.size();
            assert slow.containsAll(fast) && fast.containsAll(slow)
                : "FAIL: result mismatch";
            System.out.println("PASS test1: correctness (small scale) — " + fast.size() + " dangling");
            passed++;
        }

        // ---- Test 2: correctness — all tombstoned ----
        {
            List<Tombstone> tombstones = new ArrayList<>();
            List<Index> diskIndices = new ArrayList<>();
            for (int i = 0; i < 50; i++) {
                tombstones.add(new Tombstone(new Index("idx-" + i, "uuid-" + i)));
                diskIndices.add(new Index("idx-" + i, "uuid-" + i));
            }
            List<Index> slow = slowResult(diskIndices, tombstones);
            List<Index> fast = fastResult(diskIndices, tombstones);
            assert slow.size() == 0 : "FAIL: expected 0 dangling";
            assert fast.size() == 0 : "FAIL: expected 0 dangling (fast)";
            System.out.println("PASS test2: correctness (all tombstoned) — " + fast.size() + " dangling");
            passed++;
        }

        // ---- Test 3: operation count ratio ----
        {
            int I = 500;  // dangling index files on disk
            int T = 500;  // tombstones (max default)
            List<Tombstone> tombstones = new ArrayList<>();
            List<Index> diskIndices = new ArrayList<>();
            // None overlap → worst case for slow (full scan every time)
            for (int i = 0; i < T; i++) {
                tombstones.add(new Tombstone(new Index("tomb-" + i, "uuid-t" + i)));
            }
            for (int i = 0; i < I; i++) {
                diskIndices.add(new Index("disk-" + i, "uuid-d" + i));
            }

            long slowOps = slowFindDanglingIndices(diskIndices, tombstones);
            long fastOps = fastFindDanglingIndices(diskIndices, tombstones);
            double ratio = (double) slowOps / fastOps;

            System.out.printf("PASS test3: I=%d T=%d  slow=%d ops  fast=%d ops  ratio=%.1fx%n",
                I, T, slowOps, fastOps, ratio);
            assert ratio >= 10.0
                : "FAIL: ratio " + ratio + " < 10x at I=" + I + " T=" + T;
            passed++;
        }

        // ---- Test 4: timing benchmark ----
        {
            int I = 2000;
            int T = 500;
            List<Tombstone> tombstones = new ArrayList<>();
            List<Index> diskIndices = new ArrayList<>();
            for (int i = 0; i < T; i++) {
                tombstones.add(new Tombstone(new Index("tomb-" + i, "uuid-t" + i)));
            }
            for (int i = 0; i < I; i++) {
                diskIndices.add(new Index("disk-" + i, "uuid-d" + i));
            }

            int reps = 200;

            long t0 = System.nanoTime();
            for (int r = 0; r < reps; r++) slowResult(diskIndices, tombstones);
            long slowNs = System.nanoTime() - t0;

            long t1 = System.nanoTime();
            for (int r = 0; r < reps; r++) fastResult(diskIndices, tombstones);
            long fastNs = System.nanoTime() - t1;

            double ratio = (double) slowNs / fastNs;
            System.out.printf("PASS test4: timing I=%d T=%d  slow=%.1fms fast=%.1fms ratio=%.1fx%n",
                I, T,
                slowNs / 1e6 / reps,
                fastNs / 1e6 / reps,
                ratio);
            assert ratio >= 10.0
                : "FAIL: timing ratio " + ratio + " < 10x";
            passed++;
        }

        System.out.println(passed + "/" + passed + " PASS");
    }
}