"""Read-only verification of the 589-row T339 reference selection.

Install the numberdb package with SageMath:

    $ sage -pip install numberdb

Download the table JSON export from https://numberdb.org/api/table?id=T339
and save it as table.json, then verify it with SageMath:

    $ sage -python generate.py --snapshot table.json
    $ sage -python generate.py --snapshot table.json --digits 150

The export must have the coverage of this generator's revision; older
revisions can have different selections. With no arguments, verify
prepared.json beside this file. The program reads only the chosen local
snapshot, makes no HTTP requests and provides no CLI writes or publishing.

Bernoulli probabilities are reduced 0 < p <= 1/2 with denominator at most 12,
together with p=1/m for 2<=m<=20. The first is an existing bounded reference
family of binary partitions of small uniform models; the second supplies the
Bernoulli companions of integer-mean waiting-time models. Complement symmetry
makes a second Bernoulli orientation unnecessary.

Geometric success probabilities are 1/m and 1-1/m for 2<=m<=20. The reciprocal
orientation has mean waiting time m; the complementary orientation has mean
m/(m-1). Log-series decay parameters are the same two rational orientations,
but are not success probabilities. With success q, Log(1-q) is the jump law in
a compound Poisson representation of NB(r,q), with Poisson rate -r*log(q).
See Zhou et al. (2012), section 4.1, equations (18)-(19):
https://icml.cc/2012/papers/665.pdf
The finite bounds 12 and 20 are noncanonical exploratory reference choices,
not published demands for every input. Other distribution families are
unchanged. Enumeration preserves the relative order of retained row keys.

All logarithms are natural before conversion to bits by division by log(2).
Working precision is numberdb.bits(digits, losing=128). Positive series tails
are bounded by 10^(-digits-12) nats and added to the computed ball before unit
conversion. Every returned ball must be finite, positive and have radius at
most 10^(-digits-6) times its lower bound. The accompanying verification.json
records achieved precision and tests both 100 and 150 requested digits,
including the new slowest log-series input 19/20. Extra bits alone are not a
certificate.

For negative binomial probabilities, the decreasing successive ratio is
bounded by alpha=(1+q)/2 after the tested cutoff, with q=1-p.
Since the binomial coefficient is at least one,
-log(P_k) <= -r*log(p)-k*log(q). Summing the geometric majorant and its first
moment gives _negative_binomial_tail_bound.

For Poisson probabilities, the tested cutoff makes all later ratios at most
alpha=1/2. The inequality log(k!) <= k^2 gives
-log(P_k) <= lambda+k*abs(log(lambda))+k^2. The first two geometric moments
give _poisson_tail_bound.

For logarithmic probabilities P_k=c*p^k/k, c=-1/log(1-p), use
-log(P_k) <= abs(log(c))-k*log(p)+k. For k>=m, 1/k<=1/m;
summing p^k gives _logarithmic_tail_bound. This bound holds for 0<p<1,
including the new parameters above 1/2. No unproved fixed constant is used.

Retained numeric strings and row comments belong to their original revisions.
The generator checks their values without replacing their payloads. It never
removes published rows, private baselines or historical attachments.
"""

import argparse
import json
import math
import sys
from pathlib import Path

import numberdb.sage as numberdb
from sage.arith.misc import binomial
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField


WORKING_GUARD = 128
TAIL_GUARD_DIGITS = 12

BERNOULLI_PARTITION_DENOMINATOR = 12
MAX_MODEL_SIZE = 20

SMALL_PROBABILITIES = (
    QQ(1) / 2,
    QQ(1) / 3,
    QQ(1) / 4,
    QQ(1) / 10,
)

HYPERGEOMETRIC_SHAPES = (
    (10, 2, 2),
    (10, 2, 5),
    (10, 2, 8),
    (10, 5, 2),
    (10, 5, 5),
    (10, 5, 8),
    (20, 2, 2),
    (20, 2, 5),
    (20, 2, 10),
    (20, 5, 2),
    (20, 5, 5),
    (20, 5, 10),
    (20, 10, 2),
    (20, 10, 5),
    (20, 10, 10),
)


def _field(digits):
    return RealBallField(numberdb.bits(digits, losing=WORKING_GUARD))


def _q(text):
    return QQ(str(text))


def _target(field, digits):
    return field(QQ(1) / QQ(10) ** (digits + TAIL_GUARD_DIGITS))


def _ordered_probabilities():
    probabilities = [QQ(value) for value in (
        "1/2", "1/3", "1/4", "1/5", "1/10", "2/5")]
    for denominator in range(2, BERNOULLI_PARTITION_DENOMINATOR + 1):
        for numerator in range(1, denominator // 2 + 1):
            probability = QQ(numerator) / QQ(denominator)
            if probability.denominator() == denominator and probability not in probabilities:
                probabilities.append(probability)
    probabilities.append(QQ(1) / QQ(20))
    for model_size in range(13, MAX_MODEL_SIZE + 1):
        probability = QQ(1) / QQ(model_size)
        if probability not in probabilities:
            probabilities.append(probability)
    return tuple(probabilities)


def _model_probabilities():
    probabilities = [QQ(value) for value in (
        "1/2", "1/3", "1/4", "1/5", "1/10", "1/20")]
    for model_size in range(2, MAX_MODEL_SIZE + 1):
        probability = QQ(1) / QQ(model_size)
        if probability not in probabilities:
            probabilities.append(probability)
    for model_size in range(2, MAX_MODEL_SIZE + 1):
        probability = QQ(model_size - 1) / QQ(model_size)
        if probability not in probabilities:
            probabilities.append(probability)
    return tuple(probabilities)


def _half_integer_grid():
    return tuple(QQ(k) / QQ(2) for k in range(1, 21)) + tuple(QQ(k) for k in range(11, 21))


def _entropy_term(probability):
    if probability == 0:
        return probability
    if (not probability.is_finite() or probability.lower() <= 0
            or probability.upper() > 1):
        raise ArithmeticError("probability is not enclosed in (0, 1]")
    return -probability * probability.log()


def _finite_entropy(probabilities, digits):
    field = _field(digits)
    total = field(0)
    for probability in probabilities:
        total += _entropy_term(field(probability))
    return total


def _finite_entropy_from_balls(probabilities, digits):
    return _finite_entropy(probabilities, digits)


def _bernoulli_entropy(shape, digits):
    p = _q(shape)
    return _finite_entropy((p, 1 - p), digits)


def _binomial_entropy(shape, digits):
    n_text, p_text = shape.split(",")
    n = int(n_text)
    p = _q(p_text)
    q = 1 - p
    probabilities = [
        QQ(binomial(n, k)) * p ** k * q ** (n - k)
        for k in range(n + 1)
    ]
    return _finite_entropy(probabilities, digits)


def _geometric_entropy(shape, digits):
    field = _field(digits)
    p = field(_q(shape))
    q = 1 - p
    return -p.log() - q * q.log() / p


def _negative_binomial_tail_bound(field, p_start, k_start, r, p, alpha):
    q = 1 - p
    one = field(1)
    a = field(alpha)
    denominator = one - a
    k = field(k_start)
    a_log = field(r) * (-field(p).log())
    b_log = -field(q).log()
    return p_start * (
        (a_log + k * b_log) / denominator
        + b_log * a / (denominator ** 2)
    )


def _negative_binomial_entropy(shape, digits):
    r_text, p_text = shape.split(",")
    r = int(r_text)
    p = _q(p_text)
    q = 1 - p
    field = _field(digits)
    target = _target(field, digits)
    alpha = (1 + q) / 2

    total = field(0)
    probability = field(p) ** r
    k = 0
    while True:
        total += _entropy_term(probability)
        next_probability = probability * field(q) * field(k + r) / field(k + 1)
        k_start = k + 1
        ratio_bound = q * QQ(k_start + r) / QQ(k_start + 1)
        if ratio_bound <= alpha:
            tail = _negative_binomial_tail_bound(
                field, next_probability, k_start, r, p, alpha)
            if tail.upper() < target.lower():
                return total.add_error(tail.upper())
        probability = next_probability
        k += 1


def _poisson_tail_bound(field, p_start, k_start, lam, alpha):
    one = field(1)
    a = field(alpha)
    denominator = one - a
    k = field(k_start)
    lam_ball = field(lam)
    abs_log_lam = lam_ball.log().abs()
    sum_one = one / denominator
    sum_j = a / (denominator ** 2)
    sum_j2 = a * (one + a) / (denominator ** 3)
    sum_k = k * sum_one + sum_j
    sum_k2 = (k ** 2) * sum_one + 2 * k * sum_j + sum_j2
    return p_start * (lam_ball * sum_one + abs_log_lam * sum_k + sum_k2)


def _poisson_entropy(shape, digits):
    lam = _q(shape)
    field = _field(digits)
    target = _target(field, digits)
    alpha = QQ(1) / QQ(2)

    total = field(0)
    probability = (-field(lam)).exp()
    k = 0
    while True:
        total += _entropy_term(probability)
        next_probability = probability * field(lam) / field(k + 1)
        k_start = k + 1
        if QQ(lam) / QQ(k_start + 1) <= alpha:
            tail = _poisson_tail_bound(
                field, next_probability, k_start, lam, alpha)
            if tail.upper() < target.lower():
                return total.add_error(tail.upper())
        probability = next_probability
        k += 1


def _uniform_entropy(shape, digits):
    field = _field(digits)
    return field(int(shape)).log()


def _hypergeometric_entropy(shape, digits):
    population_text, successes_text, draws_text = shape.split(",")
    population = int(population_text)
    successes = int(successes_text)
    draws = int(draws_text)
    denominator = QQ(binomial(population, draws))
    low = max(0, draws - (population - successes))
    high = min(draws, successes)
    probabilities = []
    for k in range(low, high + 1):
        probabilities.append(
            QQ(binomial(successes, k))
            * QQ(binomial(population - successes, draws - k))
            / denominator)
    return _finite_entropy(probabilities, digits)


def _logarithmic_tail_bound(field, p_power, n_plus_one, c, p):
    p_ball = field(p)
    one_minus_p = field(1 - p)
    a = c.log().abs()
    b = -p_ball.log()
    geometric_tail = p_power / one_minus_p
    return c * (a * geometric_tail / field(n_plus_one)
                + (b + 1) * geometric_tail)


def _logarithmic_entropy(shape, digits):
    p = _q(shape)
    field = _field(digits)
    target = _target(field, digits)
    p_ball = field(p)
    c = -1 / (1 - p_ball).log()

    total = field(0)
    p_power = p_ball
    k = 1
    while True:
        probability = c * p_power / field(k)
        total += _entropy_term(probability)
        next_power = p_power * p_ball
        tail = _logarithmic_tail_bound(field, next_power, k + 1, c, p)
        if tail.upper() < target.lower():
            return total.add_error(tail.upper())
        p_power = next_power
        k += 1


def _zipf_entropy(shape, digits):
    s_text, n_text = shape.split(",")
    exponent = int(s_text)
    size = int(n_text)
    normalisation = sum(QQ(1) / QQ(k) ** exponent for k in range(1, size + 1))
    probabilities = [
        (QQ(1) / QQ(k) ** exponent) / normalisation
        for k in range(1, size + 1)
    ]
    return _finite_entropy(probabilities, digits)


def _benford_entropy(digits):
    field = _field(digits)
    log10 = field(10).log()
    probabilities = [
        (1 + field(QQ(1) / QQ(d))).log() / log10
        for d in range(1, 10)
    ]
    return _finite_entropy_from_balls(probabilities, digits)


def _entropy_nats(distribution, shape, digits):
    if distribution == "bernoulli":
        return _bernoulli_entropy(shape, digits)
    if distribution == "binomial":
        return _binomial_entropy(shape, digits)
    if distribution == "geometric":
        return _geometric_entropy(shape, digits)
    if distribution == "negative-binomial":
        return _negative_binomial_entropy(shape, digits)
    if distribution == "poisson":
        return _poisson_entropy(shape, digits)
    if distribution == "discrete-uniform":
        return _uniform_entropy(shape, digits)
    if distribution == "hypergeometric":
        return _hypergeometric_entropy(shape, digits)
    if distribution == "logarithmic":
        return _logarithmic_entropy(shape, digits)
    if distribution == "zipf":
        return _zipf_entropy(shape, digits)
    if distribution == "benford":
        return _benford_entropy(digits)
    raise ValueError("unknown distribution %r" % (distribution,))


def _to_unit(value, unit, digits):
    if unit == "nats":
        return value
    if unit != "bits":
        raise ValueError("unknown unit %r" % (unit,))
    field = _field(digits)
    return field(value) / field(2).log()


def _check_enclosure(value, digits):
    if not value.is_finite():
        raise ArithmeticError("entropy enclosure is not finite")
    lower = value.lower().exact_rational()
    upper = value.upper().exact_rational()
    if lower <= 0:
        raise ArithmeticError("entropy enclosure is not strictly positive")
    if (upper - lower) / 2 > lower / QQ(10) ** (digits + 6):
        raise ArithmeticError("entropy enclosure does not justify requested digits")


def _power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0


def _skip_entry(distribution, shape, unit):
    if unit != "bits":
        return False
    if distribution == "bernoulli" and shape == "1/2":
        return True
    if distribution == "geometric" and shape == "1/2":
        return True
    if distribution == "discrete-uniform" and _power_of_two(int(shape)):
        return True
    if distribution == "binomial" and shape == "2,1/2":
        return True
    return False


def _comment(distribution, shape, unit):
    if unit != "nats":
        return ""
    if distribution == "bernoulli" and shape == "1/2":
        return "The omitted bits row is exactly $1$."
    if distribution == "geometric" and shape == "1/2":
        return "The omitted bits row is exactly $2$."
    if distribution == "discrete-uniform":
        n = int(shape)
        if _power_of_two(n):
            return "The omitted bits row is exactly $%d$." % (n.bit_length() - 1)
    if distribution == "binomial" and shape == "2,1/2":
        return "The omitted bits row is exactly $3/2$."
    return ""


def _format_probability(value):
    return str(value)


def _scipy_expected(params):
    import scipy.stats as stats

    distribution = params["distribution"]
    shape = params["shape"]
    unit = params["unit"]
    if distribution == "bernoulli":
        expected = stats.bernoulli(float(_q(shape))).entropy()
    elif distribution == "binomial":
        n_text, p_text = shape.split(",")
        expected = stats.binom(int(n_text), float(_q(p_text))).entropy()
    elif distribution == "geometric":
        expected = stats.geom(float(_q(shape))).entropy()
    elif distribution == "negative-binomial":
        r_text, p_text = shape.split(",")
        expected = stats.nbinom(int(r_text), float(_q(p_text))).entropy()
    elif distribution == "poisson":
        expected = stats.poisson(float(_q(shape))).entropy()
    elif distribution == "discrete-uniform":
        expected = math.log(int(shape))
    elif distribution == "hypergeometric":
        population_text, successes_text, draws_text = shape.split(",")
        expected = stats.hypergeom(
            int(population_text), int(successes_text), int(draws_text)).entropy()
    elif distribution == "logarithmic":
        expected = stats.logser(float(_q(shape))).entropy()
    elif distribution == "zipf":
        s_text, n_text = shape.split(",")
        if hasattr(stats, "zipfian"):
            expected = stats.zipfian(int(s_text), int(n_text)).entropy()
        else:
            weights = [k ** (-int(s_text)) for k in range(1, int(n_text) + 1)]
            total = sum(weights)
            expected = -sum((w / total) * math.log(w / total) for w in weights)
    elif distribution == "benford":
        probabilities = [math.log10(1 + 1 / d) for d in range(1, 10)]
        expected = -sum(p * math.log(p) for p in probabilities)
    else:
        raise ValueError("unknown distribution %r" % (distribution,))
    if unit == "bits":
        expected /= math.log(2)
    return expected


def _midpoint(value):
    if isinstance(value, dict):
        value = value["number"]
    return float((value.lower() + value.upper()) / 2)


class ShannonEntropies(numberdb.Generator):

    table = "T339"
    parameters = ("distribution", "shape", "unit")
    type = "R"
    digits = 100
    rigour = "proven"

    def enumerate(self):
        for p in _ordered_probabilities():
            shape = _format_probability(p)
            for unit in ("nats", "bits"):
                if not _skip_entry("bernoulli", shape, unit):
                    yield {"distribution": "bernoulli", "shape": shape, "unit": unit}

        for n in range(2, 21):
            for p in SMALL_PROBABILITIES:
                shape = "%d,%s" % (n, p)
                for unit in ("nats", "bits"):
                    if not _skip_entry("binomial", shape, unit):
                        yield {"distribution": "binomial", "shape": shape, "unit": unit}

        for p in _model_probabilities():
            shape = _format_probability(p)
            for unit in ("nats", "bits"):
                if not _skip_entry("geometric", shape, unit):
                    yield {"distribution": "geometric", "shape": shape, "unit": unit}

        for r in range(2, 11):
            for p in SMALL_PROBABILITIES:
                shape = "%d,%s" % (r, p)
                for unit in ("nats", "bits"):
                    yield {"distribution": "negative-binomial", "shape": shape, "unit": unit}

        for lam in _half_integer_grid():
            shape = _format_probability(lam)
            for unit in ("nats", "bits"):
                yield {"distribution": "poisson", "shape": shape, "unit": unit}

        for n in range(2, 31):
            shape = str(n)
            for unit in ("nats", "bits"):
                if not _skip_entry("discrete-uniform", shape, unit):
                    yield {"distribution": "discrete-uniform", "shape": shape, "unit": unit}

        for population, successes, draws in HYPERGEOMETRIC_SHAPES:
            shape = "%d,%d,%d" % (population, successes, draws)
            for unit in ("nats", "bits"):
                yield {"distribution": "hypergeometric", "shape": shape, "unit": unit}

        for p in _model_probabilities():
            shape = _format_probability(p)
            for unit in ("nats", "bits"):
                yield {"distribution": "logarithmic", "shape": shape, "unit": unit}

        for exponent in (1, 2, 3):
            for size in (10, 100):
                shape = "%d,%d" % (exponent, size)
                for unit in ("nats", "bits"):
                    yield {"distribution": "zipf", "shape": shape, "unit": unit}

        for unit in ("nats", "bits"):
            yield {"distribution": "benford", "shape": "-", "unit": unit}

    def value(self, params, digits):
        distribution = str(params["distribution"])
        shape = str(params["shape"])
        unit = str(params["unit"])
        value = _to_unit(_entropy_nats(distribution, shape, digits), unit, digits)
        _check_enclosure(value, digits)
        comment = _comment(distribution, shape, unit)
        if comment:
            return {"number": value, "comment": comment}
        return value


def run_integrity_checks(digits=100):
    import scipy

    generator = ShannonEntropies()
    largest = {
        unit: {"absolute_difference": 0.0, "params": None}
        for unit in ("nats", "bits")
    }
    checked = 0
    for params in generator.enumerate():
        value = generator.value(params, digits)
        got = _midpoint(value)
        expected = _scipy_expected(params)
        if not math.isfinite(got) or not math.isfinite(expected):
            raise ArithmeticError("nonfinite SciPy comparison: %s" % params)
        difference = abs(got - expected)
        unit = params["unit"]
        if difference > largest[unit]["absolute_difference"]:
            largest[unit] = {
                "absolute_difference": difference,
                "params": dict(params),
                "computed": got,
                "scipy": expected,
            }
        if difference > 5e-9:
            raise ArithmeticError(
                "SciPy check failed for %s: %.17g here, %.17g independently"
                % (params, got, expected))
        checked += 1
    return {
        "checked": checked,
        "scipy": scipy.__version__,
        "absolute_tolerance_in_each_rows_unit": 5e-9,
        "largest_by_unit": largest,
        "role": "double-precision convention check, not a 100-digit proof",
    }


class SnapshotClient:
    def __init__(self, document):
        self.document = document

    def request(self, path, parameters):
        if path != "api/table" or parameters != {"id": "T339"}:
            raise RuntimeError("only the offline T339 snapshot can be read")
        return self.document


def verify_snapshot(document, digits=100):
    generator = ShannonEntropies()
    expected = [
        (distribution, shape, unit)
        for distribution, shapes in document["Numbers"].items()
        for shape, units in shapes.items()
        for unit in units
    ]
    enumerated = [
        tuple(str(params[name]) for name in generator.parameters)
        for params in generator.enumerate()
    ]
    if enumerated != expected or len(set(enumerated)) != len(enumerated):
        raise ArithmeticError("default enumeration differs from the snapshot")
    return generator.verify(
        sample=None, digits=digits, client=SnapshotClient(document))


def main(argv=None):
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument(
        "--snapshot", default=str(Path(__file__).with_name("prepared.json")),
        help="offline table export; defaults to prepared.json beside this file")
    parser.add_argument("--digits", type=int, choices=(100, 150), default=100)
    options = parser.parse_args(argv)
    with open(options.snapshot, encoding="utf-8") as snapshot_file:
        snapshot = json.load(snapshot_file)
    report = verify_snapshot(snapshot, digits=options.digits)
    print(report)
    return 0 if report.ok and not report.coarser else 1


if __name__ == "__main__":
    sys.exit(main())
