"""
Unit test for evolution-0002: Calendar search_hit_cache dedup O(N^2) fix.

Simulates cal_searching_got_instance_cb() collecting unique time_t values
into a dedup'd cache. Measures op-count for defective (GSList linear scan)
vs fixed (GHashTable O(1)) implementations.

Asserts speedup > 3x at N=100 and N=1000.
"""
import time
import sys

PASS = True


def collect_instances_defective(instances):
    """
    Defective: linear scan for each new instance.
    Equivalent to g_slist_find_custom on a growing GSList.
    Returns (cache_list, op_count).
    """
    cache = []
    ops = 0
    for val in instances:
        # Scan entire cache for duplicate — O(k) per insert
        found = False
        for c in cache:
            ops += 1
            if c == val:
                found = True
                break
        if not found:
            cache.append(val)
    return cache, ops


def collect_instances_fixed(instances):
    """
    Fixed: O(1) hash set membership check.
    Equivalent to g_hash_table_contains before g_slist_append.
    Returns (cache_list, op_count).
    """
    cache = []
    cache_set = set()
    ops = 0
    for val in instances:
        ops += 1  # One hash lookup per insert
        if val not in cache_set:
            cache_set.add(val)
            cache.append(val)
    return cache, ops


def run_test(label, n_instances, expected_speedup):
    global PASS

    # Generate N unique timestamps (weekly recurring event instances)
    # Mix in some duplicates: same event across two calendars = same timestamp
    unique = list(range(n_instances))
    # 20% duplicates simulating overlapping calendar subscriptions
    duplicates = unique[: n_instances // 5]
    instances = unique + duplicates

    # Shuffle deterministically for reproducibility
    # (keep order as-is; order doesn't change big-O result)

    _, ops_defective = collect_instances_defective(instances)
    cache_fixed, ops_fixed = collect_instances_fixed(instances)

    ratio = ops_defective / max(ops_fixed, 1)

    status = "PASS" if ratio >= expected_speedup else "FAIL"
    if status == "FAIL":
        PASS = False

    print(
        f"[{status}] {label}: N={n_instances} | "
        f"defective={ops_defective} ops | fixed={ops_fixed} ops | ratio={ratio:.1f}x "
        f"(expected >= {expected_speedup}x)"
    )

    # Verify correctness: both produce same unique set
    cache_defective, _ = collect_instances_defective(instances)
    if sorted(cache_defective) != sorted(cache_fixed):
        print(f"  [FAIL] correctness: cache contents differ!")
        PASS = False
    else:
        print(f"  correctness: caches match ({len(cache_fixed)} unique timestamps)")


def run_wall_time_test(label, n_instances):
    """Wall-clock speedup check for large N."""
    unique = list(range(n_instances))
    duplicates = unique[: n_instances // 5]
    instances = unique + duplicates

    t0 = time.perf_counter()
    collect_instances_defective(instances)
    t1 = time.perf_counter()
    collect_instances_fixed(instances)
    t2 = time.perf_counter()

    defective_ms = (t1 - t0) * 1000
    fixed_ms = (t2 - t1) * 1000
    ratio = defective_ms / max(fixed_ms, 1e-9)
    print(
        f"  wall-clock {label}: defective={defective_ms:.2f}ms fixed={fixed_ms:.2f}ms ratio={ratio:.1f}x"
    )


if __name__ == "__main__":
    print("evolution-0002: Calendar search_hit_cache dedup O(N^2) fix")
    print("=" * 65)

    run_test("N=50   op-count", 50, 3.0)
    run_test("N=100  op-count", 100, 10.0)
    run_test("N=500  op-count", 500, 50.0)
    run_test("N=1000 op-count", 1000, 100.0)

    print()
    run_wall_time_test("N=1000 wall-clock", 1000)
    run_wall_time_test("N=5000 wall-clock", 5000)

    print()
    if PASS:
        print("ALL TESTS PASSED")
        sys.exit(0)
    else:
        print("SOME TESTS FAILED")
        sys.exit(1)