import java.util.*;

/**
 * Java simulation unit tests for Grafana CWE-407 defects.
 * Simulates the O(N^2) slice membership patterns found in Grafana's
 * folder/dashboard permission dedup code.
 *
 * grafana-0001: getDashboardsSharedWithUser dashboard UID dedup O(P^2)
 * grafana-0002: folder UID dedup via slices.Contains O(P^2) — 4 sites
 * grafana-0003: deduplicateAvailableFolders ContainsFunc O(F*A)
 * grafana-0004: checkFolderPermissionEscalation slices.Contains O(A*U*S)
 */
public class GrafanaTest {

    // ---------------------------------------------------------------
    // grafana-0001: dashboard UID dedup O(P^2) vs O(P)
    // ---------------------------------------------------------------

    /** BEFORE: slices.Contains on growing list — O(P^2) */
    static List<String> dedupDashboardUidsBefore(List<String> permissions, String prefix) {
        List<String> dashboardUids = new ArrayList<>();
        for (String p : permissions) {
            if (p.startsWith(prefix)) {
                String uid = p.substring(prefix.length());
                if (!dashboardUids.contains(uid)) {
                    dashboardUids.add(uid);
                }
            }
        }
        return dashboardUids;
    }

    /** AFTER: map for O(1) dedup — O(P) */
    static List<String> dedupDashboardUidsAfter(List<String> permissions, String prefix) {
        Set<String> seen = new HashSet<>(permissions.size());
        List<String> dashboardUids = new ArrayList<>(permissions.size());
        for (String p : permissions) {
            if (p.startsWith(prefix)) {
                String uid = p.substring(prefix.length());
                if (seen.add(uid)) {
                    dashboardUids.add(uid);
                }
            }
        }
        return dashboardUids;
    }

    static void testGrafana0001() {
        String prefix = "dashboards:uid:";
        int N = 500;
        List<String> permissions = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            permissions.add(prefix + "dash-" + (i % (N / 2))); // 50% duplicates
        }

        // Warm up
        for (int i = 0; i < 3; i++) {
            dedupDashboardUidsBefore(permissions, prefix);
            dedupDashboardUidsAfter(permissions, prefix);
        }

        long t0 = System.nanoTime();
        int ITER = 200;
        for (int i = 0; i < ITER; i++) dedupDashboardUidsBefore(permissions, prefix);
        long befNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) dedupDashboardUidsAfter(permissions, prefix);
        long aftNs = System.nanoTime() - t0;

        // Correctness
        List<String> a = dedupDashboardUidsBefore(permissions, prefix);
        List<String> b = dedupDashboardUidsAfter(permissions, prefix);
        assert a.equals(b) : "grafana-0001 correctness: results differ";

        double ratio = (double) befNs / aftNs;
        System.out.printf("grafana-0001 dashboard-uid-dedup   BEFORE=%,dns  AFTER=%,dns  ratio=%.1fx  %s%n",
                befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
        assert ratio > 2.0 : "grafana-0001: expected >2x speedup, got " + ratio;
    }

    // ---------------------------------------------------------------
    // grafana-0002: folder UID dedup O(P^2) vs O(P)
    // ---------------------------------------------------------------

    /** BEFORE: slices.Contains on growing list */
    static List<String> dedupFolderUidsBefore(List<String> permissions, String prefix) {
        List<String> folderUids = new ArrayList<>();
        for (String p : permissions) {
            if (p.startsWith(prefix)) {
                String uid = p.substring(prefix.length());
                if (!folderUids.contains(uid)) {
                    folderUids.add(uid);
                }
            }
        }
        return folderUids;
    }

    /** AFTER: map-based dedup */
    static List<String> dedupFolderUidsAfter(List<String> permissions, String prefix) {
        Set<String> seen = new HashSet<>(permissions.size());
        List<String> folderUids = new ArrayList<>(permissions.size());
        for (String p : permissions) {
            if (p.startsWith(prefix)) {
                String uid = p.substring(prefix.length());
                if (seen.add(uid)) {
                    folderUids.add(uid);
                }
            }
        }
        return folderUids;
    }

    static void testGrafana0002() {
        String prefix = "folders:uid:";
        int N = 500;
        List<String> permissions = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            permissions.add(prefix + "folder-" + (i % (N / 2)));
        }

        // Warm up
        for (int i = 0; i < 3; i++) {
            dedupFolderUidsBefore(permissions, prefix);
            dedupFolderUidsAfter(permissions, prefix);
        }

        long t0 = System.nanoTime();
        int ITER = 200;
        for (int i = 0; i < ITER; i++) dedupFolderUidsBefore(permissions, prefix);
        long befNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) dedupFolderUidsAfter(permissions, prefix);
        long aftNs = System.nanoTime() - t0;

        List<String> a = dedupFolderUidsBefore(permissions, prefix);
        List<String> b = dedupFolderUidsAfter(permissions, prefix);
        assert a.equals(b) : "grafana-0002 correctness: results differ";

        double ratio = (double) befNs / aftNs;
        System.out.printf("grafana-0002 folder-uid-dedup       BEFORE=%,dns  AFTER=%,dns  ratio=%.1fx  %s%n",
                befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
        assert ratio > 2.0 : "grafana-0002: expected >2x speedup, got " + ratio;
    }

    // ---------------------------------------------------------------
    // grafana-0003: deduplicateAvailableFolders ContainsFunc O(F*A)
    // ---------------------------------------------------------------

    static class FolderRef {
        String uid;
        String parentUID;
        String fullpathUIDs; // slash-separated

        FolderRef(String uid, String parentUID, String fullpathUIDs) {
            this.uid = uid;
            this.parentUID = parentUID;
            this.fullpathUIDs = fullpathUIDs;
        }
    }

    /** BEFORE: linear scan of allFolders for each folder */
    static List<FolderRef> deduplicateBefore(List<FolderRef> folders, List<FolderRef> allFolders) {
        List<FolderRef> result = new ArrayList<>();
        for (FolderRef f : folders) {
            boolean isSubfolder = false;
            // Check if parent is in allFolders — O(A) scan
            for (FolderRef af : allFolders) {
                if (f.parentUID.equals(af.uid)) {
                    isSubfolder = true;
                    break;
                }
            }
            if (!isSubfolder) {
                String[] pathUIDs = f.fullpathUIDs.split("/");
                for (String puid : pathUIDs) {
                    if (!puid.isEmpty() && !puid.equals(f.uid)) {
                        // O(A) scan per parentUID
                        for (FolderRef af : allFolders) {
                            if (af.uid.equals(puid)) {
                                isSubfolder = true;
                                break;
                            }
                        }
                        if (isSubfolder) break;
                    }
                }
            }
            if (!isSubfolder) result.add(f);
        }
        return result;
    }

    /** AFTER: map-based O(1) lookup */
    static List<FolderRef> deduplicateAfter(List<FolderRef> folders, List<FolderRef> allFolders) {
        Set<String> allUIDs = new HashSet<>(allFolders.size());
        for (FolderRef af : allFolders) allUIDs.add(af.uid);

        List<FolderRef> result = new ArrayList<>();
        for (FolderRef f : folders) {
            boolean isSubfolder = allUIDs.contains(f.parentUID);
            if (!isSubfolder) {
                String[] pathUIDs = f.fullpathUIDs.split("/");
                for (String puid : pathUIDs) {
                    if (!puid.isEmpty() && !puid.equals(f.uid)) {
                        if (allUIDs.contains(puid)) {
                            isSubfolder = true;
                            break;
                        }
                    }
                }
            }
            if (!isSubfolder) result.add(f);
        }
        return result;
    }

    static void testGrafana0003() {
        int F = 500, A = 500;
        List<FolderRef> allFolders = new ArrayList<>(A);
        for (int i = 0; i < A; i++) {
            allFolders.add(new FolderRef("af-" + i, "root", "root/af-" + i));
        }
        // Folders to check — parents NOT in allFolders (worst case: full scan each time)
        List<FolderRef> folders = new ArrayList<>(F);
        for (int i = 0; i < F; i++) {
            folders.add(new FolderRef("f-" + i, "nonexistent-" + i,
                    "root/nonexistent-" + i + "/f-" + i));
        }

        // Warm up
        for (int i = 0; i < 3; i++) {
            deduplicateBefore(folders, allFolders);
            deduplicateAfter(folders, allFolders);
        }

        long t0 = System.nanoTime();
        int ITER = 100;
        for (int i = 0; i < ITER; i++) deduplicateBefore(folders, allFolders);
        long befNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) deduplicateAfter(folders, allFolders);
        long aftNs = System.nanoTime() - t0;

        List<FolderRef> a = deduplicateBefore(folders, allFolders);
        List<FolderRef> b = deduplicateAfter(folders, allFolders);
        assert a.size() == b.size() : "grafana-0003 correctness: sizes differ";

        double ratio = (double) befNs / aftNs;
        System.out.printf("grafana-0003 folder-dedup-contains  BEFORE=%,dns  AFTER=%,dns  ratio=%.1fx  %s%n",
                befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
        assert ratio > 2.0 : "grafana-0003: expected >2x speedup, got " + ratio;
    }

    // ---------------------------------------------------------------
    public static void main(String[] args) {
        testGrafana0001();
        testGrafana0002();
        testGrafana0003();
        System.out.println("\nAll 3 Grafana CWE-407 tests PASSED.");
    }
}