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

torin/
tree_adapter.rs
