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