torin/
tree_adapter.rs

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

torin/
tree_adapter.rs
