orx_tree/traversal/breadth_first/
into_iter.rs

1use super::BreadthFirstEnumeration;
2use super::iter_ptr::BfsIterPtr;
3use super::queue::Item;
4use crate::TreeVariant;
5use crate::aliases::Col;
6use crate::memory::MemoryPolicy;
7use crate::pinned_storage::PinnedStorage;
8use alloc::collections::VecDeque;
9use orx_self_or::SoM;
10use orx_selfref_col::{NodePtr, Refs};
11
12pub struct BfsIterInto<'a, V, M, P, E, S>
13where
14    V: TreeVariant,
15    M: MemoryPolicy,
16    P: PinnedStorage,
17    E: BreadthFirstEnumeration,
18    S: SoM<VecDeque<Item<V, E>>>,
19{
20    col: &'a mut Col<V, M, P>,
21    root_ptr: NodePtr<V>,
22    iter: BfsIterPtr<V, E, S>,
23}
24
25impl<'a, V, M, P, E, S> BfsIterInto<'a, V, M, P, E, S>
26where
27    V: TreeVariant,
28    M: MemoryPolicy,
29    P: PinnedStorage,
30    E: BreadthFirstEnumeration,
31    S: SoM<VecDeque<Item<V, E>>>,
32{
33    /// # Safety
34    ///
35    /// We are creating a mutable iterator over nodes of the collection `col`.
36    /// This is safe only when the second argument `iter` makes sure that there exists only one mutable
37    /// reference to the collection.
38    ///
39    /// This is the case how this method is used, as follows:
40    /// * Mutable iterators are created through the `Dfs` traverser's `TraverserMut::iter_mut` method.
41    /// * This method requires a mutable reference to a mutable node `NodeMut` which is guaranteed to
42    ///   be the only reference to the collection.
43    /// * Finally, this iterator's lifetime is equal to the borrow duration of the mutable node.
44    #[allow(clippy::type_complexity)]
45    pub(crate) unsafe fn from(
46        (col, iter, root_ptr): (&'a mut Col<V, M, P>, BfsIterPtr<V, E, S>, NodePtr<V>),
47    ) -> Self {
48        let node = unsafe { &mut *root_ptr.ptr_mut() };
49
50        match node.prev().get() {
51            Some(parent) => {
52                let parent = unsafe { &mut *parent.ptr_mut() };
53                let sibling_idx = parent.next_mut().remove(root_ptr.ptr() as usize);
54                debug_assert!(sibling_idx.is_some());
55
56                node.prev_mut().clear();
57            }
58            None => {
59                // node_ptr points to the root node
60                col.ends_mut().clear();
61            }
62        }
63
64        Self {
65            col,
66            root_ptr,
67            iter,
68        }
69    }
70
71    fn take_element(&mut self, element: E::Item<NodePtr<V>>) -> E::Item<V::Item> {
72        E::map_node_data(element, |ptr| {
73            let col = unsafe { &mut *(self.col as *mut Col<V, M, P>) };
74            col.close(&ptr)
75        })
76    }
77}
78
79impl<V, M, P, E, S> Iterator for BfsIterInto<'_, V, M, P, E, S>
80where
81    V: TreeVariant,
82    M: MemoryPolicy,
83    P: PinnedStorage,
84    E: BreadthFirstEnumeration,
85    S: SoM<VecDeque<Item<V, E>>>,
86{
87    type Item = E::Item<V::Item>;
88
89    fn next(&mut self) -> Option<Self::Item> {
90        self.iter.next().map(|element| self.take_element(element))
91    }
92}
93
94impl<V, M, P, E, S> Drop for BfsIterInto<'_, V, M, P, E, S>
95where
96    V: TreeVariant,
97    M: MemoryPolicy,
98    P: PinnedStorage,
99    E: BreadthFirstEnumeration,
100    S: SoM<VecDeque<Item<V, E>>>,
101{
102    fn drop(&mut self) {
103        while let Some(element) = self.iter.next() {
104            self.take_element(element);
105        }
106        self.col.reclaim_from_closed_node(&self.root_ptr);
107    }
108}
orx_tree/traversal/breadth_first/into_iter.rs

orx_tree/traversal/breadth_first/
into_iter.rs
