java-topology/defects/thunderbird-0004/test/ThunderbirdImapFlagUidStateTest.java

import java.util.*;

/**
 * Unit test for thunderbird-0004: nsImapFlagAndUidState Contains/IndexOf O(N) on sorted array
 *
 * The UID array is maintained sorted. The file already uses binary search
 * (IndexOfFirstElementGt) in one method but uses linear Contains()/IndexOf()
 * in HasMessage() and GetMessageFlagsByUid().
 *
 * Defective: O(N) linear scan per lookup on sorted data
 * Fixed: O(log N) binary search (already available in the codebase)
 */
public class ThunderbirdImapFlagUidStateTest {

    // Sorted UID array (simulating fUids)
    private int[] sortedUids;
    private int[] flags;

    ThunderbirdImapFlagUidStateTest(int size) {
        sortedUids = new int[size];
        flags = new int[size];
        for (int i = 0; i < size; i++) {
            sortedUids[i] = (i + 1) * 3; // sorted UIDs: 3, 6, 9, ...
            flags[i] = (i % 5 == 0) ? 0x200000 : 0; // some deleted
        }
    }

    // --- Defective: O(N) linear Contains ---
    boolean hasMessageDefective(int uid) {
        for (int u : sortedUids) {
            if (u == uid) return true;
        }
        return false;
    }

    // --- Fixed: O(log N) binary search ---
    boolean hasMessageFixed(int uid) {
        int idx = Arrays.binarySearch(sortedUids, uid);
        return idx >= 0;
    }

    // --- Defective: O(N) linear IndexOf ---
    int getFlagsByUidDefective(int uid) {
        for (int i = 0; i < sortedUids.length; i++) {
            if (sortedUids[i] == uid) return flags[i];
        }
        return -1;
    }

    // --- Fixed: O(log N) binary search ---
    int getFlagsByUidFixed(int uid) {
        int idx = Arrays.binarySearch(sortedUids, uid);
        if (idx >= 0) return flags[idx];
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("=== thunderbird-0004: nsImapFlagAndUidState linear on sorted O(N) ===\n");

        // Correctness
        ThunderbirdImapFlagUidStateTest state = new ThunderbirdImapFlagUidStateTest(1000);
        // UID 15 = index 4, exists (5*3=15)
        assert state.hasMessageDefective(15) == state.hasMessageFixed(15);
        assert state.hasMessageDefective(15) == true;
        assert state.hasMessageDefective(16) == false;
        assert state.hasMessageFixed(16) == false;
        assert state.getFlagsByUidDefective(15) == state.getFlagsByUidFixed(15);
        System.out.println("PASS correctness: HasMessage and GetFlagsByUid match");

        // Benchmark HasMessage
        int[] sizes = {1000, 5000, 10000, 50000};
        System.out.println("\n--- HasMessage benchmark ---");
        for (int N : sizes) {
            state = new ThunderbirdImapFlagUidStateTest(N);
            Random rng = new Random(42);
            int[] lookups = new int[1000];
            for (int i = 0; i < lookups.length; i++) {
                lookups[i] = rng.nextInt(N * 3 + 10); // mix of hits and misses
            }

            // Warmup
            for (int w = 0; w < 3; w++) {
                for (int uid : lookups) {
                    state.hasMessageDefective(uid);
                    state.hasMessageFixed(uid);
                }
            }

            int iters = Math.max(1, 500000 / N);
            long t0 = System.nanoTime();
            for (int r = 0; r < iters; r++)
                for (int uid : lookups) state.hasMessageDefective(uid);
            long defTime = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int r = 0; r < iters; r++)
                for (int uid : lookups) state.hasMessageFixed(uid);
            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=%6d  defective=%8dns  fixed=%8dns  ratio=%.1fx%n",
                    status, N, defTime / iters, fixTime / iters, ratio);
        }

        // Benchmark GetFlagsByUid
        System.out.println("\n--- GetFlagsByUid benchmark ---");
        for (int N : sizes) {
            state = new ThunderbirdImapFlagUidStateTest(N);
            Random rng = new Random(42);
            int[] lookups = new int[1000];
            for (int i = 0; i < lookups.length; i++) {
                lookups[i] = (rng.nextInt(N) + 1) * 3; // valid UIDs
            }

            // Warmup
            for (int w = 0; w < 3; w++) {
                for (int uid : lookups) {
                    state.getFlagsByUidDefective(uid);
                    state.getFlagsByUidFixed(uid);
                }
            }

            int iters = Math.max(1, 500000 / N);
            long t0 = System.nanoTime();
            for (int r = 0; r < iters; r++)
                for (int uid : lookups) state.getFlagsByUidDefective(uid);
            long defTime = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int r = 0; r < iters; r++)
                for (int uid : lookups) state.getFlagsByUidFixed(uid);
            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=%6d  defective=%8dns  fixed=%8dns  ratio=%.1fx%n",
                    status, N, defTime / iters, fixTime / iters, ratio);
        }

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