## Generated by Claude Sonnet 4.6
## Can be run with: python3 ./hash_benchmark.py --graph
##                  python3 ./hash_benchmark.py --summary

import math
import random
import sys

# ── Hash functions ──────────────────────────────────────────────────────────

def simple_mod(k, m):
    return k % m

def division(k, m):
    return k % m

def multiplication(k, m, A=None):
    if A is None:
        A = (math.sqrt(5) - 1) / 2
    return math.floor(m * ((k * A) % 1))

def mid_square(k, m):
    squared = k * k
    s = str(squared)
    r = max(1, len(str(m)) - 1)
    mid = len(s) // 2
    start = max(0, mid - r // 2)
    digits = s[start:start + r]
    return int(digits) % m

def digit_folding(k, m):
    digits = str(k)
    group_size = 2
    groups = [digits[i:i+group_size] for i in range(0, len(digits), group_size)]
    total = sum(int(g) for g in groups)
    return total % m

# ── Collision tracking ───────────────────────────────────────────────────────

def track_collisions(hash_fn, keys, m):
    table = {}
    cumulative = []
    cols = 0
    for k in keys:
        idx = hash_fn(k, m)
        if idx in table:
            cols += 1
        else:
            table[idx] = k
        cumulative.append(cols)
    return cumulative

def count_collisions(hash_fn, keys, m):
    table = {}
    cols = 0
    for k in keys:
        idx = hash_fn(k, m)
        if idx in table:
            cols += 1
        else:
            table[idx] = k
    return cols

def std_dev(hash_fn, keys, m):
    bucket_sizes = [0] * m
    for k in keys:
        bucket_sizes[hash_fn(k, m)] += 1
    mean = sum(bucket_sizes) / m
    variance = sum((x - mean) ** 2 for x in bucket_sizes) / m
    return math.sqrt(variance)

# ── Output modes ─────────────────────────────────────────────────────────────

def ascii_line_graph(title, series, width=60, height=20):
    all_vals = [v for _, _, vals in series for v in vals]
    max_val  = max(all_vals) if all_vals else 1
    n_points = len(series[0][2])
    step     = max(1, n_points // width)
    sampled  = [(label, sym, vals[::step]) for label, sym, vals in series]
    n_cols   = len(sampled[0][2])
    grid     = [[' '] * n_cols for _ in range(height)]

    for label, sym, vals in sampled:
        for x, v in enumerate(vals):
            y = int((v / (max_val + 1e-9)) * (height - 1))
            y = height - 1 - y
            if 0 <= y < height and 0 <= x < n_cols:
                grid[y][x] = sym

    print(f"\n  {title}")
    print(f"  {'─' * (n_cols + 8)}")
    for i, row in enumerate(grid):
        y_val = int(max_val - (i / (height - 1)) * max_val)
        print(f"  {y_val:>4} │{''.join(row)}")
    print(f"  {'':>4} └{'─' * n_cols}")
    print(f"  {'':>5} 0{' ' * (n_cols - 10)}{n_points} (keys inserted)")
    print(f"\n  Legend:")
    for label, sym, _ in series:
        print(f"    {sym}  {label}")

def text_summary(dist_name, keys, methods):
    print(f"\n  {'─' * 65}")
    print(f"  {'Method':<38} {'m':>5} {'Collisions':>12} {'Std Dev':>10}")
    print(f"  {'─' * 65}")
    for name, sym, fn, m in methods:
        cols   = count_collisions(fn, keys, m)
        stddev = std_dev(fn, keys, m)
        print(f"  {name:<38} {m:>5} {cols:>12} {stddev:>10.4f}")
    print(f"  {'─' * 65}")

# ── Key distributions ────────────────────────────────────────────────────────

def uniform_keys(n):
    random.seed(42)
    return random.sample(range(1, 10000), n)

def multiples_of_4(n):
    return [i * 4 for i in range(1, n + 1)]

def clustered_keys(n):
    random.seed(42)
    centers = [100, 500, 1000, 5000, 9000]
    keys = set()
    while len(keys) < n:
        center = random.choice(centers)
        k = center + random.randint(-20, 20)
        if k > 0:
            keys.add(k)
    return list(keys)[:n]

def sequential_keys(n):
    return list(range(1, n + 1))

# ── Main ─────────────────────────────────────────────────────────────────────

USAGE = """
Usage: python3 hash_benchmark.py [--graph | --summary]

  --graph    Show ascii line graphs of cumulative collisions (default)
  --summary  Show text summary table with collision details
"""

if __name__ == "__main__":
    mode = "graph"
    if len(sys.argv) > 1:
        arg = sys.argv[1]
        if arg == "--summary":
            mode = "summary"
        elif arg == "--graph":
            mode = "graph"
        else:
            print(USAGE)
            sys.exit(1)

    NUM_KEYS   = 100
    M_SIMPLE   = 100
    M_DIVISION = 97
    M_MULT     = 128
    M_OTHER    = 100

    methods = [
        ("Simple Mod (naive, m=100)",      '#', simple_mod,     M_SIMPLE),
        ("Division (prime, m=97)",         '*', division,       M_DIVISION),
        ("Multiplication (Knuth, m=128)",  'o', multiplication, M_MULT),
        ("Mid-Square (m=100)",             '+', mid_square,     M_OTHER),
        ("Digit Folding (m=100)",          '.', digit_folding,  M_OTHER),
    ]

    distributions = [
        ("Uniform random",   uniform_keys(NUM_KEYS)),
        ("Multiples of 4",   multiples_of_4(NUM_KEYS)),
        ("Clustered keys",   clustered_keys(NUM_KEYS)),
        ("Sequential keys",  sequential_keys(NUM_KEYS)),
    ]

    for dist_name, keys in distributions:
        print(f"\n{'#'*60}")
        print(f"  Input distribution: {dist_name}")
        print(f"  Sample: {keys[:5]}...")
        print(f"{'#'*60}")

        if mode == "graph":
            series = []
            for name, sym, fn, m in methods:
                series.append((name, sym, track_collisions(fn, keys, m)))
            ascii_line_graph(
                f"Cumulative collisions over insertions ({dist_name})",
                series
            )
        else:
            text_summary(dist_name, keys, methods)