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