tawasuyu/taffy

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