import java.util.*;

/**
 * CWE-407 unit tests for Redmine defects.
 *
 * redmine-0001: issue.rb blocks?() BFS uses Array for 'all' visited set — O(V^2) subtraction
 * redmine-0002: issue.rb would_reschedule?() same BFS Array pattern — O(V^2)
 * redmine-0003: user.rb project_ids_by_role project_ids.include? in members.each — O(M*P)
 */
public class RedmineCWE407Test {

    // ---- redmine-0001: blocks? BFS with Array visited set ----

    /** Unpatched: Array 'all' grows, Array subtraction O(C*A) per BFS layer */
    static boolean blocksBfsUnpatched(int startId, int targetId, Map<Integer, List<Integer>> graph) {
        List<Integer> all = new ArrayList<>();
        all.add(startId);
        List<Integer> last = new ArrayList<>();
        last.add(startId);

        while (!last.isEmpty()) {
            Set<Integer> currentSet = new LinkedHashSet<>();
            for (int node : last) {
                List<Integer> neighbors = graph.getOrDefault(node, Collections.emptyList());
                currentSet.addAll(neighbors);
            }
            List<Integer> current = new ArrayList<>(currentSet);

            // Array subtraction: current -= last, current -= all  (both O(N) per element)
            current.removeAll(last);
            Iterator<Integer> it = current.iterator();
            while (it.hasNext()) {
                if (all.contains(it.next())) {  // O(A) per element
                    it.remove();
                }
            }

            if (current.contains(targetId)) return true;

            last = current;
            all.addAll(last);
        }
        return false;
    }

    /** Patched: Set 'all' for O(1) membership — O(V+E) total */
    static boolean blocksBfsPatched(int startId, int targetId, Map<Integer, List<Integer>> graph) {
        Set<Integer> all = new HashSet<>();
        all.add(startId);
        List<Integer> last = new ArrayList<>();
        last.add(startId);

        while (!last.isEmpty()) {
            Set<Integer> currentSet = new LinkedHashSet<>();
            for (int node : last) {
                List<Integer> neighbors = graph.getOrDefault(node, Collections.emptyList());
                currentSet.addAll(neighbors);
            }
            List<Integer> current = new ArrayList<>(currentSet);

            // Set-based removal: O(1) per element
            current.removeIf(all::contains);

            if (current.contains(targetId)) return true;

            last = current;
            all.addAll(last);
        }
        return false;
    }

    // ---- redmine-0003: user project_ids membership ----

    /** Unpatched: project_ids.include? in members.each — O(M*P) */
    static Map<Integer, List<Integer>> projectIdsByRoleUnpatched(
            int userId, List<int[]> members, List<Integer> projectIds) {
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for (int[] member : members) {
            int memberUserId = member[0];
            int roleId = member[1];
            int projectId = member[2];

            // Skip builtin group roles if user is a member of this project
            if (memberUserId != userId && projectIds.contains(projectId)) {  // O(P) per member
                continue;
            }
            hash.computeIfAbsent(roleId, k -> new ArrayList<>()).add(projectId);
        }
        return hash;
    }

    /** Patched: project_ids.to_set for O(1) lookup — O(M+P) */
    static Map<Integer, List<Integer>> projectIdsByRolePatched(
            int userId, List<int[]> members, List<Integer> projectIds) {
        Set<Integer> projectIdsSet = new HashSet<>(projectIds);  // O(P) once
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for (int[] member : members) {
            int memberUserId = member[0];
            int roleId = member[1];
            int projectId = member[2];

            if (memberUserId != userId && projectIdsSet.contains(projectId)) {  // O(1) per member
                continue;
            }
            hash.computeIfAbsent(roleId, k -> new ArrayList<>()).add(projectId);
        }
        return hash;
    }

    // ---- Test harness ----

    static void testRedmine0001and0002() {
        System.out.println("=== redmine-0001/0002: issue BFS blocks?/would_reschedule? ===");
        // Build a chain graph: 0 -> 1 -> 2 -> ... -> V-1
        int V = 20000;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < V - 1; i++) {
            graph.put(i, List.of(i + 1));
        }
        int targetId = V - 1;

        // Warmup
        blocksBfsPatched(0, targetId, graph);

        long t0 = System.nanoTime();
        boolean r1 = blocksBfsUnpatched(0, targetId, graph);
        long unpatched = System.nanoTime() - t0;

        t0 = System.nanoTime();
        boolean r2 = blocksBfsPatched(0, targetId, graph);
        long patched = System.nanoTime() - t0;

        assert r1 == r2 : "Result mismatch";
        assert r1 == true : "Expected true";

        double ratio = (double) unpatched / patched;
        System.out.printf("  V=%d  unpatched=%dms  patched=%dms  ratio=%.1fx%n",
                V, unpatched / 1_000_000, patched / 1_000_000, ratio);
        assert ratio > 3.0 : "Expected >3x ratio, got " + ratio;
        System.out.println("  PASS (covers both blocks? and would_reschedule?)");
    }

    static void testRedmine0003() {
        System.out.println("=== redmine-0003: user project_ids_by_role membership ===");
        int M = 50000;  // membership rows
        int P = 5000;   // user's projects
        int userId = 1;

        List<Integer> projectIds = new ArrayList<>(P);
        for (int i = 0; i < P; i++) {
            projectIds.add(i);
        }

        // Generate member rows: mix of user's own and builtin group entries
        List<int[]> members = new ArrayList<>(M);
        Random rng = new Random(42);
        for (int i = 0; i < M; i++) {
            int uid = rng.nextBoolean() ? userId : 999;  // 50% user, 50% builtin group
            int roleId = rng.nextInt(10);
            int projectId = rng.nextInt(P * 2);  // some in user's projects, some not
            members.add(new int[]{uid, roleId, projectId});
        }

        // Warmup
        projectIdsByRolePatched(userId, members, projectIds);

        long t0 = System.nanoTime();
        Map<Integer, List<Integer>> r1 = projectIdsByRoleUnpatched(userId, members, projectIds);
        long unpatched = System.nanoTime() - t0;

        t0 = System.nanoTime();
        Map<Integer, List<Integer>> r2 = projectIdsByRolePatched(userId, members, projectIds);
        long patched = System.nanoTime() - t0;

        // Verify same results
        int totalR1 = r1.values().stream().mapToInt(List::size).sum();
        int totalR2 = r2.values().stream().mapToInt(List::size).sum();
        assert totalR1 == totalR2 : "Result mismatch: " + totalR1 + " vs " + totalR2;

        double ratio = (double) unpatched / patched;
        System.out.printf("  M=%d P=%d  unpatched=%dms  patched=%dms  ratio=%.1fx%n",
                M, P, unpatched / 1_000_000, patched / 1_000_000, ratio);
        assert ratio > 3.0 : "Expected >3x ratio, got " + ratio;
        System.out.println("  PASS");
    }

    public static void main(String[] args) {
        testRedmine0001and0002();
        testRedmine0003();
        System.out.println("\nAll 3 Redmine CWE-407 tests PASSED.");
    }
}