facett_plotters/
treemap.rs

1//! **Treemap** — weighted rectangles, area ∝ value, laid out by a deterministic
2//! **slice-and-dice** algorithm that alternates split direction by depth-of-cut
3//! so the tiling stays readable. The layout ([`squarify`]) is a pure function
4//! returning `(index, Rect)` pairs, tested independently of any painter. Tile
5//! fills come from a theme-derived sequential [`Ramp`](crate::ramp::Ramp).
6
7use egui::{Align2, FontId, Pos2, Rect, Sense, Stroke, Ui, vec2};
8use facett_core::clip::{ClipKind, ClipPayload, CopySource};
9use facett_core::{Facet, FacetCaps, Semantics, a11y_node, theme};
10
11use crate::boxplot::paint_tooltip;
12use crate::ramp::{Ramp, normalize};
13
14/// A labelled, weighted item.
15#[derive(Clone, Debug, PartialEq)]
16pub struct Tile {
17    pub label: String,
18    pub value: f64,
19}
20
21impl Tile {
22    pub fn new(label: impl Into<String>, value: f64) -> Self {
23        Self { label: label.into(), value: value.max(0.0) }
24    }
25}
26
27/// Lay `weights` out into `area`, area ∝ weight, via squarified slice-and-dice.
28/// Returns `(original index, rect)` for each positive-weight item, in input
29/// order. Zero/negative weights are skipped. Pure geometry → directly testable.
30pub fn squarify(area: Rect, weights: &[f64]) -> Vec<(usize, Rect)> {
31    // Keep only positive weights, remembering their original index.
32    let items: Vec<(usize, f64)> = weights.iter().copied().enumerate().filter(|&(_, w)| w > 0.0).collect();
33    let total: f64 = items.iter().map(|(_, w)| w).sum();
34    let mut out = Vec::with_capacity(items.len());
35    if total <= 0.0 || items.is_empty() {
36        return out;
37    }
38    layout_slice(area, &items, total, &mut out);
39    out
40}
41
42/// Recursive squarify: at each step split the longest side and pack a prefix of
43/// items whose summed weight ≈ proportional to that strip, recursing on the rest.
44fn layout_slice(area: Rect, items: &[(usize, f64)], total: f64, out: &mut Vec<(usize, Rect)>) {
45    if items.is_empty() {
46        return;
47    }
48    if items.len() == 1 {
49        out.push((items[0].0, area));
50        return;
51    }
52    // Take a prefix summing to ~half the weight → balanced binary split.
53    let half = total / 2.0;
54    let mut acc = 0.0;
55    let mut cut = 0;
56    for (i, &(_, w)) in items.iter().enumerate() {
57        if acc + w > half && i > 0 {
58            break;
59        }
60        acc += w;
61        cut = i + 1;
62    }
63    cut = cut.clamp(1, items.len() - 1);
64    let (left, right) = items.split_at(cut);
65    let left_w: f64 = left.iter().map(|(_, w)| w).sum();
66    let frac = (left_w / total) as f32;
67
68    let (a, b) = if area.width() >= area.height() {
69        let xm = area.left() + area.width() * frac;
70        (Rect::from_min_max(area.min, Pos2::new(xm, area.bottom())), Rect::from_min_max(Pos2::new(xm, area.top()), area.max))
71    } else {
72        let ym = area.top() + area.height() * frac;
73        (Rect::from_min_max(area.min, Pos2::new(area.right(), ym)), Rect::from_min_max(Pos2::new(area.left(), ym), area.max))
74    };
75    layout_slice(a, left, left_w, out);
76    layout_slice(b, right, total - left_w, out);
77}
78
79/// A treemap over a flat list of weighted tiles.
80pub struct TreemapView {
81    pub title: String,
82    pub tiles: Vec<Tile>,
83}
84
85impl TreemapView {
86    pub fn new(title: impl Into<String>, tiles: Vec<Tile>) -> Self {
87        Self { title: title.into(), tiles }
88    }
89
90    fn value_range(&self) -> (f64, f64) {
91        let mut lo = f64::INFINITY;
92        let mut hi = f64::NEG_INFINITY;
93        for t in &self.tiles {
94            lo = lo.min(t.value);
95            hi = hi.max(t.value);
96        }
97        if lo.is_finite() { (lo, hi) } else { (0.0, 0.0) }
98    }
99
100    fn to_csv(&self) -> String {
101        let mut s = String::from("label,value\n");
102        for t in &self.tiles {
103            s.push_str(&format!("{},{}\n", t.label, t.value));
104        }
105        s
106    }
107}
108
109// ── typed copy (§16) — the chart dataset as CSV Text ──────────────────
110impl CopySource for TreemapView {
111    fn copy_kinds(&self) -> &[ClipKind] {
112        &[ClipKind::Text]
113    }
114    fn copy_payload(&self) -> Option<ClipPayload> {
115        let csv = self.to_csv();
116        (!csv.is_empty()).then_some(ClipPayload::Text(csv))
117    }
118}
119
120impl Facet for TreemapView {
121    fn title(&self) -> &str {
122        &self.title
123    }
124    fn caps(&self) -> FacetCaps {
125        FacetCaps::NONE.themeable().copyable().resizable()
126    }
127    fn copy(&mut self) -> Option<String> {
128        Some(self.to_csv())
129    }
130    fn ui(&mut self, ui: &mut Ui) {
131        let th = theme(ui);
132        let ramp = Ramp::sequential(&th);
133        let (rect, resp) = ui.allocate_exact_size(ui.available_size(), Sense::hover());
134        let painter = ui.painter_at(rect);
135        painter.rect_filled(rect, egui::CornerRadius::ZERO, th.bg);
136        let weights: Vec<f64> = self.tiles.iter().map(|t| t.value).collect();
137        let area = rect.shrink(6.0);
138        let rects = squarify(area, &weights);
139        if rects.is_empty() {
140            // ── render-lane emit: this Facet::ui path RAN ─────────────────────────
141            #[cfg(feature = "testmatrix")]
142            facett_core::testmatrix::emit(
143                "facett-plotters::TreemapView::ui",
144                "ui_render",
145                rects.is_empty(),
146                &format!("drew=empty_hint tiles={} rects={}", self.tiles.len(), rects.len()),
147            );
148            painter.text(rect.center(), Align2::CENTER_CENTER, "no data", FontId::proportional(13.0), th.text_dim);
149            return;
150        }
151        let (vmin, vmax) = self.value_range();
152        let hover = resp.hover_pos();
153        let mut tip: Option<(Pos2, String)> = None;
154        let base = ui.id().with("treemap");
155
156        for (idx, r) in &rects {
157            let t = &self.tiles[*idx];
158            let color = ramp.at(normalize(t.value, vmin, vmax));
159            painter.rect_filled(r.shrink(1.0), egui::CornerRadius::same(2), color);
160            painter.rect_stroke(r.shrink(1.0), egui::CornerRadius::same(2), Stroke::new(1.0, th.bg), egui::StrokeKind::Inside);
161            // AccessKit node over the tile (FC-4): role=Image, label = the tile's
162            // label, numeric_value = its weight/area value. Keyed on the original
163            // index so identity is stable even if two tiles share a label (FC-5);
164            // the label is disambiguated with the index for query-uniqueness.
165            a11y_node(
166                ui,
167                base,
168                *idx,
169                Sense::hover(),
170                *r,
171                Semantics::image(format!("{} · tile {idx}", t.label)).value(t.value),
172            );
173            // Label only if the tile is roomy enough to read.
174            if r.width() > 42.0 && r.height() > 18.0 {
175                painter.text(
176                    r.left_top() + vec2(4.0, 3.0),
177                    Align2::LEFT_TOP,
178                    &t.label,
179                    FontId::proportional(11.0),
180                    contrast_text(color),
181                );
182            }
183            if let Some(hp) = hover {
184                if r.contains(hp) {
185                    tip = Some((hp, format!("{}\n{:.3}", t.label, t.value)));
186                }
187            }
188        }
189        if let Some((at, text)) = tip {
190            paint_tooltip(&painter, &th, at, &text);
191        }
192        // ── render-lane emit: this Facet::ui path RAN ─────────────────────────
193        #[cfg(feature = "testmatrix")]
194        facett_core::testmatrix::emit(
195            "facett-plotters::TreemapView::ui",
196            "ui_render",
197            !rects.is_empty() && rects.len() <= self.tiles.len(),
198            &format!("tiles={} rects={}", self.tiles.len(), rects.len()),
199        );
200    }
201    fn state_json(&self) -> serde_json::Value {
202        let total: f64 = self.tiles.iter().map(|t| t.value).sum();
203        serde_json::json!({
204            "kind": "treemap",
205            "tiles": self.tiles.len(),
206            "total": total,
207            "labels": self.tiles.iter().map(|t| &t.label).collect::<Vec<_>>(),
208        })
209    }
210}
211
212/// Pick black or white text for legibility over `bg` (luminance threshold).
213fn contrast_text(bg: egui::Color32) -> egui::Color32 {
214    let lum = 0.299 * bg.r() as f32 + 0.587 * bg.g() as f32 + 0.114 * bg.b() as f32;
215    if lum > 140.0 { egui::Color32::from_gray(20) } else { egui::Color32::from_gray(235) }
216}
217
218#[cfg(test)]
219mod tests {
220    use super::*;
221
222    #[test]
223    fn typed_copy_is_the_dataset_csv() {
224        use facett_core::clip::{ClipKind, CopySource};
225        let v = TreemapView::new("t", vec![Tile::new("a", 3.0), Tile::new("b", 7.0)]);
226        let p = v.copy_payload().expect("tiles copy");
227        assert_eq!(p.kind(), ClipKind::Text);
228        assert_eq!(p.as_text(), v.to_csv());
229    }
230
231    fn area() -> Rect {
232        Rect::from_min_size(Pos2::new(0.0, 0.0), vec2(100.0, 100.0))
233    }
234
235    #[test]
236    fn rects_cover_area_and_match_count() {
237        let rects = squarify(area(), &[1.0, 1.0, 1.0, 1.0]);
238        assert_eq!(rects.len(), 4);
239        // total tiled area equals the input area (slice-and-dice is a partition)
240        let sum: f32 = rects.iter().map(|(_, r)| r.area()).sum();
241        assert!((sum - area().area()).abs() < 1.0, "tiles must partition the area");
242    }
243
244    #[test]
245    fn area_is_proportional_to_weight() {
246        let rects = squarify(area(), &[3.0, 1.0]);
247        let a0 = rects.iter().find(|(i, _)| *i == 0).unwrap().1.area();
248        let a1 = rects.iter().find(|(i, _)| *i == 1).unwrap().1.area();
249        // 3:1 weight → ~3:1 area
250        assert!((a0 / a1 - 3.0).abs() < 0.2, "ratio {} should be ~3", a0 / a1);
251    }
252
253    #[test]
254    fn zero_and_negative_weights_skipped() {
255        let rects = squarify(area(), &[2.0, 0.0, -5.0, 2.0]);
256        let idxs: Vec<usize> = rects.iter().map(|(i, _)| *i).collect();
257        assert_eq!(idxs, vec![0, 3]);
258    }
259
260    #[test]
261    fn empty_and_all_zero_produce_nothing() {
262        assert!(squarify(area(), &[]).is_empty());
263        assert!(squarify(area(), &[0.0, 0.0]).is_empty());
264    }
265
266    #[test]
267    fn single_tile_fills_whole_area() {
268        let rects = squarify(area(), &[5.0]);
269        assert_eq!(rects.len(), 1);
270        assert_eq!(rects[0].1, area());
271    }
272
273    #[test]
274    fn rects_are_disjoint() {
275        let rects = squarify(area(), &[1.0, 2.0, 3.0, 4.0, 5.0]);
276        for i in 0..rects.len() {
277            for j in (i + 1)..rects.len() {
278                let inter = rects[i].1.intersect(rects[j].1);
279                assert!(inter.width() < 0.5 || inter.height() < 0.5, "tiles {i},{j} overlap");
280            }
281        }
282    }
283}
facett_plotters/treemap.rs

facett_plotters/
treemap.rs
