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