tawasuyu/taffy

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