nb-tree 0.2.0-alpha01

//! `Path<B>`s are arrays of branches of type `B`.
//! They are used to designate a position in a [`Tree<N, B>`].
//!
//!
//!
//!
//!
//! [`Tree`]: crate::tree::Tree
//! [`Tree<N, B>`]: crate::tree::Tree
//! [`TreeNode`]: crate::tree::node::TreeNode

use std::collections::vec_deque::{Iter, IterMut};
use std::collections::{vec_deque::IntoIter, VecDeque};
use std::fmt::{Debug as Dbg, Display};
use std::hash::Hash;
use std::ops::{Deref, Index, IndexMut};
use std::str::FromStr;

use crate::prelude::iter::depth::Traversal;

/// Path branch index
pub type PathIDX = usize;

/// A path to a [`Tree`] node.
///
/// A `Path` is a collection of branches to follow to get to the desired node.
/// An empty `Path` represents the root of the [`Tree`].
///
/// # Examples
/// ```rust
/// use nb_tree::{path, prelude::{Tree, Path}};
/// let mut tree = Tree::new();
/// // Paths from string litterals, vectors, or manually built
/// let path_d: Path<String> = "/b/d".into();
/// let path_e: Path<String> = vec!["a", "c", "e"].into();
/// let path_g: Path<String> = path!["a", "g"];
/// let mut path_f = Path::new();
/// path_f.l("b").l("f");
/// // Use paths to insert data
/// tree.i("/", 0)
///     .i("/a", 1)
///     .i("/b", 2)
///     .i("/a/c", 3)
///     .i(path_d, 4)
///     .i(path_e, 5)
///     .i(path_f, 6)
///     .i(path_g, 7);
///
/// // Use paths to retrieve data
/// assert_eq!(tree.get(&"/a/c".into()), Ok(&3));
///
/// // Use paths to remove data
/// assert_eq!(tree.len(), 8);
/// assert_eq!(tree.remove_subtree(&"/a".into()), Ok(()));
/// // The whole "/a/[c/e, g]" subtree is removed, removing all nodes below it too
/// assert_eq!(tree.len(), 4);
/// ```
///
/// [`Tree`]: crate::tree::Tree
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Path<B> {
    /// Array of branches.
    path: VecDeque<B>,
}

impl<B> Default for Path<B> {
    fn default() -> Self {
        Self {
            path: VecDeque::default(),
        }
    }
}

impl<B: Clone> Clone for Path<B> {
    fn clone(&self) -> Self {
        Self {
            path: self.path.clone(),
        }
    }
}

impl<B> Path<B> {
    /// Creates a new empty `Path`.
    pub fn new() -> Self {
        Self {
            path: VecDeque::new(),
        }
    }

    /// Creates a new empty `Path`.
    pub fn with(root: B) -> Self {
        let mut path = VecDeque::new();
        path.push_back(root);
        Self { path }
    }

    /// Removes the first branch of the `Path`.
    pub fn pop_first(&mut self) -> Option<B> {
        self.path.pop_front()
    }

    /// Removes the last branch of the `Path`.
    pub fn pop_last(&mut self) -> Option<B> {
        self.path.pop_back()
    }

    /// Adds `branch` at the end of the `Path`.
    pub fn push_last(&mut self, branch: B) {
        self.path.push_back(branch);
    }

    /// Appends all `branches` at the end of the `Path`.
    pub fn append(&mut self, mut branches: Path<B>) {
        self.path.append(&mut branches.path);
    }

    /// Adds `branch` at the end of the `Path`.
    ///
    /// Calls can be chained.
    pub fn l(&mut self, branch: impl Into<B>) -> &mut Self {
        self.path.push_back(branch.into());
        self
    }

    /// Adds `branch` at the start of the `Path`.
    pub fn push_first(&mut self, branch: B) {
        self.path.push_front(branch);
    }

    /// Returns the last branch of the `Path`.
    ///
    /// If the `Path` is empty, None is returned.
    pub fn last(&self) -> Option<&B> {
        self.path.back()
    }

    /// Returns the first branch of the `Path`.
    ///
    /// If the `Path` is empty, None is returned.
    pub fn first(&self) -> Option<&B> {
        self.path.front()
    }

    /// Returns true if the `Path` is empty, false otherwise.
    pub fn is_empty(&self) -> bool {
        self.path.is_empty()
    }

    /// Returns the length of the `Path`.
    pub fn len(&self) -> usize {
        self.path.len()
    }

    /// Removes `n` branches from the end of the Path.
    pub fn truncate_end(&mut self, n: usize) {
        if self.path.len() <= n {
            self.path.clear();
        } else {
            self.path.truncate(self.path.len() - n);
        }
    }

    /// Removes `n` branches from the start of the Path.
    pub fn truncate_start(&mut self, n: usize) {
        if self.path.len() <= n {
            self.path.clear();
        } else {
            self.path.rotate_left(n);
            self.path.truncate(self.path.len() - n);
        }
    }

    /// Clears the Path.
    pub fn clear(&mut self) {
        self.path.clear()
    }

    /// Traverses the Tree nodes depth first.
    ///
    /// The children are visited in arbitrary order.
    pub fn iter(&self) -> std::collections::vec_deque::Iter<'_, B> {
        self.path.iter()
    }

    pub fn range<R>(&self, range: R) -> std::collections::vec_deque::Iter<'_, B>
    where
        R: std::ops::RangeBounds<usize>,
    {
        self.path.range(range)
    }
}

impl<B> Index<PathIDX> for Path<B> {
    type Output = B;

    fn index(&self, index: PathIDX) -> &Self::Output {
        &self.path[index]
    }
}

impl<B> IndexMut<PathIDX> for Path<B> {
    fn index_mut(&mut self, index: PathIDX) -> &mut Self::Output {
        &mut self.path[index]
    }
}

impl<B> Path<B>
where
    B: Clone,
{
    /// Creates a copy stopping at the given index (excluded).
    pub fn path_to(&self, path_idx: PathIDX) -> Path<B> {
        Self {
            path: self.path.range(..path_idx).cloned().collect(),
        }
    }

    /// Creates a copy starting at the given index (included).
    pub fn path_from(&self, path_idx: PathIDX) -> Path<B> {
        Self {
            path: self.path.range(path_idx..).cloned().collect(),
        }
    }

    /// Follows the given [`DepthFirstTraversalNode`], moving up the `Path` and going down a branch.
    ///
    /// The branch type can be something else than B, as long as it can be converted to it.
    /// # Examples
    /// ```rust
    /// use nb_tree::prelude::{Tree, Path};
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0).i("/a", 1).i("/a/b", 2);
    /// let mut iter = tree.into_iter();
    /// let mut path: Path<String> = Path::new();
    /// path.apply(&iter.next().unwrap());
    /// assert_eq!(path, "/".into());
    /// path.apply(&iter.next().unwrap());
    /// assert_eq!(path, "/a".into());
    /// path.apply(&iter.next().unwrap());
    /// assert_eq!(path, "/a/b".into());
    /// ```
    pub fn apply<N>(&mut self, node: &Traversal<N, B>) -> bool {
        if let Traversal::Step {
            up,
            branch,
            data: _,
        } = node
        {
            assert!(self.len() >= *up, "Moving up out of the tree");
            // Move up
            self.truncate_end(*up);
            // Move down
            self.push_last(branch.clone());
            true
        } else {
            false
        }
    }

    /// Dereferences the branch in `node` and applies it like [`apply()`].
    ///
    /// [`apply()`]: Self::apply()
    pub fn apply_deref<N, C>(&mut self, node: &Traversal<N, C>) -> bool
    where
        C: Deref<Target = B>,
    {
        if let Traversal::Step {
            up,
            branch,
            data: _,
        } = node
        {
            assert!(self.len() >= *up, "Moving up out of the tree");
            // Move up
            self.truncate_end(*up);
            // Move down
            self.push_last(branch.deref().clone());
            true
        } else {
            false
        }
    }

    /// Follows the given [`DepthFirstTraversalNode`] like [`apply()`] transformed by the given `op`.
    ///
    /// # Examples
    /// ```rust
    /// use nb_tree::{path, prelude::{Tree, Path}};
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0).i("/a", 1).i("/a/b", 2);
    /// let mut iter = tree.iter();
    /// let mut path = Path::new();
    /// let mut e = 0;
    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
    /// e += 1;
    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
    /// assert_eq!(path, path![("a".into(), 1)]);
    /// e += 1;
    /// path.apply_with(&iter.next().unwrap(), |&c: &&String| (c.clone(), e.clone()));
    /// assert_eq!(path, path![("a".into(), 1), ("b".into(), 2)]);
    /// ```
    ///
    /// [`apply()`]: Self::apply()
    pub fn apply_with<N, C>(&mut self, node: &Traversal<N, C>, op: impl Fn(&C) -> B) -> bool {
        if let Traversal::Step {
            up,
            branch,
            data: _,
        } = node
        {
            assert!(self.len() >= *up, "Moving up out of the tree");
            // Move up
            self.truncate_end(*up);
            // Move down
            self.push_last(op(branch));
            true
        } else {
            false
        }
    }
}

impl<B> Path<B>
where
    B: Clone + Eq,
{
    pub fn offshoot_from(&self, branch: Self) -> Path<B> {
        let mut iter = self.iter().zip(branch.iter());
        let mut next = iter.next();
        while next.and_then(|(sb, ob)| (sb == ob).then_some(())).is_some() {
            next = iter.next();
        }

        if let Some((root, _)) = next {
            iter.fold(Path::with(root.clone()), |mut ph, (b, _)| {
                ph.push_last(b.clone());
                ph
            })
        } else {
            Path::new()
        }
    }
}

impl<B> Path<&B>
where
    B: Clone,
{
    pub fn branches_to_owned(&self) -> Path<B> {
        Path {
            path: self.path.iter().map(|&i| i.clone()).collect(),
        }
    }
}

/// Error describing a failed attempt at parsing a `Path`.
#[derive(Debug)]
pub enum ParsePathError<P> {
    /// The given value to parse does not contain any root.
    NoRoot,
    /// The parsing failed.
    ParseError(P),
}

impl<P> From<P> for ParsePathError<P> {
    fn from(value: P) -> Self {
        ParsePathError::ParseError(value)
    }
}

impl<B: FromStr> FromStr for Path<B> {
    type Err = ParsePathError<B::Err>;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if !s.contains('/') {
            return Err(ParsePathError::NoRoot);
        }
        // Skip everything preceeding the root slash
        Ok(Self {
            path: s
                .split('/')
                .skip(1)
                .filter(|s| !s.is_empty())
                .map(|s| s.parse::<B>())
                .collect::<Result<VecDeque<B>, _>>()
                .map_err(ParsePathError::ParseError)?,
        })
    }
}

impl<B> From<&str> for Path<B>
where
    B: FromStr,
    <B as FromStr>::Err: Dbg,
{
    fn from(value: &str) -> Self {
        value.parse().unwrap()
    }
}

impl<A: Into<B>, B> From<Vec<A>> for Path<B> {
    fn from(value: Vec<A>) -> Self {
        Self {
            path: value.into_iter().map(|v| v.into()).collect(),
        }
    }
}

impl<'a, B> IntoIterator for &'a Path<B> {
    type Item = &'a B;

    type IntoIter = Iter<'a, B>;

    fn into_iter(self) -> Self::IntoIter {
        self.path.iter()
    }
}

impl<'a, B> IntoIterator for &'a mut Path<B> {
    type Item = &'a mut B;

    type IntoIter = IterMut<'a, B>;

    fn into_iter(self) -> Self::IntoIter {
        self.path.iter_mut()
    }
}

impl<B> IntoIterator for Path<B> {
    type Item = B;

    type IntoIter = IntoIter<B>;

    fn into_iter(self) -> Self::IntoIter {
        self.path.into_iter()
    }
}

impl<B> FromIterator<B> for Path<B> {
    fn from_iter<T: IntoIterator<Item = B>>(iter: T) -> Self {
        Self {
            path: iter.into_iter().collect(),
        }
    }
}

impl<B: Display> Display for Path<B> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_empty() {
            write!(f, "/")?;
        } else {
            //NOTE: multi line B display management?
            for b in self.path.iter() {
                write!(f, "/{}", b)?;
            }
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use crate::prelude::Tree;

    use super::*;

    fn path() -> Path<i32> {
        let mut path: Path<i32> = Path::new();
        path.l(0).l(1).l(2).l(3).l(4).l(5).l(6).l(7).l(8).l(9);
        path
    }

    fn tree() -> Tree<i32, i32> {
        let mut tree = Tree::new();
        tree.insert(&"/".into(), 75).unwrap();
        tree.insert(&"/0".into(), 0).unwrap();
        tree.insert(&"/0/1".into(), 1).unwrap();
        tree.insert(&"/0/1/2".into(), 2).unwrap();
        tree.insert(&"/0/1/2/3".into(), 3).unwrap();
        tree.insert(&"/0/1/2/3/4".into(), 4).unwrap();
        tree
    }

    #[test]
    fn push_pop_get() {
        let mut path = Path::new();
        path.push_last(0);
        path.push_last(1);
        path.push_last(2);
        path.l(6).l(7);
        assert_eq!(path, vec![0, 1, 2, 6, 7].into());
        path.pop_last();
        path.pop_last();
        path.push_last(3);
        assert_eq!(path, vec![0, 1, 2, 3].into());
        path.pop_first();
        assert_eq!(path, vec![1, 2, 3].into());
        assert_eq!(path.last(), Some(&3));
        path.push_first(10);
        assert_eq!(path, vec![10, 1, 2, 3].into());
        assert_eq!(path.first(), Some(&10));
    }

    #[test]
    fn from_to() {
        let mut path = path();
        assert_eq!(path, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9].into());
        path = path.path_to(5);
        assert_eq!(path, vec![0, 1, 2, 3, 4].into());
        path = path.path_from(2);
        assert_eq!(path, vec![2, 3, 4].into());
    }

    #[test]
    fn apply() {
        let mut path: Path<i32> = Path::new();
        let mut tree = tree();
        tree.insert(&"/0/1/5".into(), 5).unwrap();
        let mut iter = tree.into_iter();
        path.apply(&iter.next().unwrap());
        assert_eq!(path, "/".into());
        path.apply(&iter.next().unwrap());
        assert_eq!(path, "/0".into());
        path.apply(&iter.next().unwrap());
        assert_eq!(path, "/0/1".into());
        let node = iter.next().unwrap();
        if *node.branch().unwrap() == 2 {
            path.apply(&node);
            assert_eq!(path, "/0/1/2".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3/4".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/5".into());
        } else {
            path.apply(&node);
            assert_eq!(path, "/0/1/5".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3".into());
            path.apply(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3/4".into());
        }
    }

    #[test]
    fn apply_deref() {
        let mut path: Path<i32> = Path::new();
        let mut tree = tree();
        tree.insert(&"/0/1/5".into(), 5).unwrap();
        let mut iter = tree.iter();
        path.apply_deref(&iter.next().unwrap());
        assert_eq!(path, "/".into());
        path.apply_deref(&iter.next().unwrap());
        assert_eq!(path, "/0".into());
        path.apply_deref(&iter.next().unwrap());
        assert_eq!(path, "/0/1".into());
        let node = iter.next().unwrap();
        if **node.branch().unwrap() == 2 {
            path.apply_deref(&node);
            assert_eq!(path, "/0/1/2".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3/4".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/5".into());
        } else {
            path.apply_deref(&node);
            assert_eq!(path, "/0/1/5".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3".into());
            path.apply_deref(&iter.next().unwrap());
            assert_eq!(path, "/0/1/2/3/4".into());
        }
    }

    #[test]
    fn apply_with() {
        let mut path = Path::new();
        let mut tree = tree();
        let c = |&&c: &&i32| 10 - c;
        tree.insert(&"/0/1/5".into(), 5).unwrap();
        let mut iter = tree.iter();
        path.apply_with(&iter.next().unwrap(), c);
        assert_eq!(path, "/".into());
        path.apply_with(&iter.next().unwrap(), c);
        assert_eq!(path, "/10".into());
        path.apply_with(&iter.next().unwrap(), c);
        assert_eq!(path, "/10/9".into());
        let node = iter.next().unwrap();
        if node.branch().unwrap() == &&2 {
            path.apply_with(&node, c);
            assert_eq!(path, "/10/9/8".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/8/7".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/8/7/6".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/5".into());
        } else {
            path.apply_with(&node, c);
            assert_eq!(path, "/10/9/5".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/8".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/8/7".into());
            path.apply_with(&iter.next().unwrap(), c);
            assert_eq!(path, "/10/9/8/7/6".into());
        }
    }

    #[test]
    fn iter() {
        for (v, &b) in path().iter().enumerate() {
            assert_eq!(v as i32, b);
        }
    }
}