"""Bishop and Bishop (2024), Appendices A, B and C: Linear Algebra, Calculus of Variations and
Lagrange Multipliers.

Reproduces the figures of the three mathematical appendices of C. M. Bishop and H. Bishop, Deep
Learning: Foundations and Concepts (Springer, 2024), pp. 609-624, written from scratch with numpy,
scipy and matplotlib, and supplies the reference numbers of the two browser demonstrations. Every
function is short and meant to be read next to the lecture notes (appendices.html):

* Appendix A.1-A.2: the push-through identity (A.5)-(A.6), the Woodbury identity (A.7), the
  determinant from its permutation definition (A.10) (det_leibniz), Sylvester's identity (A.14).
* Appendix A.3: matrix derivatives by central differences (num_grad_matrix), for testing
  (A.19)-(A.28), including Jacobi's formula (A.22).
* Appendix A.4: the closed-form eigen-decomposition of a 2 x 2 matrix (eig2), real or complex, which
  is the code of eigen-linear-map-demo.html; the facts the notes add (|U| = +-1, rank and
  eigenvalues, positive definiteness of non-symmetric matrices, the two condition numbers).
* Appendix B: the Euler-Lagrange example (B.9)-(B.10) solved in closed form and by direct
  minimisation of a discretised functional (el_exact, el_discrete), the shortest path, and the
  maximum entropy density found by maximising a discretised entropy under constraints (maxent_grid).
* Appendix C: the worked example (C.5)-(C.8); the inequality-constrained example of the notes (a
  concave quadratic on a disc, kkt_disc); the projection onto the probability simplex
  (simplex_projection), with both kinds of multiplier; and LagrangeDemo, a plain-float copy of the
  solver in lagrange-kkt-demo.html, so the page reproduces it number for number.

Figures reproduced: B.1 (a function and a perturbation of it, drawn for concrete functions), C.1
and C.3 (the geometry of an equality and of an inequality constraint, drawn for a concrete
objective and constraint, with the gradients computed rather than sketched) and C.2 (the worked
example (C.5), computed). Appendix A has no figures. No figure is skipped.

Supplementary figures (our own, numbered A.S1, A.S2, B.S1, B.S2, C.S1, C.S2; they illustrate the
gaps filled in the notes): A.S1 three 2 x 2 matrices as linear maps of the unit circle (symmetric,
the book's (A.49), a reflection with determinant -1); A.S2 the quadratic form w^T A w on the unit
circle, which shows why eigenvalues decide positive definiteness only for symmetric matrices;
B.S1 the Euler-Lagrange solution of (B.10) against direct minimisation, and the functional along a
line of perturbations; B.S2 the maximum entropy density and the shortest path found numerically;
C.S1 the KKT example as the constraint switches from inactive to active (complementary slackness);
C.S2 a constraint whose gradient vanishes (no multiplier exists) and the multiplier as a
sensitivity.

Run `python3 appendices.py --list`, `python3 appendices.py` (all figures, about 10 seconds on one
CPU thread) or `python3 appendices.py --fig C.2 B.S2`. Files go to ../img/appendices/.
"""
import argparse
import itertools
import math
import os
import sys
import time

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from scipy import optimize  # noqa: E402

import common  # noqa: E402
from common import panel_label  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
FOLDER = "appendices"


def save(fig, name, out_dir=None):
    """Save fig as <out_dir>/appendices/<name>.{png,svg,pdf}.

    common.savefig always writes to a folder named chNN, so the appendices use this copy of it,
    with the same reproducible (timestamp-free) metadata, writing to img/appendices/ instead.
    """
    out = os.path.join(out_dir or common.OUT_DIR, FOLDER)
    os.makedirs(out, exist_ok=True)
    for ext in ("png", "svg", "pdf"):
        meta = {"Date": None} if ext == "svg" else ({"CreationDate": None} if ext == "pdf" else None)
        fig.savefig(os.path.join(out, name + "." + ext), metadata=meta)
    plt.close(fig)
    print("wrote", os.path.relpath(os.path.join(out, name + ".png"), os.getcwd()), "(+ svg, pdf)")


# =========================================================================== Appendix A.1-A.2
def push_through(P, B, R):
    """Both sides of (A.5): (P^-1 + B^T R^-1 B)^-1 B^T R^-1 and P B^T (B P B^T + R)^-1."""
    Ri = np.linalg.inv(R)
    lhs = np.linalg.inv(np.linalg.inv(P) + B.T @ Ri @ B) @ B.T @ Ri
    rhs = P @ B.T @ np.linalg.inv(B @ P @ B.T + R)
    return lhs, rhs


def woodbury(A, B, C, D):
    """Both sides of (A.7): (A + B D^-1 C)^-1 and A^-1 - A^-1 B (D + C A^-1 B)^-1 C A^-1."""
    Ai = np.linalg.inv(A)
    lhs = np.linalg.inv(A + B @ np.linalg.inv(D) @ C)
    rhs = Ai - Ai @ B @ np.linalg.inv(D + C @ Ai @ B) @ C @ Ai
    return lhs, rhs


def perm_sign(p):
    """+1 for an even permutation of 0..n-1, -1 for an odd one (count the transpositions of a sort)."""
    p, s = list(p), 1
    for i in range(len(p)):
        while p[i] != i:
            j = p[i]
            p[i], p[j] = p[j], p[i]
            s = -s
    return s


def det_leibniz(A):
    """The determinant from its definition (A.10): a signed sum over all n! permutations."""
    n = A.shape[0]
    return sum(perm_sign(p) * np.prod([A[i, p[i]] for i in range(n)]) for p in itertools.permutations(range(n)))


def num_grad_matrix(f, A, h=1e-6):
    """Matrix of central differences d f / d A_ij (the convention of (A.23)-(A.28))."""
    G = np.zeros_like(A, dtype=float)
    for i in range(A.shape[0]):
        for j in range(A.shape[1]):
            E = np.zeros_like(A, dtype=float)
            E[i, j] = h
            G[i, j] = (f(A + E) - f(A - E)) / (2 * h)
    return G


def row_reduce_rank(A, tol=1e-10):
    """Rank by Gaussian elimination with partial pivoting: the number of pivots (independent rows)."""
    M = np.array(A, dtype=float).copy()
    r = 0
    for c in range(M.shape[1]):
        if r == M.shape[0]:
            break
        p = r + int(np.argmax(np.abs(M[r:, c])))
        if abs(M[p, c]) < tol:
            continue
        M[[r, p]] = M[[p, r]]
        M[r + 1:] -= np.outer(M[r + 1:, c] / M[r, c], M[r])
        r += 1
    return r


# =========================================================================== Appendix A.4
def eig2(A):
    """Eigen-decomposition of a real 2 x 2 matrix in closed form (the code of eigen-linear-map-demo.html).

    The characteristic equation (A.30) is lambda^2 - T lambda + D = 0 with T = Tr A and D = |A|.
    Returns a dict with tr, det, disc = T^2/4 - D and, if disc >= 0, the real eigenvalues l1 >= l2
    and unit eigenvectors v1, v2 (None when the eigenspace is the whole plane); if disc < 0 the
    complex pair re +- i im.
    """
    a, b, c, d = float(A[0][0]), float(A[0][1]), float(A[1][0]), float(A[1][1])
    T, D = a + d, a * d - b * c
    disc = T * T / 4 - D
    out = {"tr": T, "det": D, "disc": disc}
    if disc < 0:
        out.update(real=False, re=T / 2, im=math.sqrt(-disc))
        return out
    s = math.sqrt(disc)
    l1, l2 = T / 2 + s, T / 2 - s
    out.update(real=True, l1=l1, l2=l2, v1=_eigvec2(a, b, c, d, l1), v2=_eigvec2(a, b, c, d, l2))
    return out


def _eigvec2(a, b, c, d, lam):
    """A unit vector in the null space of A - lam I, from whichever row of A - lam I is larger."""
    r1, r2 = (a - lam, b), (c, d - lam)
    r = r1 if math.hypot(*r1) >= math.hypot(*r2) else r2
    n = math.hypot(*r)
    if n < 1e-12:            # A = lam I: every vector is an eigenvector
        return None
    v = (-r[1] / n, r[0] / n)
    if v[0] < 0 or (v[0] == 0 and v[1] < 0):
        v = (-v[0], -v[1])
    return v


def sym_part_eigs(A):
    """Eigenvalues (larger first) of the symmetric part (A + A^T)/2: the range of w^T A w on |w| = 1."""
    A = np.asarray(A, float)
    S = 0.5 * (A + A.T)
    e = eig2(S)
    return e["l1"], e["l2"]


def eigen_summary(A):
    """The numbers shown in eigen-linear-map-demo.html for a 2 x 2 matrix A."""
    A = np.asarray(A, float)
    e = eig2(A)
    s1, s2 = sym_part_eigs(A)
    sv = np.linalg.svd(A, compute_uv=False)
    out = {"tr": e["tr"], "det": e["det"], "real": e["real"], "s1": s1, "s2": s2,
           "sv1": float(sv[0]), "sv2": float(sv[1]), "rank": int(np.linalg.matrix_rank(A))}
    if e["real"]:
        out.update(l1=e["l1"], l2=e["l2"])
        if e["v1"] is not None and e["v2"] is not None:
            out["cos12"] = abs(e["v1"][0] * e["v2"][0] + e["v1"][1] * e["v2"][1])
    else:
        out.update(re=e["re"], im=e["im"])
    return out


EIGEN_PRESETS = [
    [[2.0, 1.0], [1.0, 2.0]],     # 1 symmetric positive definite
    [[1.0, 2.0], [3.0, 4.0]],     # 2 the book's (A.49)
    [[1.0, 4.0], [0.0, 1.0]],     # 3 positive eigenvalues, not positive definite
    [[0.0, -1.0], [1.0, 0.0]],    # 4 rotation by 90 degrees: complex eigenvalues
    [[0.0, 1.0], [0.0, 0.0]],     # 5 rank 1, both eigenvalues 0
]


# =========================================================================== Appendix B
def el_exact(x, a, b):
    """Solution of y'' = y (B.10) with y(0) = a, y(1) = b: (a sinh(1 - x) + b sinh x) / sinh 1."""
    return (a * np.sinh(1 - x) + b * np.sinh(x)) / math.sinh(1.0)


def F_quad(y, h):
    """Discretised F[y] = int (y^2 + y'^2) dx (B.9) on a uniform grid with spacing h (trapezoid + differences)."""
    yy = 0.5 * (y[1:] ** 2 + y[:-1] ** 2)
    dy = np.diff(y) / h
    return float(np.sum((yy + dy ** 2) * h))


def el_discrete(n, a, b):
    """Minimise the discretised (B.9) over the n - 1 interior values: a linear system (the functional is quadratic)."""
    h = 1.0 / n
    m = n - 1
    # dF/dy_i = h y_i (from the two trapezoid halves) + (2 y_i - y_{i-1} - y_{i+1}) * 2 / h = 0
    K = np.zeros((m, m))
    rhs = np.zeros(m)
    for i in range(m):
        K[i, i] = 2 * h + 4.0 / h
        if i > 0:
            K[i, i - 1] = -2.0 / h
        if i < m - 1:
            K[i, i + 1] = -2.0 / h
    rhs[0] += 2.0 / h * a
    rhs[-1] += 2.0 / h * b
    y = np.concatenate([[a], np.linalg.solve(K, rhs), [b]])
    return np.linspace(0, 1, n + 1), y


def path_length(y, x):
    return float(np.sum(np.hypot(np.diff(x), np.diff(y))))


def shortest_path(n=40, seed=0):
    """Minimise the length of a polygonal path from (0, 0) to (1, 1) over its n - 1 interior heights,
    starting from a wiggly curve. Returns x, the initial and the optimised heights."""
    rng = np.random.default_rng(seed)
    x = np.linspace(0, 1, n + 1)
    y0 = x + 0.35 * np.sin(3 * np.pi * x) + 0.05 * np.concatenate([[0], rng.normal(size=n - 1), [0]])

    def L(z):
        return path_length(np.concatenate([[0.0], z, [1.0]]), x)

    res = optimize.minimize(L, y0[1:-1], method="BFGS", options={"gtol": 1e-10, "maxiter": 5000})
    return x, y0, np.concatenate([[0.0], res.x, [1.0]])


def maxent_grid(n=161, half=7.0, mean=0.0, var=1.0):
    """Maximise the discretised entropy -sum p ln p dx over densities on a grid of [-half, half]
    subject to sum p dx = 1, sum x p dx = mean and sum (x - mean)^2 p dx = var.

    Solved as a generic constrained problem (SLSQP on the n values p_i >= 0); nothing about the
    form of the answer is assumed. Returns x, p and the entropy reached.
    """
    x = np.linspace(-half, half, n)
    dx = x[1] - x[0]
    p0 = np.where(np.abs(x - mean) < 2.5, 1.0, 0.05)
    p0 /= p0.sum() * dx

    def negH(p):
        q = np.maximum(p, 1e-300)
        return float(np.sum(q * np.log(q)) * dx)

    def negH_grad(p):
        return (np.log(np.maximum(p, 1e-300)) + 1.0) * dx

    cons = [{"type": "eq", "fun": lambda p: np.sum(p) * dx - 1.0, "jac": lambda p: np.full(n, dx)},
            {"type": "eq", "fun": lambda p: np.sum(x * p) * dx - mean, "jac": lambda p: x * dx},
            {"type": "eq", "fun": lambda p: np.sum((x - mean) ** 2 * p) * dx - var, "jac": lambda p: (x - mean) ** 2 * dx}]
    res = optimize.minimize(negH, p0, jac=negH_grad, constraints=cons, bounds=[(1e-12, None)] * n,
                            method="SLSQP", options={"maxiter": 2000, "ftol": 1e-13})
    return x, res.x, -res.fun


def entropies_same_variance(var=1.0):
    """Differential entropies (nats) of four densities with the same variance: the Gaussian is largest."""
    s = math.sqrt(var)
    return {"Gaussian": 0.5 * math.log(2 * math.pi * math.e * var),
            "Laplace": 1 + math.log(2 * s / math.sqrt(2)),
            "logistic": math.log(s * math.sqrt(3) / math.pi) + 2,
            "uniform": math.log(2 * math.sqrt(3) * s)}


# =========================================================================== Appendix C
def book_example():
    """(C.5)-(C.8): stationary point of 1 - x1^2 - x2^2 + lam (x1 + x2 - 1), solved as a linear system."""
    M = np.array([[-2.0, 0.0, 1.0], [0.0, -2.0, 1.0], [1.0, 1.0, 0.0]])
    x1, x2, lam = np.linalg.solve(M, [0.0, 0.0, 1.0])
    return np.array([x1, x2]), lam


def book_example_value(c):
    """Constrained maximum of 1 - x1^2 - x2^2 on x1 + x2 = c: f*(c) = 1 - c^2/2 (multiplier lam = c)."""
    return 1 - c * c / 2


def kkt_disc(a):
    """Maximise f = -(x1 - a)^2 - (x2 - a)^2 subject to g = 1 - x1^2 - x2^2 >= 0.

    KKT: grad f + lam grad g = 0 gives x = a (1, 1) / (1 + lam); the constraint is inactive (lam = 0)
    while 2 a^2 <= 1 and active with lam = sqrt(2) a - 1 > 0 beyond. Returns x*, lam, g(x*).
    """
    lam = max(0.0, math.sqrt(2) * abs(a) - 1)
    x = np.array([a, a]) / (1 + lam)
    return x, lam, 1 - x @ x


def kkt_numeric(f, g, x0, ineq=True):
    """Maximise f subject to g >= 0 (or g = 0) with SLSQP: an independent referee for the closed forms."""
    cons = [{"type": "ineq" if ineq else "eq", "fun": g}]
    r = optimize.minimize(lambda x: -f(x), x0, constraints=cons, method="SLSQP", options={"ftol": 1e-14, "maxiter": 500})
    return r.x


def simplex_projection(y):
    """argmin ||x - y||^2 subject to sum x = 1, x >= 0 (KKT with one equality and K inequality multipliers).

    The KKT conditions give x_k = max(y_k - tau, 0), with tau (minus half the equality multiplier)
    fixed by sum x = 1. Returns x, tau and the inequality multipliers mu_k = 2 max(tau - y_k, 0).
    """
    y = np.asarray(y, float)
    u = np.sort(y)[::-1]
    css = np.cumsum(u)
    k = np.nonzero(u - (css - 1) / np.arange(1, len(y) + 1) > 0)[0][-1]
    tau = (css[k] - 1) / (k + 1)
    x = np.maximum(y - tau, 0)
    mu = 2 * np.maximum(tau - y, 0)
    return x, tau, mu


class LagrangeDemo:
    """A plain-float copy of the solver of lagrange-kkt-demo.html.

    Objective (maximised): f(x) = c0 - (x - m)^T S (x - m), S = R diag(q1, q2) R^T with R the
    rotation by the angle th (degrees); q1 = q2 = 1, m = 0, c0 = 1 is the book's 1 - x1^2 - x2^2.
    Constraint, written g(x) = 0 or g(x) >= 0 as in Appendix C:
      'line':   g = n^T x - b with n = sqrt(2) (cos phi, sin phi), so phi = 45, b = 1 is x1 + x2 - 1;
      'circle': g = r^2 - |x - p|^2 (g >= 0 is the disc).
    The equality problem is solved along the curve (x = x0 + t d on a line, an angle t on a
    circle): on a line f is a concave quadratic in t with one stationary point; on a circle a grid
    of 720 angles brackets every stationary point of f along the curve and Newton's method polishes
    it. The maximum is the stationary point with the largest f. The inequality problem returns the
    unconstrained maximiser m if it is feasible (lam = 0) and the boundary maximum otherwise. lam
    solves grad f + lam grad g = 0 in the least-squares sense, lam = -grad f . grad g / |grad g|^2
    (exact at a stationary point).
    """

    def __init__(self, q1=1.0, q2=1.0, th=0.0, m=(0.0, 0.0), c0=1.0, kind="line", phi=45.0, b=1.0,
                 p=(0.0, 0.0), r=1.0, ineq=False):
        self.m = np.array(m, float)
        self.c0, self.kind, self.phi, self.b = c0, kind, phi, b
        self.p, self.r, self.ineq = np.array(p, float), r, ineq
        t = math.radians(th)
        Rm = np.array([[math.cos(t), -math.sin(t)], [math.sin(t), math.cos(t)]])
        self.S = Rm @ np.diag([q1, q2]) @ Rm.T

    def f(self, x):
        d = np.asarray(x, float) - self.m
        return float(self.c0 - d @ self.S @ d)

    def grad_f(self, x):
        return -2 * self.S @ (np.asarray(x, float) - self.m)

    def _n(self):
        ph = math.radians(self.phi)
        return math.sqrt(2) * np.array([math.cos(ph), math.sin(ph)])

    def g(self, x):
        x = np.asarray(x, float)
        if self.kind == "line":
            return float(self._n() @ x - self.b)
        return float(self.r ** 2 - (x - self.p) @ (x - self.p))

    def grad_g(self, x):
        if self.kind == "line":
            return self._n()
        return -2 * (np.asarray(x, float) - self.p)

    def curve(self, t):
        """Point, tangent and second derivative of the constraint curve at the parameter t."""
        if self.kind == "line":
            n = self._n()
            d = np.array([-n[1], n[0]]) / np.linalg.norm(n)
            return self.b * n / (n @ n) + t * d, d, np.zeros(2)
        u = np.array([math.cos(t), math.sin(t)])
        return self.p + self.r * u, self.r * np.array([-u[1], u[0]]), -self.r * u

    def _phi(self, t):
        """First and second derivatives of f along the curve at t."""
        x, d, dd = self.curve(t)
        gf = self.grad_f(x)
        return float(gf @ d), float(-2 * d @ self.S @ d + gf @ dd)

    def stationary_points(self):
        if self.kind == "line":
            x0, d, _ = self.curve(0.0)
            # f(x0 + t d) is a quadratic in t with second derivative -2 d^T S d < 0: one stationary point
            return [float(self.grad_f(x0) @ d / (2 * d @ self.S @ d))]
        ts = np.linspace(0, 2 * math.pi, 721)
        vals = [self._phi(t)[0] for t in ts]
        roots = []
        for k in range(len(ts) - 1):
            if vals[k] == 0 or vals[k] * vals[k + 1] < 0:
                t = 0.5 * (ts[k] + ts[k + 1])
                for _ in range(50):
                    d1, d2 = self._phi(t)
                    if d2 == 0:
                        break
                    step = d1 / d2
                    t -= step
                    if abs(step) < 1e-15:
                        break
                t = t % (2 * math.pi)
                if all(abs(math.remainder(t - s, 2 * math.pi)) > 1e-9 for s in roots):
                    roots.append(t)
        return roots

    def lam_at(self, x):
        gg = self.grad_g(x)
        return float(-self.grad_f(x) @ gg / (gg @ gg))

    def solve(self):
        """Returns dict: x (maximiser), lam, f, active (bool), stationary (list of (x, lam, f) along the curve)."""
        st = []
        for t in self.stationary_points():
            x = self.curve(t)[0]
            st.append((x, self.lam_at(x), self.f(x)))
        st.sort(key=lambda s: -s[2])
        if self.ineq and self.g(self.m) >= 0:
            return {"x": self.m.copy(), "lam": 0.0, "f": self.f(self.m), "active": False, "stationary": st}
        x, lam, fv = st[0]
        return {"x": x, "lam": lam, "f": fv, "active": True, "stationary": st}


LAGRANGE_PRESETS = [
    # 1 the book's example (C.5): f = 1 - x1^2 - x2^2 on x1 + x2 = 1
    dict(q1=1, q2=1, th=0, m=(0, 0), c0=1, kind="line", phi=45, b=1, ineq=False),
    # 2 an elongated objective on a circle: several stationary points of the Lagrangian
    dict(q1=1.6, q2=0.25, th=30, m=(0.6, 0.3), c0=1, kind="circle", p=(0, 0), r=1.2, ineq=False),
    # 3 inequality, inactive: the unconstrained maximum is inside the disc
    dict(q1=1, q2=1, th=0, m=(0.5, 0.5), c0=0, kind="circle", p=(0, 0), r=1.0, ineq=True),
    # 4 inequality, active: the notes' KKT example with a = 1 (lam = sqrt 2 - 1)
    dict(q1=1, q2=1, th=0, m=(1.0, 1.0), c0=0, kind="circle", p=(0, 0), r=1.0, ineq=True),
    # 5 the book's objective with the half-plane x1 + x2 >= 1: active, lam = 1
    dict(q1=1, q2=1, th=0, m=(0, 0), c0=1, kind="line", phi=45, b=1, ineq=True),
]


def lagrange_preset(k):
    """The solved problem of preset k (1-based) of lagrange-kkt-demo.html."""
    return LagrangeDemo(**LAGRANGE_PRESETS[k - 1]).solve()


# =========================================================================== figures
def _arrow(ax, x, v, color, label=None, scale=1.0, **kw):
    ax.annotate("", xy=(x[0] + scale * v[0], x[1] + scale * v[1]), xytext=(x[0], x[1]),
                arrowprops=dict(arrowstyle="-|>", color=color, lw=1.6, shrinkA=0, shrinkB=0))
    if label:
        kw.setdefault("fontsize", 10)
        ax.text(x[0] + scale * v[0] * 1.08, x[1] + scale * v[1] * 1.08, label, color=color, **kw)


def fig_b_1(out_dir=None):
    """Figure B.1: a function y(x) and a perturbed function y(x) + eps eta(x)."""
    x = np.linspace(0, 1, 400)
    y = 0.35 + 0.5 * x + 0.18 * np.sin(2.4 * np.pi * x)
    eta = np.exp(-((x - 0.55) / 0.13) ** 2) * np.cos(9 * (x - 0.55))
    eps = 0.16
    fig, ax = plt.subplots(figsize=(4.6, 2.9))
    ax.plot(x, y, color=common.BLUE, label=r"$y(x)$")
    ax.plot(x, y + eps * eta, color=common.RED, label=r"$y(x)+\epsilon\eta(x)$")
    ax.fill_between(x, y, y + eps * eta, color=common.RED, alpha=0.12, lw=0)
    ax.plot(x, 0.05 + 0.5 * eps * eta, color=common.GREY, lw=1, ls="--", label=r"$\frac{1}{2}\epsilon\eta(x)$ (shifted)")
    ax.set_xlabel(r"$x$")
    ax.set_xlim(0, 1)
    ax.set_ylim(-0.05, 1.1)
    ax.set_yticks([])
    ax.legend(loc="upper left", frameon=False)
    save(fig, "figB-1", out_dir)


def fig_c_1(out_dir=None):
    """Figure C.1: maximising f on the curve g(x) = 0; at the solution grad f and grad g are parallel."""
    D = LagrangeDemo(q1=1, q2=1, th=0, m=(1.7, 1.25), c0=0, kind="circle", p=(0, 0), r=1.0, ineq=False)
    sol = D.solve()
    xs = sol["x"]
    X, Y = np.meshgrid(np.linspace(-1.6, 2.3, 300), np.linspace(-1.5, 2.0, 300))
    Fv = -((X - 1.7) ** 2 + (Y - 1.25) ** 2)
    fig, ax = plt.subplots(figsize=(4.3, 3.9))
    ax.contour(X, Y, Fv, levels=-np.array([3.5, 2.5, 1.7, 1.0, 0.45, 0.12])[::-1][::-1], colors=common.GREY, linewidths=0.8, linestyles="--")
    t = np.linspace(0, 2 * np.pi, 400)
    ax.plot(np.cos(t), np.sin(t), color=common.RED, lw=2)
    ax.text(-0.95, -1.12, r"$g(\mathbf{x})=0$", color=common.RED)
    gf, gg = D.grad_f(xs), D.grad_g(xs)
    _arrow(ax, xs, gf / np.linalg.norm(gf), common.BLUE, r"$\nabla f(\mathbf{x})$", 0.75, ha="left")
    _arrow(ax, xs, gg / np.linalg.norm(gg), common.GREEN, r"$\nabla g(\mathbf{x})$", 0.75, ha="right", va="top")
    ax.plot(*xs, "o", color="k", ms=5)
    ax.text(xs[0] + 0.06, xs[1] - 0.2, r"$\mathbf{x}_A$")
    # a non-optimal point: grad f has a component along the curve
    tp = 2.2
    xp = np.array([math.cos(tp), math.sin(tp)])
    gp = D.grad_f(xp)
    tang = np.array([-xp[1], xp[0]])
    _arrow(ax, xp, 0.6 * gp / np.linalg.norm(gp), common.BLUE)
    _arrow(ax, xp, 0.6 * (gp @ tang) * tang / np.linalg.norm(gp), common.MAGENTA, "along the curve", 1.0, ha="left", fontsize=8.5)
    ax.plot(*xp, "o", color=common.GREY, ms=4)
    ax.plot(1.7, 1.25, "+", color="k", ms=9)
    ax.set_aspect("equal")
    ax.set_xlim(-1.6, 2.3)
    ax.set_ylim(-1.5, 2.0)
    ax.set_xticks([])
    ax.set_yticks([])
    save(fig, "figC-1", out_dir)


def fig_c_2(out_dir=None):
    """Figure C.2: the example (C.5): contours of 1 - x1^2 - x2^2 and the line x1 + x2 = 1."""
    xs, lam = book_example()
    X, Y = np.meshgrid(np.linspace(-1.2, 1.4, 300), np.linspace(-1.2, 1.4, 300))
    Fv = 1 - X ** 2 - Y ** 2
    fig, ax = plt.subplots(figsize=(3.9, 3.7))
    cs = ax.contour(X, Y, Fv, levels=[-1.0, -0.5, 0.0, 0.5, 0.8], colors=common.BLUE, linewidths=0.9)
    ax.clabel(cs, fmt="%.1f", fontsize=7.5)
    t = np.linspace(-1.2, 1.4, 2)
    ax.plot(t, 1 - t, color=common.RED, lw=2)
    ax.text(1.12, 0.1, r"$g(x_1,x_2)=0$", color=common.RED, rotation=-45, ha="center")
    ax.plot(*xs, "o", color="k", ms=5)
    ax.text(xs[0] + 0.07, xs[1] + 0.07, r"$(x_1^\star,x_2^\star)=(\frac{1}{2},\frac{1}{2})$", fontsize=9)
    _arrow(ax, xs, np.array([-1.0, -1.0]) * 0.5, common.BLUE, r"$\nabla f$", 0.9, ha="right")
    _arrow(ax, xs, np.array([1.0, 1.0]) * 0.5, common.GREEN, r"$\nabla g$", 0.9)
    ax.set_xlabel(r"$x_1$")
    ax.set_ylabel(r"$x_2$")
    ax.set_aspect("equal")
    ax.set_xlim(-1.2, 1.4)
    ax.set_ylim(-1.2, 1.4)
    save(fig, "figC-2", out_dir)


def fig_c_3(out_dir=None):
    """Figure C.3: maximising f subject to g(x) >= 0; an active solution x_A and an inactive one x_B."""
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.6))
    t = np.linspace(0, 2 * np.pi, 400)
    X, Y = np.meshgrid(np.linspace(-1.6, 2.2, 300), np.linspace(-1.6, 2.0, 300))
    for ax, m, lab in ((axes[0], (1.6, 1.15), "A"), (axes[1], (-0.3, 0.25), "B")):
        D = LagrangeDemo(q1=1, q2=1, m=m, c0=0, kind="circle", p=(0, 0), r=1.0, ineq=True)
        sol = D.solve()
        ax.fill(np.cos(t), np.sin(t), color=common.RED, alpha=0.09, lw=0)
        ax.plot(np.cos(t), np.sin(t), color=common.RED, lw=2)
        ax.text(-0.35, -0.55, r"$g(\mathbf{x})>0$", color=common.RED)
        ax.text(-1.5, -1.45, r"$g(\mathbf{x})=0$", color=common.RED)
        Fv = -((X - m[0]) ** 2 + (Y - m[1]) ** 2)
        ax.contour(X, Y, Fv, levels=[-3.0, -2.0, -1.2, -0.6, -0.2, -0.04], colors=common.GREY, linewidths=0.8, linestyles="--")
        xs = sol["x"]
        ax.plot(*xs, "o", color="k", ms=5)
        if sol["active"]:
            gf, gg = D.grad_f(xs), D.grad_g(xs)
            _arrow(ax, xs, gf / np.linalg.norm(gf), common.BLUE, r"$\nabla f$", 0.7)
            _arrow(ax, xs, gg / np.linalg.norm(gg), common.GREEN, r"$\nabla g$", 0.7, ha="right", va="top")
            ax.set_title(r"(a) active: $\nabla f=-\lambda\nabla g$, $\lambda=%.3f>0$" % sol["lam"])
            ax.text(xs[0] + 0.08, xs[1] - 0.22, r"$\mathbf{x}_A$")
        else:
            ax.set_title(r"(b) inactive: $\nabla f(\mathbf{x}_B)=\mathbf{0}$, $\lambda=0$")
            ax.text(xs[0] + 0.07, xs[1] + 0.07, r"$\mathbf{x}_B$")
        ax.set_aspect("equal")
        ax.set_xlim(-1.6, 2.2)
        ax.set_ylim(-1.6, 2.0)
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    save(fig, "figC-3", out_dir)


def _map_panel(ax, A, title):
    t = np.linspace(0, 2 * np.pi, 400)
    C = np.stack([np.cos(t), np.sin(t)])
    I = np.asarray(A) @ C
    ax.plot(C[0], C[1], color=common.GREY, lw=1, ls="--")
    ax.plot(I[0], I[1], color=common.BLUE, lw=1.8)
    e = eig2(A)
    if e["real"]:
        for v, lam, col in ((e["v1"], e["l1"], common.RED), (e["v2"], e["l2"], common.GREEN)):
            if v is None:
                continue
            v = np.array(v)
            ax.plot([-5 * v[0], 5 * v[0]], [-5 * v[1], 5 * v[1]], color=col, lw=0.7, alpha=0.6)
            _arrow(ax, (0, 0), v, col)
            _arrow(ax, (0, 0), lam * v, col)
            ax.text(*(lam * v * 1.12 + np.array([0.05, 0.05])), r"$\lambda=%.2f$" % lam, color=col, fontsize=8.5)
    U, s, Vt = np.linalg.svd(A)
    for k in range(2):
        ax.plot([0, s[k] * U[0, k]], [0, s[k] * U[1, k]], color=common.BLUE, lw=0.8, ls=":")
    ax.set_title(title, fontsize=9.5)
    ax.set_aspect("equal")
    lim = 1.15 * max(1.2, s[0])
    ax.set_xlim(-lim, lim)
    ax.set_ylim(-lim, lim)
    ax.axhline(0, color="k", lw=0.4)
    ax.axvline(0, color="k", lw=0.4)


def fig_a_s1(out_dir=None):
    """Figure A.S1: three 2 x 2 matrices as maps of the unit circle (eigenvectors in red/green, image ellipse in blue)."""
    th = math.radians(25)
    c, s = math.cos(th), math.sin(th)
    Hh = np.array([[c * c - s * s, 2 * c * s], [2 * c * s, s * s - c * c]])   # reflection in the line at 25 degrees
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.4))
    _map_panel(axes[0], [[2, 1], [1, 2]], "(a) symmetric: orthogonal eigenvectors\nare the axes of the ellipse")
    _map_panel(axes[1], [[1, 2], [3, 4]], "(b) the book's (A.49): eigenvectors\nnot orthogonal, not the axes")
    _map_panel(axes[2], Hh, "(c) a reflection: orthogonal,\n$|\\mathbf{U}|=-1$, circle maps to itself")
    fig.tight_layout()
    save(fig, "figA-s1", out_dir)


def fig_a_s2(out_dir=None):
    """Figure A.S2: the quadratic form w^T A w for unit w = (cos t, sin t), against t."""
    t = np.linspace(0, np.pi, 400)
    W = np.stack([np.cos(t), np.sin(t)])
    mats = [([[2, 1], [1, 2]], "symmetric [[2,1],[1,2]]", common.GREEN),
            ([[1, 2], [3, 4]], "(A.49) [[1,2],[3,4]]", common.BLUE),
            ([[1, 4], [0, 1]], "[[1,4],[0,1]]", common.RED)]
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 2.9), sharey=False)
    for ax, (A, lab, col) in zip(axes, mats):
        A = np.array(A, float)
        q = np.einsum("in,ij,jn->n", W, A, W)
        ax.plot(np.degrees(t), q, color=col)
        ax.axhline(0, color="k", lw=0.5)
        s1, s2 = sym_part_eigs(A)
        e = eig2(A)
        for v in (s1, s2):
            ax.axhline(v, color=common.GREY, ls="--", lw=0.9)
        if e["real"]:
            for v in (e["l1"], e["l2"]):
                ax.axhline(v, color=common.MAGENTA, ls=":", lw=1.1)
        ax.fill_between(np.degrees(t), q, 0, where=q < 0, color=common.RED, alpha=0.15, lw=0)
        ax.set_title(lab, fontsize=9.5)
        ax.set_xlabel(r"angle of $\mathbf{w}$ (degrees)")
        ax.set_xlim(0, 180)
        ax.set_xticks([0, 45, 90, 135, 180])
    axes[0].set_ylabel(r"$\mathbf{w}^{\mathrm{T}}\mathbf{A}\mathbf{w}$, $\|\mathbf{w}\|=1$")
    axes[2].plot([], [], color=common.GREY, ls="--", label=r"eigenvalues of $\frac{1}{2}(\mathbf{A}+\mathbf{A}^{\mathrm{T}})$")
    axes[2].plot([], [], color=common.MAGENTA, ls=":", label=r"eigenvalues of $\mathbf{A}$")
    axes[2].legend(loc="upper right", fontsize=7.5, frameon=False)
    fig.tight_layout()
    save(fig, "figA-s2", out_dir)


def fig_b_s1(out_dir=None):
    """Figure B.S1: the Euler-Lagrange solution of (B.10) against direct minimisation, and F along y* + eps eta."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.1))
    ax = axes[0]
    xf = np.linspace(0, 1, 300)
    for (a, b), col in (((0, 1), common.BLUE), ((1, 1), common.RED), ((2, -1), common.GREEN)):
        ax.plot(xf, el_exact(xf, a, b), color=col, label=r"$y(0)=%g,\ y(1)=%g$" % (a, b))
        xd, yd = el_discrete(10, a, b)
        ax.plot(xd, yd, "o", color=col, ms=3.5, mfc="white")
    ax.set_xlabel(r"$x$")
    ax.set_ylabel(r"$y(x)$")
    ax.legend(fontsize=8, frameon=False, loc="lower left")
    ax.set_title("(a) closed form (lines), direct minimisation\nof the discretised functional (circles, 10 steps)", fontsize=9)
    ax = axes[1]
    n = 400
    x = np.linspace(0, 1, n + 1)
    ys = el_exact(x, 0, 1)
    eps = np.linspace(-1, 1, 101)
    for eta, col, lab in ((np.sin(np.pi * x), common.BLUE, r"$\eta=\sin\pi x$"),
                          (x * (1 - x) * (x - 0.3) * 8, common.RED, r"$\eta=8x(1-x)(x-0.3)$")):
        Fe = [F_quad(ys + e * eta, 1.0 / n) for e in eps]
        ax.plot(eps, Fe, color=col, label=lab)
    ax.axvline(0, color="k", lw=0.5)
    ax.set_xlabel(r"$\epsilon$")
    ax.set_ylabel(r"$F[y^\star+\epsilon\eta]$")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("(b) minimum at $\\epsilon=0$, slope zero there\n(the first variation (B.4) vanishes)", fontsize=9)
    fig.tight_layout()
    save(fig, "figB-s1", out_dir)


def fig_b_s2(out_dir=None):
    """Figure B.S2: the maximum entropy density found numerically, and the shortest path found numerically."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.1))
    ax = axes[0]
    x, p, H = maxent_grid()
    xf = np.linspace(-4, 4, 400)
    ax.plot(xf, np.exp(-xf ** 2 / 2) / math.sqrt(2 * math.pi), color=common.BLUE, label=r"$\mathcal{N}(0,1)$")
    ax.plot(x, p, "o", ms=2.6, color=common.RED, mfc="white", label="numerical maximiser")
    ax.plot(xf, np.exp(-np.sqrt(2) * np.abs(xf)) / np.sqrt(2), color=common.GREY, lw=1, ls="--", label="Laplace, same variance")
    ax.set_xlim(-4, 4)
    ax.set_xlabel(r"$x$")
    ax.set_title("(a) maximum entropy with mean 0, variance 1:\nH = %.4f nats (Gaussian %.4f)" % (H, 0.5 * math.log(2 * math.pi * math.e)), fontsize=9)
    ax.legend(fontsize=8, frameon=False)
    ax = axes[1]
    xs, y0, y1 = shortest_path()
    ax.plot(xs, y0, color=common.GREY, ls="--", label="start, length %.3f" % path_length(y0, xs))
    ax.plot(xs, y1, color=common.RED, label="minimiser, length %.6f" % path_length(y1, xs))
    ax.plot([0, 1], [0, 1], "o", color="k", ms=4)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$x$")
    ax.set_ylabel(r"$y$")
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    ax.set_title("(b) shortest path: the straight line\n(length $\\sqrt{2}=%.6f$)" % math.sqrt(2), fontsize=9)
    fig.tight_layout()
    save(fig, "figB-s2", out_dir)


def fig_c_s1(out_dir=None):
    """Figure C.S1: the KKT example as a grows: inactive (lam = 0) then active (g = 0); lam g = 0 throughout."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2), gridspec_kw={"width_ratios": [1, 1.25]})
    ax = axes[0]
    t = np.linspace(0, 2 * np.pi, 300)
    ax.fill(np.cos(t), np.sin(t), color=common.RED, alpha=0.08, lw=0)
    ax.plot(np.cos(t), np.sin(t), color=common.RED, lw=1.6)
    for a, col in ((0.4, common.GREEN), (1 / math.sqrt(2), common.GREY), (1.2, common.BLUE)):
        xs, lam, gv = kkt_disc(a)
        ax.plot(a, a, "+", color=col, ms=9)
        ax.plot(*xs, "o", color=col, ms=5)
        ax.plot([a, xs[0]], [a, xs[1]], color=col, lw=0.8, ls=":")
        ax.text(a + 0.06, a - 0.02, r"$a=%.2f$" % a, color=col, fontsize=8.5)
    ax.plot([0, 1.4], [0, 1.4], color="k", lw=0.4)
    ax.set_aspect("equal")
    ax.set_xlim(-1.15, 1.6)
    ax.set_ylim(-1.15, 1.6)
    ax.set_title("(a) + unconstrained maximum $(a,a)$,\n o constrained maximum", fontsize=9)
    ax = axes[1]
    a = np.linspace(0, 1.6, 400)
    L = np.array([kkt_disc(v)[1] for v in a])
    G = np.array([kkt_disc(v)[2] for v in a])
    ax.plot(a, L, color=common.BLUE, label=r"multiplier $\lambda^\star$")
    ax.plot(a, G, color=common.RED, label=r"constraint value $g(\mathbf{x}^\star)$")
    ax.plot(a, L * G, color="k", lw=1, ls="--", label=r"$\lambda^\star g(\mathbf{x}^\star)$ (always 0)")
    ax.axvline(1 / math.sqrt(2), color=common.GREY, lw=0.8, ls=":")
    ax.text(1 / math.sqrt(2) + 0.02, 1.0, r"$a=1/\sqrt{2}$", fontsize=8.5, color=common.GREY)
    ax.set_xlabel(r"centre $a$ of the objective")
    ax.legend(fontsize=8, frameon=False, loc="lower left")
    ax.set_title("(b) inactive ($\\lambda=0$, $g>0$), then active ($\\lambda>0$, $g=0$)", fontsize=9)
    fig.tight_layout()
    save(fig, "figC-s1", out_dir)


def fig_c_s2(out_dir=None):
    """Figure C.S2: (a) a constraint with a vanishing gradient (no multiplier); (b) the multiplier as a sensitivity."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    ax = axes[0]
    s = np.linspace(-1.2, 1.2, 400)
    ax.plot(np.abs(s) ** (2 / 3), s, color=common.RED, lw=2, label=r"$g=x_2^2-x_1^3=0$")
    for c in (-0.4, 0.0, 0.4, 0.8):
        ax.axvline(c, color=common.GREY, lw=0.8, ls="--")
    ax.plot(0, 0, "o", color="k", ms=5)
    _arrow(ax, (0, 0), (-0.45, 0), common.BLUE, r"$\nabla f$", 1.0, ha="right", va="bottom")
    ax.text(0.05, -0.18, r"$\nabla g(\mathbf{0})=\mathbf{0}$", color=common.GREEN, fontsize=9)
    ax.set_xlim(-0.75, 1.3)
    ax.set_ylim(-1.2, 1.2)
    ax.set_xlabel(r"$x_1$")
    ax.set_ylabel(r"$x_2$")
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    ax.set_title("(a) maximise $f=-x_1$: the maximum is the cusp,\nwhere no $\\lambda$ satisfies (C.3); dashed: contours of $f$", fontsize=9)
    ax = axes[1]
    c = np.linspace(0, 2, 200)
    ax.plot(c, book_example_value(c), color=common.BLUE, label=r"$f^\star(c)=1-c^2/2$")
    ax.plot(c, book_example_value(1.0) - 1.0 * (c - 1), color=common.RED, ls="--", label=r"slope $-\lambda=-1$ at $c=1$")
    ax.plot(1, book_example_value(1.0), "o", color="k", ms=4)
    ax.set_xlabel(r"constraint level $c$ in $x_1+x_2=c$")
    ax.set_ylabel("constrained maximum")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("(b) the example (C.5) with $x_1+x_2=c$:\n$\\mathrm{d}f^\\star/\\mathrm{d}c=-\\lambda$", fontsize=9)
    fig.tight_layout()
    save(fig, "figC-s2", out_dir)


FIGURES = {"B.1": fig_b_1, "C.1": fig_c_1, "C.2": fig_c_2, "C.3": fig_c_3,
           "A.S1": fig_a_s1, "A.S2": fig_a_s2, "B.S1": fig_b_s1, "B.S2": fig_b_s2,
           "C.S1": fig_c_s1, "C.S2": fig_c_s2}


def main(argv=None):
    """Command-line driver (common.run is written for numbered chapters)."""
    p = argparse.ArgumentParser(description="Reproduce the figures of Bishop and Bishop (2024), Appendices A-C.")
    p.add_argument("--fig", nargs="*", help="figure numbers, e.g. C.2 B.S1 (default: all)")
    p.add_argument("--out", default=None, help="output folder (default: ../img; files go to <out>/appendices)")
    p.add_argument("--list", action="store_true", help="list the reproducible figures")
    a = p.parse_args(argv)
    if a.list:
        for k, f in FIGURES.items():
            print(k, "-", (f.__doc__ or "").strip().split("\n")[0])
        return
    for k in a.fig or list(FIGURES):
        if k not in FIGURES:
            sys.exit("unknown figure %s; use --list" % k)
        t0 = time.time()
        FIGURES[k](a.out)
        print("  Figure %s done in %.1f s" % (k, time.time() - t0))


if __name__ == "__main__":
    main()
