pub mod default;
pub mod diff;
pub mod iter;
pub mod node;
pub mod sub_tree;

use std::mem;
use std::{fmt::Debug, hash::Hash, ops::Index};

use crate::path::PathIDX;

use self::node::TreeNode;

use super::path::Path;

macro_rules! ok_or_return {
    ( $e:expr, $r:expr ) => {
        match $e {
            Some(x) => x,
            None => return $r,
        }
    };
}

type NodeIDX = usize;

/// Tree structure with generic node and branch data
/// Each node is linked to its children via branches.
/// # Building trees
/// Trees can be built in several ways using (chainable) insertion methods.
/// ## Inserting data
/// Data can be added or overwritten at a specified location via [insert].
/// ```rust
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<usize, String> = Tree::new();
/// // Insert at root (None reflects the creation of a new node)
/// assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
/// assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
/// assert_eq!(tree.insert(&"/b".into(), 2), Ok(None));
/// assert_eq!(tree.insert(&"/b/c".into(), 3), Ok(None));
/// // One can't insert below an inexistent node with [insert]
/// // Use [insert_extend] for this
/// assert_eq!(tree.insert(&"/a/x/z".into(), 12), Err("/a".into()));
/// ```
/// A shorthand exists for chaining insertions
/// ```rust
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<usize, String> = Tree::new();
/// tree.i("/", 0)
///     .i("/a", 1)
///     .i("/a/b", 2)
///     .i("/a/c", 3)
///     .i("/d", 4);
/// ```
/// Note that [i] panics if the insertion fails.
///
/// For node data types that are [Default], [insert_extend] can be used to build
/// intermediary nodes with default data between the last existing node of the
/// given [Path] in the [Tree] and the one to insert
/// ```rust
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<usize, String> = Tree::new();
/// tree.insert_extend(&"/a/b/c/x/y/z".into(), 1000000);
/// assert_eq!(tree.values().len(), 7);
/// ```
/// [insert_extend] returns the old value if any.
/// If the node did not exist, it returns the default value of the node type.
/// ## Removing data
/// Subtrees can be removed from a tree.
/// [remove_sub_tree] removes the subtree whom root is pointed at by the given [Path]
/// ```rust
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<usize, String> = Tree::new();
/// tree.i("/", 0)
///     .i("/a", 1)
///     .i("/a/b", 2);
/// tree.remove_sub_tree(&"/a".into());
/// assert_eq!(tree.values().len(), 1);
/// ```
/// [remove_sub_tree_trim] also trims out parent nodes containing the default value
/// ```rust
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<Option<usize>, String> = Tree::new();
/// tree.insert(&"a".into(), Some(1));
/// tree.insert_extend(&"/a/b/c/i/j/k/x/y/z".into(), Some(1000000));
/// // [remove_sub_tree] only removes the subtree
/// tree.remove_sub_tree(&"/a/b/c/i/j/k".into());
/// assert_eq!(tree.values().len(), 7);
/// // [remove_sub_tree_trim] also removes the parent nodes containing `None`
/// tree.remove_sub_tree_trim(&"/a/b/c".into());
/// // Only the node at "/a" remains, containing non default data
/// assert_eq!(tree.values().len(), 1);
/// ```
/// # Diffing and applying Diffs
/// Tree differentials can be applied to a tree via [apply] and [apply_extend].
/// Differentials (diffs) contain the difference between two trees.
/// This can be useful to save differences between two trees and use them
/// as patches for instance.
///
/// Diffs are trees with for each node a potential Before and Now value,
/// representing the values of two Before and Now trees compared
/// against each other.
/// Their type is `Tree<(Option<N>, Option<N>), B>`
/// where each Before and Now N values are wrapped in an Option to represent the
/// potential absence of an equivalent node in the other tree.
/// They form a tuple wrapped in an other Option which allows for diffs
/// together in a tuple

/// # Examples
/// # Data structure
#[derive(Debug, Default)]
pub struct Tree<N, B>
where
    N: Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    /// The first node is the tree's root
    /// Nodes are added and removed through `insert()` and `remove()` only
    nodes: Vec<TreeNode<N, B>>,
    /// Nodes removed from the tree
    /// These indexes will be reused later upon inserting new nodes via `insert()`, and `remove()` adds them to the vec
    removed: Vec<NodeIDX>,
}

pub type TreeBuilder<N, B> = Tree<Option<N>, B>;
pub type DiffTree<N, B> = Tree<(Option<N>, Option<N>), B>;

impl<N, B> Clone for Tree<N, B>
where
    N: Clone + Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    fn clone(&self) -> Self {
        Self {
            nodes: self.nodes.clone(),
            removed: self.removed.clone(),
        }
    }
}
impl<N, B> Index<&Path<B>> for Tree<N, B>
where
    N: Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    type Output = N;

    fn index(&self, index: &Path<B>) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl<N, B> PartialEq for Tree<N, B>
where
    N: Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    fn eq(&self, other: &Self) -> bool {
        (self.is_empty() && other.is_empty())
            || (!self.is_empty()
                && !other.is_empty()
                && self.is_sub_tree_eq(self.get_root_idx(), other, other.get_root_idx()))
    }
}

impl<N, B> Eq for Tree<N, B>
where
    N: Debug + PartialEq + Eq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
}

impl<N, B> Tree<N, B>
where
    N: Debug + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    /// Creates a new empty tree
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            removed: Default::default(),
        }
    }

    /// Returns the index of the node pointed to by the given [path]
    /// If the node doesn't exist, it returns the index of the closest existing node in the tree and the index of the inexistent child in [path].
    /// If the tree is empty, None is returned.
    fn get_idx(
        &self,
        path: &Path<B>,
        from_idx: Option<NodeIDX>,
    ) -> Result<NodeIDX, Option<(NodeIDX, PathIDX)>> {
        if self.is_empty() {
            return Err(None);
        }
        path.iter().enumerate().try_fold(
            from_idx.unwrap_or(self.get_root_idx()),
            |node_idx, (path_idx, branch)| {
                self.nodes[node_idx]
                    .children
                    .get(branch)
                    .cloned()
                    .ok_or(Some((node_idx, path_idx)))
            },
        )
    }

    /// Returns a reference to the value of the node at the given [path]
    pub fn get(&self, path: &Path<B>) -> Result<&N, Option<Path<B>>> {
        Ok(&self.nodes[self
            .get_idx(path, None)
            .map_err(|r| r.map(|(_, v)| path.path_to(v)))?]
        .value)
    }

    pub fn get_root(&self) -> Option<&N> {
        if self.is_empty() {
            None
        } else {
            Some(&self.nodes[0].value)
        }
    }

    /// Protection against direct root node access (self.nodes[0]) although it got removed
    fn get_root_idx(&self) -> NodeIDX {
        debug_assert!(!self.is_empty());
        0
    }

    /// Returns a vector of the index of every node along the given [path]
    /// If a node doesn't exist, the vector up until this node is returned as well as the index of the inexistent child in [path].
    /// If the tree is empty, None is returned.
    fn get_path_idxs(&self, path: &Path<B>) -> Result<Vec<NodeIDX>, Option<(Vec<NodeIDX>, usize)>> {
        if self.is_empty() {
            return Err(None);
        }
        path.iter().enumerate().try_fold(
            vec![self.get_root_idx()],
            |mut node_idx, (path_idx, branch)| {
                node_idx.push(
                    self.nodes[*node_idx.last().unwrap()]
                        .children
                        .get(&branch)
                        .cloned()
                        //NOTE: No way to do without the cloning? (E0505)
                        .ok_or(Some((node_idx.clone(), path_idx)))?,
                );
                Ok(node_idx)
            },
        )
    }

    /// # Warning
    /// It does not check for index validity.
    fn is_sub_tree_eq(&self, idx_s: usize, o: &Self, idx_o: usize) -> bool {
        let ns = &self.nodes[idx_s];
        let no = &o.nodes[idx_o];
        ns.value == no.value
            && ns.children.len() == no.children.len()
            && ns
                .children
                .keys()
                .find(|attr| {
                    !self.is_sub_tree_eq(
                        *ok_or_return!(ns.children.get(attr), false),
                        o,
                        *ok_or_return!(no.children.get(attr), false),
                    )
                })
                .is_none()
    }

    // pub fn navigate() -> TreeNavigation {
    //     (up, down(child), get(path))
    // }

    /// Inserts a value at the given [path]
    /// Returns the existing value if any.
    /// Insertions can be done on any existing node ([path] points to an existing node) or on children of existing nodes ([path] points to an inexistent immediate child of an existing node).
    /// Insertions cannot be done if [path] points to a node further away from the existing tree as it cannot close the gap between the last existing node and the new one to insert.
    /// In this case the operation will fail and the [Path] to the closest existing node will be returned.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<_, String> = Tree::new();
    /// // Set root
    /// assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
    /// // Append node
    /// assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
    /// // Overwrite existing node
    /// assert_eq!(tree.insert(&"/a".into(), 2), Ok(Some(1)));
    /// // Leave tree
    /// assert_eq!(tree.insert(&"/a/b/c".into(), 2), Err("/a".into()));
    /// ```
    pub fn insert(&mut self, path: &Path<B>, value: N) -> Result<Option<N>, Path<B>> {
        let mut path = path.clone();
        if let Some(child) = path.pop_leaf() {
            self.insert_at(
                self.get_idx(&path, None)
                    .map_err(|r| path.path_to(r.unwrap_or((0, 0)).1))?,
                child,
                value,
            )
            .map(|r| r.err())
        } else {
            Ok(self.insert_root(value))
        }
    }

    pub fn insert_root(&mut self, value: N) -> Option<N> {
        if self.nodes.is_empty() {
            // Initialize the tree with a root node
            self.nodes.push(value.into());
            None
        } else if self.removed.last() == Some(&0) {
            // Reinsert the removed node
            self.removed.pop();
            self.removed
                .append(&mut self.nodes[0].children.values().cloned().collect());
            Some(mem::replace(&mut self.nodes[0], value.into()).value)
        } else {
            // The root should not have been removed
            debug_assert!(!self.removed.contains(&0));
            // Replace the current value
            Some(mem::replace(&mut self.nodes[0].value, value))
        }
    }

    /// Inserts a value as the [child] node of the given parent
    /// # Warning
    /// Does not check the validity of [parent_idx].
    fn insert_at(
        &mut self,
        parent_idx: NodeIDX,
        child: B,
        value: N,
    ) -> Result<Result<NodeIDX, N>, Path<B>> {
        // Child exists?
        if let Some(child_idx) = self.nodes[parent_idx].children.get(&child).cloned() {
            Ok(Err(mem::replace(&mut self.nodes[child_idx].value, value)))
        } else {
            // Get a node
            let idx = if let Some(idx) = self.removed.pop() {
                // Use a removed one
                self.removed
                    .append(&mut self.nodes[idx].children.values().cloned().collect());
                self.nodes[idx] = TreeNode::from(value);
                self.nodes[parent_idx].children.insert(child, idx);
                idx
            } else {
                let idx = self.nodes.len();
                // Extend the vec
                self.nodes.push(TreeNode::from(value));
                //NOTE: Any way to do without the variable? (E0502)
                self.nodes[parent_idx].children.insert(child, idx);
                idx
            };

            Ok(Ok(idx))
        }
    }

    /// Chainable insertion
    /// Calls `insert` and returns a mutable reference to self
    /// # Panics
    /// Panics if the insertion fails
    pub fn i(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self {
        let ph: Path<B> = path.into();
        self.insert(&ph, value)
            .expect(&format!("Could not insert into the tree at {:?}", &ph));
        self
    }

    /// Removes the sub tree at the given [path] from the tree
    /// If the root node is not found, it returns the path to the closest existing node, or None if the tree is empty.
    /// # Examples
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree1: Tree<_, String> = Tree::new();
    /// tree1.insert(&"/".into(), 0);
    /// tree1.insert(&"/a".into(), 1);
    /// tree1.insert(&"/a".into(), 2);
    /// tree1.insert(&"/b".into(), 3);
    /// let mut tree2 = tree1.clone();
    ///
    /// // Add a branch to tree2
    /// tree2.insert(&"/c".into(), 4);
    /// tree2.insert(&"/c/d".into(), 5);
    ///
    /// // Remove the branch
    /// tree2.remove_sub_tree(&"/c".into());
    /// assert_eq!(tree1, tree2);
    /// ```
    pub fn remove_sub_tree(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>> {
        let mut path = path.clone();
        if self.is_empty() {
            Err(None)
        } else if let Some(child) = path.pop_leaf() {
            // Remove a node
            let parent_idx = self
                .get_idx(&path, None)
                .map_err(|r| r.map(|(_, v)| path.path_to(v)))?;
            self.remove_sub_tree_at(parent_idx, child)
                .map(|_| ())
                .ok_or(Some(path))
        } else {
            // Root is being removed
            self.nodes.clear();
            self.removed.clear();
            Ok(())
        }
    }
    /// Removes the sub tree at the [child] of the given parent node
    /// # Warning
    /// Does not check [parent_idx]'s validity
    fn remove_sub_tree_at(&mut self, parent_idx: NodeIDX, child: B) -> Option<()> {
        let idx = self.nodes[parent_idx].children.remove(&child)?;
        self.removed.push(idx);
        Some(())
    }

    /// Returns a vector of all values and their position relative to each other
    /// The first value of the tuple is the root item's, followed by a vector of [TreeTraversal] items.
    /// Each one of the vector's items contains the value of the described node as well as its position relative to the previous node.
    pub fn flat<'a>(&'a self) -> Option<(&'a N, Vec<TreeTraversalNode<'a, N, B>>)> {
        fn flat_rec<'a, N, B>(
            up: usize,
            nodes: &'a Vec<TreeNode<N, B>>,
            idx: usize,
            branch: &'a B,
        ) -> (Vec<TreeTraversalNode<'a, N, B>>, usize)
        where
            N: Debug,
            B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
        {
            let mut f = nodes[idx].children.iter().fold(
                (
                    vec![TreeTraversalNode {
                        up,
                        branch,
                        value: &nodes[idx].value,
                        idx,
                    }],
                    0,
                ),
                |(mut flat, child_up), (b, child_idx)| {
                    let (mut sub_flat, new_up) = flat_rec(child_up, nodes, *child_idx, b);
                    flat.append(&mut sub_flat);
                    (flat, new_up)
                },
            );
            f.1 += 1;
            f
        }

        if self.is_empty() {
            None
        } else {
            Some((
                &self.nodes[0].value,
                self.nodes[0]
                    .children
                    .iter()
                    .fold((Vec::new(), 0), |(mut flat, child_up), (b, child_idx)| {
                        let (mut sub_flat, new_up) = flat_rec(child_up, &self.nodes, *child_idx, b);
                        flat.append(&mut sub_flat);
                        (flat, new_up)
                    })
                    .0,
            ))
        }
    }

    /*
    pub fn move_sub_tree(
        &mut self,
        from: Path<B>,
        to: Path<B>,
        destination: Option<&mut Tree<N, B>>,
    ) -> Result<(), Path<B>> {
        let path_idxs = self
            .get_path_idxs(path)
            .map_err(|(_, idx)| path.path_to(idx))?;

        //remove children
        self.move_sub_tree(path_idxs.pop().unwrap());
        let mut attr = path.pop_leaf();

        //remove empty parent nodes
        while !path_idxs.is_empty() && self.nodes[path_idxs.last()].children.len() == 1 {
            self.nodes.remove(path_idxs.pop().unwrap());
            attr = path.pop_leaf();
        }

        //remove child link of parent
        if !path_idxs.is_empty() {
            self.nodes[path_idxs].children.remove(attr);
        }
        Ok(())
    }*/

    //fn move_sub_tree(&mut self, from: NodeIDX, to: NodeIDX, tree: &mut Tree<N, B>) {
    //      tree.nodes[to].children.insert(attr, tree.nodes.len());
    //      tree.nodes.push(TreeNode {})
    //      self.remove_sub_tree(idx, );

    /// Returns the index of the node at the given [path]
    /// If the node doesn't exist, it returns the index of the closest existing node in the tree and the index of the inexistent child in [path].
    /// If the tree is empty, None is returned.

    //TODO opti: use idx to iter
    /// Applies the differential to the tree without checking its validity beforehand
    ///
    /// # Panics
    /// If a targetted node's parent does not exist upon change or addition
    fn overwrite(&mut self, diff: DiffTree<N, B>) {
        for (ph, d) in diff {
            if let Some(now) = d.1 {
                // New or change node
                // Panics if the parent is inexistent
                self.insert(&ph, now).unwrap();
            } else if d.0.is_some() {
                // Remove node if it exists
                let _ = self.remove_sub_tree(&ph);
            }
        }
    }

    /// Applies the differential to the tree if it is valid
    pub fn apply(&mut self, diff: DiffTree<N, B>) -> Result<(), Path<B>> {
        // Diff validity check
        for (ph, d) in diff.iter() {
            if let Some(before) = &d.0 {
                // Check case: Change or delete node
                // Corresponding node in tree?
                let node_idx = self
                    .get_idx(&ph, None)
                    //TODO: Even when empty?
                    .map_err(|r| ph.path_to(r.unwrap_or((0, 0)).1))?;
                // Diff corresponds to node value?
                if &self.nodes[node_idx].value != before {
                    return Err(ph);
                }
            } else if d.1.is_some() {
                // Check case: New node
                let mut ph = ph.clone();
                ph.pop_leaf();
                self.get_idx(&ph, None)
                    .map_err(|r| ph.path_to(r.unwrap_or((0, 0)).1))?;
            }
        }

        // Apply diff
        self.overwrite(diff);
        Ok(())
    }
    /*
        pub fn values(&self) -> Vec<&N> {
            if let Some(n) = self.get(0) {
                let values = Vec::new();
                values.push(n);
                values.append(self.iter().map(|(_, value)| value).collect());
                values
            } else {
                Default::default()
            }
        }
    */
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty() || self.removed.last() == Some(&0)
    }
}

impl<N, B> Tree<N, B>
where
    N: Debug + Clone + PartialEq,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    pub fn diff(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
        // Check if one of the trees is empty
        let mut diff = DiffTree::new();
        if other.nodes.is_empty() {
            diff.mirror_sub_tree(self, &Path::new(), false);
            return diff;
        }
        if self.nodes.is_empty() {
            diff.mirror_sub_tree(other, &Path::new(), true);
            return diff;
        }

        // Set the root node
        if self.nodes[0].value == other.nodes[0].value {
            // values are identical, no difference to save
            diff.insert_root((None, None));
        } else {
            diff.insert_root((
                Some(self.nodes[0].value.clone()),
                Some(other.nodes[0].value.clone()),
            ));
        }

        // Check and set the child nodes
        self.diff_rec(&mut diff, other, 0, 0, 0);
        diff
    }

    fn diff_rec(
        &self,
        diff: &mut DiffTree<N, B>,
        other: &Tree<N, B>,
        idx_d: NodeIDX,
        idx_s: NodeIDX,
        idx_o: NodeIDX,
    ) {
        let mut branches_o = other.nodes[idx_o].children.clone();
        // Get children of self
        for (branch, &c_idx_s) in &self.nodes[idx_s].children {
            // Get corresponding child in other
            if let Some(c_idx_o) = branches_o.remove(branch) {
                // Create a child node in diff
                let c_idx_d = diff
                    .insert_at(
                        idx_d,
                        branch.clone(),
                        (
                            Some(self.nodes[c_idx_s].value.clone()),
                            Some(other.nodes[c_idx_o].value.clone()),
                        ),
                    )
                    .unwrap()
                    .unwrap();
                self.diff_rec(diff, other, c_idx_d, c_idx_s, c_idx_o);
            } else {
                // Create a child node in diff
                let c_idx_d = diff
                    .insert_at(idx_d, branch.clone(), Default::default())
                    .unwrap()
                    .unwrap();
                diff.mirror_sub_tree_at(self, c_idx_d, c_idx_s, false);
            }
        }
        // Get remaining children of other
        for (branch, c_idx_o) in branches_o {
            // Create a child node in diff
            let c_idx_d = diff
                .insert_at(idx_d, branch.clone(), Default::default())
                .unwrap()
                .unwrap();
            diff.mirror_sub_tree_at(other, c_idx_d, c_idx_o, true);
        }
    }
    /*
        let (rs, node_s) = if let Some((r, nodes)) = self.flat() {
            (r, nodes)
        } else {
            let diff = DiffTree::new();
            diff.;
            return diff;
        };

        let (ro, node_o) = if let Some((r, nodes)) = other.flat() {
            (r, nodes)
        } else {
            return DiffTree::new()
        };

        for b in self.flat() {
            self.nodes[]
        }
        todo!()
    }*/
    pub fn zip(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
        let mut diff = DiffTree::new();
        diff.mirror_sub_tree(&self, &Path::new(), false);
        diff.mirror_sub_tree(other, &Path::new(), true);
        diff
    }
}

/// Describes a node's value and position relatively
#[derive(Debug)]
pub struct TreeTraversalNode<'a, N, B>
where
    N: Debug,
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
{
    /// How much higher the parent of the described node is compared to the previous node
    pub up: usize,
    /// The branch leading from the parent to the described node
    pub branch: &'a B,
    /// The node's value
    pub value: &'a N,
    /// The node's index
    idx: NodeIDX,
}