orx_tree/subtrees/
subtree.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
use crate::TreeVariant;

pub(crate) mod sealed {

    use crate::{
        pinned_storage::PinnedStorage, DepthFirstSequence, MemoryPolicy, NodeIdx, NodeMut,
        NodeMutOrientation, Tree, TreeVariant,
    };
    use orx_selfref_col::NodePtr;

    pub trait SubTreeCore<Vs: TreeVariant>: Sized {
        fn root_ptr(&self) -> NodePtr<Vs>;

        fn root_parent_ptr(&self) -> Option<NodePtr<Vs>>;

        fn root_sibling_idx(&self) -> usize;

        fn create_subtree(&mut self) -> impl IntoIterator<Item = (usize, Vs::Item)>;

        // provided methods

        fn append_to_node_as_child<V, M, P, MO>(
            mut self,
            parent: &mut NodeMut<V, M, P, MO>,
            child_position: usize,
        ) -> NodeIdx<V>
        where
            V: TreeVariant<Item = Vs::Item>,
            M: MemoryPolicy,
            P: PinnedStorage,
            MO: NodeMutOrientation,
        {
            let subtree = self.create_subtree();
            parent.append_subtree_as_child(subtree, child_position)
        }

        fn into_new_tree<V2, M2, P2>(mut self) -> Tree<V2, M2, P2>
        where
            V2: TreeVariant<Item = Vs::Item>,
            M2: MemoryPolicy,
            P2: PinnedStorage,
            P2::PinnedVec<V2>: Default,
        {
            let subtree = self.create_subtree();
            let dfs = DepthFirstSequence::from(subtree);
            Tree::try_from(dfs).expect("subtree is a valid depth first sequence")
        }
    }
}

/// A subtree is a subset of a tree, also having a single root and satisfying structural tree properties.
///
/// SubTree implementations are used to efficiently and conveniently move parts of the tree between different trees.
pub trait SubTree<Vs>: sealed::SubTreeCore<Vs>
where
    Vs: TreeVariant,
{
}

impl<Vs, S> SubTree<Vs> for S
where
    Vs: TreeVariant,
    S: sealed::SubTreeCore<Vs>,
{
}