1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
16pub struct TreeId(pub u32);
17
18#[derive(Debug, Clone, PartialEq)]
20pub struct TreeNode {
21 pub id: TreeId,
23 pub name: String,
25 pub value: f64,
27 pub children: Vec<TreeNode>,
29}
30
31impl TreeNode {
32 #[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 #[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 #[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 #[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#[derive(Debug, Clone, PartialEq)]
104pub struct TreeLayout {
105 root: TreeNode,
106}
107
108impl TreeLayout {
109 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 #[must_use]
124 pub fn root(&self) -> &TreeNode {
125 &self.root
126 }
127
128 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 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
525fn 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}