"""Wasserman (2004), Chapter 21: Smoothing Using Orthogonal Functions.

Companion code for Chapter 21 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 327-348, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch21-orthogonal-functions.html):

* Section 21.1, orthogonal functions: cos_basis (the cosine basis (21.7), counted from phi_0 = 1),
  reg_basis (the same basis counted from 1, as Section 21.3 uses it), legendre and legendre_onb (the
  Legendre polynomials by the recursion (21.10), and their orthonormal versions), cos_coefs (the
  coefficients beta_j of a function, computed with a fine midpoint rule written as a discrete cosine
  transform) and doppler (the test function of Example 21.2).
* Section 21.2, density estimation: density_series (beta_hat (21.11), sigma_hat_j^2 (21.17), the risk
  estimate (21.16), the choice of J, the estimate and the band (21.18)-(21.19)), density_true_risk (the
  risk (21.15) of a known density) and the samplers claw_sample_js and beta_sample_js (the Bart Simpson
  density of Example 21.7 and the Beta(15, 4) density of Exercise 21.10, drawn with the browser demos'
  generator).
* Section 21.3, regression: reg_series (beta_hat (21.23), sigma_hat^2 (21.26), the risk estimate
  (21.27) and the choice of J), reg_fit, reg_band (Theorem 21.11) and reg_true_risk ((21.25)).
* Section 21.4 and the appendix, Haar wavelets: haar_psi and haar_phi (21.30)-(21.32), haar_dwt (the
  discrete wavelet transform of the appendix), haar_idwt (its inverse), haar_direct (the coefficients
  (21.35) summed directly, to confirm the transform), haar_threshold (universal hard or soft
  thresholding (21.36) with the noise level (21.37)), haar_projection (the resolution-J
  approximation (21.34) of a function) and noise_survival (Theorem 21.15 by simulation).
* soft_risk, hard_risk: the risk of soft and hard thresholding of one Normal observation, used for the
  oracle inequality of the notes.
* JSRandom, js_uniforms and js_normals: the seeded generator of the browser demonstrations (DK.rng in
  courses/demo-kit.js), so that the simulations on the pages can be reproduced here number for number.

All eight figures of the chapter are computed from a function, a model or a simulation, and all are
reproduced: 21.1 (the cosine basis), 21.2 (cosine approximations of the doppler function), 21.3 (the
Bart Simpson density and its estimate with a 95% band), 21.4 (doppler data and the cosine estimate),
21.5 (confidence bands with J chosen by the risk estimate and with J = 45), 21.6 (two Haar wavelets),
21.7 (Haar approximations of the doppler function) and 21.8 (universal thresholding of doppler data).
Nothing is skipped. The simulated figures use their own random draws, so the chosen J differs from the
book's 234 (any one sample gives a different value).
Twelve supplementary figures illustrate the gaps filled in the notes and the exercises:
  21.S1 the Legendre polynomials and their Gram matrix (Exercise 21.5);
  21.S2 smoothness and the decay of the cosine coefficients;
  21.S3 the risk estimate (21.16) against the true risk, Bart Simpson density;
  21.S4 the risk estimate (21.27) against the true risk, doppler regression;
  21.S5 how conservative the two confidence bands are (simulation);
  21.S6 Theorem 21.15: the chance that pure noise survives the universal threshold;
  21.S7 the risk of soft and hard thresholding and the oracle bound;
  21.S8 Exercises 21.6 and 21.12: partial sums in the cosine and Haar bases;
  21.S9 Exercise 21.7: the glass data;
  21.S10 Exercise 21.9: cosine bands for J = 10, ..., 100 and the Haar fit;
  21.S11 Exercise 21.10: the Haar histogram with B chosen by leave-one-out cross-validation;
  21.S12 Exercise 21.11: the median absolute deviation against the standard deviation.
Run `python3 ch21_orthogonal_functions.py --list`, `python3 ch21_orthogonal_functions.py` (the JSON file
and all twenty figures, about two minutes on one CPU thread, most of it for Figure 21.S5) or `python3 ch21_orthogonal_functions.py --fig 21.5`.
Files go to ../img/ch21/. The data used by the demonstrations go to ../data/ch21-data.json (export_json).
"""
import json
import math
import os

import numpy as np
from scipy import fft as sfft
from scipy import stats

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig

CH = 21
HERE = os.path.dirname(os.path.abspath(__file__))
M32 = 0xFFFFFFFF

# seeds shared with the browser demonstrations
SEED_DENS = 2107      # cosine-density-demo.html (sample of size n uses DK.rng(SEED_DENS))
SEED_REG = 2110       # cosine-regression-band-demo.html
SEED_HAAR = 2116      # haar-multiresolution-demo.html


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32, norm() the Box-Muller transform that returns r cos(t) and keeps r sin(t) for the next
    call, and exp(mean) = -mean log(U) with U > 0, exactly as in JavaScript."""

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self.pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def exp(self, mean=1.0):
        return -mean * math.log(self.pos())


def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed), vectorised (mulberry32 adds a constant
    to its state at each call, so the j-th output is a hash of seed + j * 0x6D2B79F5 mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


def js_normals(seed, n):
    """The first n values of DK.rng(seed).norm() (Box-Muller pairs: cos first, then the cached sin)."""
    npair = (n + 1) // 2
    u = js_uniforms(seed, 2 * npair)
    u1, u2 = u[0::2], u[1::2]
    if np.any(u1 == 0.0):
        raise RuntimeError("a zero uniform: use JSRandom for this stream")
    r = np.sqrt(-2.0 * np.log(u1))
    th = 2.0 * np.pi * u2
    out = np.empty(2 * npair)
    out[0::2] = r * np.cos(th)
    out[1::2] = r * np.sin(th)
    return out[:n]


# =========================================================================== 21.1 orthogonal functions
def doppler(x):
    """The doppler function of Example 21.2: sqrt(x(1 - x)) sin(2.1 pi / (x + 0.05))."""
    x = np.asarray(x, dtype=float)
    return np.sqrt(x * (1 - x)) * np.sin(2.1 * np.pi / (x + 0.05))


def cos_basis(x, J):
    """Matrix [phi_0(x), ..., phi_{J-1}(x)] of the cosine basis (21.7): phi_0 = 1, phi_j = sqrt(2) cos(j pi x)."""
    x = np.asarray(x, dtype=float)
    j = np.arange(J)
    B = np.sqrt(2.0) * np.cos(np.pi * np.outer(x, j))
    B[:, 0] = 1.0
    return B


def reg_basis(x, J):
    """The cosine basis counted from 1, as in Section 21.3: phi_1 = 1, phi_j = sqrt(2) cos((j - 1) pi x)."""
    return cos_basis(x, J)


def cos_coefs(f, J, N=2 ** 18):
    """beta_0, ..., beta_{J-1} of f in the cosine basis, by the midpoint rule on N points.

    With x_m = (m + 1/2)/N the midpoint sum (1/N) sum_m f(x_m) sqrt(2) cos(j pi x_m) is exactly a
    type-II discrete cosine transform, so all coefficients cost one FFT."""
    x = (np.arange(N) + 0.5) / N
    y = sfft.dct(f(x), type=2)            # y_j = 2 sum_m f(x_m) cos(pi j (2m + 1) / (2N))
    b = y[:J] / (2.0 * N) * np.sqrt(2.0)
    b[0] = y[0] / (2.0 * N)
    return b


def legendre(x, J):
    """P_0(x), ..., P_{J-1}(x) by the three-term recursion (21.10)."""
    x = np.asarray(x, dtype=float)
    P = np.empty((x.size, J))
    P[:, 0] = 1.0
    if J > 1:
        P[:, 1] = x
    for j in range(1, J - 1):
        P[:, j + 1] = ((2 * j + 1) * x * P[:, j] - j * P[:, j - 1]) / (j + 1)
    return P


def legendre_onb(x, J):
    """The orthonormal Legendre basis sqrt((2j + 1)/2) P_j(x) of L2(-1, 1)."""
    return legendre(x, J) * np.sqrt((2 * np.arange(J) + 1) / 2.0)


# =========================================================================== 21.2 density estimation
def claw_g(x):
    """The claw (Bart Simpson) density of Marron and Wand (1992) on the real line:
    (1/2) N(0, 1) + sum_{l=0}^{4} (1/10) N(l/2 - 1, 0.1^2). (The book's weights 5/6 and 1/6 add to 10/6.)"""
    x = np.asarray(x, dtype=float)
    g = 0.5 * stats.norm.pdf(x)
    for mu in (-1.0, -0.5, 0.0, 0.5, 1.0):
        g += 0.1 * stats.norm.pdf(x, mu, 0.1)
    return g


CLAW_MASS = 0.5 * (stats.norm.cdf(3) - stats.norm.cdf(-3)) + 0.5   # mass of [-3, 3] (spikes: all of it)


def claw_pdf(y):
    """The claw rescaled to [0, 1] by y = (x + 3)/6, as in Example 21.7, and conditioned on [0, 1]."""
    y = np.asarray(y, dtype=float)
    out = 6.0 * claw_g(6.0 * y - 3.0) / CLAW_MASS
    return np.where((y >= 0) & (y <= 1), out, 0.0)


def claw_sample_js(seed, n):
    """n draws from claw_pdf with DK.rng(seed): per draw one uniform picks the component (below 0.5 the
    wide Normal, otherwise spike floor((u - 0.5)/0.1)), one Normal gives the value; draws outside
    [0, 1] are rejected. Identical to the sampler of cosine-density-demo.html."""
    g = JSRandom(seed)
    out = []
    while len(out) < n:
        u = g.u()
        z = g.norm()
        if u < 0.5:
            x = z
        else:
            k = min(int((u - 0.5) / 0.1), 4)
            x = (k / 2.0 - 1.0) + 0.1 * z
        y = (x + 3.0) / 6.0
        if 0.0 <= y <= 1.0:
            out.append(y)
    return np.array(out)


def beta_sample_js(seed, n, a=15, b=4):
    """n draws from Beta(a, b) (integer a, b) with DK.rng(seed): G1/(G1 + G2) with G1, G2 sums of a and
    b standard exponentials. Identical to the sampler of cosine-density-demo.html."""
    g = JSRandom(seed)
    out = np.empty(n)
    for i in range(n):
        g1 = sum(g.exp() for _ in range(a))
        g2 = sum(g.exp() for _ in range(b))
        out[i] = g1 / (g1 + g2)
    return out


def density_series(X, p=None, alpha=0.05, J=None):
    """Orthogonal series density estimate on [0, 1] (summary box of Section 21.2).

    beta_hat_j = mean phi_j(X_i), j = 1..p (21.11) with p = floor(sqrt(n)); sigma_hat_j^2 (21.17);
    Rhat(J) (21.16) for J = 1..p; the minimiser Jhat (or the J given); the band half-width
    c = K^2 sqrt(J chi^2_{J,alpha} / n) of (21.19) with K = sqrt(2); and the corrected half-width
    c2 = K sqrt(J lambda_max chi^2_{J,alpha} / n) that uses the largest eigenvalue of the estimated
    covariance matrix of (phi_1(X), ..., phi_J(X)) (see the notes). The estimate is
    fhat(x) = 1 + sum_{j <= J} beta_hat_j phi_j(x), since beta_0 = 1 for every density on [0, 1]."""
    X = np.asarray(X, dtype=float)
    n = X.size
    if p is None:
        p = int(math.floor(math.sqrt(n)))
    Phi = cos_basis(X, p + 1)[:, 1:]                # phi_1..phi_p at the data
    bh = Phi.mean(0)
    s2 = Phi.var(0, ddof=1)
    Js = np.arange(1, p + 1)
    cum_var = np.cumsum(s2) / n
    gain = np.maximum(bh ** 2 - s2 / n, 0.0)
    tail = np.concatenate([np.cumsum(gain[::-1])[::-1][1:], [0.0]])   # sum_{j=J+1}^{p}
    Rhat = cum_var + tail
    Jhat = int(Js[np.argmin(Rhat)])
    Juse = Jhat if J is None else int(J)
    chi2 = stats.chi2.ppf(1 - alpha, Juse)
    K = math.sqrt(2.0)
    c = K ** 2 * math.sqrt(Juse * chi2 / n)
    S = np.cov(Phi[:, :Juse], rowvar=False, ddof=1).reshape(Juse, Juse)
    lmax = float(np.linalg.eigvalsh(S)[-1])
    c2 = K * math.sqrt(Juse * lmax * chi2 / n)
    return dict(n=n, p=p, beta=bh, s2=s2, Rhat=Rhat, Jhat=Jhat, J=Juse, c=c, c2=c2, lmax=lmax, chi2=chi2)


def density_eval(fit, x, J=None):
    J = fit["J"] if J is None else J
    return 1.0 + cos_basis(x, J + 1)[:, 1:] @ fit["beta"][:J]


def density_truth(f, jmax=400, N=2 ** 18):
    """beta_j and sigma_j^2 = 1 + beta_{2j}/sqrt(2) - beta_j^2 of a density f on [0, 1], j = 0..jmax."""
    b = cos_coefs(f, 2 * jmax + 2, N)
    j = np.arange(jmax + 1)
    s2 = 1.0 + b[2 * j] / np.sqrt(2.0) - b[j] ** 2
    s2[0] = 0.0
    return b[: jmax + 1], s2


def density_true_risk(f, n, Jmax, jmax=400):
    """R(J) of (21.15) for J = 1..Jmax: sum_{j<=J} sigma_j^2/n + sum_{j>J} beta_j^2 (the tail from
    ||f||^2 - sum_{j<=J} beta_j^2, by Parseval)."""
    b, s2 = density_truth(f, jmax)
    x = (np.arange(2 ** 18) + 0.5) / 2 ** 18
    norm2 = float(np.mean(f(x) ** 2))
    J = np.arange(1, Jmax + 1)
    var = np.cumsum(s2[1:Jmax + 1]) / n
    tail = norm2 - np.cumsum(b[: Jmax + 1] ** 2)[1:]
    return J, var + tail


# =========================================================================== 21.3 regression
def cos_table_mat(n, m):
    """cos(pi * m_j * i / n) for i = 1..n (rows) and the frequencies m (columns), with the angle reduced
    exactly modulo 2 pi first (m i mod 2n), as the browser demo does."""
    i = np.arange(1, n + 1)
    k = np.mod(np.outer(i, m), 2 * n)
    return np.cos(np.pi * k / n)


def reg_series(Y, x=None, k=None, alpha=0.05):
    """Orthogonal series regression on x_i = i/n (box of Section 21.3).

    beta_hat_j = (1/n) sum_i Y_i phi_j(x_i), j = 1..n (21.23), with phi_1 = 1 and
    phi_j = sqrt(2) cos((j - 1) pi x); sigma_hat^2 = (n/k) sum_{j=n-k+1}^{n} beta_hat_j^2 (21.26),
    k = n // 4; Rhat(J) (21.27) for J = 1..n and its minimiser."""
    Y = np.asarray(Y, dtype=float)
    n = Y.size
    if x is None:
        C = cos_table_mat(n, np.arange(n))
        Phi = np.sqrt(2.0) * C
        Phi[:, 0] = 1.0
    else:
        Phi = reg_basis(x, n)
    bh = Phi.T @ Y / n
    if k is None:
        k = n // 4
    s2 = n / k * float(np.sum(bh[n - k:] ** 2))
    gain = np.maximum(bh ** 2 - s2 / n, 0.0)
    tail = np.concatenate([np.cumsum(gain[::-1])[::-1][1:], [0.0]])
    Js = np.arange(1, n + 1)
    Rhat = Js * s2 / n + tail
    Jhat = int(Js[np.argmin(Rhat)])
    return dict(n=n, k=k, beta=bh, s2=s2, sigma=math.sqrt(s2), Rhat=Rhat, Jhat=Jhat, alpha=alpha)


def reg_fit(fit, x, J=None):
    J = fit["Jhat"] if J is None else J
    return reg_basis(x, J) @ fit["beta"][:J]


def reg_band(fit, x, J=None, alpha=0.05):
    """Half-width c(x) = a(x) sigma_hat chi_{J,alpha} / sqrt(n) of Theorem 21.11, a(x)^2 = sum_{j<=J} phi_j(x)^2."""
    J = fit["Jhat"] if J is None else J
    a = np.sqrt(np.sum(reg_basis(x, J) ** 2, axis=1))
    chi = math.sqrt(stats.chi2.ppf(1 - alpha, J))
    return a * fit["sigma"] * chi / math.sqrt(fit["n"])


_DOP_COEF = None


def doppler_coefs(jmax=4096):
    """beta_0..beta_{jmax-1} of the doppler function (cos_coefs on 2^20 points: the function oscillates
    fast near 0) and its squared norm."""
    global _DOP_COEF
    if _DOP_COEF is None or _DOP_COEF[0].size < jmax:
        N = 2 ** 20
        b = cos_coefs(doppler, jmax, N)
        x = (np.arange(N) + 0.5) / N
        _DOP_COEF = (b, float(np.mean(doppler(x) ** 2)))
    return _DOP_COEF[0][:jmax], _DOP_COEF[1]


def reg_true_risk(beta, norm2, n, sigma, Jmax):
    """R(J) = J sigma^2/n + sum_{j>J} beta_j^2 (21.25), J = 1..Jmax, beta counted from 1 (beta[0] is the
    constant term)."""
    J = np.arange(1, Jmax + 1)
    return J, J * sigma ** 2 / n + (norm2 - np.cumsum(beta[:Jmax] ** 2))


def doppler_data(n, sigma, seed):
    """Y_i = doppler(i/n) + sigma eps_i with eps from DK.rng(seed).norm(), as in the browser demos."""
    x = np.arange(1, n + 1) / n
    return x, doppler(x) + sigma * js_normals(seed, n)


# =========================================================================== 21.4 Haar wavelets
def haar_phi(x):
    """Father wavelet (21.30), taken on (0, 1] so that the sampled version at x_i = i/n matches the
    discrete transform of the appendix (the endpoint convention is immaterial in L2)."""
    x = np.asarray(x, dtype=float)
    return ((x > 0) & (x <= 1)).astype(float)


def haar_psi(x, j=0, k=0):
    """psi_{j,k}(x) = 2^{j/2} psi(2^j x - k) (21.32), with psi = -1 on (0, 1/2] and +1 on (1/2, 1] (21.31)."""
    t = 2.0 ** j * np.asarray(x, dtype=float) - k
    return 2.0 ** (j / 2.0) * (np.where((t > 0) & (t <= 0.5), -1.0, 0.0) + np.where((t > 0.5) & (t <= 1), 1.0, 0.0))


def haar_dwt(y):
    """The discrete Haar transform of the appendix: returns (alpha_hat, [D_0, ..., D_{J-1}]) with D_j of
    length 2^j, equal to (21.35): alpha_hat = (1/n) sum y_i and D_{j,k} = (1/n) sum psi_{j,k}(x_i) y_i."""
    y = np.asarray(y, dtype=float)
    n = y.size
    J = int(round(math.log2(n)))
    assert 2 ** J == n, "n must be a power of 2"
    temp = y / math.sqrt(n)
    D = [None] * J
    for j in range(J - 1, -1, -1):
        odd, even = temp[0::2], temp[1::2]        # temp[2I - 1] and temp[2I] in the book's 1-based R code
        D[j] = (even - odd) / math.sqrt(2.0)
        temp = (even + odd) / math.sqrt(2.0)
    return float(temp[0]), D


def haar_idwt(alpha, D):
    """Inverse of haar_dwt: the values sum alpha phi(x_i) + sum D_{j,k} psi_{j,k}(x_i), i = 1..n."""
    temp = np.array([alpha])
    for j in range(len(D)):
        out = np.empty(2 * temp.size)
        out[0::2] = (temp - D[j]) / math.sqrt(2.0)
        out[1::2] = (temp + D[j]) / math.sqrt(2.0)
        temp = out
    return temp * math.sqrt(temp.size)


def haar_direct(y):
    """(21.35) summed directly over the sampled Haar functions (O(n^2); used to confirm haar_dwt)."""
    y = np.asarray(y, dtype=float)
    n = y.size
    J = int(round(math.log2(n)))
    x = np.arange(1, n + 1) / n
    alpha = float(np.mean(haar_phi(x) * y))
    D = [np.array([np.mean(haar_psi(x, j, k) * y) for k in range(2 ** j)]) for j in range(J)]
    return alpha, D


def mad_sigma(D, n):
    """(21.37): sqrt(n) median(|D_{J-1,k}|) / 0.6745."""
    return math.sqrt(n) * float(np.median(np.abs(D[-1]))) / 0.6745


def haar_threshold(y, rule="hard", sigma=None, lam=None, j0=0):
    """Haar wavelet regression (box of Section 21.4): DWT, noise level (21.37) unless sigma is given,
    universal threshold lambda = sigma sqrt(2 log n / n) (21.36) unless lam is given, hard or soft
    thresholding of D_{j,k} for j >= j0 (coarser levels are kept), inverse DWT."""
    y = np.asarray(y, dtype=float)
    n = y.size
    a, D = haar_dwt(y)
    s = mad_sigma(D, n) if sigma is None else sigma
    lam = s * math.sqrt(2 * math.log(n) / n) if lam is None else lam
    Dt, kept = [], 0
    for j, d in enumerate(D):
        if j < j0:
            Dt.append(d.copy())
            kept += d.size
            continue
        keep = np.abs(d) > lam
        kept += int(keep.sum())
        Dt.append(np.where(keep, d if rule == "hard" else np.sign(d) * (np.abs(d) - lam), 0.0))
    return dict(fit=haar_idwt(a, Dt), sigma=s, lam=lam, kept=kept, alpha=a, D=D, Dt=Dt)


def haar_projection(f, J, N=2 ** 20):
    """The resolution-J approximation (21.34) of f on [0, 1]: f averaged over each dyadic interval of
    length 2^-J (fine midpoint rule). Returns the 2^J block averages."""
    x = (np.arange(N) + 0.5) / N
    return f(x).reshape(2 ** J, -1).mean(1)


def noise_survival(n, R, seed0, sigma_known=True, rule_sigma=1.0):
    """Theorem 21.15 by simulation: pure noise y_i = eps_i (sigma = 1), replication r drawn from
    DK.rng(seed0 + r); returns the number of replications in which at least one of the n - 1 detail
    coefficients exceeds the universal threshold (sigma known, or estimated by (21.37))."""
    hits = 0
    for r in range(R):
        y = rule_sigma * js_normals(seed0 + r, n)
        a, D = haar_dwt(y)
        s = rule_sigma if sigma_known else mad_sigma(D, n)
        lam = s * math.sqrt(2 * math.log(n) / n)
        if max(float(np.max(np.abs(d))) for d in D) > lam:
            hits += 1
    return hits


def soft_risk(lam, mu):
    """E(eta_S(X) - mu)^2 for X ~ N(mu, 1) and soft thresholding at lam (closed form)."""
    mu = np.asarray(mu, dtype=float)
    a, b = lam - mu, -lam - mu          # X - mu > a  <=>  X > lam ; X - mu < b <=> X < -lam
    pdf, cdf = stats.norm.pdf, stats.norm.cdf
    # |X| <= lam contributes mu^2 P(b <= Z <= a); X > lam contributes E(Z - lam)^2 1{Z > a};
    # X < -lam contributes E(Z + lam)^2 1{Z < b} (Z = X - mu)
    mid = mu ** 2 * (cdf(a) - cdf(b))
    up = (1 + lam ** 2) * stats.norm.sf(a) + (a - 2 * lam) * pdf(a)
    lo = (1 + lam ** 2) * cdf(b) - (2 * lam + b) * pdf(b)
    return mid + up + lo


def hard_risk(lam, mu):
    """E(eta_H(X) - mu)^2 for X ~ N(mu, 1) and hard thresholding at lam (closed form)."""
    mu = np.asarray(mu, dtype=float)
    a, b = lam - mu, -lam - mu
    pdf, cdf = stats.norm.pdf, stats.norm.cdf
    mid = mu ** 2 * (cdf(a) - cdf(b))
    tails = stats.norm.sf(a) + a * pdf(a) + cdf(b) - b * pdf(b)    # E Z^2 1{Z > a} + E Z^2 1{Z < b}
    return mid + tails


# =========================================================================== data
def faithful_eruptions():
    d = common.aos_data("faithful.dat", sep=r"\s+", engine="python", skiprows=23)
    return d["eruptions"].to_numpy(dtype=float)


FAITH_LO, FAITH_HI = 1.5, 5.5         # eruptions (minutes) are mapped to [0, 1] by (x - 1.5)/4


def glass():
    d = common.aos_data("glass.dat")
    return d["Al"].to_numpy(dtype=float), d["RI"].to_numpy(dtype=float)


def glass_sorted():
    al, ri = glass()
    o = np.lexsort((ri, al))
    return al[o], ri[o]


def reflect_pad(y, m):
    """Extend y to length m by mirror reflection at the right end (for the Haar transform)."""
    y = np.asarray(y, dtype=float)
    out = np.concatenate([y, y[::-1]])
    while out.size < m:
        out = np.concatenate([out, out[::-1]])
    return out[:m]


# =========================================================================== figures
def _clean(ax):
    ax.set_xticks([])
    ax.set_yticks([])


def fig_21_1(out_dir=None):
    """The first six functions of the cosine basis."""
    fig, axes = common.panel_grid(3, 2, size=(2.6, 1.5))
    x = np.linspace(0, 1, 801)
    B = cos_basis(x, 6)
    for j in range(6):
        ax = axes[j // 2, j % 2]
        ax.plot(x, B[:, j], color="k", lw=1.3)
        ax.set_ylim(-1.6, 1.6)
        ax.set_xlim(0, 1)
        ax.set_title(r"$\phi_%d$" % j, fontsize=10, pad=2)
        ax.set_yticks([-1.41, 0, 1.41])
        ax.set_yticklabels([r"$-\sqrt{2}$", "0", r"$\sqrt{2}$"] if j % 2 == 0 else [])
        ax.set_xticks([0, 0.5, 1] if j >= 4 else [])
    fig.tight_layout()
    return savefig(fig, CH, "fig21-1", out_dir)


def fig_21_2(out_dir=None):
    """The doppler function and its cosine approximations with J = 5, 20, 200 terms."""
    b, _ = doppler_coefs()
    x = np.linspace(0.0005, 1, 4001)
    fig, axes = common.panel_grid(2, 2, size=(3.0, 2.0))
    panels = [("$f$", doppler(x))] + [("$J = %d$" % J, cos_basis(x, J) @ b[:J]) for J in (5, 20, 200)]
    for ax, (lab, y) in zip(axes.flat, panels):
        ax.plot(x, y, color="k", lw=0.8)
        ax.set_ylim(-0.6, 0.6)
        ax.set_xlim(0, 1)
        ax.text(0.97, 0.94, lab, transform=ax.transAxes, ha="right", va="top")
    fig.tight_layout()
    return savefig(fig, CH, "fig21-2", out_dir)


def claw_fit(n=5000, seed=SEED_DENS):
    X = claw_sample_js(seed, n)
    return X, density_series(X)


def fig_21_3(out_dir=None):
    """The Bart Simpson density (top) and its orthogonal series estimate with a 95% band, n = 5000."""
    X, fit = claw_fit()
    x = np.linspace(0, 1, 1001)
    fh = density_eval(fit, x)
    fig, axes = common.panel_grid(2, 1, size=(5.6, 2.3))
    ax = axes[0, 0]
    ax.plot(x, claw_pdf(x), color="k", lw=1.3)
    ax.set_ylim(0, 4.2)
    ax.set_ylabel("true density")
    ax = axes[1, 0]
    ax.fill_between(x, fh - fit["c"], fh + fit["c"], color=BLUE, alpha=0.15, lw=0, label="95% band (21.18)")
    ax.plot(x, fh, color=BLUE, lw=1.4, label=r"estimate, $\hat J = %d$" % fit["J"])
    ax.plot(x, claw_pdf(x), color="k", lw=0.8, ls="--", label="true density")
    ax.set_ylim(-1.2, 5.2)
    ax.set_ylabel("estimate")
    ax.legend(loc="upper left", frameon=False, fontsize=8.5)
    for a in axes[:, 0]:
        a.set_xlim(0, 1)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-3", out_dir)


def doppler_example(n=2048, sigma=0.1, seed=SEED_REG):
    x, Y = doppler_data(n, sigma, seed)
    return x, Y, reg_series(Y)


def fig_21_4(out_dir=None):
    """Doppler data (n = 2048, sigma = 0.1) and the cosine estimate with J chosen by the risk estimate."""
    x, Y, fit = doppler_example()
    xx = np.linspace(0.0005, 1, 4001)
    fig, axes = common.panel_grid(1, 2, size=(3.2, 2.5))
    axes[0, 0].plot(x, Y, ".", ms=1.6, color=GREY)
    axes[0, 0].plot(xx, doppler(xx), color="k", lw=0.8)
    axes[0, 0].set_title("data and the doppler function")
    axes[0, 1].plot(xx, reg_fit(fit, xx), color=BLUE, lw=0.8)
    axes[0, 1].set_title(r"estimate, $\hat J = %d$ terms" % fit["Jhat"])
    for ax in axes[0]:
        ax.set_xlim(0, 1)
        ax.set_ylim(-0.75, 0.75)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-4", out_dir)


def fig_21_5(out_dir=None):
    """Estimates and 95% bands (Theorem 21.11) with J chosen by the risk estimate and with J = 45."""
    x, Y, fit = doppler_example()
    xx = np.linspace(0.0005, 1, 4001)
    fig, axes = common.panel_grid(1, 2, size=(3.2, 2.6))
    for ax, J in zip(axes[0], (fit["Jhat"], 45)):
        r = reg_fit(fit, xx, J)
        c = reg_band(fit, xx, J)
        ax.fill_between(xx, r - c, r + c, color=BLUE, alpha=0.18, lw=0)
        ax.plot(xx, r, color=BLUE, lw=0.7)
        ax.plot(xx, r - c, color=BLUE, lw=0.4)
        ax.plot(xx, r + c, color=BLUE, lw=0.4)
        ax.set_title(r"$J = %d$, half-width about %.2f" % (J, float(np.median(c))))
        ax.set_xlim(0, 1)
        ax.set_ylim(-1.3, 1.3)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-5", out_dir)


def fig_21_6(out_dir=None):
    """The mother Haar wavelet psi and psi_{2,2}."""
    x = np.linspace(-0.2, 1.2, 2801)
    fig, axes = common.panel_grid(1, 2, size=(2.8, 2.2))
    for ax, (j, k, lab) in zip(axes[0], ((0, 0, r"$\psi(x)$"), (2, 2, r"$\psi_{2,2}(x)$"))):
        y = haar_psi(x, j, k)
        ax.step(x, y, where="post", color="k", lw=1.3)
        ax.axhline(0, color=GREY, lw=0.5)
        ax.set_ylim(-2.3, 2.3)
        ax.set_xlim(-0.2, 1.2)
        ax.set_title(lab)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-6", out_dir)


def fig_21_7(out_dir=None):
    """The doppler function and its Haar approximations at resolution J = 3, 5, 8."""
    x = np.linspace(0.0005, 1, 4001)
    fig, axes = common.panel_grid(2, 2, size=(3.0, 2.0))
    axes[0, 0].plot(x, doppler(x), color="k", lw=0.8)
    axes[0, 0].text(0.97, 0.94, "$f$", transform=axes[0, 0].transAxes, ha="right", va="top")
    for ax, J in zip(axes.flat[1:], (3, 5, 8)):
        v = haar_projection(doppler, J)
        edges = np.arange(2 ** J + 1) / 2 ** J
        ax.stairs(v, edges, color="k", lw=0.9)
        ax.text(0.97, 0.94, "$J = %d$" % J, transform=ax.transAxes, ha="right", va="top")
    for ax in axes.flat:
        ax.set_xlim(0, 1)
        ax.set_ylim(-0.55, 0.55)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-7", out_dir)


def haar_example(n=2048, sigma=0.1, seed=SEED_HAAR):
    x, Y = doppler_data(n, sigma, seed)
    return x, Y, haar_threshold(Y)


def fig_21_8(out_dir=None):
    """Doppler data and the Haar estimate with universal hard thresholding (n = 2048, sigma = 0.1)."""
    x, Y, h = haar_example()
    fig, axes = common.panel_grid(1, 2, size=(3.2, 2.5))
    axes[0, 0].plot(x, Y, ".", ms=1.6, color=GREY)
    axes[0, 0].set_title("data")
    axes[0, 0].set_ylim(-0.8, 0.8)
    edges = np.arange(x.size + 1) / x.size
    axes[0, 1].stairs(h["fit"], edges, color=BLUE, lw=0.8)
    axes[0, 1].set_title("estimate: %d coefficients kept" % h["kept"])
    axes[0, 1].set_ylim(-0.55, 0.55)
    for ax in axes[0]:
        ax.set_xlim(0, 1)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-8", out_dir)


# --------------------------------------------------------------------------- supplementary figures
def fig_21_s1(out_dir=None):
    """Exercise 21.5: the first five Legendre polynomials and the Gram matrix of the orthonormal versions."""
    x = np.linspace(-1, 1, 801)
    P = legendre(x, 5)
    fig, axes = common.panel_grid(1, 2, size=(3.2, 2.7))
    cols = ["k", RED, BLUE, GREEN, PURPLE]
    for j in range(5):
        axes[0, 0].plot(x, P[:, j], color=cols[j], lw=1.3, label="$P_%d$" % j)
    axes[0, 0].legend(frameon=False, fontsize=8, ncol=5, loc="upper center", handlelength=1.2, columnspacing=0.8)
    axes[0, 0].set_ylim(-1.1, 1.55)
    axes[0, 0].set_title("Legendre polynomials (21.10)")
    from numpy.polynomial.legendre import leggauss
    t, w = leggauss(40)
    Q = legendre_onb(t, 5)
    G = (Q * w[:, None]).T @ Q
    ax = axes[0, 1]
    ax.imshow(G, cmap="Blues", vmin=0, vmax=1)
    for i in range(5):
        for j in range(5):
            ax.text(j, i, "%.0f" % abs(G[i, j]) if abs(G[i, j]) > 1e-12 else "0", ha="center", va="center",
                    color="white" if G[i, j] > 0.5 else "k", fontsize=9)
    ax.set_xticks(range(5))
    ax.set_yticks(range(5))
    ax.set_title("Gram matrix of $\\sqrt{(2j+1)/2}\\,P_j$\n(largest error %.0e)" % np.max(np.abs(G - np.eye(5))), fontsize=9.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S1", out_dir)


def fig_21_s2(out_dir=None):
    """Smoothness and decay: |beta_j| of four functions in the cosine basis."""
    funcs = [("jump: $1\\{x>0.3\\}$", lambda x: (x > 0.3).astype(float), RED),
             ("kink: $|x-0.3|$", lambda x: np.abs(x - 0.3), BLUE),
             ("smooth: $e^{-(x-0.3)^2/0.02}$", lambda x: np.exp(-(x - 0.3) ** 2 / 0.02), GREEN),
             ("doppler", doppler, "k")]
    fig, axes = common.panel_grid(1, 1, size=(5.2, 3.2))
    ax = axes[0, 0]
    j = np.arange(1, 2049).astype(float)
    for lab, f, col in funcs:
        b = cos_coefs(f, 2049, 2 ** 20)[1:]
        # envelope: maximum over blocks of 8 consecutive j, which hides the zeros of the oscillation
        env = np.maximum.accumulate(np.abs(b)[::-1])[::-1]
        ax.loglog(j, env, color=col, lw=1.3, label=lab)
    for p, ls in ((1, ":"), (2, "--")):
        ax.loglog(j, 0.4 * j ** (-p), color=GREY, ls=ls, lw=0.9)
        ax.text(1300, 0.4 * 1300 ** (-p) * 1.6, "$j^{-%d}$" % p, color=GREY, fontsize=9)
    ax.set_ylim(1e-9, 1)
    ax.set_xlabel("$j$")
    ax.set_ylabel(r"$\max_{i\geq j}|\beta_i|$")
    ax.legend(frameon=False, fontsize=8.5, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S2", out_dir)


def fig_21_s3(out_dir=None):
    """The risk estimate (21.16) and the true risk (21.15), Bart Simpson density, n = 500 and 5000."""
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.7))
    for ax, n in zip(axes[0], (500, 5000)):
        X = claw_sample_js(SEED_DENS, n)
        fit = density_series(X)
        J, R = density_true_risk(claw_pdf, n, fit["p"])
        ax.plot(J, R, color="k", lw=1.4, label="true risk $R(J)$")
        ax.plot(J, fit["Rhat"], color=BLUE, lw=1.2, label=r"estimate $\hat R(J)$")
        ax.axvline(fit["Jhat"], color=BLUE, ls=":", lw=1)
        ax.axvline(J[np.argmin(R)], color="k", ls=":", lw=1)
        ax.set_title(r"$n = %d$: $\hat J = %d$, best $J = %d$" % (n, fit["Jhat"], J[np.argmin(R)]))
        ax.set_xlabel("$J$")
        ax.set_ylim(0, min(1.2 * float(R.max()), 1.2))
        ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S3", out_dir)


def fig_21_s4(out_dir=None):
    """The risk estimate (21.27) and the true risk (21.25), doppler regression, n = 2048, sigma = 0.1."""
    x, Y, fit = doppler_example()
    b, nrm = doppler_coefs()
    n = fit["n"]
    J, R = reg_true_risk(b, nrm, n, 0.1, n)
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.7))
    ax = axes[0, 0]
    ax.semilogy(J, R, color="k", lw=1.3, label="true risk")
    ax.semilogy(J, fit["Rhat"], color=BLUE, lw=1.1, label="risk estimate")
    ax.axvline(fit["Jhat"], color=BLUE, ls=":", lw=1)
    ax.set_xlabel("$J$")
    ax.set_title(r"$\hat J = %d$, best $J = %d$" % (fit["Jhat"], J[np.argmin(R)]))
    ax.legend(frameon=False, fontsize=8)
    ax = axes[0, 1]
    j = np.arange(1, n + 1)
    ax.semilogy(j, np.abs(fit["beta"]), ".", ms=1.2, color=GREY, label=r"$|\hat\beta_j|$")
    ax.semilogy(j, np.abs(b[:n]) + 1e-12, color="k", lw=0.8, label=r"$|\beta_j|$")
    ax.axhline(fit["sigma"] / math.sqrt(n), color=RED, lw=1, label=r"$\hat\sigma/\sqrt{n}$")
    ax.axvline(n - fit["k"], color=GREEN, ls="--", lw=1)
    ax.text(n - fit["k"] + 15, 2e-1, "last $k$", color=GREEN, fontsize=8)
    ax.set_ylim(1e-6, 1)
    ax.set_xlabel("$j$")
    ax.legend(frameon=True, framealpha=0.95, fontsize=8, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S4", out_dir)


def band_coverage(R=400, seed0=50000):
    """Simulated distribution of sup_x |fhat_J - f_J| / c for the density band (21.18) (claw, n = 5000,
    J = 20) and of sup_x |rhat_J - r_J| / c(x) for the regression band (21.29) (doppler, n = 2048,
    J = 45). Returns the two arrays of ratios (the band covers when the ratio is <= 1)."""
    rng = np.random.default_rng(seed0)
    xg = np.linspace(0, 1, 801)
    # density
    Jd, n = 20, 5000
    btrue, _ = density_truth(claw_pdf, 60)
    fJ = 1.0 + cos_basis(xg, Jd + 1)[:, 1:] @ btrue[1:Jd + 1]
    grid = np.linspace(0, 1, 20001)
    cdf = np.cumsum(claw_pdf(grid))
    cdf /= cdf[-1]
    ratio_d, ratio_d2 = [], []
    for r in range(R):
        X = np.interp(rng.random(n), cdf, grid)
        fit = density_series(X, J=Jd)
        sup = float(np.max(np.abs(density_eval(fit, xg) - fJ)))
        ratio_d.append(sup / fit["c"])
        ratio_d2.append(sup / fit["c2"])
    # regression
    Jr, n2 = 45, 2048
    xi = np.arange(1, n2 + 1) / n2
    b, _ = doppler_coefs()
    rJ = reg_basis(xg, Jr) @ b[:Jr]
    C = cos_table_mat(n2, np.arange(Jr))
    Phi = np.sqrt(2.0) * C
    Phi[:, 0] = 1.0
    ratio_r = []
    a = np.sqrt(np.sum(reg_basis(xg, Jr) ** 2, axis=1))
    chi = math.sqrt(stats.chi2.ppf(0.95, Jr))
    for r in range(R):
        Y = doppler(xi) + 0.1 * rng.standard_normal(n2)
        fit = reg_series(Y)
        rh = reg_basis(xg, Jr) @ fit["beta"][:Jr]
        ratio_r.append(float(np.max(np.abs(rh - rJ) / (a * fit["sigma"] * chi / math.sqrt(n2)))))
    return np.array(ratio_d), np.array(ratio_d2), np.array(ratio_r)


def fig_21_s5(out_dir=None):
    """How conservative the bands are: sup error divided by the half-width, 400 simulated samples each."""
    rd, rd2, rr = band_coverage()
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.6))
    ax = axes[0, 0]
    ax.hist(rd, bins=30, color=BLUE, alpha=0.7, label="book's $c$ (21.19)")
    ax.hist(rd2, bins=30, color=ORANGE, alpha=0.6, label="corrected $c'$")
    ax.axvline(1, color="k", lw=1)
    ax.set_title("density, claw, $n=5000$, $J=20$")
    ax.set_xlabel(r"$\sup_x|\hat f_J-f_J|\,/\,c$")
    ax.legend(frameon=False, fontsize=8)
    ax = axes[0, 1]
    ax.hist(rr, bins=30, color=GREEN, alpha=0.7)
    ax.axvline(1, color="k", lw=1)
    ax.set_title("regression, doppler, $n=2048$, $J=45$")
    ax.set_xlabel(r"$\sup_x|\hat r_J-r_J|/c(x)$")
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S5", out_dir)


def survival_curve(R=400):
    """Theorem 21.15: P(some coefficient survives) for pure noise, n = 2^4..2^14: exact (sigma known),
    simulated with sigma estimated by (21.37), and the bound of the proof."""
    ns = 2 ** np.arange(4, 15)
    lam = np.sqrt(2 * np.log(ns))
    exact = 1 - (1 - 2 * stats.norm.sf(lam)) ** (ns - 1)
    bound = (ns - 1) / ns * math.sqrt(2 / math.pi) / lam
    sim = np.array([noise_survival(int(n), R, 900000 + 1000 * int(np.log2(n)), sigma_known=False) for n in ns]) / R
    return ns, exact, bound, sim


def fig_21_s6(out_dir=None):
    """Theorem 21.15: pure noise and the universal threshold."""
    ns, exact, bound, sim = survival_curve()
    fig, axes = common.panel_grid(1, 1, size=(5.0, 3.0))
    ax = axes[0, 0]
    ax.semilogx(ns, bound, "--", color=GREY, label=r"bound of the proof, $\sqrt{2/\pi}/\sqrt{2\log n}$")
    ax.semilogx(ns, exact, "-o", color="k", ms=3, label=r"exact, $\sigma$ known")
    ax.semilogx(ns, sim, "s", color=RED, ms=4, label=r"simulated, $\hat\sigma$ from (21.37), 400 runs")
    ax.set_xscale("log", base=2)
    ax.set_xlabel("$n$")
    ax.set_ylabel("P(some coefficient survives)")
    ax.set_ylim(0, 0.45)
    ax.legend(frameon=False, fontsize=8.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S6", out_dir)


def fig_21_s7(out_dir=None):
    """Risk of soft and hard thresholding at lambda = sqrt(2 log n), n = 2048, and the oracle bound."""
    n = 2048
    lam = math.sqrt(2 * math.log(n))
    mu = np.linspace(0, 6, 601)
    fig, axes = common.panel_grid(1, 1, size=(5.0, 3.0))
    ax = axes[0, 0]
    ax.plot(mu, soft_risk(lam, mu), color=BLUE, lw=1.5, label="soft thresholding")
    ax.plot(mu, hard_risk(lam, mu), color=RED, lw=1.5, label="hard thresholding")
    ax.plot(mu, np.minimum(mu ** 2, 1), color="k", lw=1.2, label=r"oracle $\min(\mu^2,1)$")
    ax.plot(mu, (1 + lam ** 2) * (1 / n + np.minimum(mu ** 2, 1)), color=GREY, ls="--", lw=1.2,
            label=r"$(2\log n+1)(1/n+\min(\mu^2,1))$")
    ax.axvline(lam, color=GREY, ls=":", lw=1)
    ax.set_ylim(0, 18)
    ax.set_xlabel(r"$\mu$ (signal in units of the noise s.d.)")
    ax.set_ylabel("risk")
    ax.set_title(r"$X\sim N(\mu,1)$, threshold $\lambda=\sqrt{2\log n}=%.2f$, $n=%d$" % (lam, n))
    ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S7", out_dir)


T_BLOCKS = np.array([.1, .13, .15, .23, .25, .40, .44, .65, .76, .78, .81])
H_BLOCKS = np.array([4, -5, 3, -4, 5, -4.2, 2.1, 4.3, -3.1, 2.1, -4.2])


def blocks(x):
    """Exercise 21.6(c): sum_j h_j K(x - t_j), K(t) = (1 + sign t)/2."""
    x = np.asarray(x, dtype=float)
    return np.sum(H_BLOCKS[None, :] * (1 + np.sign(x[:, None] - T_BLOCKS[None, :])) / 2, axis=1)


EX6 = [("(a) $\\sqrt{2}\\cos(3\\pi x)$", lambda x: np.sqrt(2) * np.cos(3 * np.pi * x)),
       ("(b) $\\sin(\\pi x)$", lambda x: np.sin(np.pi * x)),
       ("(c) blocks", blocks),
       ("(d) doppler", doppler)]


def ex6_coefs(N=4096, J=512):
    """Exercise 21.6: cosine coefficients by the Riemann sum on r/N, r = 1..N (the book's formula)."""
    x = np.arange(1, N + 1) / N
    out = []
    for _, f in EX6:
        out.append(cos_basis(x, J).T @ f(x) / N)
    return out


def haar_partial(f, B, N=2 ** 14):
    """Exercise 21.12: the Haar approximation of f using alpha and levels j < B (coefficients by the
    Riemann sum on r/N, i.e. one DWT of f(r/N))."""
    x = np.arange(1, N + 1) / N
    a, D = haar_dwt(f(x))
    Dt = [d if j < B else np.zeros_like(d) for j, d in enumerate(D)]
    return x, haar_idwt(a, Dt)


def fig_21_s8(out_dir=None):
    """Exercises 21.6 and 21.12: partial sums in the cosine basis (left) and the Haar basis (right)."""
    co = ex6_coefs()
    x = np.linspace(0.0005, 1, 2001)
    fig, axes = common.panel_grid(4, 2, size=(3.1, 1.75))
    for r, ((lab, f), b) in enumerate(zip(EX6, co)):
        ax = axes[r, 0]
        ax.plot(x, f(x), color=GREY, lw=2.2, alpha=0.6)
        for J, col in ((5, RED), (20, BLUE), (100, "k")):
            ax.plot(x, cos_basis(x, J) @ b[:J], color=col, lw=0.8, label="%d terms" % J)
        ax.set_title(lab + ", cosine", fontsize=9)
        ax = axes[r, 1]
        ax.plot(x, f(x), color=GREY, lw=2.2, alpha=0.6)
        for B, col in ((2, RED), (4, BLUE), (7, "k")):
            xx, v = haar_partial(f, B)
            ax.plot(xx, v, color=col, lw=0.8, label="%d terms" % 2 ** B)
        ax.set_title(lab + ", Haar", fontsize=9)
        if r == 1:
            axes[r, 0].legend(frameon=False, fontsize=7, loc="lower center")
            axes[r, 1].legend(frameon=False, fontsize=7, loc="lower center")
    for ax in axes.flat:
        ax.set_xlim(0, 1)
        ax.tick_params(labelsize=7)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S8", out_dir)


def glass_analysis():
    """Exercise 21.7: refractive index on aluminium, sorted by Al, regressed on the rank grid i/n."""
    al, ri = glass_sorted()
    n = al.size
    fit = reg_series(ri)
    x = np.arange(1, n + 1) / n
    rh = reg_fit(fit, x)
    c = reg_band(fit, x)
    m = 256
    h = haar_threshold(reflect_pad(ri, m))
    return dict(al=al, ri=ri, fit=fit, rh=rh, c=c, haar=h["fit"][:n], haar_kept=h["kept"], haar_sigma=h["sigma"])


def fig_21_s9(out_dir=None):
    """Exercise 21.7: the glass data, cosine fit with 95% band (left) and Haar fit (right)."""
    g = glass_analysis()
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.7))
    for ax in axes[0]:
        ax.plot(g["al"], g["ri"], "o", ms=2.5, mfc="none", color=GREY)
        ax.set_xlabel("aluminium (Al)")
    axes[0, 0].set_ylabel("refractive index (RI)")
    axes[0, 0].fill_between(g["al"], g["rh"] - g["c"], g["rh"] + g["c"], color=BLUE, alpha=0.15, lw=0)
    axes[0, 0].plot(g["al"], g["rh"], color=BLUE, lw=1.4)
    axes[0, 0].set_title(r"cosine: $\hat J = %d$, $\hat\sigma = %.2f$" % (g["fit"]["Jhat"], g["fit"]["sigma"]))
    axes[0, 1].plot(g["al"], g["haar"], color=RED, lw=1.2, drawstyle="steps-mid")
    axes[0, 1].set_title("Haar, universal threshold: %d kept" % g["haar_kept"])
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S9", out_dir)


def fig_21_s10(out_dir=None):
    """Exercise 21.9: doppler, n = 1024, sigma = 0.1: cosine fits with bands for J = 10, 40, 70, 100,
    and the Haar fit."""
    n = 1024
    x, Y = doppler_data(n, 0.1, SEED_REG + 1)
    fit = reg_series(Y)
    xx = np.linspace(0.0005, 1, 3001)
    fig, axes = common.panel_grid(2, 3, size=(2.6, 2.0))
    for ax, J in zip(axes.flat, (10, 40, 70, 100)):
        r = reg_fit(fit, xx, J)
        c = reg_band(fit, xx, J)
        ax.fill_between(xx, r - c, r + c, color=BLUE, alpha=0.2, lw=0)
        ax.plot(xx, doppler(xx), color="k", lw=0.5)
        ax.plot(xx, r, color=BLUE, lw=0.8)
        ax.set_title("$J = %d$" % J, fontsize=9)
    h = haar_threshold(Y)
    ax = axes[1, 1]
    ax.plot(xx, doppler(xx), color="k", lw=0.5)
    ax.stairs(h["fit"], np.arange(n + 1) / n, color=RED, lw=0.8)
    ax.set_title("Haar, universal: %d kept" % h["kept"], fontsize=9)
    ax = axes[1, 2]
    ax.plot(np.arange(1, n + 1), fit["Rhat"], color=BLUE, lw=1)
    ax.axvline(fit["Jhat"], color=BLUE, ls=":")
    ax.set_yscale("log")
    ax.set_title(r"risk estimate, $\hat J = %d$" % fit["Jhat"], fontsize=9)
    for ax in axes.flat[:5]:
        ax.set_xlim(0, 1)
        ax.set_ylim(-0.9, 0.9)
    for ax in axes.flat:
        ax.tick_params(labelsize=7)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S10", out_dir)


def haar_hist_cv(X, Bmax):
    """Exercise 21.10: leave-one-out CV score of the Haar histogram with levels 0..B, B = -1..Bmax
    (B = -1 is the uniform density). Uses the closed form: the Haar histogram with levels 0..B is the
    ordinary histogram with m = 2^(B+1) equal bins, and CV(B) = int fhat^2 - (2/n) sum fhat_{-i}(X_i)."""
    n = X.size
    out = []
    for B in range(-1, Bmax + 1):
        m = 2 ** (B + 1)
        N = np.bincount(np.minimum((X * m).astype(int), m - 1), minlength=m)
        int_f2 = m * np.sum(N ** 2) / n ** 2
        loo = np.sum(N * m * (N - 1) / (n - 1)) / n
        out.append(int_f2 - 2 * loo)
    return np.arange(-1, Bmax + 1), np.array(out)


def haar_hist_series(X, B):
    """The Haar histogram phi + sum_{j<=B} sum_k beta_hat_{j,k} psi_{j,k} evaluated by the series (to
    confirm that it is the histogram with 2^(B+1) bins) on a grid of bin midpoints."""
    m = 2 ** (B + 1)
    xm = (np.arange(m) + 0.5) / m
    f = np.ones(m)
    for j in range(B + 1):
        for k in range(2 ** j):
            f += np.mean(haar_psi(X, j, k)) * haar_psi(xm, j, k)
    return xm, f


def ex10_data(n=1000, seed=21010):
    return np.random.default_rng(seed).beta(15, 4, n)


def haar_hist_mse(B, n, a=15, b=4):
    """Exercise 21.10(c): MSE(B) = (2^(B+1) - 1 - sum_{j<=B,k} beta_jk^2)/n + sum_{j>B,k} beta_jk^2 for
    the Beta(a, b) density (exact bin probabilities; the levels beyond 14 are negligible)."""
    J = 16
    m = 2 ** J
    P = np.diff(stats.beta.cdf(np.arange(m + 1) / m, a, b))      # bin probabilities at level J
    out = []
    # beta_{j,k} = 2^{j/2} (P(right half) - P(left half)) of the dyadic interval I_{j,k}
    betas = []
    for j in range(J):
        Pj = P.reshape(2 ** (j + 1), -1).sum(1)
        betas.append(2 ** (j / 2) * (Pj[1::2] - Pj[0::2]))
    for Bv in np.atleast_1d(B):
        var = (2 ** (Bv + 1) - 1 - sum(np.sum(betas[j] ** 2) for j in range(Bv + 1))) / n
        bias = sum(np.sum(betas[j] ** 2) for j in range(Bv + 1, J))
        out.append(var + bias)
    return np.array(out)


def fig_21_s11(out_dir=None):
    """Exercise 21.10: Haar histogram of n = 1000 Beta(15, 4) draws, B by leave-one-out CV."""
    X = ex10_data()
    Bs, cv = haar_hist_cv(X, 8)
    Bhat = int(Bs[np.argmin(cv)])
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.7))
    ax = axes[0, 0]
    ax.plot(Bs, cv, "-o", color=BLUE, ms=3, label="LOO CV score")
    mse = haar_hist_mse(Bs[1:], X.size)
    ax.plot(Bs[1:], mse - np.sum(stats.beta.pdf((np.arange(2 ** 16) + 0.5) / 2 ** 16, 15, 4) ** 2) / 2 ** 16,
            "-s", color="k", ms=3, label=r"MSE$(B)-\|f\|^2$")
    ax.axvline(Bhat, color=BLUE, ls=":")
    ax.set_xlabel("$B$")
    ax.set_title(r"$\hat B = %d$ (%d bins)" % (Bhat, 2 ** (Bhat + 1)))
    ax.legend(frameon=False, fontsize=8)
    ax = axes[0, 1]
    m = 2 ** (Bhat + 1)
    N = np.bincount(np.minimum((X * m).astype(int), m - 1), minlength=m)
    ax.stairs(m * N / X.size, np.arange(m + 1) / m, color=BLUE, lw=1.2, label="Haar histogram")
    xx = np.linspace(0, 1, 501)
    ax.plot(xx, stats.beta.pdf(xx, 15, 4), color="k", lw=1, label="Beta(15, 4)")
    ax.legend(frameon=False, fontsize=8, loc="upper left")
    ax.set_xlim(0, 1)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S11", out_dir)


def mad_vs_sd(R=1000, n=100, seed=21011, contaminate=False, outlier_sd=10.0):
    """Exercise 21.11: MSE of sigma_MAD = median|X_i|/0.6745 and of the sample s.d. for N(0, 1) data,
    optionally with each observation replaced, with probability 0.05, by a N(0, outlier_sd^2) draw."""
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((R, n))
    if contaminate:
        mask = rng.random((R, n)) < 0.05
        X = np.where(mask, outlier_sd * rng.standard_normal((R, n)), X)
    mad = np.median(np.abs(X), axis=1) / 0.6745
    sd = X.std(axis=1, ddof=1)
    return mad, sd


def fig_21_s12(out_dir=None):
    """Exercise 21.11: the median absolute deviation estimate against the standard deviation."""
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.6))
    for ax, cont, title in zip(axes[0], (False, True), ("N(0,1), n = 100", "5% outliers from N(0, 10²)")):
        mad, sd = mad_vs_sd(contaminate=cont)
        bins = np.linspace(0.5, 3.5, 61)
        ax.hist(sd, bins=bins, color=RED, alpha=0.6, label="s.d., MSE %.3f" % np.mean((sd - 1) ** 2))
        ax.hist(mad, bins=bins, color=BLUE, alpha=0.6, label="MAD, MSE %.3f" % np.mean((mad - 1) ** 2))
        ax.axvline(1, color="k", lw=1)
        ax.set_title(title, fontsize=9.5)
        ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig21-S12", out_dir)


# =========================================================================== demo data
def export_json(out=None):
    """Write ../data/ch21-data.json: the Old Faithful eruption times, the glass data (sorted by Al) and
    the cosine coefficients of the doppler function (for the true risk curve of the regression demo)."""
    out = out or os.path.normpath(os.path.join(HERE, "..", "data"))
    os.makedirs(out, exist_ok=True)
    al, ri = glass_sorted()
    b, nrm = doppler_coefs()
    obj = {
        "faithful": [round(float(v), 3) for v in faithful_eruptions()],
        "faithfulRange": [FAITH_LO, FAITH_HI],
        "glass": {"al": [float(v) for v in al], "ri": [float(v) for v in ri]},
        "dopplerBeta": [float("%.6e" % v) for v in b[:2048]],
        "dopplerNorm2": nrm,
    }
    path = os.path.join(out, "ch21-data.json")
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", path, os.path.getsize(path), "bytes")


FIGURES = {"21.1": fig_21_1, "21.2": fig_21_2, "21.3": fig_21_3, "21.4": fig_21_4, "21.5": fig_21_5,
           "21.6": fig_21_6, "21.7": fig_21_7, "21.8": fig_21_8, "21.S1": fig_21_s1, "21.S2": fig_21_s2,
           "21.S3": fig_21_s3, "21.S4": fig_21_s4, "21.S5": fig_21_s5, "21.S6": fig_21_s6,
           "21.S7": fig_21_s7, "21.S8": fig_21_s8, "21.S9": fig_21_s9, "21.S10": fig_21_s10,
           "21.S11": fig_21_s11, "21.S12": fig_21_s12}

if __name__ == "__main__":
    export_json()
    common.run(FIGURES, CH)
