tidy_tree/layout/
tidy_layout.rs

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    /// this is only for layered layout
15    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        // make modifier_to_subtree + relative_x = 0. so that
166        // there will always be collision in `separation()`'s first loop
167        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        // right contour of the left
192        let mut left = Contour::new(false, &node.children[child_index - 1]);
193        // left contour of the right
194        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                // left and right are too close. move right part with distance of dist
214                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        // debug_assert!(distance <= 1e6);
287        child_tidy.modifier_to_subtree += distance;
288
289        // distribute extra space to nodes between from_index to current_index
290        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        // not implemented for layered
433        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            // TODO: can be lazy
445            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        // TODO: this can be optimized with onscreen detection,
461        // then all nodes' absolute x position can be evaluate lazily
462        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}