tree_struct/lib.rs
1#![doc = include_str!("../README.md")]
2mod iter;
3mod node;
4
5pub use iter::{IterBFS, IterDFS};
6pub use node::{Node, NodeBuilder};
7use std::{fmt::Debug, pin::Pin, ptr::NonNull};
8
9type Owned<T> = Pin<Box<T>>;
10type Parent<T> = NonNull<T>;
11
12/// A Tree of [`Node`]s.
13/// The root of the Tree has *no parent*.
14///
15/// ### Ownership
16/// When a [`Node`] method *returns* this type, it means it is **passing ownership** of the [`Node`]s.
17///
18/// When a [`Node`] method *asks* for this type as argument, it means it is **taking ownership** of the [`Node`]s.
19pub struct Tree<T> {
20 root: Owned<Node<T>>,
21}
22impl<T> Tree<T> {
23 #[inline]
24 pub fn builder(content: T) -> NodeBuilder<T> {
25 NodeBuilder::new(content)
26 }
27
28 pub fn root(&self) -> &Node<T> {
29 self.root.as_ref().get_ref()
30 }
31 pub fn root_mut(&mut self) -> Pin<&mut Node<T>> {
32 self.root.as_mut()
33 }
34
35 /// Removes the **descendant** of the **root [`Node`]** from the [`Tree`], and returns the *detached [`Node`]* with ownership (aka a [`Tree`]).
36 ///
37 /// Returns [`None`] if it is not a **descendant** of the **root**, or **root** [`is_same_as`](Node::is_same_as()) **descendant**.
38 ///
39 /// This function can only be called from the **root [`Node`]**.
40 ///
41 /// **descendant** must be a *NonNull pointer* (obtained from [`Node::ptr`]) because, if it was a reference,
42 /// the borrow checker will consider the entire [`Tree`] to be *immutably borrowed* (including *self*).
43 /// The **descendant** pointer passed to this function will remain valid because it is [`Pin`]ned.
44 ///
45 /// # Example
46 /// ```
47 /// # use tree_struct::Node;
48 /// # let mut tree = Node::builder(0).child(Node::builder(1)).child(Node::builder(2)).build();
49 /// let target = tree.root().children()[1].ptr();
50 /// let detached = tree.detach_descendant(target).unwrap();
51 /// assert!(detached.root().is_same_as(target));
52 /// ```
53 #[inline]
54 pub fn detach_descendant(&mut self, descendant: NonNull<Node<T>>) -> Option<Self> {
55 self.root_mut().detach_descendant(descendant)
56 }
57
58 /// Mutably borrows a **descendant** of the [`Tree`]'s **root [`Node`]** as `mutable`.
59 /// See [Mutable Iterators section](self#iterators-for-mutable-nodes) for why obtaining a `&mut Node` was implemented this way.
60 ///
61 /// Returns [`None`] if it is not a **descendant** of the **root**, or **root** [`is_same_as`](Node::is_same_as()) **descendant**.
62 ///
63 /// This function can be used to *mutably borrow* a [`Node`] obtained by a [`Node iterator`](IterBFS).
64 ///
65 /// **descendant** must be a *NonNull pointer* (obtained from [`Node::ptr`]) because, if it was a reference,
66 /// the borrow checker will consider the entire [`Tree`] to be *immutably borrowed* (including *self*).
67 /// The **descendant** pointer passed to this function will remain valid because it is [`Pin`]ned.
68 ///
69 /// # Example
70 /// ```
71 /// # use tree_struct::Node;
72 /// # let mut tree = Node::builder('a').child(Node::builder('b').child(Node::builder('c'))).build();
73 /// let target = tree.iter_bfs().find(|n| n.content == 'c').unwrap().ptr();
74 /// let borrowed = tree.borrow_descendant(target).unwrap();
75 /// assert!(borrowed.is_same_as(target));
76 /// ```
77 ///
78 /// It should be enough to assert that the whole [`Tree`] is `mut`, so by extension the **descendant** is also `mut`.
79 #[inline]
80 pub fn borrow_descendant(&mut self, descendant: NonNull<Node<T>>) -> Option<Pin<&mut Node<T>>> {
81 self.root_mut().borrow_descendant(descendant)
82 }
83
84 #[inline]
85 /// Iterate over all the [`Node`]s of the [`Tree`] using **Breadth-First Search**.
86 pub fn iter_bfs(&self) -> IterBFS<T> {
87 IterBFS::new(self.root())
88 }
89 #[inline]
90 /// Iterate over all the [`Node`]s of the [`Tree`] using **Depth-First Search**.
91 pub fn iter_dfs(&self) -> IterDFS<T> {
92 IterDFS::new(self.root())
93 }
94}
95
96/* Only Tree should implement IntoIter because , semantically, it makes sense to iterate through a Tree, but doesn't make sense to iterate through a Node.
97Node still has iter_bfs() and iter_dfs() in case the user wants to use it that way. */
98impl<'a, T> IntoIterator for &'a Tree<T> {
99 type Item = &'a Node<T>;
100 type IntoIter = IterBFS<'a, T>;
101
102 #[inline]
103 fn into_iter(self) -> Self::IntoIter {
104 self.iter_bfs()
105 }
106}
107
108impl<T> From<NodeBuilder<T>> for Tree<T> {
109 #[inline]
110 fn from(builder: NodeBuilder<T>) -> Self {
111 builder.build()
112 }
113}
114impl<T: Default> Default for Tree<T> {
115 fn default() -> Self {
116 NodeBuilder::default().build()
117 }
118}
119impl<T: Clone> Clone for Tree<T> {
120 /// Clones the entire [`Tree`] by calling [`Node::clone_deep()`] on the **root**.
121 fn clone(&self) -> Self {
122 self.root().clone_deep()
123 }
124}
125impl<T: PartialEq> PartialEq for Tree<T> {
126 fn eq(&self, other: &Self) -> bool {
127 self.root().eq(other.root())
128 }
129}
130impl<T: Eq> Eq for Tree<T> {}
131impl<T: Debug> Debug for Tree<T> {
132 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133 f.debug_struct("Tree")
134 .field("root", &self.root().debug_tree())
135 .finish()
136 }
137}
138
139/// Obtained by calling [`Node::debug_tree()`].
140pub struct DebugTree<'a, T: Debug> {
141 root: &'a Node<T>,
142}
143impl<'a, T: Debug> Debug for DebugTree<'a, T> {
144 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
145 f.debug_struct("Node")
146 .field("content", &self.root.content)
147 .field(
148 "children",
149 &self
150 .root
151 .children()
152 .iter()
153 .map(|c| c.debug_tree())
154 .collect::<Box<_>>(),
155 )
156 .finish()
157 }
158}