1use std::{collections::HashSet, hash::BuildHasher, ptr::NonNull, thread::panicking};
2
3use num::Float;
4use tinyset::SetUsize;
5
6use crate::{geometry::Coord, node::TidyData, utils::nocheck_mut, Layout, Node};
7
8use super::linked_y_list::LinkedYList;
9
10pub struct TidyLayout {
11 pub parent_child_margin: Coord,
12 pub peer_margin: Coord,
13 is_layered: bool,
14 depth_to_y: Vec<Coord>,
16}
17
18const TEST: usize = 123123231;
19
20impl TidyLayout {
21 pub fn new(parent_child_margin: Coord, peer_margin: Coord) -> Self {
22 TidyLayout {
23 parent_child_margin,
24 peer_margin,
25 is_layered: false,
26 depth_to_y: vec![],
27 }
28 }
29
30 pub fn new_layered(parent_child_margin: Coord, peer_margin: Coord) -> Self {
31 TidyLayout {
32 parent_child_margin,
33 peer_margin,
34 is_layered: true,
35 depth_to_y: vec![],
36 }
37 }
38}
39
40struct Contour {
41 is_left: bool,
42 pub current: Option<NonNull<Node>>,
43 modifier_sum: Coord,
44}
45
46impl Contour {
47 pub fn new(is_left: bool, current: &Node) -> Self {
48 Contour {
49 is_left,
50 current: Some(current.into()),
51 modifier_sum: current.tidy().modifier_to_subtree,
52 }
53 }
54
55 fn node(&self) -> &Node {
56 match self.current {
57 Some(node) => {
58 let node = unsafe { node.as_ref() };
59 node
60 }
61 None => panic!(),
62 }
63 }
64
65 pub fn is_none(&self) -> bool {
66 self.current.is_none()
67 }
68
69 pub fn left(&self) -> Coord {
70 let node = self.node();
71 self.modifier_sum + node.relative_x - node.width / 2.
72 }
73
74 pub fn right(&self) -> Coord {
75 let node = self.node();
76 self.modifier_sum + node.relative_x + node.width / 2.
77 }
78
79 pub fn bottom(&self) -> Coord {
80 match self.current {
81 Some(node) => {
82 let node = unsafe { node.as_ref() };
83 node.y + node.height
84 }
85 None => 0.,
86 }
87 }
88
89 pub fn next(&mut self) {
90 if let Some(mut current) = self.current {
91 let node = unsafe { current.as_mut() };
92 if self.is_left {
93 if !node.children.is_empty() {
94 self.current = Some((&**node.children.first().unwrap()).into());
95 let node = self.node();
96 self.modifier_sum += node.tidy.as_ref().unwrap().modifier_to_subtree;
97 } else {
98 self.modifier_sum += node.tidy().modifier_thread_left;
99 self.current = node.tidy().thread_left;
100 }
101 } else if !node.children.is_empty() {
102 self.current = Some((&**node.children.last().unwrap()).into());
103 let node = self.node();
104 self.modifier_sum += node.tidy.as_ref().unwrap().modifier_to_subtree;
105 } else {
106 self.modifier_sum += node.tidy().modifier_thread_right;
107 self.current = node.tidy().thread_right;
108 }
109 if self.current.is_some() {
110 let node = self.node();
111 }
112 }
113 }
114}
115
116impl Node {
117 fn set_extreme(&mut self) {
118 let self_ptr: NonNull<Node> = self.into();
119 let tidy = self.tidy.as_mut().unwrap();
120 if self.children.is_empty() {
121 tidy.extreme_left = Some(self_ptr);
122 tidy.extreme_right = Some(self_ptr);
123 tidy.modifier_extreme_left = 0.;
124 tidy.modifier_extreme_right = 0.;
125 } else {
126 let first = self.children.first().unwrap().tidy.as_ref().unwrap();
127 tidy.extreme_left = first.extreme_left;
128 tidy.modifier_extreme_left = first.modifier_to_subtree + first.modifier_extreme_left;
129 let last = self.children.last().unwrap().tidy.as_ref().unwrap();
130 tidy.extreme_right = last.extreme_right;
131 tidy.modifier_extreme_right = last.modifier_to_subtree + last.modifier_extreme_right;
132 }
133 }
134
135 fn extreme_left(&mut self) -> &mut Node {
136 unsafe {
137 self.tidy
138 .as_mut()
139 .unwrap()
140 .extreme_left
141 .as_mut()
142 .unwrap()
143 .as_mut()
144 }
145 }
146
147 fn extreme_right(&mut self) -> &mut Node {
148 unsafe {
149 self.tidy
150 .as_mut()
151 .unwrap()
152 .extreme_right
153 .as_mut()
154 .unwrap()
155 .as_mut()
156 }
157 }
158
159 fn position_root(&mut self) {
160 let first = self.children.first().unwrap();
161 let first_child_pos = first.relative_x + first.tidy().modifier_to_subtree;
162 let last = self.children.last().unwrap();
163 let last_child_pos = last.relative_x + last.tidy().modifier_to_subtree;
164 self.relative_x = (first_child_pos + last_child_pos) / 2.;
165 self.tidy_mut().modifier_to_subtree = -self.relative_x;
168 }
169
170 fn add_child_spacing(&mut self) {
171 let mut speed = 0.;
172 let mut delta = 0.;
173 for child in &mut self.children.iter_mut() {
174 let child = child.tidy_mut();
175 speed += child.shift_acceleration;
176 delta += speed + child.shift_change;
177 child.modifier_to_subtree += delta;
178 child.shift_acceleration = 0.;
179 child.shift_change = 0.;
180 }
181 }
182}
183
184impl TidyLayout {
185 fn separate(
186 &mut self,
187 node: &mut Node,
188 child_index: usize,
189 mut y_list: LinkedYList,
190 ) -> LinkedYList {
191 let mut left = Contour::new(false, &node.children[child_index - 1]);
193 let mut right = Contour::new(true, &node.children[child_index]);
195 while !left.is_none() && !right.is_none() {
196 if left.bottom() > y_list.bottom() {
197 let b = y_list.bottom();
198 let top = y_list.pop();
199 if top.is_none() {
200 println!(
201 "Err\n\n{}\n\nleft.bottom={}\nyList.bottom={}",
202 node.str(),
203 left.bottom(),
204 b
205 );
206 }
207
208 y_list = top.unwrap();
209 }
210
211 let dist = left.right() - right.left() + self.peer_margin;
212 if dist > 0. {
213 right.modifier_sum += dist;
215 self.move_subtree(node, child_index, y_list.index, dist);
216 }
217
218 let left_bottom = left.bottom();
219 let right_bottom = right.bottom();
220 if left_bottom <= right_bottom {
221 left.next();
222 }
223 if left_bottom >= right_bottom {
224 right.next();
225 }
226 }
227
228 if left.is_none() && !right.is_none() {
229 self.set_left_thread(node, child_index, right.node(), right.modifier_sum);
230 } else if !left.is_none() && right.is_none() {
231 self.set_right_thread(node, child_index, left.node(), left.modifier_sum);
232 }
233
234 y_list
235 }
236
237 fn set_left_thread(
238 &mut self,
239 node: &mut Node,
240 current_index: usize,
241 target: &Node,
242 modifier: Coord,
243 ) {
244 let first = nocheck_mut!(node.children[0]);
245 let current = &mut node.children[current_index];
246 let diff = modifier
247 - first.tidy_mut().modifier_extreme_left
248 - first.tidy_mut().modifier_to_subtree;
249 first.extreme_left().tidy_mut().thread_left = Some(target.into());
250 first.extreme_left().tidy_mut().modifier_thread_left = diff;
251 first.tidy_mut().extreme_left = current.tidy_mut().extreme_left;
252 first.tidy_mut().modifier_extreme_left = current.tidy_mut().modifier_extreme_left
253 + current.tidy_mut().modifier_to_subtree
254 - first.tidy_mut().modifier_to_subtree;
255 }
256
257 fn set_right_thread(
258 &mut self,
259 node: &mut Node,
260 current_index: usize,
261 target: &Node,
262 modifier: Coord,
263 ) {
264 let current = nocheck_mut!(node.children[current_index]);
265 let diff = modifier
266 - current.tidy_mut().modifier_extreme_right
267 - current.tidy_mut().modifier_to_subtree;
268 current.extreme_right().tidy_mut().thread_right = Some(target.into());
269 current.extreme_right().tidy_mut().modifier_thread_right = diff;
270 let prev = node.children[current_index - 1].tidy_mut();
271 current.tidy_mut().extreme_right = prev.extreme_right;
272 current.tidy_mut().modifier_extreme_right = prev.modifier_extreme_right
273 + prev.modifier_to_subtree
274 - current.tidy_mut().modifier_to_subtree;
275 }
276
277 fn move_subtree(
278 &mut self,
279 node: &mut Node,
280 current_index: usize,
281 from_index: usize,
282 distance: Coord,
283 ) {
284 let child = &mut node.children[current_index];
285 let child_tidy = child.tidy_mut();
286 child_tidy.modifier_to_subtree += distance;
288
289 if from_index != current_index - 1 {
291 let index_diff = (current_index - from_index) as Coord;
292 node.children[from_index + 1].tidy_mut().shift_acceleration += distance / index_diff;
293 node.children[current_index].tidy_mut().shift_acceleration -= distance / index_diff;
294 node.children[current_index].tidy_mut().shift_change -=
295 distance - distance / index_diff;
296 }
297 }
298
299 fn set_y_recursive(&mut self, root: &mut Node) {
300 if !self.is_layered {
301 root.pre_order_traversal_mut(|node| {
302 self.set_y(node);
303 });
304 } else {
305 let depth_to_y = &mut self.depth_to_y;
306 depth_to_y.clear();
307 let margin = self.parent_child_margin;
308 root.bfs_traversal_with_depth_mut(|node, depth| {
309 while depth >= depth_to_y.len() {
310 depth_to_y.push(0.);
311 }
312
313 if node.parent.is_none() || depth == 0 {
314 node.y = 0.;
315 return;
316 }
317
318 let parent = node.parent().unwrap();
319 depth_to_y[depth] = Float::max(
320 depth_to_y[depth],
321 depth_to_y[depth - 1] + parent.height + self.parent_child_margin,
322 );
323 });
324 root.pre_order_traversal_with_depth_mut(|node, depth| {
325 node.y = depth_to_y[depth];
326 })
327 }
328 }
329
330 fn set_y(&mut self, node: &mut Node) {
331 node.y = if let Some(parent) = node.parent {
332 let parent_bottom = unsafe { parent.as_ref().bottom() };
333 parent_bottom + self.parent_child_margin
334 } else {
335 0.
336 };
337 }
338
339 fn first_walk(&mut self, node: &mut Node) {
340 if node.children.is_empty() {
341 node.set_extreme();
342 return;
343 }
344
345 self.first_walk(node.children.first_mut().unwrap());
346 let mut y_list = LinkedYList::new(0, node.children[0].extreme_right().bottom());
347 for i in 1..node.children.len() {
348 let current_child = node.children.get_mut(i).unwrap();
349 self.first_walk(current_child);
350 let max_y = current_child.extreme_left().bottom();
351 y_list = self.separate(node, i, y_list);
352 y_list = y_list.update(i, max_y);
353 }
354
355 node.position_root();
356 node.set_extreme();
357 }
358
359 fn first_walk_with_filter(&mut self, node: &mut Node, set: &SetUsize) {
360 if !set.contains(node as *const _ as usize) {
361 invalidate_extreme_thread(node);
362 return;
363 }
364
365 if node.children.is_empty() {
366 node.set_extreme();
367 return;
368 }
369
370 self.first_walk_with_filter(node.children.first_mut().unwrap(), set);
371 let mut y_list = LinkedYList::new(0, node.children[0].extreme_right().bottom());
372 for i in 1..node.children.len() {
373 let current_child = node.children.get_mut(i).unwrap();
374 current_child.tidy_mut().modifier_to_subtree = -current_child.relative_x;
375 self.first_walk_with_filter(current_child, set);
376 let max_y = current_child.extreme_left().bottom();
377 y_list = self.separate(node, i, y_list);
378 y_list = y_list.update(i, max_y);
379 }
380
381 node.position_root();
382 node.set_extreme();
383 }
384
385 fn second_walk(&mut self, node: &mut Node, mut mod_sum: Coord) {
386 mod_sum += node.tidy_mut().modifier_to_subtree;
387 node.x = node.relative_x + mod_sum;
388 node.add_child_spacing();
389
390 for child in node.children.iter_mut() {
391 self.second_walk(child, mod_sum);
392 }
393 }
394
395 fn second_walk_with_filter(&mut self, node: &mut Node, mut mod_sum: Coord, set: &SetUsize) {
396 mod_sum += node.tidy_mut().modifier_to_subtree;
397 let new_x = node.relative_x + mod_sum;
398 if (new_x - node.x).abs() < 1e-8 && !set.contains(node as *const _ as usize) {
399 return;
400 }
401
402 node.x = new_x;
403 node.add_child_spacing();
404
405 for child in node.children.iter_mut() {
406 self.second_walk_with_filter(child, mod_sum, set);
407 }
408 }
409}
410
411impl Layout for TidyLayout {
412 fn layout(&mut self, root: &mut Node) {
413 root.pre_order_traversal_mut(init_node);
414 self.set_y_recursive(root);
415 self.first_walk(root);
416 self.second_walk(root, 0.);
417 }
418
419 fn parent_child_margin(&self) -> Coord {
420 self.parent_child_margin
421 }
422
423 fn peer_margin(&self) -> Coord {
424 self.peer_margin
425 }
426
427 fn partial_layout(
428 &mut self,
429 root: &mut crate::Node,
430 changed: &[std::ptr::NonNull<crate::Node>],
431 ) {
432 if self.is_layered {
434 self.layout(root);
435 return;
436 }
437
438 for node in changed.iter() {
439 let node = unsafe { &mut *node.as_ptr() };
440 if node.tidy.is_none() {
441 init_node(node);
442 }
443
444 self.set_y_recursive(node);
446 }
447
448 let mut set: SetUsize = SetUsize::new();
449 for node in changed.iter() {
450 set.insert(node.as_ptr() as usize);
451 let mut node = unsafe { &mut *node.as_ptr() };
452 while node.parent.is_some() {
453 invalidate_extreme_thread(node);
454 set.insert(node.parent.unwrap().as_ptr() as usize);
455 node = node.parent_mut().unwrap();
456 }
457 }
458
459 self.first_walk_with_filter(root, &set);
460 self.second_walk_with_filter(root, 0., &set);
463 }
464}
465
466fn init_node(node: &mut Node) {
467 if node.tidy.is_some() {
468 let tidy = node.tidy_mut();
469 tidy.extreme_left = None;
470 tidy.extreme_right = None;
471 tidy.shift_acceleration = 0.;
472 tidy.shift_change = 0.;
473 tidy.modifier_to_subtree = 0.;
474 tidy.modifier_extreme_left = 0.;
475 tidy.modifier_extreme_right = 0.;
476 tidy.thread_left = None;
477 tidy.thread_right = None;
478 tidy.modifier_thread_left = 0.;
479 tidy.modifier_thread_right = 0.;
480 } else {
481 node.tidy = Some(Box::new(TidyData {
482 extreme_left: None,
483 extreme_right: None,
484 shift_acceleration: 0.,
485 shift_change: 0.,
486 modifier_to_subtree: 0.,
487 modifier_extreme_left: 0.,
488 modifier_extreme_right: 0.,
489 thread_left: None,
490 thread_right: None,
491 modifier_thread_left: 0.,
492 modifier_thread_right: 0.,
493 }));
494 }
495
496 node.x = 0.;
497 node.y = 0.;
498 node.relative_x = 0.;
499 node.relative_y = 0.;
500}
501
502fn invalidate_extreme_thread(node: &mut Node) {
503 node.set_extreme();
504 let e_left = node.extreme_left().tidy_mut();
505 e_left.thread_left = None;
506 e_left.thread_right = None;
507 e_left.modifier_thread_left = 0.;
508 e_left.modifier_thread_right = 0.;
509 let e_right = node.extreme_right().tidy_mut();
510 e_right.thread_left = None;
511 e_right.thread_right = None;
512 e_right.modifier_thread_left = 0.;
513 e_right.modifier_thread_right = 0.;
514}
515
516#[cfg(test)]
517mod test {
518 use super::*;
519 use crate::node::Node;
520 #[test]
521 fn test_tidy_layout() {
522 let mut tidy = TidyLayout::new(1., 1.);
523 let mut root = Node::new(0, 1., 1.);
524 let first_child = Node::new_with_child(
525 1,
526 1.,
527 1.,
528 Node::new_with_child(10, 1., 1., Node::new(100, 1., 1.)),
529 );
530 root.append_child(first_child);
531
532 let second = Node::new_with_child(
533 2,
534 1.,
535 1.,
536 Node::new_with_child(11, 1., 1., Node::new(101, 1., 1.)),
537 );
538 root.append_child(second);
539
540 root.append_child(Node::new(3, 1., 2.));
541 tidy.layout(&mut root);
542 println!("{}", root.str());
543 }
544}