expanse/
forest.rs

1//! Forest - ECS like datastructure for storing node trees.
2//!
3//! Backing datastructure for `Stretch` structs.
4use crate::geometry::Size;
5use crate::id::NodeId;
6use crate::node::MeasureFunc;
7use crate::number::Number;
8use crate::result::{Cache, Layout};
9use crate::style::Style;
10use crate::sys;
11
12pub(crate) struct NodeData {
13    pub(crate) style: Style,
14    pub(crate) measure: Option<MeasureFunc>,
15    pub(crate) layout: Layout,
16    pub(crate) layout_cache: Option<Cache>,
17    pub(crate) is_dirty: bool,
18}
19
20impl NodeData {
21    fn new_leaf(style: Style, measure: MeasureFunc) -> Self {
22        Self { style, measure: Some(measure), layout_cache: None, layout: Layout::new(), is_dirty: true }
23    }
24
25    fn new(style: Style) -> Self {
26        Self { style, measure: None, layout_cache: None, layout: Layout::new(), is_dirty: true }
27    }
28}
29
30pub(crate) struct Forest {
31    pub(crate) nodes: sys::Vec<NodeData>,
32    pub(crate) children: sys::Vec<sys::ChildrenVec<NodeId>>,
33    pub(crate) parents: sys::Vec<sys::ParentsVec<NodeId>>,
34}
35
36impl Forest {
37    pub fn with_capacity(capacity: usize) -> Self {
38        Self {
39            nodes: sys::new_vec_with_capacity(capacity),
40            children: sys::new_vec_with_capacity(capacity),
41            parents: sys::new_vec_with_capacity(capacity),
42        }
43    }
44
45    pub fn new_leaf(&mut self, style: Style, measure: MeasureFunc) -> NodeId {
46        let id = self.nodes.len();
47        self.nodes.push(NodeData::new_leaf(style, measure));
48        self.children.push(sys::new_vec_with_capacity(0));
49        self.parents.push(sys::new_vec_with_capacity(1));
50        id
51    }
52
53    pub fn new_node(&mut self, style: Style, children: sys::ChildrenVec<NodeId>) -> NodeId {
54        let id = self.nodes.len();
55        for child in &children {
56            self.parents[*child].push(id);
57        }
58        self.nodes.push(NodeData::new(style));
59        self.children.push(children);
60        self.parents.push(sys::new_vec_with_capacity(1));
61        id
62    }
63
64    pub fn add_child(&mut self, node: NodeId, child: NodeId) {
65        self.parents[child].push(node);
66        self.children[node].push(child);
67        self.mark_dirty(node)
68    }
69
70    pub fn clear(&mut self) {
71        self.nodes.clear();
72        self.children.clear();
73        self.parents.clear();
74    }
75
76    /// Removes a node and swaps with the last node.
77    pub fn swap_remove(&mut self, node: NodeId) -> Option<NodeId> {
78        self.nodes.swap_remove(node);
79
80        // Now the last element is swapped in at index `node`.
81        if self.nodes.is_empty() {
82            self.children.clear();
83            self.parents.clear();
84            return None;
85        }
86
87        // Remove old node as parent from all its chilren.
88        for child in &self.children[node] {
89            let parents_child = &mut self.parents[*child];
90            let mut pos = 0;
91            while pos < parents_child.len() {
92                if parents_child[pos] == node {
93                    parents_child.swap_remove(pos);
94                } else {
95                    pos += 1;
96                }
97            }
98        }
99
100        // Remove old node as child from all its parents.
101        for parent in &self.parents[node] {
102            let childrens_parent = &mut self.children[*parent];
103            let mut pos = 0;
104            while pos < childrens_parent.len() {
105                if childrens_parent[pos] == node {
106                    childrens_parent.swap_remove(pos);
107                } else {
108                    pos += 1;
109                }
110            }
111        }
112
113        let last = self.nodes.len();
114
115        if last != node {
116            // Update ids for every child of the swapped in node.
117            for child in &self.children[last] {
118                for parent in &mut self.parents[*child] {
119                    if *parent == last {
120                        *parent = node;
121                    }
122                }
123            }
124
125            // Update ids for every parent of the swapped in node.
126            for parent in &self.parents[last] {
127                for child in &mut self.children[*parent] {
128                    if *child == last {
129                        *child = node;
130                    }
131                }
132            }
133
134            self.children.swap_remove(node);
135            self.parents.swap_remove(node);
136
137            Some(last)
138        } else {
139            self.children.swap_remove(node);
140            self.parents.swap_remove(node);
141            None
142        }
143    }
144
145    pub unsafe fn remove_child(&mut self, node: NodeId, child: NodeId) -> NodeId {
146        let index = self.children[node].iter().position(|n| *n == child).unwrap();
147        self.remove_child_at_index(node, index)
148    }
149
150    pub fn remove_child_at_index(&mut self, node: NodeId, index: usize) -> NodeId {
151        let child = self.children[node].remove(index);
152        self.parents[child].retain(|p| *p != node);
153        self.mark_dirty(node);
154        child
155    }
156
157    pub fn mark_dirty(&mut self, node: NodeId) {
158        fn mark_dirty_impl(nodes: &mut sys::Vec<NodeData>, parents: &[sys::ParentsVec<NodeId>], node_id: NodeId) {
159            let node = &mut nodes[node_id];
160            node.layout_cache = None;
161            node.is_dirty = true;
162
163            for parent in &parents[node_id] {
164                mark_dirty_impl(nodes, parents, *parent);
165            }
166        }
167
168        mark_dirty_impl(&mut self.nodes, &self.parents, node);
169    }
170
171    pub fn compute_layout(&mut self, node: NodeId, size: Size<Number>) {
172        self.compute(node, size)
173    }
174}
expanse/forest.rs

expanse/
forest.rs
