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}