pathtree/
lib.rs

1//! An immutable tree data structure for fast path operations.
2//!
3//! [`PathTree`] is inexpensive to clone and supports prepending and appending paths to one
4//! another. Useful when several objects in a tree need to store their path relative to the root.
5#![warn(missing_docs)]
6
7use std::sync::Arc;
8
9#[cfg(test)]
10mod tests;
11
12/// A tree data structure for storing paths without mutation.
13///
14/// Cloning the data structure is inexpensive since each clone only clones a single [`Arc`].
15///
16/// # Examples
17///
18/// ```
19/// use pathtree::PathTree;
20///
21///
22/// let path = PathTree::empty();
23/// let path = path.append_segment(7);
24/// let path = path.append_segment(5);
25/// let path = path.prepend_segment(6);
26/// let path = path.prepend_segment(8);
27///
28/// let path_vec: Vec<_> = path.iter().copied().collect();
29/// assert_eq!(path_vec, vec![8, 6, 7, 5]);
30///
31/// let other_path = PathTree::empty();
32///
33/// let other_path = other_path.append_segment(2);
34/// let other_path = other_path.prepend_segment(1);
35/// let other_path = other_path.append_segment(3);
36/// let other_path = other_path.prepend_segment(4);
37///
38/// let full_path = other_path.append(&path);
39/// let full_path_vec: Vec<_> = full_path.iter().copied().collect();
40/// assert_eq!(full_path_vec, vec![4, 1, 2, 3, 8, 6, 7, 5]);
41/// ```
42#[derive(Debug, Default, Hash, Eq, PartialEq, Ord, PartialOrd)]
43pub struct PathTree<T>(Arc<PathTreeInner<T>>);
44
45impl<T> Clone for PathTree<T> {
46    fn clone(&self) -> Self {
47        Self(self.0.clone())
48    }
49}
50
51#[derive(Debug, Default, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
52struct PathTreeInner<T> {
53    segment: Option<T>,
54    parent: Option<PathTree<T>>,
55    child: Option<PathTree<T>>,
56}
57
58impl<T> PathTree<T> {
59    fn node(segment: Option<T>, parent: Option<PathTree<T>>, child: Option<PathTree<T>>) -> Self {
60        PathTree(Arc::new(PathTreeInner {
61            segment,
62            parent,
63            child,
64        }))
65    }
66
67    fn segment(&self) -> &Option<T> {
68        &self.0.segment
69    }
70
71    fn parent(&self) -> &Option<Self> {
72        &self.0.parent
73    }
74
75    fn child(&self) -> &Option<Self> {
76        &self.0.child
77    }
78
79    /// Creates a new [`PathTree`] with a single segment.
80    pub fn new(segment: T) -> Self {
81        Self::node(Some(segment), None, None)
82    }
83
84    /// Creates an empty [`PathTree`].
85    pub fn empty() -> Self {
86        Self::node(None, None, None)
87    }
88
89    /// Appends another [`PathTree`] to `self`.
90    pub fn append(&self, other: &PathTree<T>) -> Self {
91        Self::node(None, Some((*self).clone()), Some((*other).clone()))
92    }
93
94    /// Prepends another [`PathTree`] to `self`.
95    pub fn prepend(&self, other: &PathTree<T>) -> Self {
96        other.append(self)
97    }
98
99    /// Appends a segment to `self`.
100    pub fn append_segment(&self, segment: T) -> Self {
101        Self::node(Some(segment), Some((*self).clone()), None)
102    }
103
104    /// Prepends a segment to `self`.
105    pub fn prepend_segment(&self, segment: T) -> Self {
106        Self::node(Some(segment), None, Some((*self).clone()))
107    }
108
109    /// Creates an iterator over the items in the path.
110    pub fn iter(&self) -> Iter<'_, T> {
111        let mut iter = Iter::new();
112
113        iter.push_node_and_parents(self);
114
115        iter
116    }
117}
118
119impl<'a, T> IntoIterator for &'a PathTree<T> {
120    type Item = &'a T;
121    type IntoIter = Iter<'a, T>;
122
123    fn into_iter(self) -> Self::IntoIter {
124        self.iter()
125    }
126}
127
128impl<A> FromIterator<A> for PathTree<A> {
129    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
130        let mut iter = iter.into_iter();
131        if let Some(elem) = iter.next() {
132            let mut tree = PathTree::new(elem);
133            for elem in iter {
134                tree = tree.append_segment(elem);
135            }
136            tree
137        } else {
138            PathTree::empty()
139        }
140    }
141}
142
143/// An iterator over a [`PathTree`].
144pub struct Iter<'a, T> {
145    stack: Vec<&'a PathTree<T>>,
146}
147
148impl<'a, T> Iter<'a, T> {
149    fn new() -> Self {
150        Self { stack: Vec::new() }
151    }
152
153    fn push_node_and_parents(&mut self, node: &'a PathTree<T>) {
154        let mut parent = Some(node);
155        while let Some(curr) = parent {
156            self.stack.push(curr);
157            parent = curr.parent().as_ref();
158        }
159    }
160
161    fn push_child(&mut self, node: &'a PathTree<T>) {
162        if let Some(child) = node.child() {
163            self.push_node_and_parents(child);
164        }
165    }
166
167    fn pop(&mut self) -> Option<&'a PathTree<T>> {
168        let top = self.stack.pop();
169        if let Some(top) = top {
170            self.push_child(top);
171        }
172        top
173    }
174}
175
176impl<'a, T> Iterator for Iter<'a, T> {
177    type Item = &'a T;
178
179    fn next(&mut self) -> Option<Self::Item> {
180        while let Some(next) = self.pop() {
181            if let Some(segment) = next.segment().as_ref() {
182                return Some(segment);
183            }
184        }
185
186        None
187    }
188}
pathtree/lib.rs

pathtree/
lib.rs
