gctree 0.35.0

//!

use crate::{
    edge::Edge,
    phase::Phase,
};
use std::collections::BinaryHeap;
use super::{
    arena::Arena,
    error::{ArenaError, ArenaResult},
    node_idx::NodeIdx,
    util::deref,
};

pub use crate::new::arena::RmPol;


pub struct Forest<I, N, P, C> {
    arena: Arena<I, N, P, C>,
    roots: Vec<I>,
}

impl<I, N, P, C> Default for Forest<I, N, P, C>
where
    I: NodeIdx,
    N: Default
{
    fn default() -> Self {
        Self::with_capacity(128)
    }
}

impl<I, N, P, C> Forest<I, N, P, C>
where
    I: NodeIdx,
    N: Default
{
    pub fn with_capacity(cap: usize) -> Self {
        Self {
            arena: Arena::with_capacity(cap),
            roots: Vec::with_capacity(512),
        }
    }

    pub fn roots(&self) -> &[I] {
        &self.roots
    }

    /// If there is a single root node, return it.
    /// Otherwise, panic.
    pub fn root(&self) -> I {
        assert_eq!(self.roots.len(), 1, "Expected exactly 1 root node");
        self.roots[0]
    }

    pub fn iter_roots(&self) -> NodeIter![Item = I] {
        self.roots.iter().copied()
    }

    #[inline]
    pub fn append_root(&mut self, data: N) -> I {
        let root = self.add_node(data);
        self.roots.push(root);
        root
    }

    #[inline]
    pub fn insert_root(&mut self, pos: usize, data: N) -> I {
        let root = self.add_node(data);
        self.roots.insert(pos, root);
        root
    }

    // pub fn remove_root(&mut self, fidx: I) {
    //     if let Some(pos) = self.roots.iter().position(|&root| root == fidx) {
    //         self.roots.remove(pos);
    //     }
    // }

    fn register_root(&mut self, fidx: I) {
        self.roots.push(fidx);
    }

    // O(n) where `n = |self.roots|`
    fn unregister_root(&mut self, fidx: I) {
        self.roots = self.roots.drain(..)
            .filter(|&root| root != fidx)
            .collect();
    }

    #[inline]
    pub fn clear_roots(&mut self) {
        self.roots.clear();
    }

    #[inline]
    pub fn count_roots(&self) -> usize {
        self.roots.len()
    }


    pub fn add_node(&mut self, data: N) -> I {
        self.arena.add_node(data)
    }

    #[must_use]
    pub fn remove_tree(&mut self, fidx: I, rmpol: RmPol) -> ArenaResult<(), I> {
        self.arena.remove_tree(fidx, rmpol)
    }

    pub fn append_edge(&mut self, pidx: I, cidx: I, pdata: P, cdata: C) {
        self.arena.append_edge(pidx, cidx, pdata, cdata)
    }

    /// Add a bidirectional edge `pidx <--> cidx`.
    /// - `pidx` registers the `cidx` as a child, while `cidx`
    ///   registers `pidx` as a parent.
    /// - `pidx` is inserted in `self.parents[cidx]` at position `ppos`,
    ///   or appended at the end if `ppos` is `None`.
    /// - `pdata` is inserted in `self.pdata[cidx]` at position `ppos`,
    ///   or appended at the end if `ppos` is `None`.
    /// - `cidx` is inserted in `self.children[pidx]` at position `ppos`,
    ///   or appended at the end if `cpos` is `None`.
    /// - `cdata` is inserted in `self.cdata[pidx]` at position `ppos`,
    ///   or appended at the end if `cpos` is `None`.
    pub fn add_edge(
        &self,
        (ppos, pidx, pdata): (impl Into<Option<usize>>, I, P),
        (cpos, cidx, cdata): (impl Into<Option<usize>>, I, C),
    ) {
        self.arena.add_edge((ppos, pidx, pdata),  (cpos, cidx, cdata));
    }

    pub fn insert_edge(
        &mut self,
        (ppos, pidx, pdata): (usize, I, P),
        (cpos, cidx, cdata): (usize, I, C),
    ) {
        self.arena.insert_edge((ppos, pidx, pdata),  (cpos, cidx, cdata));
    }

    pub fn remove_edges(&self, pidxs: &[I], cidxs: &[I]) -> ArenaResult<(), I> {
        self.arena.remove_edges(pidxs, cidxs)
    }

    #[must_use]
    pub fn remove_edge(
        &mut self,
        pidx: I,
        cidx: I,
    ) -> ArenaResult<(P, C), I> {
        self.arena.remove_edge(pidx, cidx)
    }

    pub fn parent_edge(&self, src: I, dst: I) -> ArenaResult<Edge<I, &P>, I> {
        self.arena.parent_edge(src, dst)
    }

    pub fn child_edge(&self, src: I, dst: I) -> ArenaResult<Edge<I, &C>, I> {
        self.arena.child_edge(src, dst)
    }

    #[must_use]
    #[track_caller]
    /// Copy the tree rooted in `root` from `src` to `self`.
    /// Specifically, the copy of `root` becomes a child node of `dst_node`.
    /// Note that the node idxs from `src` will *NOT* be valid in `self`.
    pub fn copy_tree(
        &mut self,
        dst_node: I,
        (src, root): (&Self, I),
    ) -> ArenaResult<(), I>
    where
        N: Clone,
        P: Clone + Default,
        C: Clone + Default,
    {
        self.arena.copy_tree(dst_node, (&src.arena, root))
    }

    #[must_use]
    #[rustfmt::skip]
    /// Make `root` the last child node of `parent`.
    pub fn move_tree(&self, parent: I, root: I) -> ArenaResult<(), I>
    where
        C: Default,
        P: Default,
    {
        self.arena.move_tree(parent, root)
    }

    #[must_use]
    /// Replace the tree rooted @ `target` with the tree rooted @ `root`.
    /// This means that `target` is removed from `self` and `root` takes
    /// its place.
    pub fn replace_tree(&self, target: I, root: I) -> ArenaResult<(), I> {
        self.arena.replace_tree(target, root)
    }

    /// Get the ordinal number of `pidx` as a parent of `cidx`
    pub fn parent_ordinal(&self, pidx: I, cidx: I) -> ArenaResult<usize, I> {
        self.arena.parent_ordinal(pidx, cidx)
    }

    /// Get the ordinal number of `cidx` as a child of `pidx`
    pub fn child_ordinal(&self, pidx: I, cidx: I) -> ArenaResult<usize, I> {
        self.arena.child_ordinal(pidx, cidx)
    }

    pub fn self_or_ancestors_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.self_or_ancestors_of(nidx)
    }

    #[inline(always)]
    pub fn ancestors_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.ancestors_of(nidx)
    }

    #[inline(always)]
    pub fn self_or_siblings_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.self_or_siblings_of(nidx)
    }

    #[inline(always)]
    pub fn siblings_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.siblings_of(nidx)
    }

    #[inline(always)]
    pub fn parents_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.parents_of(nidx)
    }

    #[inline(always)]
    pub fn children_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.children_of(nidx)
    }

    #[inline(always)]
    pub fn self_or_descendants_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.self_or_descendants_of(nidx)
    }

    #[inline(always)]
    pub fn descendants_of(&self, nidx: I) -> NodeIter![Item = I] {
        self.arena.descendants_of(nidx)
    }

    #[inline(always)]
    pub fn dfs_before(&self, start_idx: I) -> NodeIter![Item = I] {
        self.arena.dfs_before(start_idx)
    }

    #[inline(always)]
    pub fn dfs_after(&self, start_idx: I) -> NodeIter![Item = I] {
        self.arena.dfs_after(start_idx)
    }

    pub fn dfs(&self, start_idx: I) -> NodeIter![Item = (I, Phase)] {
        self.arena.dfs(start_idx)
    }

    pub fn bfs(&self, start_idx: I) -> NodeIter![Item = I] {
        self.arena.bfs(start_idx)
    }

    // #[allow(unused)]
    // #[cfg(feature = "graphviz")]
    // pub fn to_graphviz_graph(&self, root_idx: I) -> DotGraph
    // where
    //     I: std::fmt::Display,
    //     N: std::fmt::Display,
    //     P: std::fmt::Display,
    //     C: std::fmt::Display,
    // {
    //     // self.arena.to_graphviz_graph(root_idx)
    //     todo!()
    // }

}

// TODO serialize
// TODO deserialize
// TODO