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::{Facet, FacetCaps, Semantics, a11y_node, theme};

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);
}

/// A treemap over a flat list of weighted tiles.
pub struct TreemapView {
    pub title: String,
    pub tiles: Vec<Tile>,
}

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

    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
    }
}

impl Facet for TreemapView {
    fn title(&self) -> &str {
        &self.title
    }
    fn caps(&self) -> FacetCaps {
        FacetCaps::NONE.themeable().copyable().resizable()
    }
    fn copy(&mut self) -> Option<String> {
        Some(self.to_csv())
    }
    fn ui(&mut self, ui: &mut Ui) {
        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() {
            painter.text(rect.center(), Align2::CENTER_CENTER, "no data", FontId::proportional(13.0), th.text_dim);
            return;
        }
        let (vmin, vmax) = self.value_range();
        let hover = resp.hover_pos();
        let mut tip: Option<(Pos2, String)> = 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) {
                    tip = Some((hp, format!("{}\n{:.3}", t.label, t.value)));
                }
            }
        }
        if let Some((at, text)) = tip {
            paint_tooltip(&painter, &th, at, &text);
        }
    }
    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::*;

    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");
            }
        }
    }
}