torin/
tree_adapter.rs

1use std::{
2    any::Any,
3    rc::Rc,
4};
5
6pub use euclid::Rect;
7
8use crate::{
9    geometry::Area,
10    node::Node,
11    prelude::{
12        AreaModel,
13        AreaOf,
14        Gaps,
15        Inner,
16        Length,
17        Size2D,
18    },
19};
20
21#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
22/// Cached layout results of a Node
23#[derive(Debug, Default, Clone)]
24pub struct LayoutNode {
25    /// Area that ocuppies this node
26    pub area: Area,
27
28    /// Area inside this Node
29    pub inner_area: AreaOf<Inner>,
30
31    /// Accumulated sizes inside this Node
32    pub inner_sizes: Size2D,
33
34    /// Outer margin
35    pub margin: Gaps,
36
37    /// Offsets
38    pub offset_x: Length,
39    pub offset_y: Length,
40
41    /// Associated data
42    #[cfg_attr(feature = "serde", serde(skip_deserializing, skip_serializing))]
43    pub data: Option<Rc<dyn Any>>,
44}
45
46impl PartialEq for LayoutNode {
47    fn eq(&self, other: &Self) -> bool {
48        self.area == other.area
49            && self.inner_area == other.inner_area
50            && self.margin == other.margin
51            && self.offset_x == other.offset_x
52            && self.offset_y == other.offset_y
53    }
54}
55
56impl LayoutNode {
57    // The area without any margin
58    pub fn visible_area(&self) -> Area {
59        self.area.without_gaps(&self.margin)
60    }
61}
62
63pub trait NodeKey: Clone + PartialEq + Eq + std::hash::Hash + Copy + std::fmt::Debug {}
64
65impl NodeKey for usize {}
66
67pub trait TreeAdapter<Key: NodeKey> {
68    fn root_id(&self) -> Key;
69
70    /// Get the Node size
71    fn get_node(&self, node_id: &Key) -> Option<Node>;
72
73    /// Get the height in the Tree of the given Node
74    fn height(&self, node_id: &Key) -> Option<u16>;
75
76    /// Get the parent of a Node
77    fn parent_of(&self, node_id: &Key) -> Option<Key>;
78
79    /// Get the children of a Node
80    fn children_of(&mut self, node_id: &Key) -> Vec<Key>;
81
82    /// Get the closest common parent Node of two Nodes
83    fn closest_common_parent(
84        &self,
85        node_a: &Key,
86        node_b: &Key,
87        walker: impl FnMut(Key),
88    ) -> Option<Key> {
89        let height_a = self.height(node_a)?;
90        let height_b = self.height(node_b)?;
91
92        let (node_a, node_b) = match height_a.cmp(&height_b) {
93            std::cmp::Ordering::Less => (
94                *node_a,
95                // Does not make sense to call the walker for when the node a is higher than the node b
96                balance_heights(self, *node_b, *node_a, None::<fn(_)>).unwrap_or(*node_b),
97            ),
98            std::cmp::Ordering::Equal => (*node_a, *node_b),
99            std::cmp::Ordering::Greater => (
100                balance_heights(self, *node_a, *node_b, Some(walker)).unwrap_or(*node_a),
101                *node_b,
102            ),
103        };
104
105        let mut currents = (node_a, node_b);
106
107        loop {
108            // Common parent of node_a and node_b
109            if currents.0 == currents.1 {
110                return Some(currents.0);
111            }
112
113            let parent_a = self.parent_of(&currents.0);
114            if let Some(parent_a) = parent_a {
115                currents.0 = parent_a;
116            } else if self.root_id() != currents.0 {
117                // Skip unconected nodes
118                break;
119            }
120
121            let parent_b = self.parent_of(&currents.1);
122            if let Some(parent_b) = parent_b {
123                currents.1 = parent_b;
124            } else if self.root_id() != currents.1 {
125                // Skip unconected nodes
126                break;
127            }
128        }
129
130        None
131    }
132}
133
134/// Walk to the ancestor of `base` with the same height of `target`
135fn balance_heights<Key: NodeKey>(
136    tree_adapter: &(impl TreeAdapter<Key> + ?Sized),
137    base: Key,
138    target: Key,
139    mut walker: Option<impl FnMut(Key)>,
140) -> Option<Key> {
141    let target_height = tree_adapter.height(&target)?;
142    let mut current = base;
143    loop {
144        if let Some(walker) = &mut walker {
145            (walker)(current);
146        }
147        if tree_adapter.height(&current)? == target_height {
148            break;
149        }
150
151        let parent_current = tree_adapter.parent_of(&current);
152        if let Some(parent_current) = parent_current {
153            current = parent_current;
154        }
155    }
156    Some(current)
157}
torin/tree_adapter.rs

torin/
tree_adapter.rs
