"""Murphy (2023), Chapter 23: Normalizing flows.

Companion code for Chapter 23 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 829-847 (the supplement's Chapter 23 has no content).
Written from scratch with numpy, matplotlib and PyTorch (CPU only, double precision), to be read next
to the lecture notes (../ch23-normalizing-flows.html).

Methods
* Section 23.1: change of variables for a composition (logdet_composition), maximum likelihood
  (forward KL, used for Figures 23.1c, 23.3 and 23.5) and the reverse-KL objective of variational
  inference (used for Figure 23.1a,b).
* Section 23.2.2: scalar bijections. The non-linear squared map (23.9) with its exact invertibility
  bound and its inverse as the real root of a cubic (nlsq, nlsq_deriv, nlsq_inverse); conical
  combinations of sigmoids with a bisection inverse (monotone_sigmoid_mix, bisect_inverse); the
  sum-of-squares polynomial (23.11) (sos_poly); the monotone rational-quadratic spline with its
  closed-form inverse (rq_spline in numpy, rq_spline_t in PyTorch).
* Section 23.2.3: masked coupling flow with rational-quadratic splines (class SplineCouplingFlow).
* Section 23.2.4: affine autoregressive flow in two dimensions (class AffineAR2D, the masked
  autoregressive flow with D = 2) and an autoregressive flow of non-linear squared maps
  (class NLSqAR2D); the autoregressive model as a one-layer flow with a uniform base (ar_as_flow).
* Section 23.2.5: contractive residual flow (fixed-point inverse, power series and Hutchinson
  estimates of the log-determinant, Russian roulette), the Weinstein-Aronszajn identity and the
  planar flow with its exact inverse (planar_forward, planar_inverse, planar_logdensity).
* Section 23.2.6: continuous-time flow, solved with RK4 together with the trace ODE (23.44).

Figures reproduced: 23.1 (non-linear squared flows), 23.3 (spline coupling flow on the two moons,
layer by layer), 23.5 (affine autoregressive flows with 1 and 5 layers on a cross-shaped density).
One own figure, x23.a (residual and continuous-time flows: fixed-point inversion, the log-determinant
series and the trace ODE).

Skipped figures, with reasons: Figure 23.2 (diagram of a coupling layer), 23.4 (diagram of an
affine autoregressive layer and its inverse) and 23.6 (diagram of an inverse autoregressive flow):
schematic illustrations with nothing computed.

Data: simulation only (the two moons are generated with scikit-learn's make_moons; the cross-shaped
density of Figure 23.5 and the four-Gaussian mixture of Figure 23.1 are explicit mixtures).
Every training run is seeded; trained weights are cached in ./cache/ch23/.
"""
import json
import os
import sys

import numpy as np

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import common  # noqa: E402
from common import BLUE, GREEN, GREY, ORANGE, RED, plt, savefig, panel_grid, panel_label  # noqa: E402

CH = 23
CACHE_DIR = os.path.join(HERE, "cache", "ch23")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)
torch = common.torch_setup(0)
torch.set_default_dtype(torch.float64)
nn = torch.nn
F = torch.nn.functional

LOG2PI = np.log(2 * np.pi)
C_NLSQ = 9.0 / (8.0 * np.sqrt(3.0))      # max over z of 2z/(1+z^2)^2, attained at z = 1/sqrt(3)


# =========================================================================== 23.1 change of variables
def std_normal_logpdf(u):
    """log N(u | 0, I) summed over the last axis (numpy or torch)."""
    if isinstance(u, torch.Tensor):
        return -0.5 * (u ** 2).sum(-1) - 0.5 * u.shape[-1] * LOG2PI
    u = np.asarray(u, float)
    return -0.5 * (u ** 2).sum(-1) - 0.5 * u.shape[-1] * LOG2PI


def logdet_composition(jacs):
    """sum_i log|det J_i| for a list of Jacobian matrices (23.4)."""
    return float(sum(np.linalg.slogdet(J)[1] for J in jacs))


# =========================================================================== 23.2.2 scalar bijections
def nlsq(u, a, b, c, d, e):
    """Non-linear squared map (23.9): h(u) = a u + b + c / (1 + (d u + e)^2)."""
    z = d * u + e
    return a * u + b + c / (1 + z * z)


def nlsq_deriv(u, a, b, c, d, e):
    z = d * u + e
    return a - 2 * c * d * z / (1 + z * z) ** 2


def nlsq_min_deriv(a, c, d):
    """Exact minimum of h'(u) over u: a - C |c| d with C = 9/(8 sqrt 3)."""
    return a - C_NLSQ * abs(c) * d


def nlsq_inverse(x, a, b, c, d, e):
    """Inverse of an invertible NLSq map, as the real root of a cubic (Cardano's formula).

    With z = d u + e, h(u) = x is (p z + q)(1 + z^2) + c = 0, p = a/d, q = b - x - a e/d, a cubic in z
    with exactly one real root when h is strictly increasing.
    """
    x = np.asarray(x, float)
    p = a / d
    q = b - x - a * e / d
    A, B, Cc = q / p, 1.0, (q + c) / p                 # z^3 + A z^2 + B z + C = 0
    P = B - A * A / 3.0
    Q = 2 * A ** 3 / 27.0 - A * B / 3.0 + Cc
    disc = (Q / 2) ** 2 + (P / 3) ** 3
    s = np.sqrt(np.maximum(disc, 0.0))
    t = np.cbrt(-Q / 2 + s) + np.cbrt(-Q / 2 - s)
    z = t - A / 3.0
    return (z - e) / d


def bisect_inverse(h, x, lo=-50.0, hi=50.0, tol=1e-12, maxit=200):
    """Invert a strictly increasing vectorised h by bisection; returns (u, iterations)."""
    x = np.asarray(x, float)
    lo = np.full_like(x, lo)
    hi = np.full_like(x, hi)
    it = 0
    while it < maxit and np.max(hi - lo) > tol:
        mid = 0.5 * (lo + hi)
        up = h(mid) < x
        lo = np.where(up, mid, lo)
        hi = np.where(up, hi, mid)
        it += 1
    return 0.5 * (lo + hi), it


def monotone_sigmoid_mix(u, w, a, b, bias=0.0):
    """Conical combination of logistic sigmoids, sum_k w_k sigma(a_k u + b_k) + bias (w_k, a_k > 0),
    plus a small linear term so that it is a bijection of R."""
    u = np.asarray(u, float)[..., None]
    return (w * common.sigmoid(a * u + b)).sum(-1) + bias + 0.05 * u[..., 0]


def sos_poly(coefs):
    """Sum-of-squares polynomial (23.11). coefs is (K, L+1); returns (h, h') as numpy poly1d with h(0) = 0."""
    dh = np.poly1d([0.0])
    for row in np.atleast_2d(coefs):
        pk = np.poly1d(row[::-1])                    # sum_l a_kl u^l
        dh = dh + pk * pk
    return dh.integ(), dh


# =========================================================================== rational-quadratic spline
def rq_knots(W, H, D, B):
    """Knots of a monotone rational-quadratic spline on [-B, B] from unnormalised parameters.

    W, H: (..., K) unnormalised widths and heights (softmax), D: (..., K-1) unnormalised interior
    derivatives (softplus); boundary derivatives are 1 so the identity tails join smoothly."""
    K = W.shape[-1]
    w = np.exp(W - W.max(-1, keepdims=True))
    w = 2 * B * w / w.sum(-1, keepdims=True)
    h = np.exp(H - H.max(-1, keepdims=True))
    h = 2 * B * h / h.sum(-1, keepdims=True)
    xk = np.concatenate([np.full(w.shape[:-1] + (1,), -B), -B + np.cumsum(w, -1)], -1)
    yk = np.concatenate([np.full(h.shape[:-1] + (1,), -B), -B + np.cumsum(h, -1)], -1)
    xk[..., -1] = B
    yk[..., -1] = B
    dk = np.concatenate([np.ones(D.shape[:-1] + (1,)), np.log1p(np.exp(D)), np.ones(D.shape[:-1] + (1,))], -1)
    assert dk.shape[-1] == K + 1
    return xk, yk, dk


def rq_eval(x, xk, yk, dk, inverse=False):
    """Monotone rational-quadratic spline through knots (xk, yk) with knot derivatives dk (all 1-D),
    identity outside [xk[0], xk[-1]]. Returns (value, log derivative) of the forward map, or of the
    inverse map if inverse=True."""
    x = np.asarray(x, float)
    out = x.copy()
    logd = np.zeros_like(x)
    lo, hi = (yk[0], yk[-1]) if inverse else (xk[0], xk[-1])
    inside = (x > lo) & (x < hi)
    xi_ = x[inside]
    edges = yk if inverse else xk
    k = np.clip(np.searchsorted(edges, xi_, side="right") - 1, 0, len(xk) - 2)
    wk = xk[k + 1] - xk[k]
    hk = yk[k + 1] - yk[k]
    s = hk / wk
    d0, d1 = dk[k], dk[k + 1]
    if not inverse:
        t = (xi_ - xk[k]) / wk
        tt = t * (1 - t)
        den = s + (d1 + d0 - 2 * s) * tt
        out[inside] = yk[k] + hk * (s * t * t + d0 * tt) / den
        der = s * s * (d1 * t * t + 2 * s * tt + d0 * (1 - t) ** 2) / den ** 2
        logd[inside] = np.log(der)
    else:
        dy = xi_ - yk[k]
        a = hk * (s - d0) + dy * (d1 + d0 - 2 * s)
        b = hk * d0 - dy * (d1 + d0 - 2 * s)
        c = -s * dy
        disc = np.maximum(b * b - 4 * a * c, 0.0)
        t = 2 * c / (-b - np.sqrt(disc))
        tt = t * (1 - t)
        den = s + (d1 + d0 - 2 * s) * tt
        out[inside] = xk[k] + t * wk
        der = s * s * (d1 * t * t + 2 * s * tt + d0 * (1 - t) ** 2) / den ** 2
        logd[inside] = -np.log(der)
    return out, logd


def rq_spline_t(x, W, H, D, B, inverse=False, min_bin=1e-3, min_der=1e-3):
    """Batched rational-quadratic spline in PyTorch. x: (N,), W, H: (N, K), D: (N, K-1).

    Returns (y, log|dy/dx|) of the forward (or inverse) map; identity outside [-B, B]."""
    K = W.shape[-1]
    w = min_bin + (1 - min_bin * K) * torch.softmax(W, -1)
    h = min_bin + (1 - min_bin * K) * torch.softmax(H, -1)
    xk = F.pad(torch.cumsum(w, -1), (1, 0)) * 2 * B - B
    yk = F.pad(torch.cumsum(h, -1), (1, 0)) * 2 * B - B
    xk = torch.cat([xk[:, :-1], torch.full_like(xk[:, :1], B)], 1)
    yk = torch.cat([yk[:, :-1], torch.full_like(yk[:, :1], B)], 1)
    one = torch.ones_like(D[:, :1])
    dk = torch.cat([one, min_der + F.softplus(D), one], 1)
    inside = (x > -B) & (x < B)
    xc = x.clamp(-B + 1e-9, B - 1e-9)
    edges = yk if inverse else xk
    k = (torch.searchsorted(edges.contiguous(), xc[:, None].contiguous(), right=True) - 1).clamp(0, K - 1)
    g = lambda T, j: T.gather(1, j).squeeze(1)  # noqa: E731
    x0, x1, y0, y1, d0, d1 = g(xk, k), g(xk, k + 1), g(yk, k), g(yk, k + 1), g(dk, k), g(dk, k + 1)
    wk, hk = x1 - x0, y1 - y0
    s = hk / wk
    if not inverse:
        t = (xc - x0) / wk
        tt = t * (1 - t)
        den = s + (d1 + d0 - 2 * s) * tt
        y = y0 + hk * (s * t * t + d0 * tt) / den
        der = s * s * (d1 * t * t + 2 * s * tt + d0 * (1 - t) ** 2) / den ** 2
        ld = torch.log(der)
    else:
        dy = xc - y0
        a = hk * (s - d0) + dy * (d1 + d0 - 2 * s)
        b = hk * d0 - dy * (d1 + d0 - 2 * s)
        c = -s * dy
        t = 2 * c / (-b - torch.sqrt((b * b - 4 * a * c).clamp_min(0)))
        tt = t * (1 - t)
        den = s + (d1 + d0 - 2 * s) * tt
        y = x0 + t * wk
        der = s * s * (d1 * t * t + 2 * s * tt + d0 * (1 - t) ** 2) / den ** 2
        ld = -torch.log(der)
    y = torch.where(inside, y, x)
    ld = torch.where(inside, ld, torch.zeros_like(ld))
    return y, ld


# =========================================================================== the scalar-bijection demo
SPLINE_XK = np.array([-3.0, -1.5, 0.0, 1.5, 3.0])


def scalar_family(fam, p):
    """(h, h') of the four families of the scalar-bijection demonstration, with its parameter names."""
    if fam == "affine":
        a = np.exp(p["la"])
        return (lambda u: a * u + p["b"]), (lambda u: a + 0 * u)
    if fam == "nlsq":
        args = (p["a"], p["b"], p["c"], p["d"], p["e"])
        return (lambda u: nlsq(u, *args)), (lambda u: nlsq_deriv(u, *args))
    if fam == "spline":
        lh = np.array([p["h1"], p["h2"], p["h3"], p["h4"]])
        hh = np.exp(lh - lh.max())
        hh = 6 * hh / hh.sum()
        yk = np.concatenate([[-3.0], -3.0 + np.cumsum(hh)])
        yk[-1] = 3.0
        dk = np.array([1.0] + [np.exp(p["ld"])] * 3 + [1.0])
        return (lambda u: rq_eval(u, SPLINE_XK, yk, dk)[0]), (lambda u: np.exp(rq_eval(u, SPLINE_XK, yk, dk)[1]))
    if fam == "sos":
        h, dh = sos_poly(np.array([[p["a0"], p["a1"]], [p["b0"], p["b1"]]]))
        return h, dh
    raise ValueError(fam)


def pushforward_on_grid(h, dh, lim=8.0, n=1600, lo=-30.0, hi=30.0, iters=80):
    """The change-of-variables density phi(u)/|h'(u)| at u = 'h^{-1}(x)' found by bisection on a midpoint grid
    (the root bisection finds, if h is not monotone), and its Riemann-sum mass. Mirrors the demo."""
    xs = -lim + (np.arange(n) + 0.5) * (2 * lim / n)
    L = np.full(n, lo)
    H = np.full(n, hi)
    for _ in range(iters):
        mid = 0.5 * (L + H)
        up = h(mid) < xs
        L = np.where(up, mid, L)
        H = np.where(up, H, mid)
    u = 0.5 * (L + H)
    dens = np.exp(-0.5 * u * u) / np.sqrt(2 * np.pi) / np.abs(dh(u))
    return xs, dens, float(dens.sum() * (2 * lim / n))


SCALAR_PRESETS = [
    ("affine", {"la": np.log(1.5), "b": 0.5}),
    ("nlsq", {"a": 1.0, "b": 0.0, "c": 1.0, "d": 1.4, "e": -2.0}),
    ("nlsq", {"a": 0.5, "b": 0.0, "c": -2.0, "d": 1.0, "e": 0.0}),
    ("spline", {"h1": -0.5, "h2": 1.0, "h3": 1.0, "h4": -0.5, "ld": np.log(0.4)}),
    ("sos", {"a0": 0.3, "a1": 1.0, "b0": 0.5, "b1": 0.0}),
]


# =========================================================================== 23.2.3 spline coupling flow
def mlp(n_in, n_out, hidden=64, depth=2, act=nn.ReLU):
    layers, n = [], n_in
    for _ in range(depth):
        layers += [nn.Linear(n, hidden), act()]
        n = hidden
    lin = nn.Linear(n, n_out)
    nn.init.zeros_(lin.weight)          # start every layer at the identity map
    nn.init.zeros_(lin.bias)
    layers.append(lin)
    return nn.Sequential(*layers)


class SplineCouplingFlow(nn.Module):
    """Masked coupling flow (23.18) in 2-D with rational-quadratic spline bijections.

    Layer l transforms coordinate l mod 2 with a spline whose 3K-1 parameters are produced by an MLP
    of the other coordinate. forward(): base -> data (sampling); inverse(): data -> base (density)."""

    def __init__(self, n_layers=8, K=8, B=4.0, hidden=64):
        super().__init__()
        self.K, self.B, self.n_layers = K, B, n_layers
        self.nets = nn.ModuleList([mlp(1, 3 * K - 1, hidden) for _ in range(n_layers)])

    def _params(self, l, cond):
        p = self.nets[l](cond[:, None])
        K = self.K
        return p[:, :K], p[:, K:2 * K], p[:, 2 * K:]

    def forward(self, u, upto=None):
        x, ld = u.clone(), torch.zeros(len(u))
        for l in range(self.n_layers if upto is None else upto):
            a = l % 2
            W, H, D = self._params(l, x[:, 1 - a])
            y, l_ = rq_spline_t(x[:, a], W, H, D, self.B)
            x = torch.stack([y, x[:, 1]], 1) if a == 0 else torch.stack([x[:, 0], y], 1)
            ld = ld + l_
        return x, ld

    def inverse(self, x):
        u, ld = x.clone(), torch.zeros(len(x))
        for l in reversed(range(self.n_layers)):
            a = l % 2
            W, H, D = self._params(l, u[:, 1 - a])
            y, l_ = rq_spline_t(u[:, a], W, H, D, self.B, inverse=True)
            u = torch.stack([y, u[:, 1]], 1) if a == 0 else torch.stack([u[:, 0], y], 1)
            ld = ld + l_
        return u, ld

    def log_prob(self, x):
        u, ld = self.inverse(x)
        return std_normal_logpdf(u) + ld


def two_moons(n, seed, noise=0.05):
    from sklearn.datasets import make_moons
    X, _ = make_moons(n, noise=noise, random_state=seed)
    return X


def train_flow(model, sampler, steps, batch, lr, seed=0, log_every=0):
    """Maximum likelihood with Adam and a cosine learning-rate schedule; sampler(n, rng) gives data."""
    torch.manual_seed(seed)
    rng = np.random.default_rng(seed)
    opt = torch.optim.Adam(model.parameters(), lr=lr)
    sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, steps)
    hist = []
    for it in range(steps):
        x = torch.as_tensor(sampler(batch, rng))
        loss = -model.log_prob(x).mean()
        opt.zero_grad()
        loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 5.0)
        opt.step()
        sched.step()
        hist.append(loss.item())
        if log_every and it % log_every == 0:
            print("   step %d  nll %.4f" % (it, float(loss)), flush=True)
    return hist


MOONS_POOL = None


def moons_sampler(n, rng):
    global MOONS_POOL
    if MOONS_POOL is None:
        MOONS_POOL = two_moons(50000, 0)
    return MOONS_POOL[rng.integers(0, len(MOONS_POOL), n)]


def get_moons_flow():
    path = os.path.join(CACHE_DIR, "moons_nsf.pt")
    model = SplineCouplingFlow()
    if os.path.exists(path):
        model.load_state_dict(torch.load(path))
        return model
    train_flow(model, moons_sampler, steps=2500, batch=256, lr=2e-3, seed=0, log_every=500)
    torch.save(model.state_dict(), path)
    return model


# =========================================================================== 23.2.4 autoregressive flows
def cross_params(sl=1.5, ss=0.25):
    """The cross-shaped density of Figure 23.5: an equal mixture of two zero-mean Gaussians elongated
    along the two diagonals (long sd sl, short sd ss)."""
    covs = []
    for ang in (np.pi / 4, -np.pi / 4):
        R = np.array([[np.cos(ang), -np.sin(ang)], [np.sin(ang), np.cos(ang)]])
        covs.append(R @ np.diag([sl ** 2, ss ** 2]) @ R.T)
    return np.array(covs)


CROSS_COVS = cross_params()


def cross_logpdf(X):
    X = np.atleast_2d(X)
    lp = np.stack([common.gauss_logpdf(X, np.zeros(2), S) for S in CROSS_COVS]) + np.log(0.5)
    return common.logsumexp(lp, axis=0)


def cross_sample(n, rng):
    k = rng.integers(0, 2, n)
    L = [np.linalg.cholesky(S) for S in CROSS_COVS]
    Z = rng.standard_normal((n, 2))
    return np.where(k[:, None] == 0, Z @ L[0].T, Z @ L[1].T)


def cross_entropy_mc(n=400000, seed=1):
    """Monte Carlo estimate of the differential entropy of the cross density (nats)."""
    X = cross_sample(n, np.random.default_rng(seed))
    lp = cross_logpdf(X)
    return float(-lp.mean()), float(lp.std() / np.sqrt(n))


class AffineAR2D(nn.Module):
    """Affine autoregressive flow (23.22) in two dimensions, with the variable order reversed after each
    layer (this is MAF with D = 2: the conditioner of the first variable is a constant, that of the second
    an MLP of the first).

    Generative layer l, in its own order (y1, y2) = (x_{p1}, x_{p2}):
        y1 = u1 exp(alpha1) + mu1,  y2 = u2 exp(alpha2(y1)) + mu2(y1).
    """

    def __init__(self, n_layers, hidden=32):
        super().__init__()
        self.n_layers = n_layers
        self.c1 = nn.Parameter(torch.zeros(n_layers, 2))                 # (mu1, alpha1) per layer
        self.nets = nn.ModuleList([mlp(1, 2, hidden, act=nn.Tanh) for _ in range(n_layers)])

    def order(self, l):
        return (0, 1) if l % 2 == 0 else (1, 0)

    def inverse(self, x):
        """data -> base, in parallel within each layer (MAF direction); returns (u, log|det J(f^{-1})|)."""
        z, ld = x.clone(), torch.zeros(len(x))
        for l in reversed(range(self.n_layers)):
            i, j = self.order(l)
            y1, y2 = z[:, i], z[:, j]
            mu1, a1 = self.c1[l, 0], self.c1[l, 1]
            p = self.nets[l](y1[:, None])
            mu2, a2 = p[:, 0], p[:, 1]
            u1 = (y1 - mu1) * torch.exp(-a1)
            u2 = (y2 - mu2) * torch.exp(-a2)
            zn = torch.empty_like(z)
            zn[:, i], zn[:, j] = u1, u2
            z = zn
            ld = ld - a1 - a2
        return z, ld

    def forward(self, u):
        """base -> data (sequential within each layer)."""
        z = u.clone()
        for l in range(self.n_layers):
            i, j = self.order(l)
            mu1, a1 = self.c1[l, 0], self.c1[l, 1]
            y1 = z[:, i] * torch.exp(a1) + mu1
            p = self.nets[l](y1[:, None])
            y2 = z[:, j] * torch.exp(p[:, 1]) + p[:, 0]
            zn = torch.empty_like(z)
            zn[:, i], zn[:, j] = y1, y2
            z = zn
        return z

    def log_prob(self, x):
        u, ld = self.inverse(x)
        return std_normal_logpdf(u) + ld


def get_maf(n_layers):
    path = os.path.join(CACHE_DIR, "maf_cross_%d.pt" % n_layers)
    model = AffineAR2D(n_layers)
    if os.path.exists(path):
        model.load_state_dict(torch.load(path))
        return model
    train_flow(model, cross_sample, steps=4000, batch=512, lr=5e-3, seed=n_layers, log_every=1000)
    torch.save(model.state_dict(), path)
    return model


def cross_test_set(n=2000, seed=123):
    return cross_sample(n, np.random.default_rng(seed))


# =========================================================================== NLSq layers in PyTorch
def nlsq_params_t(raw):
    """Map unconstrained (..., 5) to (a, b, c, d, e) with a, d > 0 and |c| < 0.95 a / (C d): always invertible."""
    a = torch.exp(raw[..., 0])
    b = raw[..., 1]
    d = torch.exp(raw[..., 3])
    c = 0.95 * a / (C_NLSQ * d) * torch.tanh(raw[..., 2])
    e = raw[..., 4]
    return a, b, c, d, e


def nlsq_t(u, a, b, c, d, e):
    z = d * u + e
    val = a * u + b + c / (1 + z * z)
    der = a - 2 * c * d * z / (1 + z * z) ** 2
    return val, torch.log(der)


class NLSq1D(nn.Module):
    """x = f(u), a composition of n_layers NLSq maps (generative direction)."""

    def __init__(self, n_layers=4):
        super().__init__()
        self.raw = nn.Parameter(torch.zeros(n_layers, 5))

    def forward(self, u):
        x, ld = u, torch.zeros_like(u)
        for l in range(self.raw.shape[0]):
            x, d = nlsq_t(x, *nlsq_params_t(self.raw[l]))
            ld = ld + d
        return x, ld

    def numpy_params(self):
        out = []
        for l in range(self.raw.shape[0]):
            out.append([float(v) for v in nlsq_params_t(self.raw[l].detach())])
        return out


def bimodal_logpdf_t(x, m=2.0, s=0.6):
    lp = torch.stack([-0.5 * ((x - m) / s) ** 2, -0.5 * ((x + m) / s) ** 2]) - np.log(s) - 0.5 * LOG2PI + np.log(0.5)
    return torch.logsumexp(lp, 0)


def get_nlsq_1d():
    """Four NLSq layers fitted by reverse KL (the variational-inference objective of Section 23.1.2.2)
    so that the pushforward of N(0, 1) matches 0.5 N(-2, 0.6^2) + 0.5 N(2, 0.6^2)."""
    path = os.path.join(CACHE_DIR, "nlsq_1d.pt")
    model = NLSq1D(4)
    if os.path.exists(path):
        model.load_state_dict(torch.load(path))
        return model
    torch.manual_seed(3)
    with torch.no_grad():
        model.raw.add_(0.3 * torch.randn_like(model.raw))
    opt = torch.optim.Adam(model.parameters(), lr=2e-2)
    for it in range(4000):
        u = torch.randn(1024)
        x, ld = model(u)
        # reverse KL up to a constant: E_u[log N(u) - log|f'(u)| - log p*(f(u))]
        loss = (-ld - bimodal_logpdf_t(x)).mean()
        opt.zero_grad()
        loss.backward()
        opt.step()
    torch.save(model.state_dict(), path)
    return model


class NLSqAR2D(nn.Module):
    """Autoregressive flow of NLSq maps in two dimensions, written in the normalizing direction:
    in layer l (order reversed after each layer) u1 = h(y1; theta1), u2 = h(y2; Theta(y1)), with h the
    NLSq map (23.9) and Theta an MLP. The generative map is the inverse, again autoregressive."""

    def __init__(self, n_layers=5, hidden=32):
        super().__init__()
        self.n_layers = n_layers
        self.c1 = nn.Parameter(torch.zeros(n_layers, 5))
        self.nets = nn.ModuleList([mlp(1, 5, hidden, act=nn.Tanh) for _ in range(n_layers)])

    def log_prob(self, x):
        z, ld = x.clone(), torch.zeros(len(x))
        for l in range(self.n_layers):
            i, j = (0, 1) if l % 2 == 0 else (1, 0)
            y1, y2 = z[:, i], z[:, j]
            u1, d1 = nlsq_t(y1, *nlsq_params_t(self.c1[l]))
            u2, d2 = nlsq_t(y2, *nlsq_params_t(self.nets[l](y1[:, None])))
            zn = torch.empty_like(z)
            zn[:, i], zn[:, j] = u1, u2
            z = zn
            ld = ld + d1 + d2
        return std_normal_logpdf(z) + ld


MOG4_MEANS = np.array([[-1.0, -1.0], [-1.0, 1.0], [1.0, -1.0], [1.0, 1.0]])
MOG4_SD = 0.15


def mog4_sample(n, rng):
    k = rng.integers(0, 4, n)
    return MOG4_MEANS[k] + MOG4_SD * rng.standard_normal((n, 2))


def get_nlsq_ar():
    path = os.path.join(CACHE_DIR, "nlsq_ar.pt")
    model = NLSqAR2D(5)
    if os.path.exists(path):
        model.load_state_dict(torch.load(path))
        return model
    train_flow(model, mog4_sample, steps=4000, batch=512, lr=5e-3, seed=5, log_every=1000)
    torch.save(model.state_dict(), path)
    return model


# =========================================================================== AR model as a one-layer flow
def ar_as_flow(u, cond_cdf_inv):
    """Sample x_i = CDF_i^{-1}(u_i | x_{1:i-1}) sequentially (23.29); cond_cdf_inv(i, ui, xprev) -> xi."""
    u = np.atleast_2d(u)
    x = np.zeros_like(u)
    for i in range(u.shape[1]):
        x[:, i] = cond_cdf_inv(i, u[:, i], x[:, :i])
    return x


# =========================================================================== 23.2.5 residual flows
def contractive_block(D=4, L=0.7, seed=0):
    """A contractive residual block F(u) = L Q tanh(u) with Q a random orthogonal matrix.

    tanh is 1-Lipschitz with slope 1 at 0 and Q preserves norms, so Lip(F) = L exactly, and near u = 0
    the Jacobian L Q diag(sech^2 u) has all its eigenvalues of modulus close to L (a worst case)."""
    rng = np.random.default_rng(seed)
    Q, _ = np.linalg.qr(rng.standard_normal((D, D)))

    def Fn(u):
        return L * np.tanh(u) @ Q.T

    def JF(u):
        return L * Q @ np.diag(1 - np.tanh(u) ** 2)

    return Fn, JF


def fixed_point_inverse(Fn, x, n_iter=50):
    """u_{n} = x - F(u_{n-1}), u_0 = x (23.34); returns the whole sequence."""
    us = [np.array(x, float)]
    for _ in range(n_iter):
        us.append(x - Fn(us[-1]))
    return np.array(us)


def logdet_series(J, n_terms):
    """Partial sums of sum_k (-1)^{k+1} tr(J^k)/k (23.35)."""
    out, P, s = [], np.eye(len(J)), 0.0
    for k in range(1, n_terms + 1):
        P = P @ J
        s += (-1) ** (k + 1) * np.trace(P) / k
        out.append(s)
    return np.array(out)


def hutchinson_logdet(J, n_terms, n_probe, rng, rademacher=False):
    """Truncated series with each trace replaced by v^T J^k v (23.36); one estimate per probe."""
    D = len(J)
    V = rng.choice([-1.0, 1.0], (n_probe, D)) if rademacher else rng.standard_normal((n_probe, D))
    est = np.zeros(n_probe)
    W = V.copy()
    for k in range(1, n_terms + 1):
        W = W @ J.T                                     # rows: (J^k v)^T
        est += (-1) ** (k + 1) * (W * V).sum(1) / k
    return est


def russian_roulette_logdet(J, p_continue, n_rep, rng):
    """Unbiased estimate: N ~ Geometric (P(N >= k) = p^{k-1}), sum_{k<=N} (-1)^{k+1} tr(J^k)/(k P(N >= k))."""
    D = len(J)
    est = np.zeros(n_rep)
    for r in range(n_rep):
        N = 1
        while rng.random() < p_continue:
            N += 1
        P, s = np.eye(D), 0.0
        for k in range(1, N + 1):
            P = P @ J
            s += (-1) ** (k + 1) * np.trace(P) / k / p_continue ** (k - 1)
        est[r] = s
    return est


# =========================================================================== planar flow
def planar_forward(U, layers):
    """f(u) = u + v tanh(w.u + b) for each (w, v, b) in layers; returns (x, log|det J|)."""
    X = np.array(U, float)
    ld = np.zeros(len(X))
    for w, v, b in layers:
        w, v = np.asarray(w, float), np.asarray(v, float)
        a = X @ w + b
        th = np.tanh(a)
        ld += np.log(np.abs(1 + (w @ v) * (1 - th ** 2)))
        X = X + th[:, None] * v[None, :]
    return X, ld


def planar_inverse_layer(X, w, v, b, n_iter=100):
    """Exact inverse of one planar layer with w.v > -1: solve alpha + (w.v) tanh(alpha + b) = w.x by
    bisection (the left side is strictly increasing), then u = x - v tanh(alpha + b)."""
    w, v = np.asarray(w, float), np.asarray(v, float)
    wv = w @ v
    t = X @ w
    lo = t - abs(wv) - 1.0
    hi = t + abs(wv) + 1.0
    for _ in range(n_iter):
        mid = 0.5 * (lo + hi)
        up = mid + wv * np.tanh(mid + b) < t
        lo = np.where(up, mid, lo)
        hi = np.where(up, hi, mid)
    al = 0.5 * (lo + hi)
    return X - np.tanh(al + b)[:, None] * v[None, :]


def planar_logdensity(X, layers):
    """log p_x(x) for a stack of invertible planar layers and a standard normal base."""
    U = np.array(X, float)
    for w, v, b in reversed(layers):
        U = planar_inverse_layer(U, w, v, b)
    _, ld = planar_forward(U, layers)
    return std_normal_logpdf(U) - ld


PLANAR_PRESETS = [
    # (name, layers [(w, v, b)])
    ("one layer, contraction along w", [((2.0, 0.0), (-0.4, 0.0), 0.0)]),
    ("one layer, expansion (bimodal)", [((3.0, 0.0), (2.0, 0.0), 0.0)]),
    ("three layers", [((3.0, 0.0), (2.0, 0.0), 0.0), ((0.0, 3.0), (0.0, 2.0), 0.0), ((2.0, 2.0), (-0.3, 0.6), 1.0)]),
    ("non-invertible, w.v = -1.6", [((2.0, 0.0), (-0.8, 0.0), 0.0)]),
    ("two oblique layers", [((2.0, 1.0), (1.0, 0.5), -1.0), ((-1.0, 2.0), (0.5, 1.5), 0.5)]),
]


def planar_grid_mass(layers, lim=6.0, n=241):
    """Riemann sum of the change-of-variables density over [-lim, lim]^2 (n x n midpoint grid)."""
    g = np.linspace(-lim, lim, n + 1)
    c = 0.5 * (g[1:] + g[:-1])
    XX, YY = np.meshgrid(c, c)
    lp = planar_logdensity(np.c_[XX.ravel(), YY.ravel()], layers)
    return float(np.exp(lp).sum() * (g[1] - g[0]) ** 2)


# =========================================================================== 23.2.6 continuous-time flows
def ode_vector_field(seed=0, D=2):
    rng = np.random.default_rng(seed)
    W = rng.standard_normal((D, D))
    A = rng.standard_normal((D, D)) * 0.8
    b = rng.standard_normal(D)

    def Fv(x, t):
        return A @ np.tanh(W @ x + b * np.cos(t))

    def JF(x, t):
        return A @ np.diag(1 - np.tanh(W @ x + b * np.cos(t)) ** 2) @ W

    return Fv, JF


def rk4_flow_with_logdet(Fv, JF, x0, T=1.0, n=200):
    """Integrate dx/dt = F(x,t), dJ/dt = J_F J and dL/dt = tr J_F jointly with RK4.

    Returns times, path x(t), L(t) from the trace ODE (23.44) and log|det J(t)| from the variational ODE."""
    D = len(x0)
    h = T / n

    def rhs(state, t):
        x = state[:D]
        Jt = state[D:D + D * D].reshape(D, D)
        JFx = JF(x, t)
        return np.concatenate([Fv(x, t), (JFx @ Jt).ravel(), [np.trace(JFx)]])

    s = np.concatenate([x0, np.eye(D).ravel(), [0.0]])
    ts, xs, Ls, lds = [0.0], [x0.copy()], [0.0], [0.0]
    for k in range(n):
        t = k * h
        k1 = rhs(s, t)
        k2 = rhs(s + h / 2 * k1, t + h / 2)
        k3 = rhs(s + h / 2 * k2, t + h / 2)
        k4 = rhs(s + h * k3, t + h)
        s = s + h / 6 * (k1 + 2 * k2 + 2 * k3 + k4)
        ts.append(t + h)
        xs.append(s[:D].copy())
        Ls.append(s[-1])
        lds.append(np.linalg.slogdet(s[D:D + D * D].reshape(D, D))[1])
    return np.array(ts), np.array(xs), np.array(Ls), np.array(lds)


def euler_flow(Fv, x0, T=1.0, n=10):
    x = np.array(x0, float)
    h = T / n
    for k in range(n):
        x = x + h * Fv(x, k * h)
    return x


# =========================================================================== figures
def _grid(lim, n):
    g = np.linspace(-lim, lim, n)
    XX, YY = np.meshgrid(g, g)
    return g, XX, YY, np.c_[XX.ravel(), YY.ravel()]


def fig_23_1(out=None):
    """Non-linear squared flows: a 4-layer elementwise map, the induced density, a 5-layer AR flow."""
    m1 = get_nlsq_1d()
    m2 = get_nlsq_ar()
    fig, ax = panel_grid(1, 3, size=(2.7, 2.5))
    uu = torch.linspace(-5, 5, 801)
    with torch.no_grad():
        xx, _ = m1(uu)
    ax[0, 0].plot(uu.numpy(), xx.numpy(), color=BLUE)
    ax[0, 0].set_xlim(-5, 5)
    ax[0, 0].set_ylim(-5, 5)
    ax[0, 0].set_xlabel("$u$")
    ax[0, 0].set_ylabel("$x=f(u)$")
    panel_label(ax[0, 0], "a")
    rng = np.random.default_rng(0)
    u = rng.standard_normal(20000)
    with torch.no_grad():
        x, _ = m1(torch.as_tensor(u))
    bins = np.linspace(-5, 5, 81)
    ax[0, 1].hist(u, bins, density=True, color=RED, alpha=0.5, label="base $p(u)$")
    ax[0, 1].hist(x.numpy(), bins, density=True, color=BLUE, alpha=0.45, label="pushforward $p(x)$")
    t = torch.linspace(-5, 5, 400)
    ax[0, 1].plot(t, np.exp(bimodal_logpdf_t(t).numpy()), color="k", lw=0.9, ls="--", label="target")
    ax[0, 1].set_xlim(-5, 5)
    ax[0, 1].set_xlabel("$u$, $x$")
    ax[0, 1].set_ylabel("density")
    ax[0, 1].legend(fontsize=7, loc="upper right", frameon=False)
    ax[0, 1].set_ylim(0, 0.62)
    panel_label(ax[0, 1], "b")
    g, XX, YY, P = _grid(2, 161)
    with torch.no_grad():
        lp = m2.log_prob(torch.as_tensor(P)).numpy().reshape(XX.shape)
    ax[0, 2].contour(XX, YY, np.exp(lp), levels=8, cmap="viridis", linewidths=0.9)
    ax[0, 2].set_aspect("equal")
    ax[0, 2].set_xlabel("$x_1$")
    ax[0, 2].set_ylabel("$x_2$")
    panel_label(ax[0, 2], "c")
    fig.tight_layout()
    savefig(fig, CH, "fig23-1", out)


def fig_23_3(out=None):
    """Samples after each of the 8 layers of a spline coupling flow fitted to the two moons."""
    model = get_moons_flow()
    torch.manual_seed(1)
    u = torch.randn(20000, 2)
    fig, ax = panel_grid(2, 4, size=(2.3, 1.55))
    for l in range(8):
        with torch.no_grad():
            x, _ = model(u, upto=l + 1)
        a = ax[l // 4, l % 4]
        a.hist2d(x[:, 0].numpy(), x[:, 1].numpy(), bins=[90, 60], range=[[-1.6, 2.6], [-1.1, 1.6]], cmap="viridis")
        a.set_title("after layer %d of 8" % (l + 1), fontsize=8.5)
        a.set_xticks([])
        a.set_yticks([])
        a.text(0.03, 0.05, "(%s)" % "abcdefgh"[l], color="white", transform=a.transAxes, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig23-3", out)


def fig_23_5(out=None):
    """Affine autoregressive flows with 1 and 5 layers fitted to a cross-shaped density."""
    g, XX, YY, P = _grid(4, 161)
    true = np.exp(cross_logpdf(P)).reshape(XX.shape)
    X = cross_sample(3000, np.random.default_rng(7))
    fig, ax = panel_grid(1, 5, size=(2.05, 2.05))
    lev = np.linspace(true.max() / 12, true.max() * 0.95, 9)

    def dens(a, Z, title):
        a.contourf(XX, YY, Z, levels=np.r_[lev, Z.max() + 1], cmap="Reds", alpha=0.85)
        a.contour(XX, YY, Z, levels=lev, colors="#7a1010", linewidths=0.6)
        a.set_title(title, fontsize=8.5)

    dens(ax[0, 0], true, "(a) true density")
    for col, L, tag in ((1, 1, "b"), (3, 5, "c")):
        m = get_maf(L)
        with torch.no_grad():
            Z = np.exp(m.log_prob(torch.as_tensor(P)).numpy()).reshape(XX.shape)
            U, _ = m.inverse(torch.as_tensor(X))
        dens(ax[0, col], Z, "(%s) %d layer%s: $\\hat p(x)$" % (tag, L, "s" if L > 1 else ""))
        ax[0, col + 1].scatter(U[:, 0], U[:, 1], s=1.2, color=GREEN, alpha=0.5, lw=0)
        ax[0, col + 1].set_title("(%s) $u=f^{-1}(x)$" % tag, fontsize=8.5)
    for a in ax[0]:
        a.set_xlim(-4, 4)
        a.set_ylim(-4, 4)
        a.set_aspect("equal")
        a.set_xticks([])
        a.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig23-5", out)


def fig_x23_a(out=None):
    """Own figure: residual and continuous-time flows."""
    fig, ax = panel_grid(1, 3, size=(2.9, 2.4))
    rng = np.random.default_rng(0)
    for L, col in ((0.5, BLUE), (0.9, RED)):
        Fn, JF = contractive_block(4, L, seed=1)
        u_true = 0.1 * rng.standard_normal(4)
        x = u_true + Fn(u_true)
        us = fixed_point_inverse(Fn, x, 60)
        err = np.linalg.norm(us - u_true, axis=1)
        n = np.arange(len(err))
        ax[0, 0].semilogy(n, np.maximum(err, 1e-17), color=col, label="$L=%.1f$" % L)
        ax[0, 0].semilogy(n, L ** n * err[0], color=col, ls=":", lw=1)
        J = JF(u_true)
        ser = logdet_series(J, 40)
        exact = np.linalg.slogdet(np.eye(4) + J)[1]
        ax[0, 1].semilogy(np.arange(1, 41), np.maximum(np.abs(ser - exact), 1e-17), color=col, label="$L=%.1f$" % L)
        kk = np.arange(1, 41)
        bound = 4 * L ** (kk + 1) / ((kk + 1) * (1 - L))
        ax[0, 1].semilogy(kk, bound, color=col, ls=":", lw=1)
    ax[0, 0].set_xlabel("iteration $n$")
    ax[0, 0].set_ylabel("$\\|u_n-f^{-1}(x)\\|$")
    ax[0, 0].set_title("fixed-point inverse (23.34)", fontsize=9)
    ax[0, 0].legend(fontsize=7, frameon=False)
    ax[0, 1].set_xlabel("terms kept")
    ax[0, 1].set_ylabel("|error| of log det")
    ax[0, 1].set_title("power series (23.35)", fontsize=9)
    ax[0, 1].legend(fontsize=7, frameon=False)
    Fv, JFv = ode_vector_field(0)
    ts, xs, Ls, lds = rk4_flow_with_logdet(Fv, JFv, np.array([0.5, -0.3]), T=2.0, n=400)
    ax[0, 2].plot(ts, Ls, color=BLUE, label="trace ODE (23.44)")
    ax[0, 2].plot(ts[::25], lds[::25], "o", ms=3.5, color=ORANGE, label="log|det J| directly")
    ax[0, 2].set_xlabel("$t$")
    ax[0, 2].set_ylabel("$L(t)$")
    ax[0, 2].set_title("continuous-time flow", fontsize=9)
    ax[0, 2].legend(fontsize=7, frameon=False)
    for a, lab in zip(ax[0], "abc"):
        panel_label(a, lab, "lower left" if lab != "c" else "upper left")
    fig.tight_layout()
    savefig(fig, CH, "figx23-a", out)


# =========================================================================== JSON for the demos
def _r(a, nd=6):
    return np.round(np.asarray(a, float), nd).tolist()


def export_json():
    """Trained weights of the affine autoregressive flows (1 to 5 layers) and a test set, for the
    cross-density demo."""
    Xte = np.round(cross_test_set(), 4)
    H_mc, _ = cross_entropy_mc()
    true_ll = float(cross_logpdf(Xte).mean())
    models = {}
    for L in (1, 2, 3, 4, 5):
        m = get_maf(L)
        layers = []
        for l in range(L):
            net = m.nets[l]
            layers.append({
                "c1": _r(m.c1[l].detach().numpy(), 8),
                "W1": _r(net[0].weight.detach().numpy()[:, 0], 8), "b1": _r(net[0].bias.detach().numpy(), 8),
                "W2": _r(net[2].weight.detach().numpy(), 8), "b2": _r(net[2].bias.detach().numpy(), 8),
                "W3": _r(net[4].weight.detach().numpy(), 8), "b3": _r(net[4].bias.detach().numpy(), 8),
            })
        with torch.no_grad():
            ll = float(m.log_prob(torch.as_tensor(Xte)).mean())
            U, _ = m.inverse(torch.as_tensor(Xte))
        U = U.numpy()
        models[str(L)] = {"layers": layers, "test_ll": ll, "u_mean": _r(U.mean(0)), "u_cov": _r(np.cov(U.T))}
    payload = {"sl": 1.5, "ss": 0.25, "test": _r(Xte, 4), "true_test_ll": true_ll, "entropy": H_mc, "models": models}
    with open(os.path.join(DATA_OUT, "ch23-maf-cross.json"), "w") as f:
        json.dump(payload, f, separators=(",", ":"))
    print("wrote data/ch23-maf-cross.json")


FIGURES = {"23.1": fig_23_1, "23.3": fig_23_3, "23.5": fig_23_5, "x23.a": fig_x23_a}


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
