nb-tree 0.2.0-alpha01

use std::{collections::HashMap, hash::Hash, marker::PhantomData, mem};
use tracing::{debug, error, trace, trace_span};

use crate::{path::Path, tree::entry::Entry, tree::iter::depth::Traversal};

use super::{
    entry::{TreeRefEntry, TREEBOUND},
    iter::depth::TreeIterTarget,
    node::TreeNode,
    NodeIDX, Tree,
};

/// Representation of a node differential
pub type DiffNode<N> = (Option<N>, Option<N>);
/// A tree containing [DiffNode]s as nodes
pub type DiffTree<N, B> = Tree<DiffNode<N>, B>;

pub struct Before<N>(PhantomData<N>);
pub struct Now<N>(PhantomData<N>);

impl<'a, N, B> TreeIterTarget<'a, DiffNode<N>, B> for Now<&'a N> {
    type Target = &'a Option<N>;
    fn target(tree: &'a Tree<DiffNode<N>, B>, idx: NodeIDX) -> Self::Target {
        &tree.nodes[idx].value.1
    }
}

impl<'a, N, B> TreeIterTarget<'a, DiffNode<N>, B> for Before<&'a N> {
    type Target = &'a Option<N>;
    fn target(tree: &'a Tree<DiffNode<N>, B>, idx: NodeIDX) -> Self::Target {
        &tree.nodes[idx].value.0
    }
}

impl<N, B> DiffTree<N, B>
where
    B: Clone,
{
    // Reverses a Differential
    pub fn rev(&mut self) {
        for node in self.nodes.iter_mut() {
            mem::swap(&mut node.value.0, &mut node.value.1);
        }
    }

    pub fn validate(&self) -> Result<(), Path<B>> {
        //TODO: rewrite method
        let mut ph = Path::new();
        for diff in self.iter_on::<&TreeNode<DiffNode<N>, B>>() {
            ph.apply(&diff);
            let d: &TreeNode<_, _> = diff.take();
            // Node removal
            if let (Some(_), None) = d.value {
                // But
                if !d.children.is_empty() {
                    return Err(ph.branches_to_owned());
                }
            }
        }
        Ok(())
    }
}

impl<N, B> DiffTree<N, B>
where
    N: Clone,
    B: Clone + Eq + Hash,
{
    pub(super) fn mirror_subtree_at(
        &mut self,
        tree: &Tree<N, B>,
        idx_s: NodeIDX,
        idx_t: NodeIDX,
        now: bool,
    ) {
        if now {
            self.nodes[idx_s].value.1 = Some(tree.nodes[idx_t].value.clone());
        } else {
            self.nodes[idx_s].value.0 = Some(tree.nodes[idx_t].value.clone());
        }
        self.mirror_subtree_rec(tree, idx_s, idx_t, now);
    }

    pub fn mirror_subtree_rec(
        &mut self,
        tree: &Tree<N, B>,
        idx_s: NodeIDX,
        idx_t: NodeIDX,
        now: bool,
    ) {
        for (branch, &c_idx_t) in &tree.nodes[idx_t].children {
            let c_idx_s = if let Some(&c_idx_s) = self.nodes[idx_s].children.get(branch) {
                if now {
                    self.nodes[c_idx_s].value.1 = Some(tree.nodes[c_idx_t].value.clone());
                } else {
                    self.nodes[c_idx_s].value.0 = Some(tree.nodes[c_idx_t].value.clone());
                }
                c_idx_s
            } else {
                self.insert_at(
                    idx_s,
                    branch.clone(),
                    if now {
                        (None, Some(tree.nodes[c_idx_t].value.clone()))
                    } else {
                        (Some(tree.nodes[c_idx_t].value.clone()), None)
                    },
                );
                self.nodes[idx_s].children[branch]
            };
            self.mirror_subtree_rec(tree, c_idx_s, c_idx_t, now);
        }
    }
}

impl<N, B> DiffTree<N, B>
where
    N: Clone + Default,
    B: Clone + Eq + Hash + Default,
{
    pub fn mirror_subtree(&mut self, tree: &Tree<N, B>, path: &Path<B>, now: bool) {
        let root_t = tree.get_idx(path, None).unwrap();
        let root_s = if let Ok(root_s) = self.get_idx(path, None) {
            root_s
        } else {
            *self.extend(path, None).last().unwrap()
        };
        self.mirror_subtree_at(tree, root_s, root_t, now)
    }
}

impl<N, B> DiffTree<N, B>
where
    N: Default + Eq,
    B: Default + Eq + Hash + Clone,
{
    pub fn is_applicable_extend(&self, tree: &Tree<N, B>) -> Result<(), DiffApplyError<B>> {
        self.is_applicable_with(tree, |entry, new| {
            // Extend if needed
            new.unwrap().1 = entry.path().len();
            Ok(())
        })
    }
}

type Insertable<N, B> = fn(
    &mut TreeRefEntry<N, B, TREEBOUND>,
    &mut Option<(usize, usize)>,
) -> Result<(), DiffApplyError<B>>;

impl<N, B> DiffTree<N, B>
where
    N: Eq,
    B: Eq + Hash + Clone,
{
    pub fn is_applicable(&self, tree: &Tree<N, B>) -> Result<(), DiffApplyError<B>> {
        self.is_applicable_with(tree, |entry, new| {
            if entry.is_node() {
                // Attached
                return Ok(());
            }
            // Can't extend, can only append
            let detached = entry.detached().unwrap();
            let detached_dist =
                detached.iter_detached_path().len() - new.map(|(s, e)| e - s).unwrap_or(0);
            debug_assert!(
                detached_dist > 0,
                "Expected detached entry, got attached entry"
            );
            if detached_dist == 1 {
                // New node will be created
                if new.is_some() {
                    new.unwrap().1 += 1;
                } else {
                    let l = entry.path().len();
                    *new = Some((l - 1, l));
                }
                Ok(())
            } else {
                // Parent node inexistent
                Err(DiffApplyError::Other("Expected Parent".to_string()))
            }
        })
    }
    fn is_applicable_with(
        &self,
        tree: &Tree<N, B>,
        insertable: Insertable<N, B>,
    ) -> Result<(), DiffApplyError<B>> {
        use DiffApplyError::*;
        let mut diff_i = self.iter_on::<&DiffNode<N>>();
        let mut entry = tree.entry(&Path::new());
        let mut deleted = None;
        let mut new = None;
        // Root
        match diff_i.next() {
            Some(Traversal::Start((b, n))) => {
                if let Some(before) = &b {
                    let _s1 = trace_span!("Node existed");
                    let _s1_ = _s1.enter();
                    // Node should exist
                    if let Some(node) = entry.node_mut() {
                        if **node != *before {
                            return Err(DifferentValue(Path::new()));
                        }
                    } else {
                        return Err(Expected(Path::new()));
                    }
                    if n.is_none() {
                        // Node deleted
                        trace!("node will be deleted");
                        deleted = Some(0);
                    } else {
                        // Node changed
                        trace!("node will change");
                    }
                } else if n.is_some() {
                    let _s1 = trace_span!("New node");
                    let _s1_ = _s1.enter();
                    // New node
                    if entry.is_detached() {
                        trace!("node will be created");
                        insertable(&mut entry, &mut new)?;
                    } else {
                        return Err(Unexpected(Path::new()));
                    }
                } else {
                    trace!("node will remain unchanged");
                    // No change
                }
            }
            None => {
                debug!("diff is empty");
                // Empty diff
                return Ok(());
            }
            Some(_) => {
                unreachable!("Tree iteration should always start with a Root node");
            }
        };
        // Children
        for d in diff_i {
            entry.apply_move_deref(&d);
            if let Some(idx) = deleted {
                if entry.path().len() <= idx {
                    deleted = None;
                }
            }

            if let Some(n) = &mut new.as_mut() {
                let l = entry.path().len();
                if l <= n.0
                /*start*/
                {
                    new = None;
                } else if l < n.1
                /*end*/
                {
                    n.1 = l;
                }
            }

            let _s1 = trace_span!("next node");
            let _s1_ = _s1.enter();
            let (b, n) = d.take();

            if let Some(before) = &b {
                let _s2 = trace_span!("Node existed");
                let _s2_ = _s2.enter();
                // Change or delete node
                // Node should exist
                if let Some(node) = entry.node_mut() {
                    // Diff corresponds to node value?
                    if **node != *before {
                        return Err(DifferentValue(node.path().clone()));
                    }
                } else {
                    return Err(Expected(entry.path().clone()));
                }
                if n.is_some() {
                    trace!("node will change");
                    // Node changed
                    if deleted.is_some() {
                        return Err(BelowDeletion(entry.path().clone()));
                    }
                } else {
                    trace!("node will be deleted");
                    // Node deleted
                    if deleted.is_none() {
                        deleted = Some(entry.path().len());
                    }
                }
            } else if n.is_some() {
                let _s2 = trace_span!("New node");
                let _s2_ = _s2.enter();
                // New node
                if deleted.is_some() {
                    return Err(BelowDeletion(entry.path().clone()));
                }
                if let Entry::Node(node) = entry {
                    return Err(Unexpected(node.path().clone()));
                }
                insertable(&mut entry, &mut new)?;
            } else {
                trace!("node will remain unchanged");
                // No change
            }
        }
        Ok(())
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DiffApplyError<B> {
    Expected(Path<B>),
    Unexpected(Path<B>),
    DifferentValue(Path<B>),
    BelowDeletion(Path<B>),
    Other(String),
}

impl<B, T> From<DiffApplyError<B>> for Result<T, DiffApplyError<B>> {
    fn from(value: DiffApplyError<B>) -> Self {
        Err(value)
    }
}

/// Structure mapping [Path]s to [DiffNodes]
pub struct DiffMap<N, B> {
    diffs: HashMap<Path<B>, DiffNode<N>>,
}

impl<N, B> IntoIterator for DiffMap<N, B> {
    type Item = (Path<B>, DiffNode<N>);

    type IntoIter = std::collections::hash_map::IntoIter<Path<B>, DiffNode<N>>;

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

impl<N, B> From<HashMap<Path<B>, DiffNode<N>>> for DiffMap<N, B> {
    fn from(value: HashMap<Path<B>, DiffNode<N>>) -> Self {
        Self { diffs: value }
    }
}

//TODO: remove Ord on N?
impl<N, B> From<DiffMap<N, B>> for DiffTree<N, B>
where
    N: Ord,
    B: Ord + Default + Hash + Clone,
{
    fn from(value: DiffMap<N, B>) -> Self {
        value
            .diffs
            .into_iter()
            .fold(DiffTree::new(), |mut tree, (ph, v)| {
                tree.insert_extend(&ph, v);
                tree
            })
    }
}