orx_tree/
tree_variant.rs

1#[cfg(feature = "parallel")]
2use orx_parallel::*;
3use orx_selfref_col::{
4    MemoryReclaimer, NodePtr, Refs, RefsArrayLeftMost, RefsSingle, RefsVec, Variant,
5    references::iter::ArrayLeftMostPtrIter,
6};
7
8/// Variant of a tree.
9pub trait TreeVariant:
10    Variant<Ends = RefsSingle<Self>, Prev = RefsSingle<Self>, Next = Self::Children> + Sync
11{
12    /// Memory reclaimer of the tree.
13    type Reclaimer: MemoryReclaimer<Self> + Sync;
14
15    /// Children references of the tree nodes.
16    type Children: RefsChildren<Self> + Refs;
17}
18
19// children
20
21pub trait RefsChildren<V: Variant> {
22    type ChildrenPtrIter<'a>: ExactSizeIterator<Item = NodePtr<V>> + DoubleEndedIterator + Default
23    where
24        V: 'a,
25        Self: 'a;
26
27    fn num_children(&self) -> usize;
28
29    fn children_ptr<'a>(&'a self) -> Self::ChildrenPtrIter<'a>;
30
31    #[cfg(feature = "parallel")]
32    fn children_ptr_par(&self) -> impl ParIter<Item = NodePtr<V>>
33    where
34        V::Item: Send + Sync;
35
36    fn get_ptr(&self, i: usize) -> Option<NodePtr<V>>;
37
38    // mut
39
40    fn push(&mut self, node_ptr: NodePtr<V>);
41
42    fn insert(&mut self, position: usize, node_ptr: NodePtr<V>);
43
44    fn replace_with(&mut self, old_node_ptr: NodePtr<V>, new_node_ptr: NodePtr<V>)
45    -> Option<usize>;
46
47    fn swap(&mut self, ptr_a: NodePtr<V>, ptr_b: NodePtr<V>) -> Option<(usize, usize)>;
48}
49
50impl<V: Variant> RefsChildren<V> for RefsVec<V> {
51    type ChildrenPtrIter<'a>
52        = core::iter::Copied<core::slice::Iter<'a, NodePtr<V>>>
53    where
54        V: 'a,
55        Self: 'a;
56
57    #[inline(always)]
58    fn num_children(&self) -> usize {
59        self.len()
60    }
61
62    #[inline(always)]
63    fn children_ptr<'a>(&'a self) -> Self::ChildrenPtrIter<'a> {
64        self.iter().copied()
65    }
66
67    #[cfg(feature = "parallel")]
68    fn children_ptr_par(&self) -> impl ParIter<Item = NodePtr<V>>
69    where
70        V::Item: Send + Sync,
71    {
72        self.as_slice().par().copied()
73    }
74
75    #[inline(always)]
76    fn get_ptr(&self, i: usize) -> Option<NodePtr<V>> {
77        self.get(i)
78    }
79
80    #[inline(always)]
81    fn push(&mut self, node_ptr: NodePtr<V>) {
82        self.push(node_ptr);
83    }
84
85    #[inline(always)]
86    fn insert(&mut self, position: usize, node_ptr: NodePtr<V>) {
87        RefsVec::insert(self, position, node_ptr);
88    }
89
90    #[inline(always)]
91    fn replace_with(
92        &mut self,
93        old_node_ptr: NodePtr<V>,
94        new_node_ptr: NodePtr<V>,
95    ) -> Option<usize> {
96        RefsVec::replace_with(self, old_node_ptr, new_node_ptr)
97    }
98
99    #[inline(always)]
100    fn swap(&mut self, ptr_a: NodePtr<V>, ptr_b: NodePtr<V>) -> Option<(usize, usize)> {
101        RefsVec::swap(self, ptr_a, ptr_b)
102    }
103}
104
105impl<const D: usize, V: Variant> RefsChildren<V> for RefsArrayLeftMost<D, V> {
106    type ChildrenPtrIter<'a>
107        = core::iter::Copied<ArrayLeftMostPtrIter<'a, V>>
108    where
109        V: 'a,
110        Self: 'a;
111
112    #[inline(always)]
113    fn num_children(&self) -> usize {
114        self.len()
115    }
116
117    #[inline(always)]
118    fn children_ptr<'a>(&'a self) -> Self::ChildrenPtrIter<'a> {
119        self.iter().copied()
120    }
121
122    #[cfg(feature = "parallel")]
123    fn children_ptr_par(&self) -> impl ParIter<Item = NodePtr<V>>
124    where
125        V::Item: Send + Sync,
126    {
127        self.as_slice()
128            .par()
129            .map(|x| {
130                x.as_ref()
131                    .expect("all elements of RefsArrayLeftMost::as_slice are of Some variant")
132            })
133            .copied()
134    }
135
136    #[inline(always)]
137    fn get_ptr(&self, i: usize) -> Option<NodePtr<V>> {
138        self.get(i)
139    }
140
141    #[inline(always)]
142    fn push(&mut self, node_ptr: NodePtr<V>) {
143        self.push(node_ptr);
144    }
145
146    #[inline(always)]
147    fn insert(&mut self, position: usize, node_ptr: NodePtr<V>) {
148        RefsArrayLeftMost::insert(self, position, node_ptr);
149    }
150
151    #[inline(always)]
152    fn replace_with(
153        &mut self,
154        old_node_ptr: NodePtr<V>,
155        new_node_ptr: NodePtr<V>,
156    ) -> Option<usize> {
157        RefsArrayLeftMost::replace_with(self, old_node_ptr, new_node_ptr)
158    }
159
160    #[inline(always)]
161    fn swap(&mut self, ptr_a: NodePtr<V>, ptr_b: NodePtr<V>) -> Option<(usize, usize)> {
162        RefsArrayLeftMost::swap(self, ptr_a, ptr_b)
163    }
164}
orx_tree/tree_variant.rs

orx_tree/
tree_variant.rs
