nb_tree/
path.rs

1//! `Path<B>`s are arrays of branches of type `B`.
2//! They are used to designate a position in a [`Tree<N, B>`].
3//!
4//!
5//!
6//!
7//!
8//! [`Tree`]: crate::tree::Tree
9//! [`Tree<N, B>`]: crate::tree::Tree
10//! [`TreeNode`]: crate::tree::node::TreeNode
11
12use std::collections::vec_deque::{Iter, IterMut};
13use std::collections::{vec_deque::IntoIter, VecDeque};
14use std::fmt::{Debug as Dbg, Display};
15use std::hash::Hash;
16use std::ops::{Deref, Index, IndexMut};
17use std::str::FromStr;
18
19use crate::prelude::iter::depth::Traversal;
20
21/// Path branch index
22pub type PathIDX = usize;
23
24/// A path to a [`Tree`] node.
25///
26/// A `Path` is a collection of branches to follow to get to the desired node.
27/// An empty `Path` represents the root of the [`Tree`].
28///
29/// # Examples
30/// ```rust
31/// use nb_tree::{path, prelude::{Tree, Path}};
32/// let mut tree = Tree::new();
33/// // Paths from string litterals, vectors, or manually built
34/// let path_d: Path<String> = "/b/d".into();
35/// let path_e: Path<String> = vec!["a", "c", "e"].into();
36/// let path_g: Path<String> = path!["a", "g"];
37/// let mut path_f = Path::new();
38/// path_f.l("b").l("f");
39/// // Use paths to insert data
40/// tree.i("/", 0)
41///     .i("/a", 1)
42///     .i("/b", 2)
43///     .i("/a/c", 3)
44///     .i(path_d, 4)
45///     .i(path_e, 5)
46///     .i(path_f, 6)
47///     .i(path_g, 7);
48///
49/// // Use paths to retrieve data
50/// assert_eq!(tree.get(&"/a/c".into()), Ok(&3));
51///
52/// // Use paths to remove data
53/// assert_eq!(tree.len(), 8);
54/// assert_eq!(tree.remove_subtree(&"/a".into()), Ok(()));
55/// // The whole "/a/[c/e, g]" subtree is removed, removing all nodes below it too
56/// assert_eq!(tree.len(), 4);
57/// ```
58///
59/// [`Tree`]: crate::tree::Tree
60#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
61pub struct Path<B> {
62    /// Array of branches.
63    path: VecDeque<B>,
64}
65
66impl<B> Default for Path<B> {
67    fn default() -> Self {
68        Self {
69            path: VecDeque::default(),
70        }
71    }
72}
73
74impl<B: Clone> Clone for Path<B> {
75    fn clone(&self) -> Self {
76        Self {
77            path: self.path.clone(),
78        }
79    }
80}
81
82impl<B> Path<B> {
83    /// Creates a new empty `Path`.
84    pub fn new() -> Self {
85        Self {
86            path: VecDeque::new(),
87        }
88    }
89
90    /// Creates a new empty `Path`.
91    pub fn with(root: B) -> Self {
92        let mut path = VecDeque::new();
93        path.push_back(root);
94        Self { path }
95    }
96
97    /// Removes the first branch of the `Path`.
98    pub fn pop_first(&mut self) -> Option<B> {
99        self.path.pop_front()
100    }
101
102    /// Removes the last branch of the `Path`.
103    pub fn pop_last(&mut self) -> Option<B> {
104        self.path.pop_back()
105    }
106
107    /// Adds `branch` at the end of the `Path`.
108    pub fn push_last(&mut self, branch: B) {
109        self.path.push_back(branch);
110    }
111
112    /// Appends all `branches` at the end of the `Path`.
113    pub fn append(&mut self, mut branches: Path<B>) {
114        self.path.append(&mut branches.path);
115    }
116
117    /// Adds `branch` at the end of the `Path`.
118    ///
119    /// Calls can be chained.
120    pub fn l(&mut self, branch: impl Into<B>) -> &mut Self {
121        self.path.push_back(branch.into());
122        self
123    }
124
125    /// Adds `branch` at the start of the `Path`.
126    pub fn push_first(&mut self, branch: B) {
127        self.path.push_front(branch);
128    }
129
130    /// Returns the last branch of the `Path`.
131    ///
132    /// If the `Path` is empty, None is returned.
133    pub fn last(&self) -> Option<&B> {
134        self.path.back()
135    }
136
137    /// Returns the first branch of the `Path`.
138    ///
139    /// If the `Path` is empty, None is returned.
140    pub fn first(&self) -> Option<&B> {
141        self.path.front()
142    }
143
144    /// Returns true if the `Path` is empty, false otherwise.
145    pub fn is_empty(&self) -> bool {
146        self.path.is_empty()
147    }
148
149    /// Returns the length of the `Path`.
150    pub fn len(&self) -> usize {
151        self.path.len()
152    }
153
154    /// Removes `n` branches from the end of the Path.
155    pub fn truncate_end(&mut self, n: usize) {
156        if self.path.len() <= n {
157            self.path.clear();
158        } else {
159            self.path.truncate(self.path.len() - n);
160        }
161    }
162
163    /// Removes `n` branches from the start of the Path.
164    pub fn truncate_start(&mut self, n: usize) {
165        if self.path.len() <= n {
166            self.path.clear();
167        } else {
168            self.path.rotate_left(n);
169            self.path.truncate(self.path.len() - n);
170        }
171    }
172
173    /// Clears the Path.
174    pub fn clear(&mut self) {
175        self.path.clear()
176    }
177
178    /// Traverses the Tree nodes depth first.
179    ///
180    /// The children are visited in arbitrary order.
181    pub fn iter(&self) -> std::collections::vec_deque::Iter<'_, B> {
182        self.path.iter()
183    }
184
185    pub fn range<R>(&self, range: R) -> std::collections::vec_deque::Iter<'_, B>
186    where
187        R: std::ops::RangeBounds<usize>,
188    {
189        self.path.range(range)
190    }
191}
192
193impl<B> Index<PathIDX> for Path<B> {
194    type Output = B;
195
196    fn index(&self, index: PathIDX) -> &Self::Output {
197        &self.path[index]
198    }
199}
200
201impl<B> IndexMut<PathIDX> for Path<B> {
202    fn index_mut(&mut self, index: PathIDX) -> &mut Self::Output {
203        &mut self.path[index]
204    }
205}
206
207impl<B> Path<B>
208where
209    B: Clone,
210{
211    /// Creates a copy stopping at the given index (excluded).
212    pub fn path_to(&self, path_idx: PathIDX) -> Path<B> {
213        Self {
214            path: self.path.range(..path_idx).cloned().collect(),
215        }
216    }
217
218    /// Creates a copy starting at the given index (included).
219    pub fn path_from(&self, path_idx: PathIDX) -> Path<B> {
220        Self {
221            path: self.path.range(path_idx..).cloned().collect(),
222        }
223    }
224
225    /// Follows the given [`DepthFirstTraversalNode`], moving up the `Path` and going down a branch.
226    ///
227    /// The branch type can be something else than B, as long as it can be converted to it.
228    /// # Examples
229    /// ```rust
230    /// use nb_tree::prelude::{Tree, Path};
231    /// let mut tree: Tree<usize, String> = Tree::new();
232    /// tree.i("/", 0).i("/a", 1).i("/a/b", 2);
233    /// let mut iter = tree.into_iter();
234    /// let mut path: Path<String> = Path::new();
235    /// path.apply(&iter.next().unwrap());
236    /// assert_eq!(path, "/".into());
237    /// path.apply(&iter.next().unwrap());
238    /// assert_eq!(path, "/a".into());
239    /// path.apply(&iter.next().unwrap());
240    /// assert_eq!(path, "/a/b".into());
241    /// ```
242    pub fn apply<N>(&mut self, node: &Traversal<N, B>) -> bool {
243        if let Traversal::Step {
244            up,
245            branch,
246            data: _,
247        } = node
248        {
249            assert!(self.len() >= *up, "Moving up out of the tree");
250            // Move up
251            self.truncate_end(*up);
252            // Move down
253            self.push_last(branch.clone());
254            true
255        } else {
256            false
257        }
258    }
259
260    /// Dereferences the branch in `node` and applies it like [`apply()`].
261    ///
262    /// [`apply()`]: Self::apply()
263    pub fn apply_deref<N, C>(&mut self, node: &Traversal<N, C>) -> bool
264    where
265        C: Deref<Target = B>,
266    {
267        if let Traversal::Step {
268            up,
269            branch,
270            data: _,
271        } = node
272        {
273            assert!(self.len() >= *up, "Moving up out of the tree");
274            // Move up
275            self.truncate_end(*up);
276            // Move down
277            self.push_last(branch.deref().clone());
278            true
279        } else {
280            false
281        }
282    }
283
284    /// Follows the given [`DepthFirstTraversalNode`] like [`apply()`] transformed by the given `op`.
285    ///
286    /// # Examples
287    /// ```rust
288    /// use nb_tree::{path, prelude::{Tree, Path}};
289    /// let mut tree: Tree<usize, String> = Tree::new();
290    /// tree.i("/", 0).i("/a", 1).i("/a/b", 2);
291    /// let mut iter = tree.iter();
292    /// let mut path = Path::new();
293    /// let mut e = 0;
294    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
295    /// e += 1;
296    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
297    /// assert_eq!(path, path![("a".into(), 1)]);
298    /// e += 1;
299    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
300    /// assert_eq!(path, path![("a".into(), 1), ("b".into(), 2)]);
301    /// ```
302    ///
303    /// [`apply()`]: Self::apply()
304    pub fn apply_with<N, C>(&mut self, node: &Traversal<N, C>, op: impl Fn(&C) -> B) -> bool {
305        if let Traversal::Step {
306            up,
307            branch,
308            data: _,
309        } = node
310        {
311            assert!(self.len() >= *up, "Moving up out of the tree");
312            // Move up
313            self.truncate_end(*up);
314            // Move down
315            self.push_last(op(branch));
316            true
317        } else {
318            false
319        }
320    }
321}
322
323impl<B> Path<B>
324where
325    B: Clone + Eq,
326{
327    pub fn offshoot_from(&self, branch: Self) -> Path<B> {
328        let mut iter = self.iter().zip(branch.iter());
329        let mut next = iter.next();
330        while next.and_then(|(sb, ob)| (sb == ob).then_some(())).is_some() {
331            next = iter.next();
332        }
333
334        if let Some((root, _)) = next {
335            iter.fold(Path::with(root.clone()), |mut ph, (b, _)| {
336                ph.push_last(b.clone());
337                ph
338            })
339        } else {
340            Path::new()
341        }
342    }
343}
344
345impl<B> Path<&B>
346where
347    B: Clone,
348{
349    pub fn branches_to_owned(&self) -> Path<B> {
350        Path {
351            path: self.path.iter().map(|&i| i.clone()).collect(),
352        }
353    }
354}
355
356/// Error describing a failed attempt at parsing a `Path`.
357#[derive(Debug)]
358pub enum ParsePathError<P> {
359    /// The given value to parse does not contain any root.
360    NoRoot,
361    /// The parsing failed.
362    ParseError(P),
363}
364
365impl<P> From<P> for ParsePathError<P> {
366    fn from(value: P) -> Self {
367        ParsePathError::ParseError(value)
368    }
369}
370
371impl<B: FromStr> FromStr for Path<B> {
372    type Err = ParsePathError<B::Err>;
373
374    fn from_str(s: &str) -> Result<Self, Self::Err> {
375        if !s.contains('/') {
376            return Err(ParsePathError::NoRoot);
377        }
378        // Skip everything preceeding the root slash
379        Ok(Self {
380            path: s
381                .split('/')
382                .skip(1)
383                .filter(|s| !s.is_empty())
384                .map(|s| s.parse::<B>())
385                .collect::<Result<VecDeque<B>, _>>()
386                .map_err(ParsePathError::ParseError)?,
387        })
388    }
389}
390
391impl<B> From<&str> for Path<B>
392where
393    B: FromStr,
394    <B as FromStr>::Err: Dbg,
395{
396    fn from(value: &str) -> Self {
397        value.parse().unwrap()
398    }
399}
400
401impl<A: Into<B>, B> From<Vec<A>> for Path<B> {
402    fn from(value: Vec<A>) -> Self {
403        Self {
404            path: value.into_iter().map(|v| v.into()).collect(),
405        }
406    }
407}
408
409impl<'a, B> IntoIterator for &'a Path<B> {
410    type Item = &'a B;
411
412    type IntoIter = Iter<'a, B>;
413
414    fn into_iter(self) -> Self::IntoIter {
415        self.path.iter()
416    }
417}
418
419impl<'a, B> IntoIterator for &'a mut Path<B> {
420    type Item = &'a mut B;
421
422    type IntoIter = IterMut<'a, B>;
423
424    fn into_iter(self) -> Self::IntoIter {
425        self.path.iter_mut()
426    }
427}
428
429impl<B> IntoIterator for Path<B> {
430    type Item = B;
431
432    type IntoIter = IntoIter<B>;
433
434    fn into_iter(self) -> Self::IntoIter {
435        self.path.into_iter()
436    }
437}
438
439impl<B> FromIterator<B> for Path<B> {
440    fn from_iter<T: IntoIterator<Item = B>>(iter: T) -> Self {
441        Self {
442            path: iter.into_iter().collect(),
443        }
444    }
445}
446
447impl<B: Display> Display for Path<B> {
448    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
449        if self.is_empty() {
450            write!(f, "/")?;
451        } else {
452            //NOTE: multi line B display management?
453            for b in self.path.iter() {
454                write!(f, "/{}", b)?;
455            }
456        }
457        Ok(())
458    }
459}
460
461#[cfg(test)]
462mod tests {
463    use crate::prelude::Tree;
464
465    use super::*;
466
467    fn path() -> Path<i32> {
468        let mut path: Path<i32> = Path::new();
469        path.l(0).l(1).l(2).l(3).l(4).l(5).l(6).l(7).l(8).l(9);
470        path
471    }
472
473    fn tree() -> Tree<i32, i32> {
474        let mut tree = Tree::new();
475        tree.insert(&"/".into(), 75).unwrap();
476        tree.insert(&"/0".into(), 0).unwrap();
477        tree.insert(&"/0/1".into(), 1).unwrap();
478        tree.insert(&"/0/1/2".into(), 2).unwrap();
479        tree.insert(&"/0/1/2/3".into(), 3).unwrap();
480        tree.insert(&"/0/1/2/3/4".into(), 4).unwrap();
481        tree
482    }
483
484    #[test]
485    fn push_pop_get() {
486        let mut path = Path::new();
487        path.push_last(0);
488        path.push_last(1);
489        path.push_last(2);
490        path.l(6).l(7);
491        assert_eq!(path, vec![0, 1, 2, 6, 7].into());
492        path.pop_last();
493        path.pop_last();
494        path.push_last(3);
495        assert_eq!(path, vec![0, 1, 2, 3].into());
496        path.pop_first();
497        assert_eq!(path, vec![1, 2, 3].into());
498        assert_eq!(path.last(), Some(&3));
499        path.push_first(10);
500        assert_eq!(path, vec![10, 1, 2, 3].into());
501        assert_eq!(path.first(), Some(&10));
502    }
503
504    #[test]
505    fn from_to() {
506        let mut path = path();
507        assert_eq!(path, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into());
508        path = path.path_to(5);
509        assert_eq!(path, vec![0, 1, 2, 3, 4].into());
510        path = path.path_from(2);
511        assert_eq!(path, vec![2, 3, 4].into());
512    }
513
514    #[test]
515    fn apply() {
516        let mut path: Path<i32> = Path::new();
517        let mut tree = tree();
518        tree.insert(&"/0/1/5".into(), 5).unwrap();
519        let mut iter = tree.into_iter();
520        path.apply(&iter.next().unwrap());
521        assert_eq!(path, "/".into());
522        path.apply(&iter.next().unwrap());
523        assert_eq!(path, "/0".into());
524        path.apply(&iter.next().unwrap());
525        assert_eq!(path, "/0/1".into());
526        let node = iter.next().unwrap();
527        if *node.branch().unwrap() == 2 {
528            path.apply(&node);
529            assert_eq!(path, "/0/1/2".into());
530            path.apply(&iter.next().unwrap());
531            assert_eq!(path, "/0/1/2/3".into());
532            path.apply(&iter.next().unwrap());
533            assert_eq!(path, "/0/1/2/3/4".into());
534            path.apply(&iter.next().unwrap());
535            assert_eq!(path, "/0/1/5".into());
536        } else {
537            path.apply(&node);
538            assert_eq!(path, "/0/1/5".into());
539            path.apply(&iter.next().unwrap());
540            assert_eq!(path, "/0/1/2".into());
541            path.apply(&iter.next().unwrap());
542            assert_eq!(path, "/0/1/2/3".into());
543            path.apply(&iter.next().unwrap());
544            assert_eq!(path, "/0/1/2/3/4".into());
545        }
546    }
547
548    #[test]
549    fn apply_deref() {
550        let mut path: Path<i32> = Path::new();
551        let mut tree = tree();
552        tree.insert(&"/0/1/5".into(), 5).unwrap();
553        let mut iter = tree.iter();
554        path.apply_deref(&iter.next().unwrap());
555        assert_eq!(path, "/".into());
556        path.apply_deref(&iter.next().unwrap());
557        assert_eq!(path, "/0".into());
558        path.apply_deref(&iter.next().unwrap());
559        assert_eq!(path, "/0/1".into());
560        let node = iter.next().unwrap();
561        if **node.branch().unwrap() == 2 {
562            path.apply_deref(&node);
563            assert_eq!(path, "/0/1/2".into());
564            path.apply_deref(&iter.next().unwrap());
565            assert_eq!(path, "/0/1/2/3".into());
566            path.apply_deref(&iter.next().unwrap());
567            assert_eq!(path, "/0/1/2/3/4".into());
568            path.apply_deref(&iter.next().unwrap());
569            assert_eq!(path, "/0/1/5".into());
570        } else {
571            path.apply_deref(&node);
572            assert_eq!(path, "/0/1/5".into());
573            path.apply_deref(&iter.next().unwrap());
574            assert_eq!(path, "/0/1/2".into());
575            path.apply_deref(&iter.next().unwrap());
576            assert_eq!(path, "/0/1/2/3".into());
577            path.apply_deref(&iter.next().unwrap());
578            assert_eq!(path, "/0/1/2/3/4".into());
579        }
580    }
581
582    #[test]
583    fn apply_with() {
584        let mut path = Path::new();
585        let mut tree = tree();
586        let c = |&&c: &&i32| 10 - c;
587        tree.insert(&"/0/1/5".into(), 5).unwrap();
588        let mut iter = tree.iter();
589        path.apply_with(&iter.next().unwrap(), c);
590        assert_eq!(path, "/".into());
591        path.apply_with(&iter.next().unwrap(), c);
592        assert_eq!(path, "/10".into());
593        path.apply_with(&iter.next().unwrap(), c);
594        assert_eq!(path, "/10/9".into());
595        let node = iter.next().unwrap();
596        if node.branch().unwrap() == &&2 {
597            path.apply_with(&node, c);
598            assert_eq!(path, "/10/9/8".into());
599            path.apply_with(&iter.next().unwrap(), c);
600            assert_eq!(path, "/10/9/8/7".into());
601            path.apply_with(&iter.next().unwrap(), c);
602            assert_eq!(path, "/10/9/8/7/6".into());
603            path.apply_with(&iter.next().unwrap(), c);
604            assert_eq!(path, "/10/9/5".into());
605        } else {
606            path.apply_with(&node, c);
607            assert_eq!(path, "/10/9/5".into());
608            path.apply_with(&iter.next().unwrap(), c);
609            assert_eq!(path, "/10/9/8".into());
610            path.apply_with(&iter.next().unwrap(), c);
611            assert_eq!(path, "/10/9/8/7".into());
612            path.apply_with(&iter.next().unwrap(), c);
613            assert_eq!(path, "/10/9/8/7/6".into());
614        }
615    }
616
617    #[test]
618    fn iter() {
619        for (v, &b) in path().iter().enumerate() {
620            assert_eq!(v as i32, b);
621        }
622    }
623}
nb_tree/path.rs

nb_tree/
path.rs
