facett_plotters/

treemap.rs

//! **Treemap** — weighted rectangles, area ∝ value, laid out by a deterministic
//! **slice-and-dice** algorithm that alternates split direction by depth-of-cut
//! so the tiling stays readable. The layout ([`squarify`]) is a pure function
//! returning `(index, Rect)` pairs, tested independently of any painter. Tile
//! fills come from a theme-derived sequential [`Ramp`](crate::ramp::Ramp).

use egui::{Align2, FontId, Pos2, Rect, Sense, Stroke, Ui, vec2};
use facett_core::clip::{ClipKind, ClipPayload, CopySource};
use facett_core::{Elm, FacetCaps, Semantics, a11y_node, theme};
use serde::{Deserialize, Serialize};

use crate::boxplot::paint_tooltip;
use crate::ramp::{Ramp, normalize};

/// A labelled, weighted item.
#[derive(Clone, Debug, PartialEq)]
pub struct Tile {
    pub label: String,
    pub value: f64,
}

impl Tile {
    pub fn new(label: impl Into<String>, value: f64) -> Self {
        Self { label: label.into(), value: value.max(0.0) }
    }
}

/// Lay `weights` out into `area`, area ∝ weight, via squarified slice-and-dice.
/// Returns `(original index, rect)` for each positive-weight item, in input
/// order. Zero/negative weights are skipped. Pure geometry → directly testable.
pub fn squarify(area: Rect, weights: &[f64]) -> Vec<(usize, Rect)> {
    // Keep only positive weights, remembering their original index.
    let items: Vec<(usize, f64)> = weights.iter().copied().enumerate().filter(|&(_, w)| w > 0.0).collect();
    let total: f64 = items.iter().map(|(_, w)| w).sum();
    let mut out = Vec::with_capacity(items.len());
    if total <= 0.0 || items.is_empty() {
        return out;
    }
    layout_slice(area, &items, total, &mut out);
    out
}

/// Recursive squarify: at each step split the longest side and pack a prefix of
/// items whose summed weight ≈ proportional to that strip, recursing on the rest.
fn layout_slice(area: Rect, items: &[(usize, f64)], total: f64, out: &mut Vec<(usize, Rect)>) {
    if items.is_empty() {
        return;
    }
    if items.len() == 1 {
        out.push((items[0].0, area));
        return;
    }
    // Take a prefix summing to ~half the weight → balanced binary split.
    let half = total / 2.0;
    let mut acc = 0.0;
    let mut cut = 0;
    for (i, &(_, w)) in items.iter().enumerate() {
        if acc + w > half && i > 0 {
            break;
        }
        acc += w;
        cut = i + 1;
    }
    cut = cut.clamp(1, items.len() - 1);
    let (left, right) = items.split_at(cut);
    let left_w: f64 = left.iter().map(|(_, w)| w).sum();
    let frac = (left_w / total) as f32;

    let (a, b) = if area.width() >= area.height() {
        let xm = area.left() + area.width() * frac;
        (Rect::from_min_max(area.min, Pos2::new(xm, area.bottom())), Rect::from_min_max(Pos2::new(xm, area.top()), area.max))
    } else {
        let ym = area.top() + area.height() * frac;
        (Rect::from_min_max(area.min, Pos2::new(area.right(), ym)), Rect::from_min_max(Pos2::new(area.left(), ym), area.max))
    };
    layout_slice(a, left, left_w, out);
    layout_slice(b, right, total - left_w, out);
}

/// Persistent, observable interaction state (FC-3): the original tile index the
/// pointer last hovered. Serialized so it round-trips headlessly.
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct TreemapState {
    /// The hovered tile's *original* index (into `tiles`), or `None`.
    pub hover: Option<usize>,
}

/// FC-2 input surface. One input: the hovered tile changing (hit-tested purely in
/// [`TreemapView::render`], applied in [`TreemapView::update`]).
#[derive(Clone, Debug, PartialEq)]
pub enum TreemapMsg {
    /// Set (or clear, with `None`) the hovered tile index.
    Hover(Option<usize>),
}

/// FC-8: the treemap does no I/O.
#[derive(Clone, Debug)]
pub enum TreemapEffect {}

/// A treemap over a flat list of weighted tiles.
pub struct TreemapView {
    pub title: String,
    pub tiles: Vec<Tile>,
    /// Observable interaction state (FC-3).
    pub state: TreemapState,
}

impl TreemapView {
    pub fn new(title: impl Into<String>, tiles: Vec<Tile>) -> Self {
        Self { title: title.into(), tiles, state: TreemapState::default() }
    }

    /// FC-3: read the complete observable interaction state.
    pub fn state(&self) -> &TreemapState {
        &self.state
    }

    /// FC-2/FC-8: the single mutation path. Apply one [`TreemapMsg`]; no effects.
    pub fn update(&mut self, msg: TreemapMsg) -> Vec<TreemapEffect> {
        match msg {
            TreemapMsg::Hover(h) => self.state.hover = h,
        }
        Vec::new()
    }

    fn value_range(&self) -> (f64, f64) {
        let mut lo = f64::INFINITY;
        let mut hi = f64::NEG_INFINITY;
        for t in &self.tiles {
            lo = lo.min(t.value);
            hi = hi.max(t.value);
        }
        if lo.is_finite() { (lo, hi) } else { (0.0, 0.0) }
    }

    fn to_csv(&self) -> String {
        let mut s = String::from("label,value\n");
        for t in &self.tiles {
            s.push_str(&format!("{},{}\n", t.label, t.value));
        }
        s
    }
}

// ── typed copy (§16) — the chart dataset as CSV Text ──────────────────
impl CopySource for TreemapView {
    fn copy_kinds(&self) -> &[ClipKind] {
        &[ClipKind::Text]
    }
    fn copy_payload(&self) -> Option<ClipPayload> {
        let csv = self.to_csv();
        (!csv.is_empty()).then_some(ClipPayload::Text(csv))
    }
}

impl TreemapView {
    /// FC-9 pure view: paints the tiles + hover tooltip (from the *stored* hover
    /// tile) and **returns** the hovered-tile change as a `Msg` — never mutates.
    fn render(&self, ui: &mut Ui) -> Vec<TreemapMsg> {
        let th = theme(ui);
        let ramp = Ramp::sequential(&th);
        let (rect, resp) = ui.allocate_exact_size(ui.available_size(), Sense::hover());
        let painter = ui.painter_at(rect);
        painter.rect_filled(rect, egui::CornerRadius::ZERO, th.bg);
        let weights: Vec<f64> = self.tiles.iter().map(|t| t.value).collect();
        let area = rect.shrink(6.0);
        let rects = squarify(area, &weights);
        if rects.is_empty() {
            // ── render-lane emit: this Facet::ui path RAN ─────────────────────────
            #[cfg(feature = "testmatrix")]
            facett_core::testmatrix::emit(
                "facett-plotters::TreemapView::ui",
                "ui_render",
                rects.is_empty(),
                &format!("drew=empty_hint tiles={} rects={}", self.tiles.len(), rects.len()),
            );
            painter.text(rect.center(), Align2::CENTER_CENTER, "no data", FontId::proportional(13.0), th.text_dim);
            return hover_msg(self.state.hover, None);
        }
        let (vmin, vmax) = self.value_range();
        let hover = resp.hover_pos();
        let mut new_hover: Option<usize> = None;
        let base = ui.id().with("treemap");

        for (idx, r) in &rects {
            let t = &self.tiles[*idx];
            let color = ramp.at(normalize(t.value, vmin, vmax));
            painter.rect_filled(r.shrink(1.0), egui::CornerRadius::same(2), color);
            painter.rect_stroke(r.shrink(1.0), egui::CornerRadius::same(2), Stroke::new(1.0, th.bg), egui::StrokeKind::Inside);
            // AccessKit node over the tile (FC-4): role=Image, label = the tile's
            // label, numeric_value = its weight/area value. Keyed on the original
            // index so identity is stable even if two tiles share a label (FC-5);
            // the label is disambiguated with the index for query-uniqueness.
            a11y_node(
                ui,
                base,
                *idx,
                Sense::hover(),
                *r,
                Semantics::image(format!("{} · tile {idx}", t.label)).value(t.value),
            );
            // Label only if the tile is roomy enough to read.
            if r.width() > 42.0 && r.height() > 18.0 {
                painter.text(
                    r.left_top() + vec2(4.0, 3.0),
                    Align2::LEFT_TOP,
                    &t.label,
                    FontId::proportional(11.0),
                    contrast_text(color),
                );
            }
            if let Some(hp) = hover {
                if r.contains(hp) {
                    new_hover = Some(*idx);
                }
            }
        }
        // Tooltip painted last (on top) from the *persisted* hover tile (set by
        // `update` last frame), keeping `render` a pure function of `&self`.
        if let Some(hp) = hover {
            if let Some(t) = self.state.hover.and_then(|i| self.tiles.get(i)) {
                paint_tooltip(&painter, &th, hp, &format!("{}\n{:.3}", t.label, t.value));
            }
        }
        // ── render-lane emit: this Facet::ui path RAN ─────────────────────────
        #[cfg(feature = "testmatrix")]
        facett_core::testmatrix::emit(
            "facett-plotters::TreemapView::ui",
            "ui_render",
            !rects.is_empty() && rects.len() <= self.tiles.len(),
            &format!("tiles={} rects={}", self.tiles.len(), rects.len()),
        );
        hover_msg(self.state.hover, new_hover)
    }
}

/// Emit a `Hover` message only when the hovered tile actually changed.
fn hover_msg(current: Option<usize>, next: Option<usize>) -> Vec<TreemapMsg> {
    if current != next { vec![TreemapMsg::Hover(next)] } else { Vec::new() }
}

impl Elm for TreemapView {
    type Model = TreemapState;
    type Msg = TreemapMsg;
    type Effect = TreemapEffect;

    fn title(&self) -> &str {
        &self.title
    }
    fn state(&self) -> &TreemapState {
        &self.state
    }
    fn update(&mut self, msg: TreemapMsg) -> Vec<TreemapEffect> {
        TreemapView::update(self, msg)
    }
    fn view(&self, ui: &mut Ui) -> Vec<TreemapMsg> {
        self.render(ui)
    }
}

// Form 3: richer derived `state_json` (tile count + total + labels) preserved
// exactly, so the macro's default `serde(state())` is suppressed.
facett_core::impl_facet_via_elm!(TreemapView, custom_state_json, {
    fn caps(&self) -> FacetCaps {
        FacetCaps::NONE.themeable().copyable().resizable()
    }
    fn copy(&mut self) -> Option<String> {
        Some(self.to_csv())
    }
    fn state_json(&self) -> serde_json::Value {
        let total: f64 = self.tiles.iter().map(|t| t.value).sum();
        serde_json::json!({
            "kind": "treemap",
            "tiles": self.tiles.len(),
            "total": total,
            "labels": self.tiles.iter().map(|t| &t.label).collect::<Vec<_>>(),
        })
    }
});

/// Pick black or white text for legibility over `bg` (luminance threshold).
fn contrast_text(bg: egui::Color32) -> egui::Color32 {
    let lum = 0.299 * bg.r() as f32 + 0.587 * bg.g() as f32 + 0.114 * bg.b() as f32;
    if lum > 140.0 { egui::Color32::from_gray(20) } else { egui::Color32::from_gray(235) }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn typed_copy_is_the_dataset_csv() {
        use facett_core::clip::{ClipKind, CopySource};
        let v = TreemapView::new("t", vec![Tile::new("a", 3.0), Tile::new("b", 7.0)]);
        let p = v.copy_payload().expect("tiles copy");
        assert_eq!(p.kind(), ClipKind::Text);
        assert_eq!(p.as_text(), v.to_csv());
    }

    fn area() -> Rect {
        Rect::from_min_size(Pos2::new(0.0, 0.0), vec2(100.0, 100.0))
    }

    #[test]
    fn rects_cover_area_and_match_count() {
        let rects = squarify(area(), &[1.0, 1.0, 1.0, 1.0]);
        assert_eq!(rects.len(), 4);
        // total tiled area equals the input area (slice-and-dice is a partition)
        let sum: f32 = rects.iter().map(|(_, r)| r.area()).sum();
        assert!((sum - area().area()).abs() < 1.0, "tiles must partition the area");
    }

    #[test]
    fn area_is_proportional_to_weight() {
        let rects = squarify(area(), &[3.0, 1.0]);
        let a0 = rects.iter().find(|(i, _)| *i == 0).unwrap().1.area();
        let a1 = rects.iter().find(|(i, _)| *i == 1).unwrap().1.area();
        // 3:1 weight → ~3:1 area
        assert!((a0 / a1 - 3.0).abs() < 0.2, "ratio {} should be ~3", a0 / a1);
    }

    #[test]
    fn zero_and_negative_weights_skipped() {
        let rects = squarify(area(), &[2.0, 0.0, -5.0, 2.0]);
        let idxs: Vec<usize> = rects.iter().map(|(i, _)| *i).collect();
        assert_eq!(idxs, vec![0, 3]);
    }

    #[test]
    fn empty_and_all_zero_produce_nothing() {
        assert!(squarify(area(), &[]).is_empty());
        assert!(squarify(area(), &[0.0, 0.0]).is_empty());
    }

    #[test]
    fn single_tile_fills_whole_area() {
        let rects = squarify(area(), &[5.0]);
        assert_eq!(rects.len(), 1);
        assert_eq!(rects[0].1, area());
    }

    #[test]
    fn rects_are_disjoint() {
        let rects = squarify(area(), &[1.0, 2.0, 3.0, 4.0, 5.0]);
        for i in 0..rects.len() {
            for j in (i + 1)..rects.len() {
                let inter = rects[i].1.intersect(rects[j].1);
                assert!(inter.width() < 0.5 || inter.height() < 0.5, "tiles {i},{j} overlap");
            }
        }
    }

    // ── Elm (FC-2/FC-3) harness properties ────────────────────────────────
    #[test]
    fn hover_transitions_are_observable() {
        let mut v = TreemapView::new("t", vec![Tile::new("a", 3.0), Tile::new("b", 7.0)]);
        assert_eq!(v.state().hover, None);
        let snap = facett_core::harness::snapshot(&mut v, [TreemapMsg::Hover(Some(1))]);
        assert_eq!(snap.hover, Some(1));
        let snap = facett_core::harness::snapshot(&mut v, [TreemapMsg::Hover(None)]);
        assert_eq!(snap.hover, None);
    }

    #[test]
    fn drive_produces_no_effects() {
        let mut v = TreemapView::new("t", vec![Tile::new("a", 3.0)]);
        let effects = facett_core::harness::drive(&mut v, [TreemapMsg::Hover(Some(0)), TreemapMsg::Hover(None)]);
        assert!(effects.is_empty());
    }

    #[test]
    fn state_serde_round_trips() {
        let st = TreemapState { hover: Some(4) };
        let back: TreemapState = serde_json::from_value(serde_json::to_value(&st).unwrap()).unwrap();
        assert_eq!(st, back);
    }
}