Skip to main content

sealed_surface/
tree.rs

1//! Squarified treemap on the sealed painter (no SVG, no DOM text).
2
3use crate::appearance::{Appearance, TypeScale};
4use crate::chart::fmt_num;
5use crate::error::Error;
6use crate::host::{ClipboardPayload, HostProjection, HostText};
7use crate::layout::{CellBox, HitKind, HitMap, Pointer, MAX_PIXMAP_AXIS};
8use crate::lens::LicenseLens;
9use crate::model::{CellValue, Column, ColumnId, Grid, Row, RowId};
10use crate::raster::Pixmap;
11use crate::surface::{Frame, FrameRequest, Surface};
12use crate::theme::Rgb;
13
14/// Opaque tree-node id.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
16pub struct TreeId(pub u32);
17
18/// One node. Leaves carry area mass in [`Self::value`]; branches use the sum of children.
19#[derive(Debug, Clone, PartialEq)]
20pub struct TreeNode {
21    /// Opaque id.
22    pub id: TreeId,
23    /// Glyph label. Not host text when sealed.
24    pub name: String,
25    /// Leaf mass. Ignored when `children` is non-empty.
26    pub value: f64,
27    /// Nested nodes. Empty ⇒ leaf.
28    pub children: Vec<TreeNode>,
29}
30
31impl TreeNode {
32    /// Leaf.
33    #[must_use]
34    pub fn leaf(id: u32, name: impl Into<String>, value: f64) -> Self {
35        Self {
36            id: TreeId(id),
37            name: name.into(),
38            value,
39            children: Vec::new(),
40        }
41    }
42
43    /// Branch. `value` is ignored; mass is the sum of children.
44    #[must_use]
45    pub fn branch(id: u32, name: impl Into<String>, children: Vec<TreeNode>) -> Self {
46        Self {
47            id: TreeId(id),
48            name: name.into(),
49            value: 0.0,
50            children,
51        }
52    }
53
54    /// Area mass (leaf value, or sum of children).
55    #[must_use]
56    pub fn mass(&self) -> f64 {
57        if self.children.is_empty() {
58            if self.value.is_finite() && self.value > 0.0 {
59                self.value
60            } else {
61                0.0
62            }
63        } else {
64            self.children.iter().map(Self::mass).sum()
65        }
66    }
67
68    /// Keep the first `lens.sample_clear_rows` leaves (DFS). Drop empty branches.
69    #[must_use]
70    pub fn apply_lens(&self, lens: &LicenseLens) -> Self {
71        let mut remaining = lens.sample_clear_rows;
72        Self::filter_leaves(self, &mut remaining).unwrap_or_else(|| Self::leaf(self.id.0, "", 0.0))
73    }
74
75    fn filter_leaves(node: &Self, remaining: &mut usize) -> Option<Self> {
76        if node.children.is_empty() {
77            if *remaining == 0 {
78                return None;
79            }
80            if *remaining != usize::MAX {
81                *remaining -= 1;
82            }
83            return Some(node.clone());
84        }
85        let children: Vec<Self> = node
86            .children
87            .iter()
88            .filter_map(|c| Self::filter_leaves(c, remaining))
89            .collect();
90        if children.is_empty() {
91            return None;
92        }
93        Some(Self {
94            id: node.id,
95            name: node.name.clone(),
96            value: 0.0,
97            children,
98        })
99    }
100}
101
102/// Hierarchical area chart. Squarified layout (Bruls / van Wijk).
103#[derive(Debug, Clone, PartialEq)]
104pub struct TreeLayout {
105    root: TreeNode,
106}
107
108impl TreeLayout {
109    /// Root must have positive finite mass.
110    ///
111    /// # Errors
112    ///
113    /// [`Error::InvalidGrid`] when mass is not > 0.
114    pub fn try_new(root: TreeNode) -> Result<Self, Error> {
115        let m = root.mass();
116        if !m.is_finite() || m <= 0.0 {
117            return Err(Error::InvalidGrid("treemap mass must be > 0"));
118        }
119        Ok(Self { root })
120    }
121
122    /// Root as supplied (pre-lens).
123    #[must_use]
124    pub fn root(&self) -> &TreeNode {
125        &self.root
126    }
127
128    /// Paint on `surface` (same PNG / host contract as tables).
129    ///
130    /// # Errors
131    ///
132    /// Raster failure.
133    pub fn render(&self, surface: &Surface, request: &FrameRequest) -> Result<Frame, Error> {
134        surface.render_tree(self, request)
135    }
136}
137
138#[derive(Clone, Copy)]
139struct RectF {
140    x: f64,
141    y: f64,
142    w: f64,
143    h: f64,
144}
145
146struct Placed {
147    id: TreeId,
148    name: String,
149    value: f64,
150    x: u32,
151    y: u32,
152    w: u32,
153    h: u32,
154    color: Rgb,
155    leaf_index: Option<u32>,
156    /// False for the root branch (caption already names it).
157    paint_name: bool,
158}
159
160pub(crate) fn render_tree(
161    surface: &Surface,
162    layout: &TreeLayout,
163    request: &FrameRequest,
164) -> Result<Frame, Error> {
165    let viewed_root = layout.root.apply_lens(surface.lens());
166    let placeholder = surface.lens().style.glyph_str();
167    let Appearance {
168        theme,
169        type_scale: scale,
170        chart: style,
171    } = surface.appearance();
172
173    let vp = request.viewport;
174    let pixmap_w = vp.width.clamp(1, MAX_PIXMAP_AXIS);
175    let pixmap_h = vp.height.clamp(1, MAX_PIXMAP_AXIS);
176    let mut pm = Pixmap::new(pixmap_w, pixmap_h, theme.background)?;
177
178    let pad = scale.pad();
179    let top: u32 = if request.caption.is_some() {
180        scale.header_height()
181    } else {
182        pad
183    };
184    if let Some(caption) = &request.caption {
185        pm.text_scaled(
186            pad,
187            scale.pixel(),
188            caption,
189            theme.accent,
190            pixmap_w.saturating_sub(pad),
191            scale,
192        );
193    }
194
195    let plot_x0 = pad;
196    let plot_y0 = top;
197    let plot_w = pixmap_w.saturating_sub(pad.saturating_mul(2)).max(4);
198    let plot_h = pixmap_h.saturating_sub(top.saturating_add(pad)).max(4);
199    pm.fill_rect(plot_x0, plot_y0, plot_w, plot_h, style.plot_background);
200
201    let mut placed = Vec::new();
202    if viewed_root.mass() > 0.0 {
203        let mut leaf_i = 0u32;
204        place_node(
205            &viewed_root,
206            RectF {
207                x: f64::from(plot_x0),
208                y: f64::from(plot_y0),
209                w: f64::from(plot_w),
210                h: f64::from(plot_h),
211            },
212            0,
213            style.series[0],
214            &style.series,
215            &mut placed,
216            &mut leaf_i,
217        );
218    }
219
220    let hover = request.pointer.and_then(|p| hit_placed(&placed, p));
221
222    for (i, node) in placed.iter().enumerate() {
223        if node.w < 2 || node.h < 2 {
224            continue;
225        }
226        let fill = if hover == Some(i) {
227            node.color.mix(theme.hover, 96)
228        } else {
229            node.color
230        };
231        if node.leaf_index.is_some() {
232            pm.fill_rect(node.x, node.y, node.w, node.h, fill);
233        }
234        let border = if hover == Some(i) {
235            theme.crosshair
236        } else {
237            theme.grid
238        };
239        stroke_rect(&mut pm, node.x, node.y, node.w, node.h, border);
240        paint_label(&mut pm, node, scale, theme.text, placeholder);
241    }
242
243    let mut boxes = Vec::new();
244    for node in &placed {
245        boxes.push(CellBox {
246            row_index: node.leaf_index,
247            col_index: node.id.0,
248            row: RowId(node.leaf_index.unwrap_or(0)),
249            col: ColumnId(node.id.0),
250            x: node.x,
251            y: node.y,
252            w: node.w,
253            h: node.h,
254            header: false,
255            kind: HitKind::Node,
256        });
257    }
258
259    let tooltip_png = match hover {
260        Some(i) => tree_tooltip(&placed[i], placeholder, theme, scale)?,
261        None => None,
262    };
263
264    let viewed = tree_to_grid(&viewed_root)?;
265    let n = viewed.rows.len() as u32;
266    let host = tree_host(surface, request, &viewed_root);
267
268    let png = pm.to_png()?;
269    Ok(Frame {
270        png,
271        hits: HitMap { boxes },
272        host,
273        tooltip_png,
274        viewed,
275        content_width: pixmap_w,
276        content_height: pixmap_h,
277        visible_row_start: 0,
278        visible_row_end: n,
279    })
280}
281
282fn place_node(
283    node: &TreeNode,
284    rect: RectF,
285    depth: u32,
286    color: Rgb,
287    palette: &[Rgb; 4],
288    out: &mut Vec<Placed>,
289    leaf_i: &mut u32,
290) {
291    let Some((x, y, w, h)) = to_u32_rect(rect) else {
292        return;
293    };
294    let is_leaf = node.children.is_empty();
295    let leaf_index = if is_leaf {
296        let i = *leaf_i;
297        *leaf_i += 1;
298        Some(i)
299    } else {
300        None
301    };
302    out.push(Placed {
303        id: node.id,
304        name: node.name.clone(),
305        value: node.mass(),
306        x,
307        y,
308        w,
309        h,
310        color,
311        leaf_index,
312        paint_name: is_leaf || depth > 0,
313    });
314    if is_leaf {
315        return;
316    }
317    let header = if depth > 0 && h > 18 && w > 24 {
318        10u32
319    } else {
320        0
321    };
322    let inner = RectF {
323        x: f64::from(x.saturating_add(1)),
324        y: f64::from(y.saturating_add(1).saturating_add(header)),
325        w: f64::from(w.saturating_sub(2)),
326        h: f64::from(h.saturating_sub(2).saturating_sub(header)),
327    };
328    if inner.w < 2.0 || inner.h < 2.0 {
329        return;
330    }
331    let masses: Vec<f64> = node.children.iter().map(TreeNode::mass).collect();
332    let child_rects = squarify(&masses, inner);
333    for (i, (ch, cr)) in node.children.iter().zip(child_rects).enumerate() {
334        let child_color = mix_depth(palette[i % palette.len()], depth.saturating_add(1));
335        place_node(
336            ch,
337            cr,
338            depth.saturating_add(1),
339            child_color,
340            palette,
341            out,
342            leaf_i,
343        );
344    }
345}
346
347fn mix_depth(color: Rgb, depth: u32) -> Rgb {
348    let a = match depth {
349        0 | 1 => 0,
350        2 => 28,
351        3 => 48,
352        _ => 64,
353    };
354    if a == 0 {
355        color
356    } else {
357        Rgb::new(0x16, 0x1b, 0x24).mix(color, 255u8.saturating_sub(a))
358    }
359}
360
361fn to_u32_rect(r: RectF) -> Option<(u32, u32, u32, u32)> {
362    if r.w < 1.0 || r.h < 1.0 || !r.w.is_finite() || !r.h.is_finite() {
363        return None;
364    }
365    let x = r.x.max(0.0) as u32;
366    let y = r.y.max(0.0) as u32;
367    let w = r.w as u32;
368    let h = r.h as u32;
369    if w == 0 || h == 0 {
370        None
371    } else {
372        Some((x, y, w, h))
373    }
374}
375
376fn hit_placed(placed: &[Placed], p: Pointer) -> Option<usize> {
377    placed
378        .iter()
379        .enumerate()
380        .rev()
381        .find(|(_, n)| {
382            p.x >= n.x
383                && p.y >= n.y
384                && p.x < n.x.saturating_add(n.w)
385                && p.y < n.y.saturating_add(n.h)
386        })
387        .map(|(i, _)| i)
388}
389
390fn stroke_rect(pm: &mut Pixmap, x: u32, y: u32, w: u32, h: u32, color: Rgb) {
391    pm.hline(x, y, w, color);
392    pm.hline(x, y.saturating_add(h.saturating_sub(1)), w, color);
393    pm.vline(x, y, h, color);
394    pm.vline(x.saturating_add(w.saturating_sub(1)), y, h, color);
395}
396
397fn paint_label(pm: &mut Pixmap, node: &Placed, scale: TypeScale, color: Rgb, placeholder: &str) {
398    if !node.paint_name {
399        return;
400    }
401    if node.w < scale.advance().saturating_add(4) || node.h < 8 {
402        return;
403    }
404    let label = if node.value <= 0.0 && node.leaf_index.is_some() {
405        placeholder
406    } else {
407        node.name.as_str()
408    };
409    let max_w = node.w.saturating_sub(4);
410    pm.text_scaled(
411        node.x.saturating_add(2),
412        node.y.saturating_add(2),
413        label,
414        color,
415        max_w,
416        scale,
417    );
418    if node.leaf_index.is_some() && node.h > scale.row_height().saturating_add(4) {
419        let mut val = String::new();
420        fmt_num(node.value, &mut val);
421        pm.text_scaled(
422            node.x.saturating_add(2),
423            node.y.saturating_add(2).saturating_add(scale.pixel() * 8),
424            &val,
425            color,
426            max_w,
427            scale,
428        );
429    }
430}
431
432fn tree_tooltip(
433    node: &Placed,
434    placeholder: &str,
435    theme: crate::theme::Theme,
436    scale: TypeScale,
437) -> Result<Option<Vec<u8>>, Error> {
438    let mut label = String::new();
439    if node.name.is_empty() {
440        label.push_str(placeholder);
441    } else {
442        label.push_str(&node.name);
443    }
444    label.push_str(": ");
445    if node.value <= 0.0 && node.leaf_index.is_some() {
446        label.push_str(placeholder);
447    } else {
448        fmt_num(node.value, &mut label);
449    }
450    let tw = crate::font::measure(&label, scale)
451        .saturating_add(16)
452        .max(48);
453    let th = scale.row_height().saturating_add(6).max(22);
454    let mut pm = Pixmap::new(tw.max(40), th, theme.tooltip)?;
455    pm.fill_rect(0, 0, pm.width(), 1, theme.accent);
456    pm.text_scaled(
457        6,
458        scale.pixel() * 2,
459        &label,
460        theme.text,
461        pm.width().saturating_sub(8),
462        scale,
463    );
464    Ok(Some(pm.to_png()?))
465}
466
467fn tree_host(surface: &Surface, request: &FrameRequest, root: &TreeNode) -> HostProjection {
468    if surface.mode().is_sealed() {
469        return HostProjection::sealed();
470    }
471    let mut text_nodes = Vec::new();
472    if let Some(caption) = &request.caption {
473        text_nodes.push(HostText {
474            kind: "caption",
475            text: caption.clone(),
476        });
477    }
478    let mut tsv = String::from("name\tvalue\n");
479    write_leaf_tsv(root, &mut tsv);
480    HostProjection {
481        text_nodes,
482        clipboard: Some(ClipboardPayload::Tsv(tsv)),
483    }
484}
485
486fn write_leaf_tsv(node: &TreeNode, tsv: &mut String) {
487    if node.children.is_empty() {
488        tsv.push_str(&node.name);
489        tsv.push('\t');
490        fmt_num(node.mass(), tsv);
491        tsv.push('\n');
492        return;
493    }
494    for c in &node.children {
495        write_leaf_tsv(c, tsv);
496    }
497}
498
499fn tree_to_grid(root: &TreeNode) -> Result<Grid, Error> {
500    let columns = vec![Column::new(0, "name"), Column::new(1, "value")];
501    let mut rows = Vec::new();
502    collect_leaves(root, &mut rows);
503    if rows.is_empty() {
504        rows.push(Row::new(0, vec![CellValue::Redacted, CellValue::Redacted]));
505    }
506    Grid::try_new(columns, rows)
507}
508
509fn collect_leaves(node: &TreeNode, rows: &mut Vec<Row>) {
510    if node.children.is_empty() {
511        let id = rows.len() as u32;
512        let mut vs = String::new();
513        fmt_num(node.mass(), &mut vs);
514        rows.push(Row::new(
515            id,
516            vec![CellValue::text(node.name.clone()), CellValue::text(vs)],
517        ));
518        return;
519    }
520    for c in &node.children {
521        collect_leaves(c, rows);
522    }
523}
524
525/// Squarified treemap (Bruls, Huizing, van Wijk). `values` order is preserved.
526fn squarify(values: &[f64], rect: RectF) -> Vec<RectF> {
527    let n = values.len();
528    if n == 0 {
529        return Vec::new();
530    }
531    let total: f64 = values.iter().copied().sum();
532    if total <= 0.0 || rect.w <= 0.0 || rect.h <= 0.0 {
533        return vec![
534            RectF {
535                w: 0.0,
536                h: 0.0,
537                ..rect
538            };
539            n
540        ];
541    }
542    let scale = (rect.w * rect.h) / total;
543    let areas: Vec<f64> = values.iter().map(|v| v * scale).collect();
544    let mut out = vec![
545        RectF {
546            x: 0.0,
547            y: 0.0,
548            w: 0.0,
549            h: 0.0
550        };
551        n
552    ];
553    let mut i = 0usize;
554    let mut x = rect.x;
555    let mut y = rect.y;
556    let mut w = rect.w;
557    let mut h = rect.h;
558    while i < n && w > 0.0 && h > 0.0 {
559        let side = w.min(h);
560        let mut row_end = i;
561        let mut best_worst = f64::INFINITY;
562        for j in i..n {
563            let worst_j = worst(&areas[i..=j], side);
564            if j > i && worst_j > best_worst {
565                break;
566            }
567            best_worst = worst_j;
568            row_end = j + 1;
569        }
570        let row = &areas[i..row_end];
571        let row_area: f64 = row.iter().sum();
572        if w >= h {
573            let rw = (row_area / h).max(0.0);
574            let mut cy = y;
575            for (k, a) in row.iter().enumerate() {
576                let rh = if rw > 0.0 { a / rw } else { 0.0 };
577                out[i + k] = RectF {
578                    x,
579                    y: cy,
580                    w: rw,
581                    h: rh,
582                };
583                cy += rh;
584            }
585            x += rw;
586            w = (w - rw).max(0.0);
587        } else {
588            let rh = (row_area / w).max(0.0);
589            let mut cx = x;
590            for (k, a) in row.iter().enumerate() {
591                let rw = if rh > 0.0 { a / rh } else { 0.0 };
592                out[i + k] = RectF {
593                    x: cx,
594                    y,
595                    w: rw,
596                    h: rh,
597                };
598                cx += rw;
599            }
600            y += rh;
601            h = (h - rh).max(0.0);
602        }
603        i = row_end;
604    }
605    out
606}
607
608fn worst(row: &[f64], side: f64) -> f64 {
609    if row.is_empty() || side <= 0.0 {
610        return f64::INFINITY;
611    }
612    let s: f64 = row.iter().sum();
613    if s <= 0.0 {
614        return f64::INFINITY;
615    }
616    let max = row.iter().copied().fold(0.0_f64, f64::max);
617    let min = row.iter().copied().fold(f64::INFINITY, f64::min);
618    let side2 = side * side;
619    (side2 * max / (s * s)).max((s * s) / (side2 * min.max(1e-12)))
620}
621
622#[cfg(test)]
623mod tests {
624    use super::*;
625
626    #[test]
627    fn squarify_two_equal_splits_area() {
628        let r = RectF {
629            x: 0.0,
630            y: 0.0,
631            w: 100.0,
632            h: 100.0,
633        };
634        let out = squarify(&[1.0, 1.0], r);
635        assert_eq!(out.len(), 2);
636        let a0 = out[0].w * out[0].h;
637        let a1 = out[1].w * out[1].h;
638        assert!((a0 - 5000.0).abs() < 1.0, "{a0}");
639        assert!((a1 - 5000.0).abs() < 1.0, "{a1}");
640    }
641
642    #[test]
643    fn squarify_preserves_order_and_coverage() {
644        let r = RectF {
645            x: 10.0,
646            y: 20.0,
647            w: 80.0,
648            h: 40.0,
649        };
650        let vals = [4.0, 1.0, 2.0, 1.0];
651        let out = squarify(&vals, r);
652        let total: f64 = out.iter().map(|c| c.w * c.h).sum();
653        assert!((total - 3200.0).abs() < 2.0, "{total}");
654        assert!(out[0].w * out[0].h > out[1].w * out[1].h);
655    }
656
657    #[test]
658    fn mass_sums_children() {
659        let t = TreeNode::branch(
660            0,
661            "root",
662            vec![TreeNode::leaf(1, "a", 10.0), TreeNode::leaf(2, "b", 5.0)],
663        );
664        assert!((t.mass() - 15.0).abs() < 1e-9);
665    }
666}