1use std::cmp::Ordering;
2
3use anyhow::{Result, ensure};
4
5use crate::model::{Atlas, Callsite, NodeId, Point, Rect};
6
7#[derive(Debug, Clone)]
8pub struct LayoutOptions {
9 pub width: u32,
10 pub height: u32,
11 pub margin_fraction: f64,
12 pub directory_padding: f64,
13 pub texture_seed: u64,
14 pub bundle_strength: f64,
15}
16
17impl Default for LayoutOptions {
18 fn default() -> Self {
19 Self {
20 width: 1920,
21 height: 1080,
22 margin_fraction: 0.045,
23 directory_padding: 1.5,
24 texture_seed: 932,
25 bundle_strength: 0.96,
26 }
27 }
28}
29
30pub fn layout_repository(atlas: &mut Atlas, options: &LayoutOptions) -> Result<()> {
31 ensure!(
32 options.width > 0 && options.height > 0,
33 "output dimensions must be positive"
34 );
35 ensure!(!atlas.nodes.is_empty(), "repository has no hierarchy nodes");
36 let margin = (options.width.min(options.height) as f64
37 * options.margin_fraction.clamp(0.0, 0.20))
38 .round();
39 atlas.nodes[0].rect = Rect {
40 x0: margin,
41 y0: margin,
42 x1: options.width as f64 - margin,
43 y1: options.height as f64 - margin,
44 };
45 layout_children(atlas, 0, options);
46 Ok(())
47}
48
49fn layout_children(atlas: &mut Atlas, parent: NodeId, options: &LayoutOptions) {
50 let mut children = atlas.nodes[parent].children.clone();
51 if children.is_empty() {
52 return;
53 }
54 children.sort_by(|left, right| {
55 atlas.nodes[*right]
56 .weight
57 .partial_cmp(&atlas.nodes[*left].weight)
58 .unwrap_or(Ordering::Equal)
59 .then_with(|| atlas.nodes[*left].path.cmp(&atlas.nodes[*right].path))
60 });
61
62 let depth = atlas.nodes[parent].depth;
63 let padding = if parent == 0 {
64 0.0
65 } else {
66 options.directory_padding / (depth as f64).sqrt().max(1.0)
67 };
68 let area = atlas.nodes[parent].rect.inset(padding);
69 let rectangles = squarify(
70 &children
71 .iter()
72 .map(|id| atlas.nodes[*id].weight.max(0.0001))
73 .collect::<Vec<_>>(),
74 area,
75 );
76
77 for (child, rect) in children.into_iter().zip(rectangles) {
78 atlas.nodes[child].rect = rect;
79 layout_children(atlas, child, options);
80 }
81}
82
83pub fn squarify(weights: &[f64], rect: Rect) -> Vec<Rect> {
84 if weights.is_empty() {
85 return Vec::new();
86 }
87 let total = weights.iter().sum::<f64>().max(f64::EPSILON);
88 let scale = rect.area() / total;
89 let areas: Vec<f64> = weights.iter().map(|weight| weight * scale).collect();
90 let mut output = vec![Rect::default(); weights.len()];
91 let mut remaining = rect;
92 let mut row: Vec<usize> = Vec::new();
93
94 for index in 0..areas.len() {
95 let short_side = remaining.width().min(remaining.height()).max(f64::EPSILON);
96 if row.is_empty()
97 || worst_ratio(&row_with(&row, index), &areas, short_side)
98 <= worst_ratio(&row, &areas, short_side)
99 {
100 row.push(index);
101 } else {
102 layout_row(&row, &areas, &mut remaining, &mut output);
103 row.clear();
104 row.push(index);
105 }
106 }
107 if !row.is_empty() {
108 layout_row(&row, &areas, &mut remaining, &mut output);
109 }
110 output
111}
112
113fn row_with(row: &[usize], index: usize) -> Vec<usize> {
114 let mut candidate = row.to_vec();
115 candidate.push(index);
116 candidate
117}
118
119fn worst_ratio(row: &[usize], areas: &[f64], side: f64) -> f64 {
120 if row.is_empty() {
121 return f64::INFINITY;
122 }
123 let sum = row.iter().map(|index| areas[*index]).sum::<f64>();
124 let min = row
125 .iter()
126 .map(|index| areas[*index])
127 .fold(f64::INFINITY, f64::min)
128 .max(f64::EPSILON);
129 let max = row
130 .iter()
131 .map(|index| areas[*index])
132 .fold(0.0, f64::max)
133 .max(f64::EPSILON);
134 ((side * side * max) / (sum * sum)).max((sum * sum) / (side * side * min))
135}
136
137fn layout_row(row: &[usize], areas: &[f64], remaining: &mut Rect, output: &mut [Rect]) {
138 let row_area = row.iter().map(|index| areas[*index]).sum::<f64>();
139 if remaining.width() <= remaining.height() {
140 let height = (row_area / remaining.width().max(f64::EPSILON)).min(remaining.height());
141 let mut x = remaining.x0;
142 for (position, index) in row.iter().enumerate() {
143 let width = if position + 1 == row.len() {
144 remaining.x1 - x
145 } else {
146 areas[*index] / height.max(f64::EPSILON)
147 };
148 output[*index] = Rect {
149 x0: x,
150 y0: remaining.y0,
151 x1: x + width,
152 y1: remaining.y0 + height,
153 };
154 x += width;
155 }
156 remaining.y0 += height;
157 } else {
158 let width = (row_area / remaining.height().max(f64::EPSILON)).min(remaining.width());
159 let mut y = remaining.y0;
160 for (position, index) in row.iter().enumerate() {
161 let height = if position + 1 == row.len() {
162 remaining.y1 - y
163 } else {
164 areas[*index] / width.max(f64::EPSILON)
165 };
166 output[*index] = Rect {
167 x0: remaining.x0,
168 y0: y,
169 x1: remaining.x0 + width,
170 y1: y + height,
171 };
172 y += height;
173 }
174 remaining.x0 += width;
175 }
176}
177
178pub fn call_curve(atlas: &Atlas, call: &Callsite, options: &LayoutOptions) -> Vec<Point> {
179 let mut controls = call_control_points(atlas, call);
180
181 let first = controls[0];
182 let last = *controls.last().expect("target control point");
183 let denominator = controls.len().saturating_sub(1).max(1) as f64;
184 let bundle_strength = options.bundle_strength.clamp(0.0, 1.0);
185 for (index, point) in controls.iter_mut().enumerate() {
186 let t = index as f64 / denominator;
187 let direct = Point {
188 x: lerp(first.x, last.x, t),
189 y: lerp(first.y, last.y, t),
190 };
191 point.x = lerp(direct.x, point.x, bundle_strength);
192 point.y = lerp(direct.y, point.y, bundle_strength);
193 }
194 clamped_bspline(&controls)
195}
196
197pub fn call_control_points(atlas: &Atlas, call: &Callsite) -> Vec<Point> {
202 let source_file = &atlas.nodes[call.source];
203 let target_file = &atlas.nodes[call.target];
204 let source = line_anchor(source_file.rect, source_file.loc, call.source_line);
205 let target = call
206 .target_line
207 .map(|line| line_anchor(target_file.rect, target_file.loc, line))
208 .unwrap_or_else(|| target_file.rect.center());
209 let hierarchy = atlas.hierarchy_path(call.source, call.target);
210 let mut controls = Vec::with_capacity(hierarchy.len() + 2);
211 controls.push(source);
212 controls.extend(hierarchy.iter().map(|id| atlas.nodes[*id].rect.center()));
213 controls.push(target);
214 controls
215}
216
217pub fn line_anchor(rect: Rect, line_count: u64, line: u32) -> Point {
223 let min_x = rect.x0.ceil() as i64;
224 let min_y = rect.y0.ceil() as i64;
225 let max_x = rect.x1.floor() as i64;
226 let max_y = rect.y1.floor() as i64;
227 let width = max_x.saturating_sub(min_x) as u64;
228 let height = max_y.saturating_sub(min_y) as u64;
229 if width == 0 || height == 0 {
230 return rect.center();
231 }
232
233 let pixel_count = width.saturating_mul(height).max(1);
234 let line_count = line_count.max(1);
235 let line_index = u64::from(line.saturating_sub(1)).min(line_count - 1);
236 let region_start = scale_ratio_floor(line_index, pixel_count, line_count);
237 let region_end = scale_ratio_ceil(line_index + 1, pixel_count, line_count)
238 .max(region_start + 1)
239 .min(pixel_count);
240 let pixel_index = region_start + (region_end - region_start - 1) / 2;
241 let row = pixel_index / width;
242 let scan_column = pixel_index % width;
243 let column = if row.is_multiple_of(2) {
244 scan_column
245 } else {
246 width - 1 - scan_column
247 };
248 Point {
249 x: min_x as f64 + column as f64 + 0.5,
250 y: min_y as f64 + row as f64 + 0.5,
251 }
252}
253
254fn scale_ratio_floor(value: u64, scale: u64, denominator: u64) -> u64 {
255 ((u128::from(value) * u128::from(scale)) / u128::from(denominator)) as u64
256}
257
258fn scale_ratio_ceil(value: u64, scale: u64, denominator: u64) -> u64 {
259 let numerator = u128::from(value) * u128::from(scale);
260 numerator.div_ceil(u128::from(denominator)) as u64
261}
262
263pub fn sample_rect(rect: Rect, samples_per_side: usize) -> Vec<Point> {
264 let samples = samples_per_side.max(1);
265 let mut points = Vec::with_capacity(samples * 4);
266 for index in 0..samples {
267 let t = index as f64 / samples as f64;
268 points.push(Point {
269 x: lerp(rect.x0, rect.x1, t),
270 y: rect.y0,
271 });
272 }
273 for index in 0..samples {
274 let t = index as f64 / samples as f64;
275 points.push(Point {
276 x: rect.x1,
277 y: lerp(rect.y0, rect.y1, t),
278 });
279 }
280 for index in 0..samples {
281 let t = index as f64 / samples as f64;
282 points.push(Point {
283 x: lerp(rect.x1, rect.x0, t),
284 y: rect.y1,
285 });
286 }
287 for index in 0..samples {
288 let t = index as f64 / samples as f64;
289 points.push(Point {
290 x: rect.x0,
291 y: lerp(rect.y1, rect.y0, t),
292 });
293 }
294 points
295}
296
297fn clamped_bspline(controls: &[Point]) -> Vec<Point> {
298 if controls.len() < 2 {
299 return controls.to_vec();
300 }
301 let degree = controls.len().saturating_sub(1).min(3);
302 let knots = clamped_uniform_knots(controls.len(), degree);
303 let knot_spans = controls.len().saturating_sub(degree).max(1);
304 let line_segments = (knot_spans * 16).max(64);
305 let mut output = Vec::with_capacity(line_segments + 1);
306 for sample in 0..=line_segments {
307 let t = sample as f64 / line_segments as f64;
308 output.push(de_boor(controls, degree, &knots, t));
309 }
310 output
311}
312
313fn clamped_uniform_knots(control_count: usize, degree: usize) -> Vec<f64> {
314 let interior_count = control_count.saturating_sub(degree + 1);
315 let mut knots = Vec::with_capacity(control_count + degree + 1);
316 knots.extend(std::iter::repeat_n(0.0, degree + 1));
317 let denominator = (interior_count + 1) as f64;
318 for index in 1..=interior_count {
319 knots.push(index as f64 / denominator);
320 }
321 knots.extend(std::iter::repeat_n(1.0, degree + 1));
322 knots
323}
324
325fn de_boor(controls: &[Point], degree: usize, knots: &[f64], t: f64) -> Point {
326 let last_control = controls.len() - 1;
327 let span = if t >= 1.0 {
328 last_control
329 } else {
330 (degree..=last_control)
331 .find(|index| t >= knots[*index] && t < knots[*index + 1])
332 .unwrap_or(last_control)
333 };
334 let mut points: Vec<Point> = (0..=degree)
335 .map(|index| controls[span - degree + index])
336 .collect();
337
338 for level in 1..=degree {
339 for index in (level..=degree).rev() {
340 let knot_index = span - degree + index;
341 let denominator = knots[knot_index + degree + 1 - level] - knots[knot_index];
342 let alpha = if denominator.abs() <= f64::EPSILON {
343 0.0
344 } else {
345 (t - knots[knot_index]) / denominator
346 };
347 points[index] = Point {
348 x: lerp(points[index - 1].x, points[index].x, alpha),
349 y: lerp(points[index - 1].y, points[index].y, alpha),
350 };
351 }
352 }
353 points[degree]
354}
355
356fn lerp(start: f64, end: f64, amount: f64) -> f64 {
357 start + (end - start) * amount
358}
359
360#[cfg(test)]
361mod tests {
362 use super::*;
363
364 #[test]
365 fn squarify_preserves_total_area() {
366 let root = Rect {
367 x0: 0.0,
368 y0: 0.0,
369 x1: 1600.0,
370 y1: 900.0,
371 };
372 let rectangles = squarify(&[8.0, 5.0, 3.0, 2.0, 1.0], root);
373 let total = rectangles.iter().map(|rect| rect.area()).sum::<f64>();
374 assert!((total - root.area()).abs() < 0.01);
375 assert!(
376 rectangles
377 .iter()
378 .all(|rect| rect.width() > 0.0 && rect.height() > 0.0)
379 );
380 }
381
382 #[test]
383 fn default_bundle_strength_is_tight_but_not_fully_confluent() {
384 assert_eq!(LayoutOptions::default().bundle_strength, 0.96);
385 }
386
387 #[test]
388 fn clamped_spline_interpolates_endpoints_and_reduces_degree() {
389 let linear = clamped_bspline(&[Point { x: 0.0, y: 0.0 }, Point { x: 2.0, y: 2.0 }]);
390 assert_eq!(linear.first(), Some(&Point { x: 0.0, y: 0.0 }));
391 assert_eq!(linear.last(), Some(&Point { x: 2.0, y: 2.0 }));
392 assert_point_near(linear[32], Point { x: 1.0, y: 1.0 });
393
394 let quadratic = clamped_bspline(&[
395 Point { x: 0.0, y: 0.0 },
396 Point { x: 1.0, y: 1.0 },
397 Point { x: 2.0, y: 0.0 },
398 ]);
399 assert_point_near(quadratic[32], Point { x: 1.0, y: 0.5 });
400
401 let cubic = clamped_bspline(&[
402 Point { x: 0.0, y: 0.0 },
403 Point { x: 0.0, y: 1.0 },
404 Point { x: 1.0, y: 1.0 },
405 Point { x: 1.0, y: 0.0 },
406 ]);
407 assert_point_near(cubic[32], Point { x: 0.5, y: 0.75 });
408 }
409
410 #[test]
411 fn line_anchors_follow_a_serpentine_pixel_scan() {
412 let rect = Rect {
413 x0: 0.0,
414 y0: 0.0,
415 x1: 4.0,
416 y1: 2.0,
417 };
418 assert_eq!(line_anchor(rect, 8, 1), Point { x: 0.5, y: 0.5 });
419 assert_eq!(line_anchor(rect, 8, 4), Point { x: 3.5, y: 0.5 });
420 assert_eq!(line_anchor(rect, 8, 5), Point { x: 3.5, y: 1.5 });
421 assert_eq!(line_anchor(rect, 8, 8), Point { x: 0.5, y: 1.5 });
422 assert_eq!(
423 line_anchor(rect, 8, 999),
424 Point { x: 0.5, y: 1.5 },
425 "out-of-range analyzer lines clamp to the final line cell"
426 );
427 }
428
429 #[test]
430 fn every_pixel_maps_to_a_line_range_when_pixels_outnumber_lines() {
431 let rect = Rect {
432 x0: 10.0,
433 y0: 20.0,
434 x1: 18.0,
435 y1: 21.0,
436 };
437 let anchors: Vec<_> = (1..=4).map(|line| line_anchor(rect, 4, line)).collect();
438 assert_eq!(anchors[0], Point { x: 10.5, y: 20.5 });
439 assert_eq!(anchors[1], Point { x: 12.5, y: 20.5 });
440 assert_eq!(anchors[2], Point { x: 14.5, y: 20.5 });
441 assert_eq!(anchors[3], Point { x: 16.5, y: 20.5 });
442 }
443
444 fn assert_point_near(actual: Point, expected: Point) {
445 assert!((actual.x - expected.x).abs() < 1e-9, "x: {actual:?}");
446 assert!((actual.y - expected.y).abs() < 1e-9, "y: {actual:?}");
447 }
448}