orx_tree/dary/
aliases.rs

1use super::Dary;
2use crate::{Node, Tree, memory::Auto, pinned_storage::SplitRecursive};
3
4/// A binary tree where each of the nodes might have at most 2 children.
5pub type Binary<T> = Dary<2, T>;
6
7/// A d-ary tree where each of the nodes might have at most `D` children.
8///
9/// # Examples
10///
11/// ```
12/// use orx_tree::*;
13///
14/// // # A. BUILDING A TREE
15///
16/// //      1
17/// //     ╱ ╲
18/// //    ╱   ╲
19/// //   2     3
20/// //  ╱ ╲   ╱ ╲
21/// // 4   5 6   7
22/// // |     |  ╱ ╲
23/// // 8     9 10  11
24///
25/// let mut tree = DaryTree::<4, _>::new(1i32); // each node can have at most 4 children
26///
27/// let mut root = tree.root_mut();
28/// let [id2, id3] = root.push_children([2, 3]);
29/// let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
30/// let id8 = tree.node_mut(&id4).push_child(8);
31/// let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
32/// let id9 = tree.node_mut(&id6).push_child(9);
33/// tree.node_mut(&id7).push_children([10, 11]);
34///
35/// // traversals
36///
37/// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
38/// assert_eq!(bfs, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);
39///
40/// let dfs: Vec<_> = tree.node(&id3).walk::<Dfs>().copied().collect();
41/// assert_eq!(dfs, [3, 6, 9, 7, 10, 11]);
42///
43/// let post_order: Vec<_> = tree.node(&id3).walk::<PostOrder>().copied().collect();
44/// assert_eq!(post_order, [9, 6, 10, 11, 7, 3]);
45///
46/// let leaves: Vec<_> = tree.root().leaves::<Dfs>().copied().collect();
47/// assert_eq!(leaves, [8, 5, 9, 10, 11]);
48///
49/// let node3 = tree.node(&id3);
50/// let paths: Vec<Vec<_>> = node3.paths::<Bfs>().map(|p| p.copied().collect()).collect();
51/// assert_eq!(paths, [[9, 6, 3], [10, 7, 3], [11, 7, 3]]);
52/// ```
53///
54/// # Type Aliases and Generic Parameters
55///
56/// Below is the list of pairs of tree & node type aliases from the simplest to the most complex.
57///
58/// Note that the generic parameter `P` can almost always be omitted since the default storage is almost always preferable.
59///
60/// Generic parameter `M` can also be omitted in most cases to use the default auto reclaim policy.
61/// Therefore, we can use the simplest type signatures.
62/// However, in certain situations it is preferable to use the *never* reclaim policy which guarantees that the node indices
63/// will always remain valid.
64///
65/// Please see the relevant documentations of [`NodeIdx`] and [`MemoryPolicy`].
66///
67/// [`NodeIdx`]: crate::NodeIdx
68/// [`MemoryPolicy`]: crate::MemoryPolicy
69///
70/// *Type aliases with default pinned vector storage and default memory reclaim policy:*
71///
72/// ```ignore
73/// DaryTree<D, T>     ==> Tree<Dary<D, T>>
74/// DaryNode<'a, D, T> ==> Node<'a, Dary<D, T>>
75/// ```
76///
77/// *Type aliases with default pinned vector storage (recommended):*
78///
79/// ```ignore
80/// DaryTree<D, T, M>     ==> Tree<Dary<D, T>, M>
81/// DaryNode<'a, D, T, M> ==> Node<'a, Dary<D, T>, M>
82/// ```
83///
84/// *The most general type aliases:*
85///
86/// ```ignore
87/// DaryTree<D, T, M, P>     ==> Tree<Dary<D, T>, M, P>
88/// DaryNode<'a, D, T, M, P> ==> Node<'a, Dary<D, T>, M, P>
89/// ```
90pub type DaryTree<const D: usize, T, M = Auto, P = SplitRecursive> = Tree<Dary<D, T>, M, P>;
91
92/// A binary tree where each node might have 0, 1 or 2 children.
93///
94/// # Examples
95///
96/// ```
97/// use orx_tree::*;
98///
99/// // # A. BUILDING A TREE
100///
101/// //      1
102/// //     ╱ ╲
103/// //    ╱   ╲
104/// //   2     3
105/// //  ╱ ╲   ╱ ╲
106/// // 4   5 6   7
107/// // |     |  ╱ ╲
108/// // 8     9 10  11
109///
110/// let mut tree = BinaryTree::new(1i32); // each node can have at most 2 children
111///
112/// let mut root = tree.root_mut();
113/// let [id2, id3] = root.push_children([2, 3]);
114/// let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
115/// let id8 = tree.node_mut(&id4).push_child(8);
116/// let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
117/// let id9 = tree.node_mut(&id6).push_child(9);
118/// tree.node_mut(&id7).push_children([10, 11]);
119///
120/// // traversals
121///
122/// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
123/// assert_eq!(bfs, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);
124///
125/// let dfs: Vec<_> = tree.node(&id3).walk::<Dfs>().copied().collect();
126/// assert_eq!(dfs, [3, 6, 9, 7, 10, 11]);
127///
128/// let post_order: Vec<_> = tree.node(&id3).walk::<PostOrder>().copied().collect();
129/// assert_eq!(post_order, [9, 6, 10, 11, 7, 3]);
130///
131/// let leaves: Vec<_> = tree.root().leaves::<Dfs>().copied().collect();
132/// assert_eq!(leaves, [8, 5, 9, 10, 11]);
133///
134/// let node3 = tree.node(&id3);
135/// let paths: Vec<Vec<_>> = node3.paths::<Bfs>().map(|p| p.copied().collect()).collect();
136/// assert_eq!(paths, [[9, 6, 3], [10, 7, 3], [11, 7, 3]]);
137/// ```
138///
139/// # Type Aliases and Generic Parameters
140///
141/// Below is the list of pairs of tree & node type aliases from the simplest to the most complex.
142///
143/// Note that the generic parameter `P` can almost always be omitted since the default storage is almost always preferable.
144///
145/// Generic parameter `M` can also be omitted in most cases to use the default auto reclaim policy.
146/// Therefore, we can use the simplest type signatures.
147/// However, in certain situations it is preferable to use the *never* reclaim policy which guarantees that the node indices
148/// will always remain valid.
149///
150/// Please see the relevant documentations of [`NodeIdx`] and [`MemoryPolicy`].
151///
152/// [`NodeIdx`]: crate::NodeIdx
153/// [`MemoryPolicy`]: crate::MemoryPolicy
154///
155/// *Type aliases with default pinned vector storage and default memory reclaim policy:*
156///
157/// ```ignore
158/// BinaryTree<T>     ==> Tree<Dary<2, T>>
159/// BinaryNode<'a, T> ==> Node<'a, Dary<2, T>>
160/// ```
161///
162/// *Type aliases with default pinned vector storage (recommended):*
163///
164/// ```ignore
165/// BinaryTree<T, M>     ==> Tree<Dary<2, T>, M>
166/// BinaryNode<'a, T, M> ==> Node<'a, Dary<2, T>, M>
167/// ```
168///
169/// *The most general type aliases:*
170///
171/// ```ignore
172/// BinaryTree<T, M, P>     ==> Tree<Dary<2, T>, M, P>
173/// BinaryNode<'a, T, M, P> ==> Node<'a, Dary<2, T>, M, P>
174/// ```
175pub type BinaryTree<T, M = Auto, P = SplitRecursive> = Tree<Binary<T>, M, P>;
176
177// nodes
178
179/// Node of a [`DaryTree`].
180pub type DaryNode<'a, const D: usize, T, M = Auto, P = SplitRecursive> = Node<'a, Dary<D, T>, M, P>;
181
182/// Node of a [`BinaryTree`].
183pub type BinaryNode<'a, T, M = Auto, P = SplitRecursive> = Node<'a, Dary<2, T>, M, P>;
orx_tree/dary/aliases.rs

orx_tree/dary/
aliases.rs
