"""Aha demo: the same 100,000 keys, indexed twice.

Once inserted in ascending order — the case everyone calls the best case —
and once shuffled with a fixed seed. Same tree, same order 63, same keys.
The sorted load builds a taller index that costs more page reads per lookup,
forever.

Writes two real index files, ascending.idx and random.idx, into the current
directory. Takes ~20 seconds: it is a real on-disk build of 200,000 records.
"""

import math
import random

from btree import MAX_KEYS, BPlusTree, Node, Pager

N = 100_000
SEED = 42
PROBE = 61_234          # one key, looked up in both indexes


def build(path, keys):
    pager = Pager(path)
    tree = BPlusTree(pager)
    for key in keys:
        tree.insert(key, key * 10)
    return pager, tree


def describe_path(pager, tree):
    """Re-read the pages the last get() touched, and say how big each was."""
    parts = []
    for depth, pid in enumerate(tree.last_path):
        node = Node.unpack(pager.read_page(pid))
        kind = "leaf" if node.leaf else ("root" if depth == 0 else "inner")
        plural = "key" if len(node.keys) == 1 else "keys"
        parts.append(f"#{pid} ({kind}, {len(node.keys)} {plural})")
    return " -> ".join(parts)


def run():
    ascending = list(range(N))
    shuffled = list(range(N))
    random.Random(SEED).shuffle(shuffled)
    loads = [("ascending", "ascending.idx", ascending),
             (f"random(seed {SEED})", "random.idx", shuffled)]
    built = [(label, *build(path, keys)) for label, path, keys in loads]

    print(f"\n=== (1) {N:,} keys, order {MAX_KEYS}, two insertion orders ===")
    print(f"  {'load':<18}{'height':>7}{'pages':>8}{'leaves':>8}"
          f"{'file':>10}{'avg leaf fill':>15}")
    for label, pager, tree in built:
        s = tree.stats()
        print(f"  {label:<18}{s['height']:>7}{s['pages']:>8}{s['leaves']:>8}"
              f"{s['bytes'] / 1024 / 1024:>9.2f}M{s['fill'] * 100:>14.1f}%")

    print("\n=== (2) where the tree got taller ===")
    for label, _, tree in built:
        grew = ", ".join(f"height {h} at insert {n:,}" for n, h in tree.growth)
        print(f"  {label:<18}{grew}")

    print(f"\n=== (3) the same lookup, key {PROBE:,}, in both indexes ===")
    for label, pager, tree in built:
        pager.reads = 0
        before = tree.comparisons
        value = tree.get(PROBE)
        print(f"  {label:<18}{pager.reads} page reads, "
              f"{tree.comparisons - before} key comparisons  -> {value}")
        print(f"  {'':<18}{describe_path(pager, tree)}")

    print(f"\n=== (4) every one of the {N:,} keys, looked up ===")
    print(f"  {'load':<18}{'reads/lookup':>14}{'comparisons: min':>18}"
          f"{'avg':>8}{'max':>6}")
    for label, pager, tree in built:
        reads, lo, hi, total = set(), 10 ** 9, 0, 0
        for key in range(N):
            pager.reads = 0
            before = tree.comparisons
            assert tree.get(key) == key * 10
            comps = tree.comparisons - before
            reads.add(pager.reads)
            lo, hi, total = min(lo, comps), max(hi, comps), total + comps
        seen = str(reads.pop()) if len(reads) == 1 else "varies"
        print(f"  {label:<18}{seen:>14}{lo:>18}{total / N:>8.1f}{hi:>6}")
    print(f"  a balanced binary tree over {N:,} keys: "
          f"~{math.log2(N):.0f} reads and ~{math.log2(N):.0f} comparisons")

    for _, pager, _ in built:
        pager.close()


if __name__ == "__main__":
    run()