#!/usr/bin/env python3
"""CS01: Python 3.10+, standard library only. Deterministic evidence, not a benchmark.
The implementations retain no history. The external harness snapshots and scans
representations; that test/output overhead is deliberately not operation cost.
Run normally or with -O: checks use explicit exceptions, never assert.
"""
import copy
import itertools
import json
from collections import Counter

EMPTY = None
TOMB = "†"
FIELDS = ("bucket_visits", "key_comparisons", "search_probes", "scanned_slots",
          "moved_records", "reinsert_probes", "initialized_slots")


def require(ok, message):
    if not ok:
        raise AssertionError(message)


def cost():
    return dict.fromkeys(FIELDS, 0)


def reply(found, value=None):
    return {"found": found, "value": value}


def positive_integer(value, label):
    if type(value) is not int or value < 1:
        raise ValueError(label + " must be a positive non-bool integer")


def validate_op(op, arities, integer_arg):
    if not isinstance(op, (tuple, list)) or not op or type(op[0]) is not str:
        raise ValueError("operation must be a nonempty tuple/list with a string name")
    if op[0] not in arities or len(op) != arities[op[0]]:
        raise ValueError("unknown operation or wrong arity")
    if op[0] in integer_arg and type(op[1]) is not int:
        raise ValueError("key/index/capacity must be a non-bool integer")


class Linear:
    def __init__(self, capacity=5, fault=None):
        positive_integer(capacity, "capacity")
        self.slots = [EMPTY] * capacity
        self.n = self.used = 0
        self.fault = fault

    def locate(self, key, bill, for_put=False):
        first_tomb = None
        m = len(self.slots)
        for offset in range(m):
            pos = (key % m + offset) % m
            bill["search_probes"] += 1
            entry = self.slots[pos]
            if entry is EMPTY:
                return None, first_tomb if first_tomb is not None else pos
            if entry == TOMB:
                if self.fault == "stop_at_tomb" and not for_put:
                    return None, pos
                if self.fault == "insert_at_tomb" and for_put:
                    return None, pos
                if first_tomb is None:
                    first_tomb = pos
            else:
                bill["key_comparisons"] += 1
                if entry[0] == key:
                    return pos, None
        return None, first_tomb

    def step(self, op):
        validate_op(op, {"put": 3, "get": 2, "delete": 2, "rebuild": 2},
                    {"put", "get", "delete", "rebuild"})
        bill = cost()
        name = op[0]
        if name == "rebuild":
            m = op[1]
            if m < max(1, self.n):
                raise ValueError("new table too small")
            fresh = [EMPTY] * m
            bill["initialized_slots"] = m
            for entry in self.slots:
                bill["scanned_slots"] += 1
                if entry is EMPTY or entry == TOMB:
                    continue
                key, value = entry
                for offset in range(m):
                    pos = (key % m + offset) % m
                    bill["reinsert_probes"] += 1
                    if fresh[pos] is EMPTY:
                        fresh[pos] = (key, value)
                        bill["moved_records"] += 1
                        break
            self.slots = fresh
            self.used = self.n
            return None, bill
        key = op[1]
        hit, vacancy = self.locate(key, bill, name == "put")
        if name == "get":
            return reply(hit is not None, self.slots[hit][1] if hit is not None else None), bill
        if name == "delete":
            result = reply(hit is not None, self.slots[hit][1] if hit is not None else None)
            if hit is not None:
                self.slots[hit] = TOMB
                self.n -= 1
            return result, bill
        if name != "put":
            raise ValueError("unknown operation")
        if hit is not None:
            self.slots[hit] = (key, op[2])
            return None, bill
        if vacancy is None:
            raise OverflowError("all slots live")
        if self.slots[vacancy] is EMPTY:
            self.used += 1
        self.slots[vacancy] = (key, op[2])
        self.n += 1
        return None, bill

    def snapshot(self):
        return {"slots": copy.deepcopy(self.slots), "n": self.n, "used": self.used}


class Chained:
    """Bucket records use Python lists; deletion shifts are counted as moves.
    List append/allocation are real Python costs, not a worst-case linked-list claim.
    """
    def __init__(self, capacity=5):
        positive_integer(capacity, "capacity")
        self.buckets = [[] for _ in range(capacity)]
        self.n = 0

    def step(self, op):
        validate_op(op, {"put": 3, "get": 2, "delete": 2, "rebuild": 2},
                    {"put", "get", "delete", "rebuild"})
        bill = cost()
        name = op[0]
        if name == "rebuild":
            m = op[1]
            if m < 1:
                raise ValueError("positive capacity required")
            fresh = [[] for _ in range(m)]
            bill["initialized_slots"] = m
            for bucket in self.buckets:
                bill["scanned_slots"] += 1
                for key, value in bucket:
                    fresh[key % m].append((key, value))
                    bill["moved_records"] += 1
            self.buckets = fresh
            return None, bill
        key = op[1]
        bucket = self.buckets[key % len(self.buckets)]
        bill["bucket_visits"] = 1
        hit = None
        for i, (stored_key, _) in enumerate(bucket):
            bill["key_comparisons"] += 1
            if stored_key == key:
                hit = i
                break
        if name == "get":
            return reply(hit is not None, bucket[hit][1] if hit is not None else None), bill
        if name == "delete":
            result = reply(hit is not None, bucket[hit][1] if hit is not None else None)
            if hit is not None:
                bill["moved_records"] = len(bucket) - hit - 1
                bucket.pop(hit)
                self.n -= 1
            return result, bill
        if name != "put":
            raise ValueError("unknown operation")
        if hit is None:
            bucket.append((key, op[2]))
            self.n += 1
        else:
            bucket[hit] = (key, op[2])
        return None, bill

    def snapshot(self):
        return {"buckets": copy.deepcopy(self.buckets), "n": self.n}


def abstract_step(mapping, op):
    """Only the public map contract: no slots, hashes, probes or tombstones."""
    name = op[0]
    if name == "put":
        mapping[op[1]] = op[2]
        return None
    if name == "get":
        return reply(op[1] in mapping, mapping.get(op[1]))
    if name == "delete":
        return reply(op[1] in mapping, mapping.pop(op[1], None))
    if name == "rebuild":
        return None
    raise ValueError("unknown operation")


def inspect(table, mapping):
    """Independent representation oracle. Never calls implementation locate/get."""
    if isinstance(table, Linear):
        records = [x for x in table.slots if x is not EMPTY and x != TOMB]
        require(table.used == sum(x is not EMPTY for x in table.slots), "used count")
        require(0 <= table.n <= table.used <= len(table.slots), "count range")
        for pos, entry in enumerate(table.slots):
            if entry is EMPTY or entry == TOMB:
                continue
            home = entry[0] % len(table.slots)
            distance = (pos - home) % len(table.slots)
            preceding = [(home + j) % len(table.slots) for j in range(distance)]
            require(all(table.slots[j] is not EMPTY for j in preceding), "unreachable key")
    else:
        records = [item for bucket in table.buckets for item in bucket]
        for index, bucket in enumerate(table.buckets):
            require(all(k % len(table.buckets) == index for k, _ in bucket), "wrong bucket")
    require(len(records) == table.n, "live count")
    require(len({k for k, _ in records}) == len(records), "duplicate physical key")
    require(dict(records) == mapping, "abstract map mismatch")


HISTORY = [
    ("put", 4, "A"), ("put", 9, "B"), ("put", 14, "C"),
    ("delete", 9), ("put", 14, "C2"), ("put", 19, "D"),
    ("delete", 99), ("put", 0, "Z"), ("delete", 4), ("put", 3, "E"),
    ("get", 24), ("put", 14, "C3"), ("delete", 0), ("put", 24, "F"),
    ("rebuild", 10), ("get", 24), ("delete", 3), ("rebuild", 10),
]


def dictionary_trace():
    tables = {"chained": Chained(), "linear": Linear()}
    mapping = {}
    rows = []
    totals = {name: Counter() for name in tables}
    peak = {name: Counter() for name in tables}
    for index, op in enumerate(HISTORY, 1):
        expected = abstract_step(mapping, op)
        row = {"step": index, "op": op, "abstract": sorted(mapping.items()), "reply": expected}
        for name, table in tables.items():
            actual, bill = table.step(op)
            require(actual == expected, f"{name}: reply mismatch at {op}")
            inspect(table, mapping)
            require(name != "linear" or table.n < len(table.slots), "main trace live load")
            totals[name].update(bill)
            for field, value in bill.items():
                peak[name][field] = max(peak[name][field], value)
            row[name] = {"state": table.snapshot(), "bill": bill}
        rows.append(row)
    return {"rows": rows, "totals": totals, "single_operation_max_by_meter": peak}


def shortest_fault(fault):
    alphabet = [("put", 0, "a"), ("put", 3, "b"),
                ("get", 0), ("get", 3), ("delete", 0), ("delete", 3)]
    tested_by_length = {}
    for length in range(1, 5):
        tested = 0
        for history in itertools.product(alphabet, repeat=length):
            tested += 1
            table, mapping = Linear(3, fault), {}
            try:
                for op in history:
                    expected = abstract_step(mapping, op)
                    actual, _ = table.step(op)
                    require(actual == expected, "wrong observable reply")
                    inspect(table, mapping)
            except AssertionError as error:
                tested_by_length[length] = tested
                return {"fault": fault, "length": length, "history": history,
                        "failure": str(error), "state": table.snapshot(),
                        "expected_map": sorted(mapping.items()),
                        "tested_by_length": tested_by_length,
                        "scope": "all shorter histories over the stated six-operation alphabet"}
        tested_by_length[length] = tested
    raise AssertionError("mutation survived")


class MigratingArray:
    """No history/log. Slot copy budget is 1 or 2. Allocation is visibly linear
    in this Python realization, separately metered; no wall-clock O(1) claim.
    """
    def __init__(self, budget=2, initial=()):
        if type(budget) is not int or budget not in (1, 2):
            raise ValueError("budget must be 1 or 2")
        self.budget = budget
        self.n = len(initial)
        self.C = max(1, len(initial))
        self.A = list(initial) + [EMPTY] * (self.C - self.n)
        self.O = self.B = None
        self.N = self.k = 0

    def step(self, op, allocation_failure=False, wrong_write=False):
        validate_op(op, {"append": 2, "read": 2, "write": 3}, {"read", "write"})
        name = op[0]
        if name not in ("append", "read", "write"):
            raise ValueError("unknown operation")
        if name != "append" and not (0 <= op[1] < self.n):
            raise IndexError("index outside logical sequence")
        bill = {"user_slot_accesses": 1, "copied_slots": 0,
                "allocated_slots": 0, "retired_slots": 0,
                "copy_indices": [], "user_location": None}
        if name == "append" and self.B is None and self.n == self.C:
            if allocation_failure:
                raise MemoryError("injected before publishing new representation")
            fresh = [EMPTY] * (2 * self.C)
            bill["allocated_slots"] = len(fresh)
            self.N, self.O, self.B, self.k = self.C, self.A, fresh, 0
        result = None
        if name == "append":
            index = self.n
            target, label = (self.B, "B") if self.B is not None else (self.A, "A")
            target[index] = op[1]
            self.n += 1
        else:
            index = op[1]
            if self.B is None:
                target, label = self.A, "A"
            elif index < self.k or index >= self.N:
                target, label = self.B, "B"
            else:
                target, label = self.O, "O"
            if name == "read":
                result = target[index]
            else:
                if wrong_write and self.B is not None:
                    target, label = self.B, "B (fault)"
                target[index] = op[2]
        bill["user_location"] = f"{label}[{index}]"
        if self.B is not None:
            for _ in range(min(self.budget, self.N - self.k)):
                self.B[self.k] = self.O[self.k]
                bill["copy_indices"].append(self.k)
                self.k += 1
            bill["copied_slots"] = len(bill["copy_indices"])
            if self.k == self.N:
                bill["retired_slots"] = self.N
                self.A, self.C = self.B, 2 * self.N
                self.O = self.B = None
                self.N = self.k = 0
        return result, bill

    def snapshot(self):
        if self.B is None:
            return {"n": self.n, "C": self.C, "A": self.A[:], "migrating": False}
        return {"n": self.n, "C": self.C, "N": self.N, "k": self.k,
                "O": self.O[:], "B": self.B[:], "migrating": True}


def inspect_array(array, sequence):
    require(array.n == len(sequence), "logical array length")
    if array.B is None:
        require(len(array.A) == array.C and 0 <= array.n <= array.C, "steady shape")
        observed = array.A[:array.n]
    else:
        require(array.O is array.A, "old array identity")
        require(len(array.O) == array.N == array.C, "old capacity")
        require(len(array.B) == 2 * array.N, "new capacity")
        require(0 <= array.k < array.N and array.N < array.n <= 2 * array.N, "frontier bounds")
        require(all(x is EMPTY for x in array.B[array.k:array.N]), "unmigrated new slots")
        # Direct concatenation from the specified regions, not implementation routing.
        observed = array.B[:array.k] + array.O[array.k:array.N] + array.B[array.N:array.n]
    require(observed == sequence, "authoritative latest values")


ARRAY_HISTORY = [("append", "i"), ("write", 7, "H"), ("write", 0, "A"),
                 ("read", 7), ("append", "j"), ("read", 0),
                 ("write", 8, "I"), ("read", 8)]


def array_trace(budget, history=ARRAY_HISTORY):
    sequence = list("abcdefgh")
    array = MigratingArray(budget, sequence)
    rows = []
    for index, op in enumerate(history, 1):
        expected = None
        if op[0] == "append":
            sequence.append(op[1])
        elif op[0] == "write":
            sequence[op[1]] = op[2]
        else:
            expected = sequence[op[1]]
        actual, bill = array.step(op)
        require(actual == expected, "array return")
        inspect_array(array, sequence)
        require(bill["copied_slots"] <= budget, "copy budget")
        rows.append({"step": index, "op": op, "reply": actual, "bill": bill,
                     "state": array.snapshot(), "abstract": sequence[:]})
    return {"budget": budget, "rows": rows}


def boundaries():
    results = []
    for budget in (1, 2):
        # Invalid indices preserve BOTH logical and physical state, including k.
        a = MigratingArray(budget, list("abcdefgh"))
        a.step(("append", "i"))
        for op in [("read", -1), ("read", a.n), ("write", -1, "x"), ("write", a.n, "x")]:
            before = a.snapshot()
            try:
                a.step(op)
            except IndexError:
                require(a.snapshot() == before, "invalid index mutated state")
            else:
                raise AssertionError("invalid index accepted")
        b = MigratingArray(budget, list("abcdefgh"))
        before = b.snapshot()
        try:
            b.step(("append", "i"), allocation_failure=True)
        except MemoryError:
            require(b.snapshot() == before, "allocation failure mutated state")
        else:
            raise AssertionError("failure was not injected")
        b.step(("append", "i"))
        inspect_array(b, list("abcdefghi"))
        # N=1 commits on the triggering append, regardless of budget.
        one = MigratingArray(budget, ["a"])
        _, bill = one.step(("append", "b"))
        require(one.B is None and one.C == 2 and bill["copied_slots"] == 1, "N=1")
        # For N=8 and only appends, commit by ceil(N/budget), next round at append 9.
        c = MigratingArray(budget, list(range(8)))
        commits, starts = [], []
        seq = list(range(8))
        for t in range(1, 10):
            _, bill = c.step(("append", t + 7))
            seq.append(t + 7)
            inspect_array(c, seq)
            if bill["allocated_slots"]:
                starts.append(t)
            if bill["retired_slots"]:
                commits.append(t)
        require(starts == [1, 9] and commits[0] == (8 + budget - 1) // budget, "deadline")
        # An empty-start prefix checks multiple successive rounds against a list oracle.
        empty, seq = MigratingArray(budget), []
        for i in range(65):
            empty.step(("append", i)); seq.append(i); inspect_array(empty, seq)
            empty.step(("write", i // 2, -i)); seq[i // 2] = -i; inspect_array(empty, seq)
            result, _ = empty.step(("read", i // 2)); require(result == -i, "mixed prefix")
            inspect_array(empty, seq)
        results.append({"budget": budget, "invalid_indices": 4, "allocation_failure_preserved": True,
                        "retry_succeeded": True, "N1_copies": 1, "N8_commit_at": commits[0],
                        "N8_next_start_at": starts[1], "empty_start_mixed_operations": 195})
    # A deliberately misrouted write is rejected immediately by the independent RI.
    broken = MigratingArray(2, list("abcdefgh"))
    broken.step(("append", "i"))
    broken.step(("write", 7, "H"), wrong_write=True)
    try:
        inspect_array(broken, list("abcdefgHi"))
    except AssertionError as error:
        mutation = {"history": [("append", "i"), ("write", 7, "H")],
                    "failure": str(error), "state": broken.snapshot()}
    else:
        raise AssertionError("wrong-write mutation survived")
    # All live: finite absent lookup, update succeeds, new key fails atomically.
    table, mapping = Linear(2), {}
    for op in [("put", 0, "a"), ("put", 2, "b"), ("put", 2, "B")]:
        expected = abstract_step(mapping, op); actual, _ = table.step(op)
        require(actual == expected, "full table update"); inspect(table, mapping)
    actual, bill = table.step(("get", 4))
    require(actual == reply(False) and bill["search_probes"] == 2, "full lookup terminates")
    before = table.snapshot()
    try:
        table.step(("rebuild", 1))
    except ValueError:
        require(table.snapshot() == before, "small rebuild changed state")
    else:
        raise AssertionError("small rebuild accepted")
    try:
        table.step(("put", 4, "c"))
    except OverflowError:
        require(table.snapshot() == before, "full insertion state")
    else:
        raise AssertionError("full insertion accepted")
    return {"arrays": results, "wrong_array_write": mutation, "all_live_boundary": True}


def enumerate_valid_histories():
    alphabet = [("put", 0, "a"), ("put", 3, "b"), ("put", 3, "B"),
                ("get", 0), ("get", 3), ("delete", 0), ("delete", 3), ("rebuild", 3)]
    count = 0
    for history in itertools.product(alphabet, repeat=4):
        mapping, linear, chained = {}, Linear(3), Chained(3)
        for op in history:
            expected = abstract_step(mapping, op)
            for table in (linear, chained):
                actual, _ = table.step(op)
                require(actual == expected, "enumerated return")
                inspect(table, mapping)
        count += 1
    return {"length": 4, "alphabet_size": len(alphabet), "histories": count,
            "note": "finite exhaustive test, not a proof for arbitrary histories"}


def malformed_inputs():
    rejected = 0
    for constructor in (Linear, Chained):
        for invalid in (0, -1, 1.0, True, "5", None):
            try:
                constructor(invalid)
            except ValueError:
                rejected += 1
            else:
                raise AssertionError("invalid table capacity accepted")
        table = constructor()
        table.step(("put", 1, "a"))
        for op in ((), ("put", 1), ("get",), ("get", 1, 2), ("get", True),
                   ("put", 1.0, "x"), ("rebuild", 0), ("rebuild", 2.0),
                   ("unknown", 1), "get", ([], 1)):
            before = table.snapshot()
            try:
                table.step(op)
            except ValueError:
                require(table.snapshot() == before, "bad dictionary input changed state")
                rejected += 1
            else:
                raise AssertionError("malformed dictionary input accepted")
    for invalid in (0, 3, 1.0, 2.0, True, "1", None):
        try:
            MigratingArray(invalid)
        except ValueError:
            rejected += 1
        else:
            raise AssertionError("invalid array budget accepted")
    array = MigratingArray(1, list("abcd"))
    for op in ((), ("append",), ("append", "x", "y"), ("write", 0),
               ("read", True), ("read", 1.0), ("write", "0", "x"),
               ("unknown", 0), "read", ([], 1)):
        before = array.snapshot()
        try:
            array.step(op)
        except ValueError:
            require(array.snapshot() == before, "bad array input changed state")
            rejected += 1
        else:
            raise AssertionError("malformed array input accepted")
    # Every slot may be a tombstone: absent get/delete terminate, put reuses one.
    table, mapping = Linear(3), {}
    for op in [("put", 0, "a"), ("put", 1, "b"), ("put", 2, "c"),
               ("delete", 0), ("delete", 1), ("delete", 2),
               ("get", 3), ("delete", 3), ("put", 3, None), ("get", 3)]:
        expected = abstract_step(mapping, op)
        actual, bill = table.step(op)
        require(actual == expected, "all tombstone return")
        inspect(table, mapping)
        if op in [("get", 3), ("delete", 3)] and not mapping:
            require(bill["search_probes"] == 3, "all tombstone bounded scan")
    require(table.n == 1 and table.used == 3, "all tombstone reuse counts")
    return {"rejected_without_mutation": rejected, "all_tombstone_boundary": True,
            "stored_None_distinguished_from_missing": True}


def main():
    report = {"model": "fixed integer keys, h(k)=k mod capacity; no randomness or timing",
              "dictionary": dictionary_trace(),
              "faults": [shortest_fault("stop_at_tomb"), shortest_fault("insert_at_tomb")],
              "arrays": [array_trace(1), array_trace(2)],
              "original_N8_route": array_trace(2, [("append", "i"), ("read", 0),
                    ("write", 7, "H"), ("read", 7), ("append", "j")]),
              "boundaries": boundaries(), "malformed_inputs": malformed_inputs(),
              "finite_enumeration": enumerate_valid_histories(),
              "status": "PASS"}
    print(json.dumps(report, ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()