"""
scribus-0004: file saver names.contains O(N²) style filter on save

Simulates the defect in scribus{150,170,171}format_save.cpp where
  QList<QString> names = lists.charStyleNames();
  for style in styleList:
      if names.contains(style.name()):  // O(N) per iteration → O(N²) total
is replaced by:
  for style in styleList:
      if lists.charStyles().contains(style.name()):  // O(log N) via QMap
"""
import time
import random

PYTHONUNBUFFERED = 1  # noqa: ensure unbuffered output reminder

# ---------------------------------------------------------------------------
# Defective: QList<QString>::contains inside for-loop → O(N²)
# Simulates: charStyleNames() returns QList (from QMap::keys()), then
#            we call list.contains() for each style in styleList.
# ---------------------------------------------------------------------------

def write_styles_defective(style_names_list, used_names_set):
    """
    style_names_list: all style names in sorted order (simulates styleList)
    used_names_set: names that are 'used' (simulates ResourceCollection)

    Defective: convert to list then do O(N) contains per iteration.
    """
    ops = 0
    # Simulate QList<QString> names = lists.charStyleNames()
    # (QMap::keys() returns QList — O(K) copy)
    names_as_list = list(used_names_set)  # simulates QList<QString>

    result = []
    for style_name in style_names_list:
        # QList::contains() — O(K) linear scan
        for n in names_as_list:
            ops += 1
            if n == style_name:
                result.append(style_name)
                break
    return ops, result


# ---------------------------------------------------------------------------
# Fixed: QMap<QString,QString>::contains → O(log N)
# Simulates: lists.charStyles().contains(charStyle.name())
# ---------------------------------------------------------------------------

def write_styles_fixed(style_names_list, used_names_set):
    """
    Fixed: use the map directly for O(log N) lookup per style.
    In Python we model QMap::contains as set membership (O(1)), which
    matches the O(log N) QMap::contains behavior asymptotically vs O(N).
    """
    ops = 0
    result = []
    for style_name in style_names_list:
        # QMap::contains — O(log N) (simulated as O(1) hash set)
        ops += 1
        if style_name in used_names_set:
            result.append(style_name)
    return ops, result


# ---------------------------------------------------------------------------
# Benchmark
# ---------------------------------------------------------------------------

def benchmark(N, label):
    """
    N: number of styles in the document
    Half of all styles are 'used' (worst-case: used_names is also size N/2).
    """
    all_styles = [f"style_{i}" for i in range(N)]
    used_names = set(all_styles[:N // 2])  # first half are used

    # Defective: O(N²) — list.contains inside loop
    t0 = time.perf_counter()
    defect_ops, defect_result = write_styles_defective(all_styles, used_names)
    t1 = time.perf_counter()
    defect_time = t1 - t0

    # Fixed: O(N log N) → O(N) — map/set contains per style
    t2 = time.perf_counter()
    fixed_ops, fixed_result = write_styles_fixed(all_styles, used_names)
    t3 = time.perf_counter()
    fixed_time = t3 - t2

    op_ratio = defect_ops / max(fixed_ops, 1)
    time_ratio = defect_time / max(fixed_time, 1e-9)

    # Verify correctness — both should produce same output
    assert sorted(defect_result) == sorted(fixed_result), (
        f"Result mismatch at N={N}: defect={len(defect_result)} fixed={len(fixed_result)}"
    )

    print(
        f"  N={N:5d}: defect_ops={defect_ops:8d} fixed_ops={fixed_ops:6d} "
        f"op_ratio={op_ratio:7.1f}x  "
        f"defect_t={defect_time*1000:.1f}ms fixed_t={fixed_time*1000:.1f}ms "
        f"time_ratio={time_ratio:.1f}x  [{label}]"
    )
    return op_ratio


def main():
    print("scribus-0004: file saver names.contains O(N²) — benchmark")
    print("=" * 75)

    ratio_100 = benchmark(100, "N=100")
    ratio_500 = benchmark(500, "N=500")
    ratio_1000 = benchmark(1000, "N=1000 (professional template)")

    print()
    print(f"  op_ratio at N=100:  {ratio_100:.1f}x")
    print(f"  op_ratio at N=500:  {ratio_500:.1f}x")
    print(f"  op_ratio at N=1000: {ratio_1000:.1f}x")

    # Assert meaningful speedup — O(N²) vs O(N) should show >10x at N=500
    assert ratio_100 > 3, f"Expected >3x at N=100, got {ratio_100:.1f}x"
    assert ratio_500 > 10, f"Expected >10x at N=500, got {ratio_500:.1f}x"
    assert ratio_1000 > 20, f"Expected >20x at N=1000, got {ratio_1000:.1f}x"

    print()
    print("PASS — scribus-0004 confirmed: O(N²) file-save style filter speedup ✓")


if __name__ == "__main__":
    main()