java-topology/defects/thunderbird-0002/test/ThunderbirdCopyServiceTest.java

import java.util.*;

/**
 * Unit test for thunderbird-0002: nsMsgCopyService::DoNextCopy() O(N^2)
 *
 * Simulates the copy request scheduling pattern where ContainsObject()
 * is called inside a loop to check if a destination folder is already active.
 *
 * Defective: O(N^2) - ContainsObject linear scan per request
 * Fixed: O(N) - HashSet for active target tracking
 */
public class ThunderbirdCopyServiceTest {

    static class CopyRequest {
        String dstFolder;
        String srcMsg;
        CopyRequest(String dst, String src) {
            this.dstFolder = dst;
            this.srcMsg = src;
        }
    }

    // --- Defective: O(N^2) active target check via list contains ---
    static List<CopyRequest> doNextCopyDefective(List<CopyRequest> requests) {
        List<String> activeTargets = new ArrayList<>();
        List<CopyRequest> scheduled = new ArrayList<>();
        for (CopyRequest req : requests) {
            if (activeTargets.contains(req.dstFolder)) {
                continue; // skip - folder already active
            }
            scheduled.add(req);
            activeTargets.add(req.dstFolder);
        }
        return scheduled;
    }

    // --- Fixed: O(N) active target check via HashSet ---
    static List<CopyRequest> doNextCopyFixed(List<CopyRequest> requests) {
        Set<String> activeTargets = new HashSet<>();
        List<CopyRequest> scheduled = new ArrayList<>();
        for (CopyRequest req : requests) {
            if (activeTargets.contains(req.dstFolder)) {
                continue;
            }
            scheduled.add(req);
            activeTargets.add(req.dstFolder);
        }
        return scheduled;
    }

    public static void main(String[] args) {
        System.out.println("=== thunderbird-0002: nsMsgCopyService DoNextCopy O(N^2) ===\n");

        // Correctness
        List<CopyRequest> sample = Arrays.asList(
            new CopyRequest("Inbox", "msg1"),
            new CopyRequest("Trash", "msg2"),
            new CopyRequest("Inbox", "msg3"),  // should be skipped
            new CopyRequest("Sent", "msg4"),
            new CopyRequest("Trash", "msg5")   // should be skipped
        );
        List<CopyRequest> defResult = doNextCopyDefective(sample);
        List<CopyRequest> fixResult = doNextCopyFixed(sample);
        assert defResult.size() == 3 : "Should schedule 3 unique folders";
        assert fixResult.size() == 3 : "Should schedule 3 unique folders";
        System.out.println("PASS correctness: both schedule " + defResult.size() + " requests");

        // Benchmark
        int[] sizes = {100, 500, 1000, 5000};
        for (int N : sizes) {
            Random rng = new Random(42);
            List<CopyRequest> requests = new ArrayList<>();
            // ~50 unique destination folders, many duplicates
            int numFolders = Math.max(10, N / 10);
            for (int i = 0; i < N; i++) {
                requests.add(new CopyRequest(
                    "folder" + rng.nextInt(numFolders),
                    "msg" + i));
            }

            // Warmup
            for (int w = 0; w < 5; w++) {
                doNextCopyDefective(requests);
                doNextCopyFixed(requests);
            }

            int iters = Math.max(1, 100000 / N);
            long t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) doNextCopyDefective(requests);
            long defTime = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) doNextCopyFixed(requests);
            long fixTime = System.nanoTime() - t0;

            double ratio = (double) defTime / Math.max(1, fixTime);
            String status = ratio >= 2.0 ? "PASS" : "FAIL";
            System.out.printf("%s N=%5d  defective=%8dns  fixed=%8dns  ratio=%.1fx%n",
                    status, N, defTime / iters, fixTime / iters, ratio);
        }

        System.out.println("\nAll tests passed.");
    }
}