orx_tree/traversal/post_order/
iter_ptr.rs

1use super::{post_enumeration::PostOrderEnumeration, states::State};
2use crate::{TreeVariant, traversal::enumeration::Enumeration, tree_variant::RefsChildren};
3use alloc::vec::Vec;
4use core::marker::PhantomData;
5use orx_self_or::SoM;
6use orx_selfref_col::NodePtr;
7
8pub type Item<V, E> = <E as Enumeration>::Item<NodePtr<V>>;
9
10pub struct PostOrderIterPtr<V, E, S = Vec<State<V>>>
11where
12    E: PostOrderEnumeration,
13    V: TreeVariant,
14    S: SoM<Vec<State<V>>>,
15{
16    states: S,
17    depth: usize,
18    phantom: PhantomData<(V, E)>,
19}
20
21impl<V, E, S> From<(S, NodePtr<V>)> for PostOrderIterPtr<V, E, S>
22where
23    E: PostOrderEnumeration,
24    V: TreeVariant,
25    S: SoM<Vec<State<V>>>,
26{
27    fn from((mut states, root): (S, NodePtr<V>)) -> Self {
28        states.get_mut().clear();
29        states.get_mut().push((root, 0));
30        Self {
31            states,
32            depth: 0,
33            phantom: PhantomData,
34        }
35    }
36}
37
38impl<V, E> Default for PostOrderIterPtr<V, E, Vec<State<V>>>
39where
40    E: PostOrderEnumeration,
41    V: TreeVariant,
42{
43    fn default() -> Self {
44        Self {
45            states: Vec::default(),
46            depth: 0,
47            phantom: PhantomData,
48        }
49    }
50}
51
52impl<V, E> Clone for PostOrderIterPtr<V, E, Vec<State<V>>>
53where
54    E: PostOrderEnumeration,
55    V: TreeVariant,
56{
57    fn clone(&self) -> Self {
58        Self {
59            states: self.states.clone(),
60            depth: self.depth,
61            phantom: PhantomData,
62        }
63    }
64}
65
66// iterator
67
68impl<V, E, S> PostOrderIterPtr<V, E, S>
69where
70    E: PostOrderEnumeration,
71    V: TreeVariant,
72    S: SoM<Vec<State<V>>>,
73{
74    fn current(&self) -> Option<&State<V>> {
75        match self.depth < usize::MAX {
76            true => self.states.get_ref().get(self.depth),
77            false => None,
78        }
79    }
80
81    fn move_deeper(&mut self, child: NodePtr<V>) {
82        self.depth += 1;
83        super::states::set(self.states.get_mut(), self.depth, child);
84    }
85
86    fn move_shallower(&mut self) {
87        match self.depth {
88            0 => self.depth = usize::MAX,
89            _ => {
90                self.depth -= 1;
91                super::states::increment_child_idx(self.states.get_mut(), self.depth);
92            }
93        }
94    }
95}
96
97impl<V, E, S> Iterator for PostOrderIterPtr<V, E, S>
98where
99    E: PostOrderEnumeration,
100    V: TreeVariant,
101    S: SoM<Vec<State<V>>>,
102{
103    type Item = Item<V, E>;
104
105    fn next(&mut self) -> Option<Self::Item> {
106        loop {
107            match self.current() {
108                None => return None,
109                Some((ptr, child_idx)) => {
110                    let node = unsafe { &*ptr.ptr() };
111                    let child_ptr = node.next().get_ptr(*child_idx).cloned();
112                    match child_ptr {
113                        Some(child_ptr) => self.move_deeper(child_ptr),
114                        None => {
115                            let output = Some(E::create_post_item(
116                                ptr.clone(),
117                                self.depth,
118                                self.states.get_ref(),
119                            ));
120                            self.move_shallower();
121                            return output;
122                        }
123                    }
124                }
125            }
126        }
127    }
128}
orx_tree/traversal/post_order/iter_ptr.rs

orx_tree/traversal/post_order/
iter_ptr.rs
