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

orx_tree/
tree_variant.rs
