"""Run with SageMath:

    $ sage -pip install numberdb
    $ sage -python generate.py            # verify all live entries, no key needed
    $ sage -python generate.py --publish  # uses NUMBERDB_API_KEY

An optional offline mode verifies an exported table document instead:

    $ sage -python generate.py --snapshot snapshot.json

This repaired T339 generator reproduces the 717 retained published rows,
including their ordering. The frozen
Bernoulli, geometric and logarithmic probability lists preserve published
identities; they do not endorse the legacy hundredths mesh or introduce a new
grid. No application for that mesh has been established.

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. This measures achieved accuracy
rather than assuming that extra working bits guarantee it.
An all-entry audit at 100 requested digits measured at least 110 relative
decimal digits, with the weakest enclosure at logarithmic p=3/100 in nats.

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. No unproved fixed constant is used.

Fresh snapshot verification is not evidence of how the published values were
originally produced. Publishing uses the standard numberdb.Generator method
and its environment-based credentials and provenance, including
NUMBERDB_API_KEY and NUMBERDB_ASSISTED_BY. It does not authorize numerical
corrections, precision reductions or removals.
"""

import argparse
import json
import math
import sys

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

LEGACY_BERNOULLI_PROBABILITIES = tuple(QQ(value) for value in (
    "1/2",
    "1/3",
    "1/4",
    "1/5",
    "1/10",
    "11/100",
    "2/5",
    "1/6",
    "1/7",
    "2/7",
    "3/7",
    "1/8",
    "3/8",
    "1/9",
    "2/9",
    "4/9",
    "3/10",
    "1/11",
    "2/11",
    "3/11",
    "4/11",
    "5/11",
    "1/12",
    "5/12",
    "1/20",
    "1/25",
    "2/25",
    "1/50",
    "3/50",
    "1/100",
    "3/100",
    "7/100",
    "9/100",
    "3/20",
    "7/20",
    "9/20",
    "3/25",
    "4/25",
    "6/25",
    "7/25",
    "8/25",
    "9/25",
    "11/25",
    "12/25",
    "7/50",
    "9/50",
    "11/50",
    "13/50",
    "17/50",
    "19/50",
    "21/50",
    "23/50",
    "13/100",
    "17/100",
    "19/100",
    "21/100",
    "23/100",
    "27/100",
    "29/100",
    "31/100",
    "33/100",
    "37/100",
    "39/100",
    "41/100",
    "43/100",
    "47/100",
    "49/100",
))

LEGACY_SHARED_PROBABILITIES = tuple(QQ(value) for value in (
    "1/2",
    "1/3",
    "1/4",
    "1/5",
    "1/10",
    "11/100",
    "2/5",
    "3/10",
    "1/20",
    "3/20",
    "7/20",
    "9/20",
    "1/25",
    "2/25",
    "3/25",
    "4/25",
    "6/25",
    "7/25",
    "8/25",
    "9/25",
    "11/25",
    "12/25",
    "1/50",
    "3/50",
    "7/50",
    "9/50",
    "11/50",
    "13/50",
    "17/50",
    "19/50",
    "21/50",
    "23/50",
    "1/100",
    "3/100",
    "7/100",
    "9/100",
    "13/100",
    "17/100",
    "19/100",
    "21/100",
    "23/100",
    "27/100",
    "29/100",
    "31/100",
    "33/100",
    "37/100",
    "39/100",
    "41/100",
    "43/100",
    "47/100",
    "49/100",
))

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():
    return LEGACY_BERNOULLI_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 LEGACY_SHARED_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 LEGACY_SHARED_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):
    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, client=SnapshotClient(document))


def main(argv=None):
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_mutually_exclusive_group()
    modes.add_argument("--snapshot", help="verify an offline table export")
    modes.add_argument("--publish", action="store_true")
    options = parser.parse_args(argv)
    generator = ShannonEntropies()
    print(json.dumps(run_integrity_checks(), indent=2))
    if options.publish:
        print(generator.publish(
            message="restore reproducible coverage of retained Shannon entropies"))
        return 0
    if options.snapshot:
        with open(options.snapshot, encoding="utf-8") as snapshot_file:
            snapshot = json.load(snapshot_file)
        report = verify_snapshot(snapshot)
    else:
        report = generator.verify(sample=None)
    print(report)
    return 0 if report.ok and not report.coarser else 1


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

