"""James et al. (2021, 2023), Chapter 8: Tree-Based Methods.

Reproduces the figures of Chapter 8 of G. James, D. Witten, T. Hastie and R. Tibshirani, An Introduction
to Statistical Learning with Applications in R, 2nd edition (Springer, 2021), pp. 327-365 (the same
figures appear in the Python edition of 2023, with J. Taylor), written from scratch with numpy, scipy,
scikit-learn and matplotlib. The trees come from ch08_lab.py: RTree grows and prunes trees with the rules
of R's tree package, Forest grows bagged trees and random forests, BART is the sampler of Algorithm 8.3;
RRandom reproduces R's set.seed()/sample(), so every training set below can be drawn in R as well.

Figures reproduced: 8.1, 8.2, 8.4, 8.5, 8.6, 8.7, 8.8, 8.9, 8.13, and two figures for the exercises
(ex8-3: Gini index, entropy and error rate; ex8-4: the solutions of Exercise 4).
Skipped:
* 8.3 and 8.12 are schematic drawings (a partition that recursive binary splitting cannot produce, and
  three made-up perturbations of a BART tree);
* 8.10 and 8.11 use a gene-expression data set (349 tissue samples, 4718 genes, 15 classes) that is not
  distributed with the book; Exercise 7 makes the analogue of Figure 8.10 on the Boston data;
* 8.14 is the drawing that Exercise 4 asks about (its solution is figure ex8-4).
Run `python3 ch08_tree_based_methods.py --list`, or `--fig 8.5`, or `--fig demos` to write the data of the
three demonstrations to ../data/ch08-*.json and print their reference numbers.

Settings chosen where the book gives none:
* Figures 8.1-8.2: all 263 players with a salary, log(Salary) on Years and Hits; the tree grown with
  tree()'s default controls and pruned to three leaves (it gives the book's 5.107, 5.998, 6.740).
* Figures 8.4-8.5: nine inputs (AtBat, Hits, HmRun, Runs, RBI, Walks, Years, PutOuts, Assists), training
  set R's set.seed(1); sample(263, 132); six folds by row number (row i of the training set in fold
  i mod 6). The CV error is computed at the cost-complexity values k of the tree grown on the whole
  training set and shown against that tree's size (the book's footnote 2); the bars are +/- 1 standard
  error (over the six folds for CV, over the test players for the test error).
* Figures 8.6, 8.8, 8.9, 8.13: the 297 patients with no missing value; training set R's set.seed(2);
  sample(297, 150). Trees for Figure 8.6 grown with deviance, pruned with the misclassification count,
  ten-fold CV with folds set.seed(3); sample(10, 150, replace = TRUE). For the forests, ChestPain and
  Thal become one 0/1 column per level (4 + 3 columns), so p = 18 columns, and m = 4 (about sqrt(18),
  and the book's 4 of 13) for the random forest. Forests: 300 trees, numpy default_rng(88).
* Figure 8.7: x uniform on [-2, 2]^2, 200 training and 10000 test points (numpy default_rng(87));
  top row: class 1 when x1 + x2 > 0 (a linear boundary); bottom row: class 1 when x1 > -0.5 and
  x2 > -0.5; fits: logistic regression and a tree pruned by ten-fold CV.
* Figure 8.13: probit BART with K = 200 trees, 100 burn-in iterations, and 10000 iterations in all;
  the error at iteration b uses the posterior mean of the draws after burn-in up to b (and the current
  draw during burn-in). Boosting: gbm_like() with stumps and shrinkage 0.1. Cached in cache/ch08_fig8_13.npz.
"""
import json
import os

import numpy as np
import pandas as pd

import common
from common import BLUE, GREEN, GREY, ORANGE, RED, savefig
from ch08_lab import (BART, Forest, RRandom, RTree, cv_tree, draw_tree, dummies, factors, gbm_like, mse)

HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE = os.path.join(HERE, "cache")
NINE = ["AtBat", "Hits", "HmRun", "Runs", "RBI", "Walks", "Years", "PutOuts", "Assists"]


def hitters():
    H = factors(common.isl_data("Hitters")).dropna().reset_index(drop=True)
    H["logSalary"] = np.log(H["Salary"])
    return H


def heart():
    D = factors(common.isl_data("Heart", index_col=0)).dropna().reset_index(drop=True)
    tr = RRandom(2).sample(len(D), 150) - 1
    te = np.setdiff1d(np.arange(len(D)), tr)
    return D, tr, te


def heart_matrix(D):
    """Heart inputs as numbers for scikit-learn: ChestPain and Thal as 0/1 columns (one per level)."""
    X = dummies(D.drop(columns="AHD"), drop_first=False)
    return X, (D["AHD"] == "Yes").to_numpy(int)


# ======================================================================== Figures 8.1 and 8.2
def years_hits_tree():
    H = hitters()
    t = RTree().fit(H[["Years", "Hits"]], H["logSalary"])
    return H, t, t.prune(3)


def fig_8_1(out=None):
    """The three-leaf regression tree for log(Salary) on Years and Hits."""
    import matplotlib.pyplot as plt
    _, _, p = years_hits_tree()
    fig, ax = plt.subplots(figsize=(4.2, 3.4))
    draw_tree(p, ax, digits=2, fontsize=10, leaf_fmt=lambda s: "%.2f" % s["yval"])
    return savefig(fig, 8, "fig8-1", out)


def fig_8_2(out=None):
    """The three regions of Figure 8.1 in the (Years, Hits) plane."""
    import matplotlib.pyplot as plt
    H, _, p = years_hits_tree()
    fig, ax = plt.subplots(figsize=(4.6, 4.0))
    ax.scatter(H["Years"], H["Hits"], s=9, c=ORANGE, alpha=0.7, lw=0)
    ax.axvline(4.5, color=GREEN, lw=2)
    ax.plot([4.5, 25], [117.5, 117.5], color=GREEN, lw=2)
    for x, y, lab in ((2.2, 200, "R1"), (14, 50, "R2"), (14, 200, "R3")):
        ax.text(x, y, lab, fontsize=14, ha="center", va="center")
    ax.set(xlabel="Years", ylabel="Hits", xlim=(0, 25), ylim=(0, 240), xticks=[1, 4.5, 24], yticks=[1, 117.5, 238])
    return savefig(fig, 8, "fig8-2", out)


# ======================================================================== Figures 8.4 and 8.5
def hitters_split():
    H = hitters()
    tr = RRandom(1).sample(len(H), 132) - 1
    te = np.setdiff1d(np.arange(len(H)), tr)
    return H, tr, te


def fig_8_4(out=None):
    """The unpruned tree grown on the 132 training players with nine inputs."""
    import matplotlib.pyplot as plt
    H, tr, _ = hitters_split()
    t = RTree().fit(H[NINE].iloc[tr], H["logSalary"].iloc[tr])
    fig, ax = plt.subplots(figsize=(9, 5))
    draw_tree(t, ax, digits=3, fontsize=8)
    return savefig(fig, 8, "fig8-4", out)


def tree_size_curves():
    """Training, six-fold CV and test MSE (with standard errors) along the pruned sequence (Figure 8.5)."""
    H, tr, te = hitters_split()
    X, y = H[NINE], H["logSalary"]
    t = RTree().fit(X.iloc[tr], y.iloc[tr])
    seq = t.prune_sequence()
    sizes, ks = seq["size"], seq["k"]
    train = seq["dev"] / len(tr)
    test, test_se = [], []
    for s in sizes:
        e = (t.prune(s).predict(X.iloc[te]) - y.iloc[te].to_numpy()) ** 2
        test.append(e.mean())
        test_se.append(e.std(ddof=1) / np.sqrt(len(e)))
    fold = np.arange(len(tr)) % 6
    per_fold = []
    Xtr, ytr = X.iloc[tr].reset_index(drop=True), y.iloc[tr].reset_index(drop=True)
    for f in range(6):
        tl = RTree().fit(Xtr[fold != f], ytr[fold != f])
        per_fold.append(tl.prune_sequence(k=ks, newX=Xtr[fold == f], newy=ytr[fold == f])["dev"] / (fold == f).sum())
    per_fold = np.array(per_fold)
    return dict(size=sizes, k=ks, train=train, test=np.array(test), test_se=np.array(test_se),
                cv=per_fold.mean(0), cv_se=per_fold.std(0, ddof=1) / np.sqrt(6))


def fig_8_5(out=None):
    """Training, cross-validation and test MSE against the size of the pruned tree."""
    import matplotlib.pyplot as plt
    c = tree_size_curves()
    keep = c["size"] <= 11
    fig, ax = plt.subplots(figsize=(4.8, 4.0))
    ax.plot(c["size"][keep], c["train"][keep], "o-", color="black", ms=3.5, label="Training")
    ax.errorbar(c["size"][keep], c["cv"][keep], yerr=c["cv_se"][keep], fmt="o-", color=GREEN, ms=3.5, capsize=2, label="Cross-Validation")
    ax.errorbar(c["size"][keep], c["test"][keep], yerr=c["test_se"][keep], fmt="o-", color=ORANGE, ms=3.5, capsize=2, label="Test")
    ax.set(xlabel="Tree Size", ylabel="Mean Squared Error", ylim=(0, 1.0))
    ax.legend(frameon=False)
    return savefig(fig, 8, "fig8-5", out)


# ======================================================================== Figure 8.6
def heart_trees():
    D, tr, te = heart()
    X, y = D.drop(columns="AHD"), D["AHD"]
    t = RTree().fit(X.iloc[tr], y.iloc[tr])
    seq = t.prune_sequence("misclass")
    rand = RRandom(3).sample(10, len(tr), replace=True)
    cv = cv_tree(t, X.iloc[tr], y.iloc[tr], rand, method="misclass")
    yte = y.iloc[te].astype(str).to_numpy()
    test = np.array([np.mean(t.prune(s, "misclass").predict(X.iloc[te], "class", rng=RRandom(4)) != yte) for s in seq["size"]])
    j = int(np.argmin(cv["dev"][::-1]))                  # the smallest tree among the CV minima
    best = int(cv["size"][::-1][j])
    return dict(tree=t, pruned=t.prune(best, "misclass"), size=seq["size"], train=seq["dev"] / len(tr),
                cv=cv["dev"] / len(tr), test=test, best=best)


def fig_8_6(out=None):
    """Heart data: the unpruned tree, the error curves, and the tree pruned by cross-validation."""
    import matplotlib.pyplot as plt
    h = heart_trees()
    fig = plt.figure(figsize=(10, 8))
    ax = fig.add_axes([0.0, 0.47, 1.0, 0.53])
    draw_tree(h["tree"], ax, fontsize=7)
    ax = fig.add_axes([0.07, 0.06, 0.38, 0.36])
    ax.plot(h["size"], h["train"], "o-", color="black", ms=3, label="Training")
    ax.plot(h["size"], h["cv"], "o-", color=GREEN, ms=3, label="Cross-Validation")
    ax.plot(h["size"], h["test"], "o-", color=ORANGE, ms=3, label="Test")
    ax.set(xlabel="Tree Size", ylabel="Error", ylim=(0, 0.6))
    ax.legend(frameon=False, fontsize=8)
    ax = fig.add_axes([0.52, 0.04, 0.47, 0.38])
    draw_tree(h["pruned"], ax, fontsize=8)
    return savefig(fig, 8, "fig8-6", out)


# ======================================================================== Figure 8.7
def fig_8_7(out=None):
    """A linear and a non-linear boundary: logistic regression against a classification tree."""
    import matplotlib.pyplot as plt
    from matplotlib.colors import ListedColormap
    from sklearn.linear_model import LogisticRegression
    rng = np.random.default_rng(87)
    Xtr, Xte = rng.uniform(-2, 2, (200, 2)), rng.uniform(-2, 2, (10000, 2))
    truths = [lambda X: (X[:, 0] + X[:, 1] > 0).astype(int),
              lambda X: ((X[:, 0] > -0.5) & (X[:, 1] > -0.5)).astype(int)]
    g = np.linspace(-2, 2, 241)
    G = np.array(np.meshgrid(g, g)).reshape(2, -1).T
    fig, axes = plt.subplots(2, 2, figsize=(7.2, 7.0))
    cmap = ListedColormap(["#f4d8a8", "#b9d7ee"])
    res = {}
    for r, truth in enumerate(truths):
        ytr, yte = truth(Xtr), truth(Xte)
        lg = LogisticRegression(C=1e6, max_iter=10000).fit(Xtr, ytr)    # (nearly) unpenalised
        lin = lambda Z: lg.predict(Z)
        df = pd.DataFrame(Xtr, columns=["X1", "X2"])
        yc = pd.Series(np.where(ytr == 1, "b", "a"))
        t = RTree().fit(df, yc)
        rand = (np.arange(200) % 10) + 1
        cv = cv_tree(t, df, yc, rand, method="misclass")
        best = int(cv["size"][::-1][int(np.argmin(cv["dev"][::-1]))])
        tp = t.prune(best, "misclass") if best < len(t.leaves()) else t
        tree = lambda Z: (tp.predict(pd.DataFrame(Z, columns=["X1", "X2"]), "class") == "b").astype(int)
        for c, (name, f) in enumerate((("linear", lin), ("tree", tree))):
            ax = axes[r, c]
            ax.contourf(g, g, f(G).reshape(len(g), len(g)), levels=[-0.5, 0.5, 1.5], cmap=cmap)
            if r == 0:
                ax.plot([-2, 2], [2, -2], color="black", lw=1, ls="--")
            else:
                ax.plot([-0.5, -0.5, 2], [2, -0.5, -0.5], color="black", lw=1, ls="--")
            ax.scatter(Xtr[:, 0], Xtr[:, 1], c=np.where(ytr == 1, BLUE, ORANGE), s=7, lw=0)
            err = np.mean(f(Xte) != yte)
            res[(r, name)] = err
            ax.set_title("%s, test error %.3f" % ("logistic regression" if name == "linear" else "tree (%d leaves)" % len(tp.leaves()), err), fontsize=9)
            ax.set(xlabel="X1", ylabel="X2", xlim=(-2, 2), ylim=(-2, 2), aspect="equal")
    print("Figure 8.7 test errors:", {k: round(v, 4) for k, v in res.items()})
    return savefig(fig, 8, "fig8-7", out)


# ======================================================================== Figures 8.8 and 8.9
def heart_forests(B=300):
    D, tr, te = heart()
    X, y = heart_matrix(D)
    X = X.to_numpy(float)
    out = {}
    for name, m in (("bagging", X.shape[1]), ("forest", 4)):
        F = Forest(m, ntree=B, classification=True, seed=88).fit(X[tr], y[tr])
        P = F.tree_predictions(X[te])                    # class index 0/1 for each tree
        votes = np.cumsum(P, 0)
        nb = np.arange(1, B + 1)[:, None]
        test = ((2 * votes > nb).astype(int) != y[te]).mean(1)
        Po = F.tree_predictions(X[tr])
        oobm = F.inbag == 0
        v1, vn = np.cumsum(Po * oobm, 0), np.cumsum(oobm, 0)
        ok = vn > 0
        oob = np.array([np.mean(((2 * v1[b] > vn[b]).astype(int) != y[tr])[ok[b]]) for b in range(B)])
        out[name] = dict(test=test, oob=oob, forest=F)
    h = heart_trees()
    out["single_tree"] = h["test"][list(h["size"]).index(h["best"])]
    out["names"] = list(heart_matrix(D)[0].columns)
    return out


def fig_8_8(out=None):
    """Bagging and a random forest on the Heart data: test and out-of-bag error against B."""
    import matplotlib.pyplot as plt
    r = heart_forests()
    B = np.arange(1, 301)
    fig, ax = plt.subplots(figsize=(5.6, 4.2))
    ax.plot(B, r["bagging"]["test"], color="black", lw=1.2, label="Test: Bagging")
    ax.plot(B, r["forest"]["test"], color=ORANGE, lw=1.2, label="Test: RandomForest")
    ax.plot(B, r["bagging"]["oob"], color=GREEN, lw=1.2, label="OOB: Bagging")
    ax.plot(B, r["forest"]["oob"], color=BLUE, lw=1.2, label="OOB: RandomForest")
    ax.axhline(r["single_tree"], color="black", ls="--", lw=1)
    ax.set(xlabel="Number of Trees", ylabel="Error", ylim=(0.05, 0.35))
    ax.legend(frameon=False, fontsize=8)
    print("Figure 8.8: after 300 trees test error bagging %.4f, forest %.4f; OOB %.4f, %.4f; single tree %.4f"
          % (r["bagging"]["test"][-1], r["forest"]["test"][-1], r["bagging"]["oob"][-1], r["forest"]["oob"][-1], r["single_tree"]))
    return savefig(fig, 8, "fig8-8", out)


def heart_importance():
    r = heart_forests()
    imp = r["forest"]["forest"].importance()["IncNodePurity"]
    imp.index = r["names"]
    groups = {}
    for nm, v in imp.items():                            # add the 0/1 columns of a factor back together
        base = "ChestPain" if nm.startswith("ChestPain") else "Thal" if nm.startswith("Thal") else nm
        groups[base] = groups.get(base, 0.0) + v
    s = pd.Series(groups)
    return 100 * s / s.max()


def fig_8_9(out=None):
    """Variable importance (mean decrease in the Gini index) for the Heart data, relative to the largest."""
    import matplotlib.pyplot as plt
    s = heart_importance().sort_values()
    fig, ax = plt.subplots(figsize=(5.2, 4.2))
    ax.barh(np.arange(len(s)), s.to_numpy(), color=RED, height=0.6)
    ax.set_yticks(np.arange(len(s)), s.index)
    ax.set(xlabel="Variable Importance", xlim=(0, 100))
    print("Figure 8.9 importances:", s.sort_values(ascending=False).round(1).to_dict())
    return savefig(fig, 8, "fig8-9", out)


# ======================================================================== Figure 8.13
def bart_vs_boosting(iters=10000):
    path = os.path.join(CACHE, "ch08_fig8_13.npz")
    if os.path.exists(path):
        return dict(np.load(path))
    D, tr, te = heart()
    X, y = heart_matrix(D)
    X = X.to_numpy(float)
    from scipy.stats import norm
    L = 100
    rec = {"bart_train": [], "bart_test": []}
    acc = {"tr": np.zeros(len(tr)), "te": np.zeros(len(te))}

    def trace(it, ftr, fte):
        ptr, pte = norm.cdf(ftr), norm.cdf(fte)
        if it >= L:
            acc["tr"] += ptr
            acc["te"] += pte
            ptr, pte = acc["tr"] / (it - L + 1), acc["te"] / (it - L + 1)
        rec["bart_train"].append(np.mean((ptr > 0.5) != y[tr]))
        rec["bart_test"].append(np.mean((pte > 0.5) != y[te]))
    BART(ntree=200, nskip=L, ndpost=iters - L, binary=True, seed=13).fit(X[tr], y[tr], X[te], keep_draws=False, trace=trace)
    g = gbm_like(iters, depth=1, shrinkage=0.1, classification=True, seed=13).fit(X[tr], y[tr])
    rec["boost_train"] = [np.mean(p != y[tr]) for p in g.staged_predict(X[tr])]
    rec["boost_test"] = [np.mean(p != y[te]) for p in g.staged_predict(X[te])]
    rec = {k: np.array(v) for k, v in rec.items()}
    os.makedirs(CACHE, exist_ok=True)
    np.savez(path, **rec)
    return rec


def fig_8_13(out=None):
    """BART and boosting on the Heart data: training and test error against the number of iterations."""
    import matplotlib.pyplot as plt
    r = bart_vs_boosting()
    it = np.arange(1, len(r["bart_train"]) + 1)
    fig, ax = plt.subplots(figsize=(5.8, 4.2))
    ax.axvspan(1, 100, color="#dddddd")
    ax.plot(it, r["bart_train"], color=GREEN, lw=1, label="BART Training Error")
    ax.plot(it, r["bart_test"], color=RED, lw=1, label="BART Test Error")
    ax.plot(it, r["boost_train"], color=GREY, lw=1, label="Boosting Training Error")
    ax.plot(it, r["boost_test"], color=BLUE, lw=1, label="Boosting Test Error")
    ax.set(xscale="log", xlabel="Number of Iterations", ylabel="Error", ylim=(0, 0.5), xlim=(5, len(it)))
    ax.legend(frameon=False, fontsize=8)
    print("Figure 8.13: final BART train/test %.4f %.4f; boosting train/test %.4f %.4f; boosting test min %.4f at %d"
          % (r["bart_train"][-1], r["bart_test"][-1], r["boost_train"][-1], r["boost_test"][-1],
             r["boost_test"].min(), 1 + int(np.argmin(r["boost_test"]))))
    return savefig(fig, 8, "fig8-13", out)


# ======================================================================== exercise figures
def fig_ex_8_3(out=None):
    """Exercise 3: Gini index, entropy and classification error for two classes."""
    import matplotlib.pyplot as plt
    p = np.linspace(0.0005, 0.9995, 999)
    fig, ax = plt.subplots(figsize=(4.8, 3.6))
    ax.plot(p, 2 * p * (1 - p), color=BLUE, label="Gini index")
    ax.plot(p, -(p * np.log(p) + (1 - p) * np.log(1 - p)), color=RED, label="entropy (natural log)")
    ax.plot(p, 1 - np.maximum(p, 1 - p), color=GREEN, label="classification error")
    ax.set(xlabel=r"$\hat p_{m1}$", ylabel="impurity", xlim=(0, 1), ylim=(0, 0.72))
    ax.legend(frameon=False, fontsize=8)
    return savefig(fig, 8, "ex8-3", out)


def fig_ex_8_4(out=None):
    """Exercise 4: (a) the tree for the left panel of Figure 8.14; (b) the partition for its right panel."""
    import matplotlib.pyplot as plt
    fig, ax = plt.subplots(1, 2, figsize=(9, 3.8))
    a = ax[0]
    nodes = {(0, 0): "X1 < 1", (-1, -1): "X2 < 1", (1, -1): "5", (-1.6, -2): "X1 < 0", (-0.4, -2): "15",
             (-2.2, -3): "3", (-1.0, -3): "X2 < 0", (-1.5, -4): "10", (-0.5, -4): "0"}
    edges = [((0, 0), (-1, -1)), ((0, 0), (1, -1)), ((-1, -1), (-1.6, -2)), ((-1, -1), (-0.4, -2)),
             ((-1.6, -2), (-2.2, -3)), ((-1.6, -2), (-1.0, -3)), ((-1.0, -3), (-1.5, -4)), ((-1.0, -3), (-0.5, -4))]
    for (x0, y0), (x1, y1) in edges:
        a.plot([x0, x0, x1, x1], [y0, y0 - 0.5, y0 - 0.5, y1], color=BLUE, lw=1)
    for (x, y), lab in nodes.items():
        internal = "<" in lab
        a.text(x, y + (0.05 if internal else -0.08), lab, ha="center", va="bottom" if internal else "top", fontsize=9)
    a.set_xlim(-2.7, 1.5)
    a.set_ylim(-4.6, 0.4)
    a.axis("off")
    a.set_title("(a) the tree; each label is the left branch", fontsize=9)
    b = ax[1]
    b.plot([-1, 2], [1, 1], color="black")
    b.plot([1, 1], [-1, 1], color="black")
    b.plot([-1, 2], [2, 2], color="black")
    b.plot([0, 0], [1, 2], color="black")
    for x, y, lab in ((0, 0, "-1.80"), (1.5, 0, "0.63"), (-0.5, 1.5, "-1.06"), (1.0, 1.5, "0.21"), (0.5, 2.5, "2.49")):
        b.text(x, y, lab, ha="center", va="center", fontsize=10)
    b.set(xlim=(-1, 2), ylim=(-1, 3), xlabel="X1", ylabel="X2")
    b.set_title("(b) the partition, with the mean of Y in each region", fontsize=9)
    return savefig(fig, 8, "ex8-4", out)


# ======================================================================== demonstrations
class Mulberry32:
    """The generator of the demonstrations (DK.rng in demo-kit.js): the same numbers as in the browser."""

    def __init__(self, seed):
        self.a = seed & 0xffffffff

    @staticmethod
    def _imul(a, b):
        return (a * b) & 0xffffffff

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


def demo_forest(X, y, Xte, yte, m, B, seed):
    """The forest of the forest demonstration, step for step as in the browser: Gini splits, grown to
    purity, m candidate columns drawn afresh at every split, bootstrap samples from Mulberry32."""
    rng = Mulberry32(seed)
    n, p = X.shape
    order = [np.argsort(X[:, j], kind="stable") for j in range(p)]

    def grow(cnt):
        nodes = []

        def node(cnt):
            tot = cnt.sum()
            pos = (cnt * y).sum()
            k = len(nodes)
            nodes.append(None)
            if pos == 0 or pos == tot or tot < 2:
                nodes[k] = ("leaf", pos / tot)
                return k
            feats = list(range(p))
            for i in range(m):
                j = i + int(rng.u() * (p - i))
                feats[i], feats[j] = feats[j], feats[i]
            best, bf, bthr = None, -1, 0.0
            for f in feats[:m]:
                nl = l1 = 0.0
                prev = None
                for i in order[f]:
                    c = cnt[i]
                    if c == 0:
                        continue
                    xv = X[i, f]
                    if prev is not None and xv > prev and nl > 0:
                        nr, r1 = tot - nl, pos - l1
                        imp = (nl - (l1 * l1 + (nl - l1) * (nl - l1)) / nl) + (nr - (r1 * r1 + (nr - r1) * (nr - r1)) / nr)
                        if best is None or imp < best:
                            best, bf, bthr = imp, f, 0.5 * (prev + xv)
                    nl += c
                    l1 += c * y[i]
                    prev = xv
            if bf < 0:
                nodes[k] = ("leaf", pos / tot)
                return k
            left = cnt * (X[:, bf] < bthr)
            right = cnt - left
            a = node(left)
            b = node(right)
            nodes[k] = ("split", bf, bthr, a, b)
            return k
        node(cnt)
        return nodes

    def predict(nodes, Z):
        out = np.zeros(len(Z), int)
        for r in range(len(Z)):
            k = 0
            while nodes[k][0] == "split":
                _, f, thr, a, b = nodes[k]
                k = a if Z[r, f] < thr else b
            out[r] = 1 if nodes[k][1] > 0.5 else 0
        return out
    trees, inbag = [], []
    for _ in range(B):
        cnt = np.zeros(n)
        for _ in range(n):
            cnt[int(rng.u() * n)] += 1
        trees.append(grow(cnt))
        inbag.append(cnt)
    Pte = np.array([predict(t, Xte) for t in trees])
    Ptr = np.array([predict(t, X) for t in trees])
    inbag = np.array(inbag)
    nb = np.arange(1, B + 1)[:, None]
    test = ((2 * np.cumsum(Pte, 0) > nb).astype(int) != yte).mean(1)
    oobm = inbag == 0
    v1, vn = np.cumsum(Ptr * oobm, 0), np.cumsum(oobm, 0)
    oob = np.array([np.mean(((2 * v1[b] > vn[b]).astype(int) != y)[vn[b] > 0]) for b in range(B)])
    roots = [t[0][1] if t[0][0] == "split" else -1 for t in trees]
    return dict(test=test, oob=oob, roots=roots, Pte=Pte)


def demo_boost(X, y, Xte, yte, lam, d, B, nmin=10, start_mean=True):
    """Algorithm 8.2 exactly as in the boosting demonstration: each tree has d splits, grown best-first
    (the split with the largest drop in RSS among all current leaves), at least nmin rows per leaf."""
    n, p = X.shape
    order = [np.argsort(X[:, j], kind="stable") for j in range(p)]
    f0 = y.mean() if start_mean else 0.0
    r = y - f0
    ftr, fte = np.full(n, f0), np.full(len(Xte), f0)
    train, test, infl = [], [], np.zeros(p)

    def best_split(mask):
        s = r[mask].sum()
        cnt = int(mask.sum())
        best = (0.0, -1, 0.0)
        if cnt < 2 * nmin:
            return best
        base = s * s / cnt
        for f in range(p):
            nl, sl, prev = 0, 0.0, None
            for i in order[f]:
                if not mask[i]:
                    continue
                xv = X[i, f]
                if prev is not None and xv > prev and nl >= nmin and cnt - nl >= nmin:
                    gain = sl * sl / nl + (s - sl) * (s - sl) / (cnt - nl) - base
                    if gain > best[0]:
                        best = (gain, f, 0.5 * (prev + xv))
                nl += 1
                sl += r[i]
                prev = xv
        return best
    for _ in range(B):
        leaves = [np.ones(n, bool)]
        tleaves = [np.ones(len(Xte), bool)]
        cand = [best_split(leaves[0])]
        for _s in range(d):
            k = int(np.argmax([c[0] for c in cand]))
            gain, f, thr = cand[k]
            if f < 0 or gain <= 0:
                break
            infl[f] += gain
            L, R = leaves[k] & (X[:, f] < thr), leaves[k] & ~(X[:, f] < thr)
            TL, TR = tleaves[k] & (Xte[:, f] < thr), tleaves[k] & ~(Xte[:, f] < thr)
            leaves[k:k + 1], tleaves[k:k + 1] = [L, R], [TL, TR]
            cand[k:k + 1] = [best_split(L), best_split(R)]
        for Lm, Tm in zip(leaves, tleaves):
            v = lam * r[Lm].mean()
            ftr[Lm] += v
            fte[Tm] += v
            r[Lm] -= v
        train.append(np.mean((y - ftr) ** 2))
        test.append(np.mean((yte - fte) ** 2))
    return dict(train=np.array(train), test=np.array(test), influence=100 * infl / max(infl.sum(), 1e-300))


def demos(out=None):
    """Write the data of the three demonstrations and print the numbers they must reproduce."""
    os.makedirs(DATA_OUT, exist_ok=True)
    # -- 1. growing and pruning a tree on Years and Hits
    H, _, _ = years_hits_tree()
    H["logSalary"] = np.round(H["logSalary"], 6)          # the values stored in the JSON file
    t = RTree().fit(H[["Years", "Hits"]], H["logSalary"])
    p3 = t.prune(3)
    seq = t.prune_sequence()
    ref1 = {"size": seq["size"].tolist(), "k": [None] + seq["k"][1:].tolist(), "rss": seq["dev"].tolist(),
            "leaves3": [p3.nodes[k]["yval"] for k in p3.leaves()], "full_leaves": len(t.leaves())}
    with open(os.path.join(DATA_OUT, "ch08-hitters-tree.json"), "w") as fh:
        json.dump({"years": H["Years"].astype(int).tolist(), "hits": H["Hits"].astype(int).tolist(),
                   "y": np.round(H["logSalary"], 6).tolist(), "ref": ref1}, fh, separators=(",", ":"))
    print("tree demo: full tree %d leaves; sequence sizes %s; k %s" % (len(t.leaves()), seq["size"].tolist(), np.round(seq["k"][1:], 5).tolist()))
    # -- 2. bagging against a random forest on the Heart data
    D, tr, te = heart()
    X, y = heart_matrix(D)
    names = list(X.columns)
    X = X.to_numpy(float)
    ref2 = {}
    for m in (18, 4):
        r = demo_forest(X[tr], y[tr], X[te], y[te], m, 100, seed=1)
        ref2["m%d" % m] = {"test100": float(r["test"][-1]), "oob100": float(r["oob"][-1]), "test10": float(r["test"][9]),
                           "roots": r["roots"][:20]}
        print("forest demo m = %d: test error after 10 / 100 trees %.4f / %.4f, OOB %.4f; root variables %s"
              % (m, r["test"][9], r["test"][-1], r["oob"][-1], r["roots"][:20]))
    ref2["single_tree"] = float(heart_forests(B=10)["single_tree"])
    with open(os.path.join(DATA_OUT, "ch08-heart-forest.json"), "w") as fh:
        json.dump({"names": names, "Xtr": X[tr].tolist(), "ytr": y[tr].tolist(), "Xte": X[te].tolist(), "yte": y[te].tolist(),
                   "ref": ref2}, fh, separators=(",", ":"))
    # -- 3. boosting on the Hitters data
    XH = dummies(H.drop(columns=["Salary", "logSalary"]))
    XHn, yH = np.round(XH.to_numpy(float), 6), H["logSalary"].to_numpy()
    ref3 = {}
    for lam, d, B in ((0.01, 1, 1000), (1.0, 1, 200), (0.1, 4, 300)):
        r = demo_boost(XHn[:200], yH[:200], XHn[200:], yH[200:], lam, d, B)
        ref3["%g_%d_%d" % (lam, d, B)] = {"train": float(r["train"][-1]), "test": float(r["test"][-1]),
                                          "test_min": float(r["test"].min()), "argmin": int(np.argmin(r["test"])) + 1}
        print("boosting demo lambda %g d %d B %d: train %.6f test %.6f (min %.6f at %d)"
              % (lam, d, B, r["train"][-1], r["test"][-1], r["test"].min(), np.argmin(r["test"]) + 1))
    r0 = demo_boost(XHn[:200], yH[:200], XHn[200:], yH[200:], 0.01, 1, 1000, start_mean=False)
    ref3["zero_start"] = {"train": float(r0["train"][-1]), "test": float(r0["test"][-1])}
    print("boosting demo, Algorithm 8.2 started at 0: train %.6f test %.6f" % (r0["train"][-1], r0["test"][-1]))
    A = np.column_stack([np.ones(200), XHn[:200]])
    ref3["lm_test"] = float(np.mean((np.column_stack([np.ones(len(yH) - 200), XHn[200:]]) @ np.linalg.lstsq(A, yH[:200], rcond=None)[0] - yH[200:]) ** 2))
    print("least squares on the same split: test MSE %.6f" % ref3["lm_test"])
    with open(os.path.join(DATA_OUT, "ch08-hitters-boost.json"), "w") as fh:
        json.dump({"names": list(XH.columns), "X": np.round(XHn, 6).tolist(), "y": np.round(yH, 6).tolist(), "ntrain": 200,
                   "ref": ref3}, fh, separators=(",", ":"))


FIGURES = {
    "8.1": fig_8_1, "8.2": fig_8_2, "8.4": fig_8_4, "8.5": fig_8_5, "8.6": fig_8_6, "8.7": fig_8_7,
    "8.8": fig_8_8, "8.9": fig_8_9, "8.13": fig_8_13, "ex8.3": fig_ex_8_3, "ex8.4": fig_ex_8_4, "demos": demos,
}

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