"""Five experiments on one Bloom filter. Run: `python3 demo.py`.

No randomness anywhere: the members are `key:0`..`key:99` and the probes are
`key:100`..`key:100099`, enumerated rather than sampled, and the hash is
SHA-256. The output is byte-identical on every run and on any machine.
"""

import math

from bloom_filter import (
    BloomFilter,
    bits_per_key_for,
    optimal_k,
    predicted_fp,
)

M = 1000        # bits in the array
N = 100         # keys actually inserted
PROBES = 100_000  # absent keys to test

MEMBERS = [f"key:{i}" for i in range(N)]
ABSENT = [f"key:{i}" for i in range(N, N + PROBES)]


def build(salt="A", k=None, m=M, members=MEMBERS):
    filt = BloomFilter(m=m, k=k if k is not None else optimal_k(m, len(members)),
                       salt=salt)
    for key in members:
        filt.add(key)
    return filt


def false_positives(filt, probes):
    """Every absent key the filter claims to hold. The 'poisoned' set."""
    return [key for key in probes if key in filt]


def part1_the_textbook_result():
    print("=== 1. The textbook result ===")
    k = optimal_k(M, N)
    filt = build()
    fps = false_positives(filt, ABSENT)
    observed = len(fps) / PROBES
    predicted = predicted_fp(M, k, N)
    print(f"  m={M} bits, n={N} keys, k=optimal_k(m,n)={k}")
    print(f"  bits set: {sum(filt.bits)}/{M}  (fill ratio {filt.fill_ratio():.3f})")
    print(f"  false positives over {PROBES} absent keys: {len(fps)}")
    print(f"  observed rate:      {observed:.4%}")
    print(f"  (1-e^-kn/m)^k:      {predicted:.4%}   <- assumes {round(M * (1 - math.exp(-k * N / M)))} bits set")
    print(f"  fill^k:             {filt.fill_ratio() ** k:.4%}   <- given the {sum(filt.bits)} actually set")
    print(f"  no false negatives: {all(key in filt for key in MEMBERS)}")
    print(f"  bits/key for a 1% filter: {bits_per_key_for(0.01):.2f}")
    print()
    return filt, fps


def part2_a_false_positive_is_permanent(filt, fps):
    print("=== 2. What that rate actually means ===")
    print(f"  poisoned keys enumerated: {len(fps)}")
    print(f"  first five: {fps[:5]}")
    victim = fps[0]
    hits = sum(1 for _ in range(10_000) if victim in filt)
    print(f"  querying {victim} 10000 times -> {hits} positives, {10000 - hits} negatives")
    print(f"  its k positions: {sorted(filt._indices(victim))}")
    clean = next(key for key in ABSENT if key not in filt)
    hits_clean = sum(1 for _ in range(10_000) if clean in filt)
    print(f"  querying {clean} 10000 times -> {hits_clean} positives")
    print()
    return victim


def part3_only_rehashing_helps(victim):
    print("=== 3. Retry never helps; rehashing does ===")
    sample = ABSENT[:10_000]
    a = build(salt="A")
    b = build(salt="B")
    poisoned_a = set(false_positives(a, sample))
    poisoned_b = set(false_positives(b, sample))
    print(f"  over the first {len(sample)} absent keys:")
    print(f"    poisoned under salt A: {len(poisoned_a)}")
    print(f"    poisoned under salt B: {len(poisoned_b)}")
    print(f"    in both:               {len(poisoned_a & poisoned_b)}")
    print(f"  {victim} in A: {victim in a}   in B: {victim in b}")
    newly_cursed = sorted(poisoned_b - poisoned_a)[:3]
    print(f"  clean under A, poisoned under B: {newly_cursed}")
    print()


def part4_more_hashing_is_not_more_accuracy():
    print("=== 4. The boundary: more hashing is not more accuracy ===")
    print("     k   fill   observed FP   fill^k   (1-e^-kn/m)^k")
    for k in (1, 2, 3, 4, 5, 6, 7, 8, 10, 14, 20):
        filt = build(k=k)
        rate = len(false_positives(filt, ABSENT)) / PROBES
        star = "   <- optimal_k" if k == optimal_k(M, N) else ""
        print(f"    {k:2d}   {filt.fill_ratio():.3f}   {rate:9.3%}   {filt.fill_ratio() ** k:6.3%}   {predicted_fp(M, k, N):11.3%}{star}")
    print()


def part5_segments_multiply_the_rate():
    print("=== 5. Ten segments at p each: the rate you feel is not p ===")
    # A stand-in for an LSM tree's on-disk segments (see ../lsm-tree/), one
    # dict per segment, each fronted by its own filter. No SSTable here.
    segments = [{f"seg{s}:key:{i}": i for i in range(N)} for s in range(10)]
    filters = [build(salt=f"S{s}", members=list(seg)) for s, seg in enumerate(segments)]
    probes = [f"seg0:key:{i}" for i in range(N, N + 10_000)]

    disk_reads = 0
    touched_any = 0
    for key in probes:
        reads = sum(1 for filt in filters if key in filt)
        disk_reads += reads
        touched_any += reads > 0
    per_segment = disk_reads / (len(probes) * len(segments))
    print(f"  {len(probes)} keys absent from all {len(segments)} segments")
    print(f"  per-segment false positive rate:      {per_segment:.3%}")
    print(f"  lookups that hit >=1 wasted read:     {touched_any / len(probes):.3%}")
    print(f"  1-(1-p)^10 for that p:                {1 - (1 - per_segment) ** 10:.3%}")
    print(f"  total wasted segment reads:           {disk_reads}")
    print()


if __name__ == "__main__":
    filt, fps = part1_the_textbook_result()
    victim = part2_a_false_positive_is_permanent(filt, fps)
    part3_only_rehashing_helps(victim)
    part4_more_hashing_is_not_more_accuracy()
    part5_segments_multiply_the_rate()