scene_graph/
detatch_iter.rs

1use thunderdome::Arena;
2
3use crate::{Children, Node, NodeIndex};
4use std::collections::VecDeque;
5
6/// An iterator over the children of a node in a [SceneGraph].
7/// See [iter_detach] and [iter_detach_all] for more information.
8///
9/// If the iterator is dropped early, it drops all the remaining elements on the iterator.
10/// 
11/// [SceneGraph]: crate::SceneGraph
12/// [iter_detach]: crate::SceneGraph::iter_detach
13/// [iter_detach_all]: crate::SceneGraph::iter_detach_from_root
14pub struct SceneGraphDetachIter<'a, T> {
15    arena: &'a mut Arena<Node<T>>,
16    stacks: VecDeque<StackState<T>>,
17}
18
19impl<'a, T> SceneGraphDetachIter<'a, T> {
20    pub(crate) fn new(
21        arena: &'a mut Arena<Node<T>>,
22        head_index: NodeIndex,
23        current_children: Option<Children>,
24    ) -> Self {
25        let mut stacks = VecDeque::new();
26
27        if let Some(children) = current_children {
28            stacks.push_front(StackState::new(
29                head_index,
30                arena.remove(children.first).unwrap(),
31                NodeIndex::Branch(children.first),
32            ));
33        }
34        SceneGraphDetachIter { arena, stacks }
35    }
36}
37
38impl<'a, T> Iterator for SceneGraphDetachIter<'a, T> {
39    type Item = DetachedNode<T>;
40
41    fn next(&mut self) -> Option<Self::Item> {
42        // if we're out of stack frames, we die here
43        let stack_frame = self.stacks.pop_front()?;
44
45        // if there's a sibling, push it onto the to do list!
46        if let Some(next_sibling) = stack_frame.current_child.next_sibling {
47            self.stacks.push_front(StackState::new(
48                stack_frame.parent,
49                self.arena.remove(next_sibling).unwrap(),
50                NodeIndex::Branch(next_sibling),
51            ));
52        }
53
54        // if there's a child, push it on the list first
55        if let Some(children) = stack_frame.current_child.children {
56            let new_stack = StackState::new(
57                stack_frame.current_child_idx,
58                self.arena.remove(children.first).unwrap(),
59                NodeIndex::Branch(children.first),
60            );
61            self.stacks.push_front(new_stack);
62        }
63
64        Some(DetachedNode {
65            parent_idx: stack_frame.parent,
66            node_idx: stack_frame.current_child_idx,
67            node_value: stack_frame.current_child.value,
68        })
69    }
70}
71
72impl<'a, T> Drop for SceneGraphDetachIter<'a, T> {
73    fn drop(&mut self) {
74        // eat up that iterator
75        for _ in self {}
76    }
77}
78
79/// A detached node from a scene graph.
80#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
81pub struct DetachedNode<T> {
82    /// The original parent idx, which may or may not still be in the scene graph itself.
83    pub parent_idx: NodeIndex,
84    /// Its old node_index.
85    pub node_idx: NodeIndex,
86    /// The value of the node.
87    pub node_value: T,
88}
89
90impl<T> std::fmt::Debug for DetachedNode<T> {
91    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
92        f.debug_struct("DetachedNode")
93            .field("parent_idx", &self.parent_idx)
94            .field("node_idx", &self.node_idx)
95            .finish_non_exhaustive()
96    }
97}
98
99struct StackState<T> {
100    parent: NodeIndex,
101    current_child: Node<T>,
102    current_child_idx: NodeIndex,
103}
104
105impl<T> std::fmt::Debug for StackState<T> {
106    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
107        f.debug_struct("StackState")
108            .field("parent", &self.parent)
109            .field("current_child", &self.current_child)
110            .field("current_child_idx", &self.current_child_idx)
111            .finish()
112    }
113}
114
115impl<T> StackState<T> {
116    fn new(parent: NodeIndex, first_child: Node<T>, first_child_idx: NodeIndex) -> Self {
117        Self {
118            parent,
119            current_child: first_child,
120            current_child_idx: first_child_idx,
121        }
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use crate::SceneGraph;
128
129    use super::*;
130
131    #[test]
132    fn detach_handles_empty() {
133        let mut scene_graph = SceneGraph::new("Root");
134
135        assert!(scene_graph.iter_detach_from_root().next().is_none());
136    }
137
138    #[test]
139    fn detach_iteration() {
140        let mut sg = SceneGraph::new("Root");
141        let root_idx = NodeIndex::Root;
142        sg.attach(root_idx, "First Child").unwrap();
143
144        let second_child = sg.attach(root_idx, "Second Child").unwrap();
145        sg.attach(second_child, "First Grandchild").unwrap();
146
147        assert_eq!(
148            Vec::from_iter(sg.iter_detach_from_root().map(|d_v| d_v.node_value)),
149            vec!["First Child", "Second Child", "First Grandchild"]
150        );
151
152        assert!(sg.is_empty());
153    }
154
155    #[test]
156    fn stagger_detach_iteration() {
157        let mut sg = SceneGraph::new("Root");
158        let root_idx = NodeIndex::Root;
159        let child = sg.attach(root_idx, "First Child").unwrap();
160        sg.attach(child, "Second Child").unwrap();
161
162        assert_eq!(
163            Vec::from_iter(sg.iter_detach_from_root().map(|value| value.node_value)),
164            vec!["First Child", "Second Child"]
165        );
166        assert!(sg.is_empty());
167    }
168
169    #[test]
170    fn single_detach_iteration() {
171        let mut sg = SceneGraph::new("Root");
172        let root_idx = NodeIndex::Root;
173        sg.attach(root_idx, "First Child").unwrap();
174
175        assert_eq!(
176            Vec::from_iter(sg.iter_detach_from_root().map(|value| value.node_value)),
177            vec!["First Child",]
178        );
179        assert!(sg.is_empty());
180    }
181
182    #[test]
183    fn child_detach_iteration() {
184        let mut sg = SceneGraph::new("Root");
185        let root_idx = NodeIndex::Root;
186        sg.attach(root_idx, "First Child").unwrap();
187
188        let second_child = sg.attach(root_idx, "Second Child").unwrap();
189        sg.attach(second_child, "First Grandchild").unwrap();
190        sg.attach(second_child, "Second Grandchild").unwrap();
191        sg.attach(second_child, "Third Grandchild").unwrap();
192        sg.attach(second_child, "Fourth Grandchild").unwrap();
193
194        assert_eq!(
195            Vec::from_iter(sg.iter_detach(second_child).unwrap().map(|d_v| d_v.node_value)),
196            vec![
197                "First Grandchild",
198                "Second Grandchild",
199                "Third Grandchild",
200                "Fourth Grandchild"
201            ]
202        );
203
204        assert!(!sg.is_empty());
205    }
206
207    #[test]
208    fn child_detach_iteration_grand() {
209        let mut sg = SceneGraph::new("Root");
210        let root_idx = NodeIndex::Root;
211        sg.attach(root_idx, "First Child").unwrap();
212
213        let second_child = sg.attach(root_idx, "Second Child").unwrap();
214        let gc = sg.attach(second_child, "First Grandchild").unwrap();
215        sg.attach(gc, "First Great-Grandchild").unwrap();
216        sg.attach(second_child, "Second Grandchild").unwrap();
217        sg.attach(second_child, "Third Grandchild").unwrap();
218
219        assert_eq!(
220            Vec::from_iter(sg.iter_detach(second_child).unwrap().map(|d_v| d_v.node_value)),
221            vec![
222                "First Grandchild",
223                "First Great-Grandchild",
224                "Second Grandchild",
225                "Third Grandchild"
226            ]
227        );
228
229        assert!(!sg.is_empty());
230    }
231
232    #[test]
233    fn child_detach_iteration_grand2() {
234        let mut sg = SceneGraph::new("Root");
235        let root_idx = NodeIndex::Root;
236        sg.attach(root_idx, "First Child").unwrap();
237
238        let second_child = sg.attach(root_idx, "Second Child").unwrap();
239        let gc = sg.attach(second_child, "First Grandchild").unwrap();
240        sg.attach(gc, "First Great-Grandchild").unwrap();
241        sg.attach(second_child, "Second Grandchild").unwrap();
242        sg.attach(second_child, "Third Grandchild").unwrap();
243
244        assert_eq!(
245            Vec::from_iter(sg.iter_detach(gc).unwrap().map(|d_v| d_v.node_value)),
246            vec!["First Great-Grandchild",]
247        );
248
249        assert_eq!(
250            Vec::from_iter(sg.iter_detach(gc).unwrap().map(|d_v| d_v.node_value)),
251            Vec::<&'static str>::new()
252        );
253    }
254}
scene_graph/detatch_iter.rs

scene_graph/
detatch_iter.rs
