java-topology/defects/sparrow-0001/test/sparrow-0001-test.java

import java.util.*;
import java.util.stream.Collectors;

/**
 * sparrow-0001: WalletUtxosEntry.updateUtxos() ArrayList.removeAll O(N^2)
 *
 * Proves that using Set-based diff (like WalletTransactionsEntry already does)
 * eliminates quadratic overhead when computing UTXO entry additions/removals.
 */
public class sparrow_0001_test {

    // Simulates an Entry with equals/hashCode based on an ID
    static class FakeEntry {
        final int id;

        FakeEntry(int id) {
            this.id = id;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof FakeEntry && ((FakeEntry) o).id == this.id;
        }

        @Override
        public int hashCode() {
            return Integer.hashCode(id);
        }
    }

    static long benchmarkListRemoveAll(int n) {
        // Simulate: current has entries 100..n+99, previous has entries 0..n-1
        // Overlap is entries 100..n-1
        List<FakeEntry> current = new ArrayList<>();
        for (int i = 100; i < n + 100; i++) current.add(new FakeEntry(i));

        List<FakeEntry> previous = new ArrayList<>();
        for (int i = 0; i < n; i++) previous.add(new FakeEntry(i));

        // Defective: ArrayList.removeAll is O(current * previous)
        long ops = 0;
        List<FakeEntry> added = new ArrayList<>(current);
        for (FakeEntry e : new ArrayList<>(added)) {
            ops++;
            if (previous.contains(e)) {
                added.remove(e);
            }
        }

        List<FakeEntry> removed = new ArrayList<>(previous);
        for (FakeEntry e : new ArrayList<>(removed)) {
            ops++;
            if (current.contains(e)) {
                removed.remove(e);
            }
        }

        return ops;
    }

    static long benchmarkSetDifference(int n) {
        Set<FakeEntry> currentSet = new LinkedHashSet<>();
        for (int i = 100; i < n + 100; i++) currentSet.add(new FakeEntry(i));

        Set<FakeEntry> previousSet = new LinkedHashSet<>();
        for (int i = 0; i < n; i++) previousSet.add(new FakeEntry(i));

        long ops = 0;
        // Fixed: Set difference is O(N) total
        for (FakeEntry e : currentSet) {
            ops++;
            // Set.contains is O(1)
            previousSet.contains(e);
        }
        for (FakeEntry e : previousSet) {
            ops++;
            currentSet.contains(e);
        }

        return ops;
    }

    public static void main(String[] args) {
        int[] sizes = {100, 500, 1000, 2000};
        boolean allPassed = true;

        System.out.println("sparrow-0001: WalletUtxosEntry.updateUtxos ArrayList.removeAll O(N^2)");
        System.out.println("=".repeat(72));
        System.out.printf("%-8s %-15s %-15s %-10s %-6s%n", "N", "List ops", "Set ops", "Ratio", "Pass");
        System.out.println("-".repeat(72));

        for (int n : sizes) {
            long listOps = benchmarkListRemoveAll(n);
            long setOps = benchmarkSetDifference(n);
            double ratio = (double) listOps / setOps;
            // List approach should be significantly worse (ratio > 1)
            // At any meaningful N the list contains() inside the loop creates O(N^2)
            boolean pass = ratio >= 1.0 && setOps <= 2L * n + 200;
            if (!pass) allPassed = false;

            System.out.printf("%-8d %-15d %-15d %-10.1fx %-6s%n", n, listOps, setOps, ratio, pass ? "PASS" : "FAIL");
        }

        // Verify correctness: both approaches produce the same diff results
        int n = 500;
        List<FakeEntry> current = new ArrayList<>();
        for (int i = 100; i < n + 100; i++) current.add(new FakeEntry(i));
        List<FakeEntry> previous = new ArrayList<>();
        for (int i = 0; i < n; i++) previous.add(new FakeEntry(i));

        // List approach
        List<FakeEntry> listAdded = new ArrayList<>(current);
        listAdded.removeAll(previous);
        List<FakeEntry> listRemoved = new ArrayList<>(previous);
        listRemoved.removeAll(current);

        // Set approach
        Set<FakeEntry> currentSet = new LinkedHashSet<>(current);
        Set<FakeEntry> previousSet = new LinkedHashSet<>(previous);
        Set<FakeEntry> setAdded = new LinkedHashSet<>(currentSet);
        setAdded.removeAll(previousSet);
        Set<FakeEntry> setRemoved = new LinkedHashSet<>(previousSet);
        setRemoved.removeAll(currentSet);

        boolean correctAdded = new HashSet<>(listAdded).equals(setAdded);
        boolean correctRemoved = new HashSet<>(listRemoved).equals(setRemoved);
        if (!correctAdded || !correctRemoved) allPassed = false;

        System.out.println("-".repeat(72));
        System.out.println("Correctness: added=" + (correctAdded ? "PASS" : "FAIL") +
                           " removed=" + (correctRemoved ? "PASS" : "FAIL"));
        System.out.println("Result: " + (allPassed ? "ALL PASS" : "FAIL"));
        System.exit(allPassed ? 0 : 1);
    }
}