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
44pub(crate) struct Forest {
45 pub(crate) nodes: Vec<NodeData>,
46 pub(crate) children: Vec<ChildrenVec<NodeId>>,
47 pub(crate) parents: Vec<ParentsVec<NodeId>>,
48}
49
50impl Forest {
51 pub fn with_capacity(capacity: usize) -> Self {
52 Self {
53 nodes: new_vec_with_capacity(capacity),
54 children: new_vec_with_capacity(capacity),
55 parents: new_vec_with_capacity(capacity),
56 }
57 }
58
59 pub fn new_leaf(&mut self, style: Style, measure: MeasureFunc) -> NodeId {
60 let id = self.nodes.len();
61 self.nodes.push(NodeData::new_leaf(style, measure));
62 self.children.push(new_vec_with_capacity(0));
63 self.parents.push(new_vec_with_capacity(1));
64 id
65 }
66
67 pub fn new_node(&mut self, style: Style, children: ChildrenVec<NodeId>) -> NodeId {
68 let id = self.nodes.len();
69 for child in &children {
70 self.parents[*child].push(id);
71 }
72 self.nodes.push(NodeData::new(style));
73 self.children.push(children);
74 self.parents.push(new_vec_with_capacity(1));
75 id
76 }
77
78 pub fn add_child(&mut self, node: NodeId, child: NodeId) {
79 self.parents[child].push(node);
80 self.children[node].push(child);
81 self.mark_dirty(node)
82 }
83
84 pub fn clear(&mut self) {
85 self.nodes.clear();
86 self.children.clear();
87 self.parents.clear();
88 }
89
90 /// Removes a node and swaps with the last node.
91 pub fn swap_remove(&mut self, node: NodeId) -> Option<NodeId> {
92 self.nodes.swap_remove(node);
93
94 // Now the last element is swapped in at index `node`.
95 if self.nodes.is_empty() {
96 self.children.clear();
97 self.parents.clear();
98 return None;
99 }
100
101 // Remove old node as parent from all its chilren.
102 for child in &self.children[node] {
103 let parents_child = &mut self.parents[*child];
104 let mut pos = 0;
105 while pos < parents_child.len() {
106 if parents_child[pos] == node {
107 parents_child.swap_remove(pos);
108 } else {
109 pos += 1;
110 }
111 }
112 }
113
114 // Remove old node as child from all its parents.
115 for parent in &self.parents[node] {
116 let childrens_parent = &mut self.children[*parent];
117 let mut pos = 0;
118 while pos < childrens_parent.len() {
119 if childrens_parent[pos] == node {
120 childrens_parent.swap_remove(pos);
121 } else {
122 pos += 1;
123 }
124 }
125 }
126
127 let last = self.nodes.len();
128
129 if last != node {
130 // Update ids for every child of the swapped in node.
131 for child in &self.children[last] {
132 for parent in &mut self.parents[*child] {
133 if *parent == last {
134 *parent = node;
135 }
136 }
137 }
138
139 // Update ids for every parent of the swapped in node.
140 for parent in &self.parents[last] {
141 for child in &mut self.children[*parent] {
142 if *child == last {
143 *child = node;
144 }
145 }
146 }
147
148 self.children.swap_remove(node);
149 self.parents.swap_remove(node);
150
151 Some(last)
152 } else {
153 self.children.swap_remove(node);
154 self.parents.swap_remove(node);
155 None
156 }
157 }
158
159 pub fn remove_child(&mut self, node: NodeId, child: NodeId) -> NodeId {
160 let index = self.children[node].iter().position(|n| *n == child).unwrap();
161 self.remove_child_at_index(node, index)
162 }
163
164 pub fn remove_child_at_index(&mut self, node: NodeId, index: usize) -> NodeId {
165 let child = self.children[node].remove(index);
166 self.parents[child].retain(|p| *p != node);
167 self.mark_dirty(node);
168 child
169 }
170
171 pub fn mark_dirty(&mut self, node: NodeId) {
172 fn mark_dirty_impl(nodes: &mut Vec<NodeData>, parents: &[ParentsVec<NodeId>], node_id: NodeId) {
173 let node = &mut nodes[node_id];
174 node.main_size_layout_cache = None;
175 node.other_layout_cache = None;
176 node.is_dirty = true;
177
178 for parent in &parents[node_id] {
179 mark_dirty_impl(nodes, parents, *parent);
180 }
181 }
182
183 mark_dirty_impl(&mut self.nodes, &self.parents, node);
184 }
185
186 pub fn compute_layout(&mut self, node: NodeId, size: Size<Number>) {
187 self.compute(node, size)
188 }
189}