nb_tree/tree/entry/

mod.rs

pub mod detached;
pub mod node;

use itertools::FoldWhile::{Continue, Done};
use itertools::Itertools;

//TODO: less/no replacement?
use replace_with::{replace_with_or_abort, replace_with_or_abort_and_return};
use std::hash::Hash;
use std::ops::{Deref, DerefMut};

use crate::path::Path;

use self::detached::DetachedEntry;
use self::node::Node;

use super::iter::depth::Traversal;
use super::{NodeIDX, Tree};

pub(super) const TREEBOUND: bool = false;
pub(super) const NODEBOUND: bool = true;

pub enum Entry<R, N, B, const BOUND: bool>
where
    R: Deref<Target = Tree<N, B>>,
{
    Node(Node<R, N, B, BOUND>),
    Detached(DetachedEntry<R, N, B, BOUND>),
}

pub type TreeRefEntry<'a, N, B, const BOUND: bool> = Entry<&'a Tree<N, B>, N, B, BOUND>;
pub type TreeMutEntry<'a, N, B, const BOUND: bool> = Entry<&'a mut Tree<N, B>, N, B, BOUND>;

impl<R, N, B, const BOUND: bool> From<Result<Node<R, N, B, BOUND>, DetachedEntry<R, N, B, BOUND>>>
    for Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
{
    fn from(value: Result<Node<R, N, B, BOUND>, DetachedEntry<R, N, B, BOUND>>) -> Self {
        match value {
            Ok(n) => Entry::Node(n),
            Err(d) => Entry::Detached(d),
        }
    }
}

impl<R, N, B, const BOUND: bool> From<Result<DetachedEntry<R, N, B, BOUND>, Node<R, N, B, BOUND>>>
    for Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
{
    fn from(value: Result<DetachedEntry<R, N, B, BOUND>, Node<R, N, B, BOUND>>) -> Self {
        match value {
            Ok(d) => Entry::Detached(d),
            Err(n) => Entry::Node(n),
        }
    }
}

impl<R, N, B, const BOUND: bool> From<Node<R, N, B, BOUND>> for Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
{
    fn from(value: Node<R, N, B, BOUND>) -> Self {
        Entry::Node(value)
    }
}

impl<R, N, B, const BOUND: bool> From<DetachedEntry<R, N, B, BOUND>> for Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
{
    fn from(value: DetachedEntry<R, N, B, BOUND>) -> Self {
        Entry::Detached(value)
    }
}

impl<R, N, B, const BOUND: bool> Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
{
    pub fn node(&self) -> Option<&Node<R, N, B, BOUND>> {
        match self {
            Entry::Node(node) => Some(node),
            Entry::Detached(_) => None,
        }
    }

    pub fn detached(&self) -> Option<&DetachedEntry<R, N, B, BOUND>> {
        match self {
            Entry::Node(_) => None,
            Entry::Detached(detached) => Some(detached),
        }
    }

    pub fn node_mut(&mut self) -> Option<&mut Node<R, N, B, BOUND>> {
        match self {
            Entry::Node(node) => Some(node),
            Entry::Detached(_) => None,
        }
    }

    pub fn detached_mut(&mut self) -> Option<&mut DetachedEntry<R, N, B, BOUND>> {
        match self {
            Entry::Node(_) => None,
            Entry::Detached(detached) => Some(detached),
        }
    }

    pub fn is_node(&self) -> bool {
        match self {
            Entry::Node(_) => true,
            Entry::Detached(_) => false,
        }
    }

    pub fn is_detached(&self) -> bool {
        !self.is_node()
    }

    pub fn branch(&self) -> Option<&B> {
        match self {
            Entry::Node(attached) => attached.branch(),
            Entry::Detached(detached) => detached.branch(),
        }
    }

    pub fn path(&self) -> &Path<B> {
        match self {
            Entry::Node(attached) => attached.path(),
            Entry::Detached(detached) => detached.path(),
        }
    }

    pub fn value(&self) -> Option<&N> {
        match self {
            Entry::Node(attached) => Some(attached.value()),
            Entry::Detached(_) => None,
        }
    }
}

impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: Deref<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    /// Applies the movement of the given traversal node, ignoring the contained data.
    ///
    /// No movement is made if the given node is a Start node or if the Step moves above the tree root.
    pub fn apply_move<T>(&mut self, node: &Traversal<T, B>) -> Result<(), usize> {
        if let Traversal::Step {
            up,
            branch,
            data: _,
        } = node
        {
            // Moves up without leaving and down. Blocks at root if overflowing
            if self.path().len() < *up {
                Err(*up - self.path().len())
            } else {
                assert!(self.move_up(*up).is_none());
                self.move_down_branch(branch.clone());
                Ok(())
            }
        } else {
            Ok(())
        }
        /*TODO: check. Check apply_move_deref too.
            return replace_with_or_abort_and_return(self, |s| {
                if let Entry::Detached(detached) = s {
                    // The Entry has to be empty to apply a root to it
                    if detached.position.is_empty() {
                        return (
                            true,
                            if detached.tree.get_root().is_some() {
                                // The tree has a root
                                let attached = detached.position.attach(0).unwrap_attached();
                                Node::from(detached.tree, attached).into()
                            } else {
                                detached.into()
                            },
                        );
                    } else {
                        (false, detached.into())
                    }
                } else {
                    (false, s)
                }
            });
        */
    }

    //TODO: check
    pub fn apply_move_deref<T, C>(&mut self, node: &Traversal<T, C>) -> bool
    where
        C: Deref<Target = B>,
    {
        if let Traversal::Step {
            up,
            branch,
            data: _,
        } = node
        {
            self.move_up(*up);
            self.move_down(path![(*branch).clone()]);
            true
        } else {
            replace_with_or_abort_and_return(self, |s| {
                if let Entry::Detached(detached) = s {
                    // The Entry has to be empty to apply a root to it
                    if detached.position.is_empty() {
                        (
                            true,
                            if detached.tree.get_root().is_some() {
                                // The tree has a root
                                let attached = detached.position.attach(0).unwrap_attached();
                                Node::from(detached.tree, attached).into()
                            } else {
                                detached.into()
                            },
                        )
                    } else {
                        (false, detached.into())
                    }
                } else {
                    (false, s)
                }
            })
        }
    }
}

impl<R, N, B, const BOUND: bool> Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
    B: Eq + Hash,
{
    pub fn from(tree: R, root: NodeIDX, path: Path<B>) -> Self {
        let mut detached = false;
        let idxs = path
            .iter()
            .fold_while(Path::new(), |mut ph, b| {
                ph.push_last(
                    if let Some(c_idx) = tree.nodes[*ph.last().unwrap_or(&root)].children.get(b) {
                        *c_idx
                    } else {
                        detached = true;
                        return Done(ph);
                    },
                );
                Continue(ph)
            })
            .into_inner();
        if detached {
            Self::Detached((tree, path, idxs).into())
        } else {
            Self::Node((tree, path, idxs).into())
        }
    }
}

impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn remove_subtree(self) -> Self {
        match self {
            Entry::Node(node) => node.remove_subtree().into(),
            Entry::Detached(_) => self,
        }
    }
}

impl<R, N, B, const BOUND: bool> Entry<R, N, B, BOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn and_modify<F>(mut self, f: F) -> Self
    where
        F: FnOnce(&mut N),
    {
        if let Entry::Node(ref mut node) = self {
            f(node.value_mut());
        }
        self
    }
    //TODO: compare to insert
    pub fn apply_data(&mut self, node: Traversal<N, B>) -> bool {
        let mut r = true;
        replace_with_or_abort(self, |s| match s {
            Entry::Node(mut n) => {
                n.insert(node.take());
                n.into()
            }
            Entry::Detached(d) => d
                .insert(node.take())
                .map_err(|e| {
                    r = false;
                    e
                })
                .into(),
        });
        r
    }
}
impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn apply(&mut self, node: Traversal<N, B>) -> bool {
        self.apply_move(&node).is_ok() && self.apply_data(node)
    }
}

impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    N: Clone + Default,
    B: Eq + Hash + Clone + Default,
{
    pub fn apply_extend(&mut self, node: Traversal<N, B>) -> bool {
        if let Traversal::Start(value) = node {
            return replace_with_or_abort_and_return(self, |s| {
                if let Entry::Detached(detached) = s {
                    if !detached.position.is_rooted() {
                        (true, detached.insert(value.clone()).into())
                    } else {
                        (false, detached.into())
                    }
                } else {
                    (false, s)
                }
            });
        }
        self.move_up(node.up());
        self.move_down(path![node.branch().unwrap().clone()]);
        //TODO: success management
        let r = true;
        replace_with_or_abort(self, |s| match s {
            Entry::Node(mut n) => {
                n.insert(node.take());
                n.into()
            }
            Entry::Detached(d) => d.insert_extend(node.take()).into(),
        });

        r
    }
}

impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: Deref<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn move_down(&mut self, path: Path<B>) {
        replace_with_or_abort(self, |s| match s {
            Entry::Node(node) => node.move_down(path),
            Entry::Detached(mut detached) => {
                detached.move_down(path);
                detached.into_entry()
            }
        })
    }
    pub fn move_down_branch(&mut self, branch: B) {
        replace_with_or_abort(self, |s| match s {
            Entry::Node(node) => node.move_down_branch(branch),
            Entry::Detached(mut detached) => {
                detached.move_down_branch(branch);
                Entry::Detached(detached)
            }
        })
    }
    pub fn move_up(&mut self, up: usize) -> Option<usize> {
        let mut overflow = None;
        replace_with_or_abort(self, |s| match s {
            Entry::Node(mut node) => {
                overflow = node.move_up(up);
                node.into_entry()
            }
            Entry::Detached(detached) => {
                let (e, o) = detached.move_up(up);
                overflow = o;
                e
            }
        });
        overflow
    }
    pub fn move_to_attached(&mut self) {
        replace_with_or_abort(self, |s| {
            if let Entry::Detached(detached) = s {
                detached.move_to_attached().into()
            } else {
                s
            }
        });
    }
}

impl<R, N, B, const BOUND: bool> Entry<R, N, B, BOUND>
where
    R: Deref<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn offshoot_len(&self) -> usize {
        match self {
            Entry::Node(_) => 0,
            Entry::Detached(detached) => detached.offshoot_len(),
        }
    }
}
impl<R, N, B, const BOUND: bool> Entry<R, N, B, BOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    B: Eq + Hash + Clone,
{
    pub fn or_insert(&mut self, value: N) -> &mut N {
        if self.is_detached() {
            /*self.detached()
            .unwrap()
            .position
            .detached_at()
            .unwrap_or_else(|| panic!("The entry is not rooted"));*/
            //replace_with_or_abort(self, |mut s| s.detached_mut().unwrap().insert(value).into());
            replace_with_or_abort(self, |s| {
                if let Entry::Detached(detached) = s {
                    detached.insert(value).into()
                } else {
                    s
                }
            });
        }
        let idx = *self.node().unwrap().position.at();
        //(o) self.node_mut().map(|node| &mut node.tree.nodes[idx].value)
        &mut self.node_mut().unwrap().tree.nodes[idx].value
    }

    pub fn insert(&mut self, value: N) -> Option<&mut N> {
        replace_with_or_abort(self, |s| match s {
            //TODO: no panic? return None?
            Entry::Detached(detached_entry) => {
                /*detached_entry
                .position
                .detached_at()
                .unwrap_or_else(|| panic!("The entry is not rooted"));*/
                detached_entry.insert(value).into()
            }
            Entry::Node(mut node) => {
                node.insert(value);
                node.into_entry()
            }
        });

        let idx = *self.node().unwrap().position.at();
        self.node_mut().map(|node| &mut node.tree.nodes[idx].value)
    }
}

impl<R, N, B> Entry<R, N, B, TREEBOUND>
where
    R: DerefMut<Target = Tree<N, B>>,
    N: Default,
    B: Default + Eq + Hash + Clone,
{
    pub fn or_insert_extend(&mut self, value: N) -> &mut N {
        replace_with_or_abort(self, |s| {
            if let Entry::Detached(detached_entry) = s {
                detached_entry.insert_extend(value).into()
            } else {
                s
            }
        });
        let idx = *self.node().unwrap().position.at();
        &mut self.node_mut().unwrap().tree.nodes[idx].value
    }

    pub fn insert_extend(&mut self, value: N) -> &mut N {
        replace_with_or_abort(self, |s| match s {
            Entry::Detached(detached_entry) => detached_entry.insert_extend(value).into(),
            Entry::Node(mut node) => {
                node.insert(value);
                node.into()
            }
        });
        let idx = *self.node().unwrap().position.at();
        &mut self.node_mut().unwrap().tree.nodes[idx].value
    }
}