facett-plotters/src/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_f32, 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 && 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 && 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> {
facett_core::navgraph::declare_own_draw_order(ui); // atoms follow the data order (navgraph §9)
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);
}
}