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    /// Hidden Nodes are not painted and do not receive events.
42    pub hidden: bool,
43
44    /// Associated data
45    #[cfg_attr(feature = "serde", serde(skip_deserializing, skip_serializing))]
46    pub data: Option<Rc<dyn Any>>,
47}
48
49impl PartialEq for LayoutNode {
50    fn eq(&self, other: &Self) -> bool {
51        self.area == other.area
52            && self.inner_area == other.inner_area
53            && self.margin == other.margin
54            && self.offset_x == other.offset_x
55            && self.offset_y == other.offset_y
56            && self.hidden == other.hidden
57    }
58}
59
60impl LayoutNode {
61    // The area without any margin
62    pub fn visible_area(&self) -> Area {
63        self.area.without_gaps(&self.margin)
64    }
65}
66
67pub trait NodeKey: Clone + PartialEq + Eq + std::hash::Hash + Copy + std::fmt::Debug {}
68
69impl NodeKey for usize {}
70
71pub trait TreeAdapter<Key: NodeKey> {
72    fn root_id(&self) -> Key;
73
74    /// Get the Node size
75    fn get_node(&self, node_id: &Key) -> Option<Node>;
76
77    /// Get the height in the Tree of the given Node
78    fn height(&self, node_id: &Key) -> Option<u16>;
79
80    /// Get the parent of a Node
81    fn parent_of(&self, node_id: &Key) -> Option<Key>;
82
83    /// Get the children of a Node
84    fn children_of(&mut self, node_id: &Key) -> Vec<Key>;
85
86    /// Get the closest common parent Node of two Nodes
87    fn closest_common_parent(
88        &self,
89        node_a: &Key,
90        node_b: &Key,
91        walker: impl FnMut(Key),
92    ) -> Option<Key> {
93        let height_a = self.height(node_a)?;
94        let height_b = self.height(node_b)?;
95
96        let (node_a, node_b) = match height_a.cmp(&height_b) {
97            std::cmp::Ordering::Less => (
98                *node_a,
99                // Does not make sense to call the walker for when the node a is higher than the node b
100                balance_heights(self, *node_b, *node_a, None::<fn(_)>).unwrap_or(*node_b),
101            ),
102            std::cmp::Ordering::Equal => (*node_a, *node_b),
103            std::cmp::Ordering::Greater => (
104                balance_heights(self, *node_a, *node_b, Some(walker)).unwrap_or(*node_a),
105                *node_b,
106            ),
107        };
108
109        let mut currents = (node_a, node_b);
110
111        loop {
112            // Common parent of node_a and node_b
113            if currents.0 == currents.1 {
114                return Some(currents.0);
115            }
116
117            let parent_a = self.parent_of(&currents.0);
118            if let Some(parent_a) = parent_a {
119                currents.0 = parent_a;
120            } else if self.root_id() != currents.0 {
121                // Skip unconected nodes
122                break;
123            }
124
125            let parent_b = self.parent_of(&currents.1);
126            if let Some(parent_b) = parent_b {
127                currents.1 = parent_b;
128            } else if self.root_id() != currents.1 {
129                // Skip unconected nodes
130                break;
131            }
132        }
133
134        None
135    }
136}
137
138/// Walk to the ancestor of `base` with the same height of `target`
139fn balance_heights<Key: NodeKey>(
140    tree_adapter: &(impl TreeAdapter<Key> + ?Sized),
141    base: Key,
142    target: Key,
143    mut walker: Option<impl FnMut(Key)>,
144) -> Option<Key> {
145    let target_height = tree_adapter.height(&target)?;
146    let mut current = base;
147    loop {
148        if let Some(walker) = &mut walker {
149            (walker)(current);
150        }
151        if tree_adapter.height(&current)? == target_height {
152            break;
153        }
154
155        let parent_current = tree_adapter.parent_of(&current);
156        if let Some(parent_current) = parent_current {
157            current = parent_current;
158        }
159    }
160    Some(current)
161}
torin/tree_adapter.rs

torin/
tree_adapter.rs
