use crate::appearance::{Appearance, TypeScale};
use crate::chart::fmt_num;
use crate::error::Error;
use crate::host::{ClipboardPayload, HostProjection, HostText};
use crate::layout::{CellBox, HitKind, HitMap, Pointer, MAX_PIXMAP_AXIS};
use crate::lens::LicenseLens;
use crate::model::{CellValue, Column, ColumnId, Grid, Row, RowId};
use crate::raster::Pixmap;
use crate::surface::{Frame, FrameRequest, Surface};
use crate::theme::Rgb;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct TreeId(pub u32);
#[derive(Debug, Clone, PartialEq)]
pub struct TreeNode {
pub id: TreeId,
pub name: String,
pub value: f64,
pub children: Vec<TreeNode>,
}
impl TreeNode {
#[must_use]
pub fn leaf(id: u32, name: impl Into<String>, value: f64) -> Self {
Self {
id: TreeId(id),
name: name.into(),
value,
children: Vec::new(),
}
}
#[must_use]
pub fn branch(id: u32, name: impl Into<String>, children: Vec<TreeNode>) -> Self {
Self {
id: TreeId(id),
name: name.into(),
value: 0.0,
children,
}
}
#[must_use]
pub fn mass(&self) -> f64 {
if self.children.is_empty() {
if self.value.is_finite() && self.value > 0.0 {
self.value
} else {
0.0
}
} else {
self.children.iter().map(Self::mass).sum()
}
}
#[must_use]
pub fn apply_lens(&self, lens: &LicenseLens) -> Self {
let mut remaining = lens.sample_clear_rows;
Self::filter_leaves(self, &mut remaining).unwrap_or_else(|| Self::leaf(self.id.0, "", 0.0))
}
fn filter_leaves(node: &Self, remaining: &mut usize) -> Option<Self> {
if node.children.is_empty() {
if *remaining == 0 {
return None;
}
if *remaining != usize::MAX {
*remaining -= 1;
}
return Some(node.clone());
}
let children: Vec<Self> = node
.children
.iter()
.filter_map(|c| Self::filter_leaves(c, remaining))
.collect();
if children.is_empty() {
return None;
}
Some(Self {
id: node.id,
name: node.name.clone(),
value: 0.0,
children,
})
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct TreeLayout {
root: TreeNode,
}
impl TreeLayout {
pub fn try_new(root: TreeNode) -> Result<Self, Error> {
let m = root.mass();
if !m.is_finite() || m <= 0.0 {
return Err(Error::InvalidGrid("treemap mass must be > 0"));
}
Ok(Self { root })
}
#[must_use]
pub fn root(&self) -> &TreeNode {
&self.root
}
pub fn render(&self, surface: &Surface, request: &FrameRequest) -> Result<Frame, Error> {
surface.render_tree(self, request)
}
}
#[derive(Clone, Copy)]
struct RectF {
x: f64,
y: f64,
w: f64,
h: f64,
}
struct Placed {
id: TreeId,
name: String,
value: f64,
x: u32,
y: u32,
w: u32,
h: u32,
color: Rgb,
leaf_index: Option<u32>,
paint_name: bool,
}
pub(crate) fn render_tree(
surface: &Surface,
layout: &TreeLayout,
request: &FrameRequest,
) -> Result<Frame, Error> {
let viewed_root = layout.root.apply_lens(surface.lens());
let placeholder = surface.lens().style.glyph_str();
let Appearance {
theme,
type_scale: scale,
chart: style,
} = surface.appearance();
let vp = request.viewport;
let pixmap_w = vp.width.clamp(1, MAX_PIXMAP_AXIS);
let pixmap_h = vp.height.clamp(1, MAX_PIXMAP_AXIS);
let mut pm = Pixmap::new(pixmap_w, pixmap_h, theme.background)?;
let pad = scale.pad();
let top: u32 = if request.caption.is_some() {
scale.header_height()
} else {
pad
};
if let Some(caption) = &request.caption {
pm.text_scaled(
pad,
scale.pixel(),
caption,
theme.accent,
pixmap_w.saturating_sub(pad),
scale,
);
}
let plot_x0 = pad;
let plot_y0 = top;
let plot_w = pixmap_w.saturating_sub(pad.saturating_mul(2)).max(4);
let plot_h = pixmap_h.saturating_sub(top.saturating_add(pad)).max(4);
pm.fill_rect(plot_x0, plot_y0, plot_w, plot_h, style.plot_background);
let mut placed = Vec::new();
if viewed_root.mass() > 0.0 {
let mut leaf_i = 0u32;
place_node(
&viewed_root,
RectF {
x: f64::from(plot_x0),
y: f64::from(plot_y0),
w: f64::from(plot_w),
h: f64::from(plot_h),
},
0,
style.series[0],
&style.series,
&mut placed,
&mut leaf_i,
);
}
let hover = request.pointer.and_then(|p| hit_placed(&placed, p));
for (i, node) in placed.iter().enumerate() {
if node.w < 2 || node.h < 2 {
continue;
}
let fill = if hover == Some(i) {
node.color.mix(theme.hover, 96)
} else {
node.color
};
if node.leaf_index.is_some() {
pm.fill_rect(node.x, node.y, node.w, node.h, fill);
}
let border = if hover == Some(i) {
theme.crosshair
} else {
theme.grid
};
stroke_rect(&mut pm, node.x, node.y, node.w, node.h, border);
paint_label(&mut pm, node, scale, theme.text, placeholder);
}
let mut boxes = Vec::new();
for node in &placed {
boxes.push(CellBox {
row_index: node.leaf_index,
col_index: node.id.0,
row: RowId(node.leaf_index.unwrap_or(0)),
col: ColumnId(node.id.0),
x: node.x,
y: node.y,
w: node.w,
h: node.h,
header: false,
kind: HitKind::Node,
});
}
let tooltip_png = match hover {
Some(i) => tree_tooltip(&placed[i], placeholder, theme, scale)?,
None => None,
};
let viewed = tree_to_grid(&viewed_root)?;
let n = viewed.rows.len() as u32;
let host = tree_host(surface, request, &viewed_root);
let png = pm.to_png()?;
Ok(Frame {
png,
hits: HitMap { boxes },
host,
tooltip_png,
viewed,
content_width: pixmap_w,
content_height: pixmap_h,
visible_row_start: 0,
visible_row_end: n,
})
}
fn place_node(
node: &TreeNode,
rect: RectF,
depth: u32,
color: Rgb,
palette: &[Rgb; 4],
out: &mut Vec<Placed>,
leaf_i: &mut u32,
) {
let Some((x, y, w, h)) = to_u32_rect(rect) else {
return;
};
let is_leaf = node.children.is_empty();
let leaf_index = if is_leaf {
let i = *leaf_i;
*leaf_i += 1;
Some(i)
} else {
None
};
out.push(Placed {
id: node.id,
name: node.name.clone(),
value: node.mass(),
x,
y,
w,
h,
color,
leaf_index,
paint_name: is_leaf || depth > 0,
});
if is_leaf {
return;
}
let header = if depth > 0 && h > 18 && w > 24 {
10u32
} else {
0
};
let inner = RectF {
x: f64::from(x.saturating_add(1)),
y: f64::from(y.saturating_add(1).saturating_add(header)),
w: f64::from(w.saturating_sub(2)),
h: f64::from(h.saturating_sub(2).saturating_sub(header)),
};
if inner.w < 2.0 || inner.h < 2.0 {
return;
}
let masses: Vec<f64> = node.children.iter().map(TreeNode::mass).collect();
let child_rects = squarify(&masses, inner);
for (i, (ch, cr)) in node.children.iter().zip(child_rects).enumerate() {
let child_color = mix_depth(palette[i % palette.len()], depth.saturating_add(1));
place_node(
ch,
cr,
depth.saturating_add(1),
child_color,
palette,
out,
leaf_i,
);
}
}
fn mix_depth(color: Rgb, depth: u32) -> Rgb {
let a = match depth {
0 | 1 => 0,
2 => 28,
3 => 48,
_ => 64,
};
if a == 0 {
color
} else {
Rgb::new(0x16, 0x1b, 0x24).mix(color, 255u8.saturating_sub(a))
}
}
fn to_u32_rect(r: RectF) -> Option<(u32, u32, u32, u32)> {
if r.w < 1.0 || r.h < 1.0 || !r.w.is_finite() || !r.h.is_finite() {
return None;
}
let x = r.x.max(0.0) as u32;
let y = r.y.max(0.0) as u32;
let w = r.w as u32;
let h = r.h as u32;
if w == 0 || h == 0 {
None
} else {
Some((x, y, w, h))
}
}
fn hit_placed(placed: &[Placed], p: Pointer) -> Option<usize> {
placed
.iter()
.enumerate()
.rev()
.find(|(_, n)| {
p.x >= n.x
&& p.y >= n.y
&& p.x < n.x.saturating_add(n.w)
&& p.y < n.y.saturating_add(n.h)
})
.map(|(i, _)| i)
}
fn stroke_rect(pm: &mut Pixmap, x: u32, y: u32, w: u32, h: u32, color: Rgb) {
pm.hline(x, y, w, color);
pm.hline(x, y.saturating_add(h.saturating_sub(1)), w, color);
pm.vline(x, y, h, color);
pm.vline(x.saturating_add(w.saturating_sub(1)), y, h, color);
}
fn paint_label(pm: &mut Pixmap, node: &Placed, scale: TypeScale, color: Rgb, placeholder: &str) {
if !node.paint_name {
return;
}
if node.w < scale.advance().saturating_add(4) || node.h < 8 {
return;
}
let label = if node.value <= 0.0 && node.leaf_index.is_some() {
placeholder
} else {
node.name.as_str()
};
let max_w = node.w.saturating_sub(4);
pm.text_scaled(
node.x.saturating_add(2),
node.y.saturating_add(2),
label,
color,
max_w,
scale,
);
if node.leaf_index.is_some() && node.h > scale.row_height().saturating_add(4) {
let mut val = String::new();
fmt_num(node.value, &mut val);
pm.text_scaled(
node.x.saturating_add(2),
node.y.saturating_add(2).saturating_add(scale.pixel() * 8),
&val,
color,
max_w,
scale,
);
}
}
fn tree_tooltip(
node: &Placed,
placeholder: &str,
theme: crate::theme::Theme,
scale: TypeScale,
) -> Result<Option<Vec<u8>>, Error> {
let mut label = String::new();
if node.name.is_empty() {
label.push_str(placeholder);
} else {
label.push_str(&node.name);
}
label.push_str(": ");
if node.value <= 0.0 && node.leaf_index.is_some() {
label.push_str(placeholder);
} else {
fmt_num(node.value, &mut label);
}
let tw = crate::font::measure(&label, scale)
.saturating_add(16)
.max(48);
let th = scale.row_height().saturating_add(6).max(22);
let mut pm = Pixmap::new(tw.max(40), th, theme.tooltip)?;
pm.fill_rect(0, 0, pm.width(), 1, theme.accent);
pm.text_scaled(
6,
scale.pixel() * 2,
&label,
theme.text,
pm.width().saturating_sub(8),
scale,
);
Ok(Some(pm.to_png()?))
}
fn tree_host(surface: &Surface, request: &FrameRequest, root: &TreeNode) -> HostProjection {
if surface.mode().is_sealed() {
return HostProjection::sealed();
}
let mut text_nodes = Vec::new();
if let Some(caption) = &request.caption {
text_nodes.push(HostText {
kind: "caption",
text: caption.clone(),
});
}
let mut tsv = String::from("name\tvalue\n");
write_leaf_tsv(root, &mut tsv);
HostProjection {
text_nodes,
clipboard: Some(ClipboardPayload::Tsv(tsv)),
}
}
fn write_leaf_tsv(node: &TreeNode, tsv: &mut String) {
if node.children.is_empty() {
tsv.push_str(&node.name);
tsv.push('\t');
fmt_num(node.mass(), tsv);
tsv.push('\n');
return;
}
for c in &node.children {
write_leaf_tsv(c, tsv);
}
}
fn tree_to_grid(root: &TreeNode) -> Result<Grid, Error> {
let columns = vec![Column::new(0, "name"), Column::new(1, "value")];
let mut rows = Vec::new();
collect_leaves(root, &mut rows);
if rows.is_empty() {
rows.push(Row::new(0, vec![CellValue::Redacted, CellValue::Redacted]));
}
Grid::try_new(columns, rows)
}
fn collect_leaves(node: &TreeNode, rows: &mut Vec<Row>) {
if node.children.is_empty() {
let id = rows.len() as u32;
let mut vs = String::new();
fmt_num(node.mass(), &mut vs);
rows.push(Row::new(
id,
vec![CellValue::text(node.name.clone()), CellValue::text(vs)],
));
return;
}
for c in &node.children {
collect_leaves(c, rows);
}
}
fn squarify(values: &[f64], rect: RectF) -> Vec<RectF> {
let n = values.len();
if n == 0 {
return Vec::new();
}
let total: f64 = values.iter().copied().sum();
if total <= 0.0 || rect.w <= 0.0 || rect.h <= 0.0 {
return vec![
RectF {
w: 0.0,
h: 0.0,
..rect
};
n
];
}
let scale = (rect.w * rect.h) / total;
let areas: Vec<f64> = values.iter().map(|v| v * scale).collect();
let mut out = vec![
RectF {
x: 0.0,
y: 0.0,
w: 0.0,
h: 0.0
};
n
];
let mut i = 0usize;
let mut x = rect.x;
let mut y = rect.y;
let mut w = rect.w;
let mut h = rect.h;
while i < n && w > 0.0 && h > 0.0 {
let side = w.min(h);
let mut row_end = i;
let mut best_worst = f64::INFINITY;
for j in i..n {
let worst_j = worst(&areas[i..=j], side);
if j > i && worst_j > best_worst {
break;
}
best_worst = worst_j;
row_end = j + 1;
}
let row = &areas[i..row_end];
let row_area: f64 = row.iter().sum();
if w >= h {
let rw = (row_area / h).max(0.0);
let mut cy = y;
for (k, a) in row.iter().enumerate() {
let rh = if rw > 0.0 { a / rw } else { 0.0 };
out[i + k] = RectF {
x,
y: cy,
w: rw,
h: rh,
};
cy += rh;
}
x += rw;
w = (w - rw).max(0.0);
} else {
let rh = (row_area / w).max(0.0);
let mut cx = x;
for (k, a) in row.iter().enumerate() {
let rw = if rh > 0.0 { a / rh } else { 0.0 };
out[i + k] = RectF {
x: cx,
y,
w: rw,
h: rh,
};
cx += rw;
}
y += rh;
h = (h - rh).max(0.0);
}
i = row_end;
}
out
}
fn worst(row: &[f64], side: f64) -> f64 {
if row.is_empty() || side <= 0.0 {
return f64::INFINITY;
}
let s: f64 = row.iter().sum();
if s <= 0.0 {
return f64::INFINITY;
}
let max = row.iter().copied().fold(0.0_f64, f64::max);
let min = row.iter().copied().fold(f64::INFINITY, f64::min);
let side2 = side * side;
(side2 * max / (s * s)).max((s * s) / (side2 * min.max(1e-12)))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn squarify_two_equal_splits_area() {
let r = RectF {
x: 0.0,
y: 0.0,
w: 100.0,
h: 100.0,
};
let out = squarify(&[1.0, 1.0], r);
assert_eq!(out.len(), 2);
let a0 = out[0].w * out[0].h;
let a1 = out[1].w * out[1].h;
assert!((a0 - 5000.0).abs() < 1.0, "{a0}");
assert!((a1 - 5000.0).abs() < 1.0, "{a1}");
}
#[test]
fn squarify_preserves_order_and_coverage() {
let r = RectF {
x: 10.0,
y: 20.0,
w: 80.0,
h: 40.0,
};
let vals = [4.0, 1.0, 2.0, 1.0];
let out = squarify(&vals, r);
let total: f64 = out.iter().map(|c| c.w * c.h).sum();
assert!((total - 3200.0).abs() < 2.0, "{total}");
assert!(out[0].w * out[0].h > out[1].w * out[1].h);
}
#[test]
fn mass_sums_children() {
let t = TreeNode::branch(
0,
"root",
vec![TreeNode::leaf(1, "a", 10.0), TreeNode::leaf(2, "b", 5.0)],
);
assert!((t.mass() - 15.0).abs() < 1e-9);
}
}