#!/usr/bin/env python3
"""
pelt_pruning_test.py

Randomized check of PELT pruning against a brute-force partitioner for the
floored Gaussian objective used in ChangePointDetector.mq5:

    C(s, e) = n * ln(max(var, eps)),   eps = 1e-8 * var_all
    F(0) = -beta,   F(t) = min over tau of [F(tau) + C(tau, t) + beta]
    segments must contain at least min_seg returns

Three pruned variants are compared with the brute-force dynamic program,
which tries every admissible tau and does no pruning:

  immediate : drop tau as soon as F(tau) + C(tau, t) > F(t)
  deferred  : keep tau until t + min_seg, then drop it (always prunes)
  guarded   : deferred, but pruning is switched on only if the smallest
              min_seg-window variance is at least 2*eps (the check done in
              CSegmentCost::Init); otherwise the full recursion is used.
              This is the variant the MQL5 script implements.

Matching criterion: a variant matches the brute-force result when
  (1) the list of change point indices is identical, and
  (2) the total objective F(n) agrees within 1e-9 (relative) / 1e-7 (absolute).

Only the Python standard library is used. Everything is driven by one
master seed, so the same seed gives the same series and the same results.

Usage:
    python pelt_pruning_test.py                 # 2400 series, seed 20261109
    python pelt_pruning_test.py --n-series 600 --seed 1
"""

import argparse
import math
import random
import sys
from collections import OrderedDict

INF = float("inf")          # plays the role of DBL_MAX ("undefined")


# ----------------------------------------------------------------------
# Cost function (mirrors CSegmentCost)
# ----------------------------------------------------------------------
class Cost:
    def __init__(self, returns):
        self.n = len(returns)
        self.cs = [0.0]
        self.css = [0.0]
        for r in returns:
            self.cs.append(self.cs[-1] + r)
            self.css.append(self.css[-1] + r * r)
        mean = self.cs[-1] / self.n
        var = self.css[-1] / self.n - mean * mean
        self.ok = math.isfinite(var) and var > 0.0
        self.eps = 1e-8 * var if self.ok else 0.0
        self.calls = 0

    def compute(self, s, e):
        self.calls += 1
        n = e - s
        if n <= 0:
            return INF
        sm = self.cs[e] - self.cs[s]
        sq = self.css[e] - self.css[s]
        mean = sm / n
        var = sq / n - mean * mean
        if not math.isfinite(var):
            return INF
        if var < 0.0:
            if var > -self.eps:
                var = 0.0
            else:
                return INF
        if var < self.eps:
            var = self.eps
        return n * math.log(var)

    def pruning_valid(self, m):
        """Smallest m-window variance must be at least 2*eps."""
        n = self.n
        if m < 2 or n < m:
            return False
        min_var = INF
        for s in range(0, n - m + 1):
            sm = self.cs[s + m] - self.cs[s]
            sq = self.css[s + m] - self.css[s]
            mean = sm / m
            v = sq / m - mean * mean
            if not math.isfinite(v):
                return False
            if v < min_var:
                min_var = v
        return min_var >= 2.0 * self.eps


def backtrack(cp, n):
    pts = []
    cur = n
    while cur > 0:
        prev = cp[cur]
        if prev < 0 or prev >= cur:
            return None
        if prev > 0:
            pts.append(prev)
        cur = prev
    pts.reverse()
    return pts


# ----------------------------------------------------------------------
# Brute-force partitioner: every admissible tau, no pruning
# ----------------------------------------------------------------------
def brute_force(cost, n, beta, m):
    F = [INF] * (n + 1)
    cp = [-1] * (n + 1)
    F[0] = -beta
    cp[0] = 0
    for t in range(1, n + 1):
        best, best_tau = INF, -1
        for tau in range(0, t - m + 1):
            if F[tau] == INF:
                continue
            c = cost.compute(tau, t)
            if c == INF:
                continue
            val = F[tau] + c + beta
            if not math.isfinite(val):
                continue
            if val < best:
                best, best_tau = val, tau
        if best_tau >= 0:
            F[t], cp[t] = best, best_tau
    if F[n] == INF:
        return None
    pts = backtrack(cp, n)
    return None if pts is None else (F[n], pts)


# ----------------------------------------------------------------------
# PELT with the three pruning variants
# ----------------------------------------------------------------------
def pelt(cost, n, beta, m, mode):
    prune_ok = True
    if mode == "guarded":
        prune_ok = cost.pruning_valid(m)

    F = [INF] * (n + 1)
    cp = [-1] * (n + 1)
    prune_at = [-1] * (n + 1)
    F[0] = -beta
    cp[0] = 0
    R = [0]

    for t in range(1, n + 1):
        best, best_tau = INF, -1
        costs = []                       # cost of (R[i], t), reused below
        for tau in R:
            if t - tau < m or F[tau] == INF:
                costs.append(None)
                continue
            c = cost.compute(tau, t)
            costs.append(c)
            if c == INF:
                continue
            val = F[tau] + c + beta
            if not math.isfinite(val):
                continue
            if val < best:
                best, best_tau = val, tau

        if best_tau >= 0:
            F[t], cp[t] = best, best_tau

        new_R = []
        for i, tau in enumerate(R):
            if t - tau < m:              # not yet admissible: keep
                new_R.append(tau)
                continue
            if F[tau] == INF:
                continue
            c = costs[i]
            if c is None or c == INF:
                continue

            if mode == "immediate":
                if F[tau] + c > F[t]:
                    continue
                new_R.append(tau)
                continue

            # deferred removal: waiting period has elapsed
            if prune_at[tau] >= 0 and t >= prune_at[tau]:
                continue
            if prune_ok and F[tau] + c > F[t] and prune_at[tau] < 0:
                prune_at[tau] = t + m
            new_R.append(tau)

        if F[t] != INF:
            new_R.append(t)
        R = new_R

    if F[n] == INF:
        return None
    pts = backtrack(cp, n)
    return None if pts is None else (F[n], pts)


# ----------------------------------------------------------------------
# Series generators (all go through closing prices, as in the script)
# ----------------------------------------------------------------------
def student_t(rng, df):
    z = rng.gauss(0.0, 1.0)
    chi2 = 2.0 * rng.gammavariate(df / 2.0, 1.0)
    return z / math.sqrt(chi2 / df)


def gen_gaussian(rng, n):
    return [rng.gauss(0.0, 0.006) for _ in range(n)], 5


def gen_student_t(rng, n):
    return [0.004 * student_t(rng, 3) for _ in range(n)], 5


def gen_garch(rng, n):
    omega, a, b = 2e-7, 0.08, 0.90
    h = omega / (1.0 - a - b)
    out = []
    for _ in range(n):
        r = math.sqrt(h) * rng.gauss(0.0, 1.0)
        out.append(r)
        h = omega + a * r * r + b * h
    return out, 5


def gen_regimes(rng, n):
    out = []
    while len(out) < n:
        length = rng.randint(10, 60)
        sd = rng.uniform(0.002, 0.012)
        mu = rng.uniform(-0.001, 0.003)
        out.extend(rng.gauss(mu, sd) for _ in range(length))
    return out[:n], 5


def gen_flat_runs(rng, n):
    out = [rng.gauss(0.0, 0.004) for _ in range(n)]
    for _ in range(rng.randint(1, 3)):
        length = rng.randint(5, 40)
        start = rng.randint(0, max(0, n - length))
        for i in range(start, min(n, start + length)):
            out[i] = 0.0                 # identical closes
    return out, 5


def gen_coarse_grid(rng, n):
    # small moves on a coarse price grid: many exactly-zero returns
    return [rng.gauss(0.0, 0.0006) for _ in range(n)], 3


GENERATORS = OrderedDict([
    ("gaussian", gen_gaussian),
    ("student_t3", gen_student_t),
    ("garch11", gen_garch),
    ("regimes", gen_regimes),
    ("flat_runs", gen_flat_runs),
    ("coarse_grid", gen_coarse_grid),
])


def make_returns(rng, kind, n):
    rets, decimals = GENERATORS[kind](rng, n)
    p = 1.1
    closes = [round(p, decimals)]
    for r in rets:
        p = p * math.exp(r)
        closes.append(round(p, decimals))
    out = []
    for i in range(n):
        out.append(math.log(closes[i + 1] / closes[i]))
    return out


# ----------------------------------------------------------------------
def same(a, b):
    if a is None or b is None:
        return a is None and b is None
    fa, pa = a
    fb, pb = b
    cost_ok = abs(fa - fb) <= max(1e-7, 1e-9 * max(abs(fa), abs(fb)))
    return cost_ok and pa == pb


def gen_floor_stress(rng, n):
    """Piecewise series with flat runs, tiny noise and ordinary noise, so the
    variance floor binds often. Returns are generated directly."""
    r = []
    while len(r) < n:
        length = rng.randint(2, 15)
        kind = rng.choice(["flat", "flat", "noise", "tiny"])
        if kind == "flat":
            r += [rng.choice([0.0, 0.0, 0.001, -0.001])] * length
        elif kind == "tiny":
            r += [rng.gauss(0.0, 1e-6) for _ in range(length)]
        else:
            r += [rng.gauss(0.0, 0.005) for _ in range(length)]
    return r[:n]


def floor_stress(n_series, seed):
    rng = random.Random(seed)
    tried = guard_off = bad_deferred = bad_guarded = 0
    for _ in range(n_series):
        n = rng.randint(20, 70)
        m = rng.randint(2, 6)
        rets = gen_floor_stress(rng, n)
        cost = Cost(rets)
        if not cost.ok:
            continue
        tried += 1
        if not cost.pruning_valid(m):
            guard_off += 1
        beta = rng.choice([0.5, 1.0, 2.0]) * 2.0 * math.log(n)
        ref = brute_force(cost, n, beta, m)
        if not same(ref, pelt(cost, n, beta, m, "deferred")):
            bad_deferred += 1
        if not same(ref, pelt(cost, n, beta, m, "guarded")):
            bad_guarded += 1
    print("\nFloor-binding stress test (n in [20,70], min_seg in [2,6], seed=%d)" % seed)
    print("  series tested                     : %d" % tried)
    print("  guard switched pruning off        : %d" % guard_off)
    print("  mismatches, deferred (no guard)   : %d" % bad_deferred)
    print("  mismatches, guarded               : %d" % bad_guarded)


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument("--n-series", type=int, default=2400)
    ap.add_argument("--seed", type=int, default=20261109)
    ap.add_argument("--stress-series", type=int, default=30000)
    args = ap.parse_args()

    kinds = list(GENERATORS.keys())
    modes = ["immediate", "deferred", "guarded"]
    rng = random.Random(args.seed)

    per_kind = {k: {"series": 0, "guard_off": 0,
                    **{m: 0 for m in modes}} for k in kinds}
    examples = []

    for i in range(args.n_series):
        kind = kinds[i % len(kinds)]
        n = rng.randint(40, 200)
        m = rng.randint(2, 15)
        scale = rng.choice([0.5, 1.0, 2.0])
        rets = make_returns(rng, kind, n)

        cost = Cost(rets)
        if not cost.ok:                  # constant series: nothing to segment
            continue
        beta = scale * 2.0 * math.log(n)

        ref = brute_force(cost, n, beta, m)
        stat = per_kind[kind]
        stat["series"] += 1
        if not cost.pruning_valid(m):
            stat["guard_off"] += 1

        for mode in modes:
            res = pelt(cost, n, beta, m, mode)
            if not same(ref, res):
                stat[mode] += 1
                if len(examples) < 5 and mode != "immediate":
                    examples.append((kind, n, m, scale, mode))

    tot = {k: sum(per_kind[x][k] for x in kinds)
           for k in ["series", "guard_off"] + modes}

    print("Pruning check against brute force (floored Gaussian objective)")
    print("seed=%d   series requested=%d   min_seg in [2,15], n in [40,200]"
          % (args.seed, args.n_series))
    print("match = identical change point list and F(n) within tolerance\n")
    hdr = "%-12s %7s %10s %10s %10s %10s" % (
        "series type", "series", "guard off", "immediate", "deferred", "guarded")
    print(hdr)
    print("-" * len(hdr))
    for k in kinds:
        s = per_kind[k]
        print("%-12s %7d %10d %10d %10d %10d" % (
            k, s["series"], s["guard_off"],
            s["immediate"], s["deferred"], s["guarded"]))
    print("-" * len(hdr))
    print("%-12s %7d %10d %10d %10d %10d" % (
        "total", tot["series"], tot["guard_off"],
        tot["immediate"], tot["deferred"], tot["guarded"]))
    print("\n(columns immediate/deferred/guarded = number of MISMATCHES with brute force;")
    print(" 'guard off' = series where the 2*eps window check disables pruning)")

    if examples:
        print("\nFirst mismatches of the deferred/guarded variants:")
        for e in examples:
            print("  type=%s n=%d min_seg=%d penalty_scale=%.1f variant=%s" % e)

    # --- efficiency demo: 500 returns, minimum length 10 -----------------
    rng2 = random.Random(args.seed + 1)
    n, m = 500, 10
    rets = make_returns(rng2, "regimes", n)
    cost_b = Cost(rets)
    beta = 2.0 * math.log(n)
    ref = brute_force(cost_b, n, beta, m)
    cost_p = Cost(rets)
    res = pelt(cost_p, n, beta, m, "guarded")
    print("\nEfficiency demo (500 returns, min_seg=10, automatic penalty %.4f)" % beta)
    print("  brute force : %8d segment cost evaluations" % cost_b.calls)
    print("  guarded PELT: %8d segment cost evaluations" % cost_p.calls)
    print("  results match: %s   change points: %d"
          % (same(ref, res), len(ref[1]) if ref else 0))

    floor_stress(args.stress_series, args.seed + 2)


if __name__ == "__main__":
    sys.exit(main())