gctree 0.35.0

//! This module deals with arena allocation.

use crate::{
    edge::Edge,
    new::{
        error::{ArenaError, ArenaResult},
        node::{NodeMut, NodeRef},
        node_idx::NodeIdx,
    },
    phase::Phase,
};
use itertools::Itertools;
#[cfg(feature = "graphviz")] use crate::graphviz::*;
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use serde::de::{self, MapAccess, SeqAccess, Visitor};
use serde::ser::SerializeStruct;
use std::cell::{Cell, RefCell};
use std::collections::{BinaryHeap, HashMap};
use std::fmt::{self, Debug};
use super::util::deref;


#[macro_export]
macro_rules! NodeIter {
    (Item = $item:ty) => {
        impl DoubleEndedIterator<Item = $item> + use<'_, I, N, P, C>
    }
}


#[derive(Clone, Debug)]
pub struct Arena<I, N, P, C> {
    /// Physical node count
    len: Cell<usize>,
    /// Associated data for each `node` in `self`
    ndata: RefCell<Vec<N>>,
    /// Parent nodes for each `node` in `self`
    parents: RefCell<Vec<Vec<I>>>,
    /// Associated data 'D' for each `node --[D]--> parent` edge in `self`
    pdata: RefCell<Vec<Vec<P>>>,
    /// Child nodes for each `node` in `self`
    children: RefCell<Vec<Vec<I>>>,
    /// Associated data `C` for each `node --[C]--> child` edge in `self`
    cdata: RefCell<Vec<Vec<C>>>,
    /// Nodes that are not logically contained
    /// in (but are physically present in) `self`
    garbage: RefCell<BinaryHeap<Garbage<I>>>,
}

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

impl<I, N, P, C> Arena<I, N, P, C>
where
    I: NodeIdx,
    N: Default,
{
    pub fn with_capacity(cap: usize) -> Self {
        Self {
            len: Cell::from(0),
            ndata: Vec::with_capacity(cap).into(),
            parents: Vec::with_capacity(cap).into(),
            pdata: Vec::with_capacity(cap).into(),
            children: Vec::with_capacity(cap).into(),
            cdata: Vec::with_capacity(cap).into(),
            garbage: BinaryHeap::with_capacity(cap).into(),
        }
    }

    fn init_up_to(&self, nidx: I) {
        self.assert_equal_vec_lens();
        for _ in self.count_nodes() ..= *nidx { // Init using default values
            self._ndata().push(N::default());
            self._parents().push(vec![]);
            self._pdata().push(vec![]);
            self._children().push(vec![]);
            self._cdata().push(vec![]);
            // No need to init self.garbage
        }
    }

    fn assert_equal_vec_lens(&self) {
        let node_count = self.count_nodes();
        debug_assert_eq!(node_count, self._ndata().len());
        debug_assert_eq!(node_count, self._parents().len());
        debug_assert_eq!(node_count, self._pdata().len());
        debug_assert_eq!(node_count, self._children().len());
        debug_assert_eq!(node_count, self._cdata().len());
    }

    fn assert_valid_nidx(&self, nidx: I) -> ArenaResult<(), I> {
        if *nidx < self.count_nodes() {
            Ok(())
        } else {
            Err(ArenaError::InvalidNodeIdx(nidx))
        }
    }


    #[inline]
    fn _len(&self) -> usize {
        self.len.get()
    }

    #[inline]
    fn _ndata(&self) -> &mut Vec<N> {
        unsafe { &mut *self.ndata.as_ptr() }
    }

    #[inline]
    fn _parents(&self) -> &mut Vec<Vec<I>> {
        unsafe { &mut *self.parents.as_ptr() }
    }

    #[inline]
    fn _pdata(&self) -> &mut Vec<Vec<P>> {
        unsafe { &mut *self.pdata.as_ptr() }
    }

    #[inline]
    fn _children(&self) -> &mut Vec<Vec<I>> {
        unsafe { &mut *self.children.as_ptr() }
    }

    #[inline]
    fn _cdata(&self) -> &mut Vec<Vec<C>> {
        unsafe { &mut *self.cdata.as_ptr() }
    }

    #[inline]
    fn _garbage(&self) -> &mut BinaryHeap<Garbage<I>> {
        unsafe { &mut *self.garbage.as_ptr() }
    }



    #[inline]
    fn ndata(&self, nidx: I) -> &mut N {
        self.init_up_to(nidx);
        &mut self._ndata()[*nidx]
    }

    #[inline]
    fn parents(&self, nidx: I) -> &mut Vec<I> {
        self.init_up_to(nidx);
        &mut self._parents()[*nidx]
    }

    #[inline]
    /// Return `&mut p` for all edges `nidx --[p]--> pidx`
    fn pdata(&self, nidx: I) -> &mut Vec<P> {
        self.init_up_to(nidx);
        &mut self._pdata()[*nidx]
    }

    #[inline]
    /// Return `&mut p` for an edge `cidx --[p]--> pidx`
    fn pdata_for_edge(&self, pidx: I, cidx: I) -> ArenaResult<&mut P, I> {
        self.init_up_to(pidx);
        let p = self.parent_ordinal(pidx, cidx)?;
        Ok(&mut self._pdata()[*cidx][p])
    }

    #[inline]
    fn children(&self, nidx: I) -> &mut Vec<I> {
        self.init_up_to(nidx);
        &mut self._children()[*nidx]
    }

    #[inline]
    /// Return `&mut c` for all edges `nidx --[p]--> cidx`
    fn cdata(&self, nidx: I) -> &mut Vec<C> {
        self.init_up_to(nidx);
        &mut self._cdata()[*nidx]
    }

    #[inline]
    /// Return `&mut c` for an edge `pidx --[c]--> cidx`
    fn cdata_for_edge(&self, pidx: I, cidx: I) -> ArenaResult<&mut C, I> {
        self.init_up_to(pidx);
        let c = self.child_ordinal(pidx, cidx)?;
        Ok(&mut self._cdata()[*pidx][c])
    }


    pub fn clear(&self) -> ArenaResult<(), I> {
        for nidx in self.iter_nodes() { // purge all nodes
            self.remove_tree(nidx, RmPol::All)?;
        }
        self.set_garbage(self.iter_nodes()); // Register all nodes as garbage
        Ok(())
    }

    fn set_garbage(&self, nidxs: impl Iterator<Item = I>) {
        *self._garbage() = nidxs
            .unique()
            .map(Garbage)
            .sorted(/* in ascending order */)
            .collect::<BinaryHeap<_>>()
            .into(/* Refcell<_> */);
    }

    #[inline]
    fn append_garbage(&self, nidxs: impl Iterator<Item = I>) {
        self._garbage().extend(nidxs.map(Garbage))
    }


    fn iter_nodes(&self) -> NodeIter![Item = I] {
        let is_not_garbage = |&nidx: &I| -> bool {
            !self.iter_garbage().contains(&nidx)
        };
        (0..self.count_nodes())
            .map(I::from)
            .filter(is_not_garbage)
    }

    fn iter_garbage(&self) -> NodeIter![Item = I] {
        self._garbage().iter(/* in arbitrary order */)
            .map(deref)
            .map(|Garbage(nidx)| nidx)
    }


    /// Get the logical size, which is defined as `physical size - garbage size`
    /// i.e. the number of allocated, non-garbage nodes in `self`.
    #[inline]
    pub fn logical_size(&self) -> usize {
        self.physical_size() - self.garbage_size()
    }

    /// Get the physical size, which is defined as the number of nodes
    /// allocated in the tree, whether they are garbage or not.
    #[inline]
    pub fn physical_size(&self) -> usize {
        self.len.get()
    }

    /// Get the garbage size i.e. the number of garbage nodes in `self`.
    #[inline]
    pub fn garbage_size(&self) -> usize {
        self._garbage().len()
    }

    pub fn node_ref<'arena>(
        &'arena self,
        nidx: I,
    ) -> ArenaResult<NodeRef<'arena, I, N, P, C>, I> {
        Ok(NodeRef {
            nidx,
            data: self.ndata(nidx),
            parents: self.parents(nidx),
            pdata: self.pdata(nidx),
            children: self.children(nidx),
            cdata: self.cdata(nidx),
        })
    }

    pub fn node_mut<'arena>(
        &'arena self,
        nidx: I,
    ) -> ArenaResult<NodeMut<'arena, I, N, P, C>, I> {
        Ok(NodeMut {
            nidx,
            data: self.ndata(nidx),
            parents: self.parents(nidx),
            pdata: self.pdata(nidx),
            children: self.children(nidx),
            cdata: self.cdata(nidx),
        })
    }

    /// Recycle or allocate a node, then assign the node `data`.
    /// Return the node index.
    pub fn add_node(&self, data: N) -> I {
        let nidx = self._garbage().pop()
            .map(|Garbage(nidx)| nidx)
            .unwrap_or_else(|| { // no garbage available for reuse
                I::from(self.count_nodes())
            });
        self.init_up_to(nidx);
        self.inc_node_count();
        *self.ndata(nidx) = data;
        nidx
    }

    pub fn is_root_node(&self, nidx: I) -> bool {
        !self.has_parents(nidx)
    }

    pub fn is_leaf_node(&self, nidx: I) -> bool {
        self.children(nidx).is_empty()
    }

    pub fn is_orphan(&self, nidx: I) -> bool {
        !self.has_parents(nidx)
    }

    pub fn has_parents(&self, nidx: I) -> bool {
        !self.parents(nidx).is_empty()
    }

    pub fn has_children(&self, nidx: I) -> bool {
        !self.children(nidx).is_empty()
    }

    pub fn count_parents(&self, nidx: I) -> usize {
        self.parents(nidx).len()
    }

    pub fn count_children(&self, nidx: I) -> usize {
        self.children(nidx).len()
    }

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

    fn inc_node_count(&self) {
        self.len.set(self.len.get() + 1);
    }

    fn dec_node_count(&self) {
        self.len.set(self.len.get() - 1);
    }

    #[must_use]
    /// Recycle all nodes in the tree rooted in `root`.  Since a node owns its
    /// children, all descendant nodes and all edges between them are removed
    /// as well.
    pub fn remove_tree(&self, root: I, rmpol: RmPol) -> ArenaResult<(), I> {
        self.assert_valid_nidx(root)?;
        let node_iter = self.dfs_before(root)
            .rev(/* leaves -> ... -> nidx */)
            .filter(|&nidx: &I| match rmpol {
                RmPol::Orphan => self.is_orphan(nidx),
                RmPol::NonOrphan => !self.is_orphan(nidx),
                RmPol::All => true,
            });
        for nidx in node_iter {
            debug_assert!(self.is_leaf_node(nidx));
            self.remove_edges(self.parents(nidx), &[nidx])?;
            debug_assert!(self.is_root_node(nidx));
            // NOTE: Don't clear `self.ndata`, for performance reasons.
            //       We can get away with this because of the of the
            //       non-optionality of the `data` param of `Self::add_node()`
            //       i.e. `self.ndata[idx]` is statically guaranteed to be
            //       in a valid state by the time the node is usable again.
            self._garbage().push(Garbage(nidx));
        }
        Ok(())
    }


    #[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(
        &self,
        dst_node: I,
        (src, root): (&Self, I),
    ) -> ArenaResult<(), I>
    where
        N: Clone,
        P: Clone + Default,
        C: Clone + Default,
    {
        type SrcTreeIdx<I> = Option<I>;
        type DstTreeIdx<I> = I;
        let mut map = HashMap::<SrcTreeIdx<I>, DstTreeIdx<I>>::new();
        map.insert(None, dst_node);
        let (sarena, darena) = (src, self);
        for src_node in sarena.dfs_before(root) {
            let src_parent: SrcTreeIdx<I> = if src_node == root {
                None // ignore the parents of `root`
            } else {
                sarena.parents(src_node).get(0).map(deref)
            };
            let dst_parent: DstTreeIdx<I> = map[&src_parent];
            let dst_node = darena.add_node(sarena.ndata(src_node).clone());
            let (pdata, cdata) = if let Some(src_parent) = src_parent {
                let pdata: &P = sarena.parent_edge(src_node, src_parent)?.data;
                let cdata: &C = sarena.child_edge(src_parent, src_node)?.data;
                (pdata.clone(), cdata.clone()) // `src_node` has a parent edge
            } else {
                (P::default(), C::default()) // `src_node` has no parent edge
            };
            darena.append_edge(dst_parent, dst_node, pdata, cdata);
            map.insert(Some(src_node), dst_node);
        }
        Ok(())
    }

    #[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,
    {
        for &old_parent in self.parents(root).iter() {
            self.remove_edge(old_parent, root)?;
        };
        self.append_edge(parent, root, P::default(), C::default());
        Ok(())
    }

    #[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> {
        for &parent in self.parents(root).iter() {
            self.remove_edge(parent, root)?;
        }
        for &parent in self.parents(target).iter() {
            let cpos = self.child_ordinal(parent, target)?;
            let (pdata, cdata) = self.remove_edge(parent, target)?;
            self.add_edge((None, parent, pdata),  (cpos, root, cdata));
        }
        self.remove_tree(target, RmPol::All)?;
        Ok(())
    }

    pub fn parent_edge(&self, src: I, dst: I) -> ArenaResult<Edge<I, &P>, I> {
        self.init_up_to(std::cmp::max(src, dst));
        let data: &P = self.pdata_for_edge(dst, src)?;
        self.parents_of(src)
            .find(|&pidx| pidx == dst)
            .map(|_| Edge { src, dst, data })
            .ok_or_else(|| ArenaError::ParentEdgeDoesNotExist {
                parent: dst,
                child: src,
            })
    }

    pub fn child_edge(&self, src: I, dst: I) -> ArenaResult<Edge<I, &C>, I> {
        self.init_up_to(std::cmp::max(src, dst));
        let data: &C = self.cdata_for_edge(src, dst)?;
        self.children_of(src)
            .find(|&cidx| cidx == dst)
            .map(|_| Edge { src, dst, data })
            .ok_or_else(|| ArenaError::ChildEdgeDoesNotExist {
                parent: src,
                child: dst,
            })
    }

    /// Add a bidirectional edge between nodes `pidx` and `cidx`. The former
    /// registers the latter as a child, while the latter registers the former
    /// as a parent.  In addition, `pdata` is assigned to the parent edge:
    ///   `cidx --[pdata]--> pidx`
    /// while `cdata` is assigned to the child edge:
    ///   `pidx --[cdata]--> cidx`
    pub fn append_edge(&self, pidx: I, cidx: I, pdata: P, cdata: C) {
        self.append_parent_edge(pidx, cidx, pdata);
        self.append_child_edge(pidx, cidx, cdata);
    }

    /// Add a `cidx --[pdata]--> pidx` edge.
    fn append_parent_edge(&self, pidx: I, cidx: I, pdata: P) {
        self.init_up_to(std::cmp::max(pidx, cidx));
        self.parents(cidx).push(pidx);
        self.pdata(cidx).push(pdata);
        self.assert_equal_vec_lens();
    }

    /// Add a `pidx --[cdata]--> cidx` edge.
    fn append_child_edge(&self, pidx: I, cidx: I, cdata: C) {
        self.init_up_to(std::cmp::max(pidx, cidx));
        self.children(pidx).push(cidx);
        self.cdata(pidx).push(cdata);
        self.assert_equal_vec_lens();
    }

    /// Insert a bidirectional edge between `pidx` and `cidx`.
    /// The former registers the latter as the `cpos`-th child, while
    /// the latter registers the former as the `ppos`-th parent.
    pub fn insert_edge(
        &self,
        (ppos, pidx, pdata): (usize, I, P),
        (cpos, cidx, cdata): (usize, I, C),
    ) {
        self.insert_parent_edge(ppos, pidx, cidx, pdata);
        self.insert_child_edge(cpos, pidx, cidx, cdata);
    }

    /// Insert a `cidx --[pdata]--> pidx` edge.
    fn insert_parent_edge(&self, pos: usize, pidx: I, cidx: I, pdata: P) {
        self.init_up_to(std::cmp::max(pidx, cidx));
        self.parents(cidx).insert(pos, pidx);
        self.pdata(cidx).insert(pos, pdata);
        self.assert_equal_vec_lens();
    }

    /// Insert an `pidx --[cdata]--> cidx` edge.
    fn insert_child_edge(&self, pos: usize, pidx: I, cidx: I, cdata: C) {
        self.init_up_to(std::cmp::max(pidx, cidx));
        self.children(pidx).insert(pos, cidx);
        self.cdata(pidx).insert(pos, cdata);
        self.assert_equal_vec_lens();
    }

    /// 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),
    ) {
        if let Some(ppos) = ppos.into() {
            self.parents(cidx).insert(ppos, pidx);
            self.pdata(cidx).insert(ppos, pdata);
        } else {
            self.parents(cidx).push(pidx);
            self.pdata(cidx).push(pdata);
        }
        if let Some(cpos) = cpos.into() {
            self.children(pidx).insert(cpos, cidx);
            self.cdata(pidx).insert(cpos, cdata);
        } else {
            self.children(pidx).push(cidx);
            self.cdata(pidx).push(cdata);
        }
    }

    #[must_use]
    /// ∀ pidx in `pidxs` and ∀ cidx in `cidxs`, remove edge `pidx <--> cidx`.
    /// Return an error if any of the `|pidxs| * |cidxs|` edges do not exist.
    pub fn remove_edges(&self, pidxs: &[I], cidxs: &[I]) -> ArenaResult<(), I> {
        for (&pidx, &cidx) in itertools::iproduct!(pidxs, cidxs) {
            self.remove_edge(pidx, cidx)?;
        }
        Ok(())
    }

    #[must_use]
    /// Remove the bidirectional edge `pidx <--> cidx`.
    /// Return an error if no such edge exists.
    pub fn remove_edge(&self, pidx: I, cidx: I) -> ArenaResult<(P, C), I> {
        let pdata: P = self.remove_parent_edge(pidx, cidx)?;
        let cdata: C = self.remove_child_edge(pidx, cidx)?;
        Ok((pdata, cdata))
    }

    /// Remove the parent edge `cidx --[P]--> pidx`.
    fn remove_parent_edge(&self, pidx: I, cidx: I) -> ArenaResult<P, I> {
        let pos = self.parent_ordinal(pidx, cidx)?; // the `pos`-th parent of `cidx`
        let _ = self.parents(cidx).remove(pos);
        let data: P = self.pdata(cidx).remove(pos);
        Ok(data)
    }

    /// Remove the child edge `pidx --[C]--> cidx`.
    fn remove_child_edge(&self, pidx: I, cidx: I) -> ArenaResult<C, I> {
        let pos = self.child_ordinal(pidx, cidx)?; // the `pos`-th child of `pidx`
        let _ = self.children(pidx).remove(pos);
        let data: C = self.cdata(pidx).remove(pos);
        Ok(data)
    }

    /// Get the ordinal number of `pidx` as a parent of `cidx`
    pub fn parent_ordinal(&self, pidx: I, cidx: I) -> ArenaResult<usize, I> {
        self.parents_of(cidx).enumerate()
            .find(|&(_, _pidx)| _pidx == pidx)
            .map(|(ordinal, _)| ordinal)
            .ok_or_else(|| ArenaError::ParentOrdinalNotFound {
                node_idx: cidx,
                parent_idx: pidx,
            })
    }

    /// Get the ordinal number of `cidx` as a child of `pidx`
    pub fn child_ordinal(&self, pidx: I, cidx: I) -> ArenaResult<usize, I> {
        self.children_of(pidx).enumerate()
            .find(|&(_, _cidx)| _cidx == cidx)
            .map(|(ordinal, _)| ordinal)
            .ok_or_else(|| ArenaError::ChildOrdinalNotFound {
                node_idx: pidx,
                child_idx: cidx,
            })
    }


    pub fn self_or_ancestors_of(&self, nidx: I) -> NodeIter![Item = I] {
        type Layer<X> = Vec<X>;
        let mut layers: Vec<Layer<I>> = Vec::with_capacity(16);
        layers.push(Layer::from([nidx]));
        while let Some(previous) = layers.last() {
            let current: Layer<_> = previous.iter()
                .flat_map(|&idx| self.parents(idx).iter().map(deref))
                .collect();
            if current.is_empty() {
                break;
            }
            layers.push(current);
        }
        layers.into_iter()
            .flat_map(Layer::into_iter)
    }

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

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

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

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

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

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

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

    pub fn dfs_before(&self, start_idx: I) -> NodeIter![Item = I] {
        self.dfs(start_idx)
            .filter(|&(_, phase)| phase == Phase::Before)
            .map(|(nidx, _)| nidx)
    }

    pub fn dfs_after(&self, start_idx: I) -> NodeIter![Item = I] {
        self.dfs(start_idx)
            .filter(|&(_, phase)| phase == Phase::After)
            .map(|(nidx, _)| nidx)
    }

    pub fn dfs(&self, start_idx: I) -> NodeIter![Item = (I, Phase)] {
        #[derive(Debug)]
        struct Entry<I: NodeIdx> {
            nidx: I,
            /// The number of children of `nidx` visited so far
            visited: usize,
        }
        let mut stack = Vec::with_capacity(1024);
        stack.push(Entry { nidx: start_idx, visited: 0 });
        let mut output = vec![];
        while let Some(current) = stack.last_mut() {
            let Entry { nidx, visited: child /*ordinal*/ } = *current;
            let is_before = child == 0;
            let is_after  = child == self.count_children(nidx);
            if is_before {
                output.push((nidx, Phase::Before));
            }
            if is_after {
                output.push((nidx, Phase::After));
                stack.pop().unwrap();
                continue
            }
            if !is_before && !is_after {
                output.push((nidx, Phase::Between(child - 1, child)));
            }
            current.visited += 1;
            stack.push(Entry {
                nidx: self.children(nidx)[child],
                visited: 0,
            });
        }
        output.into_iter()
    }

    pub fn bfs(&self, start_idx: I) -> NodeIter![Item = I] {
        type Layer<X> = Vec<X>;
        let mut layers: Vec<Layer<I>> = vec![Layer::from([start_idx])];
        while let Some(previous) = layers.last() {
            let current: Layer<I> = previous.iter()
                .flat_map(|&idx| self.children_of(idx))
                .collect();
            if current.is_empty() {
                break;
            }
            layers.push(current);
        }
        layers.into_iter().flat_map(|layer| layer.into_iter())
    }

    #[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,
    {
        let mut graph = DotGraph::default();
        for nidx in self.bfs(root_idx) {
            let ndata = &self.ndata(nidx);
            graph.add(DotNode {
                idx: crate::NodeIdx(*nidx),
                attrs: DotAttrs {
                    label: Some(format!("{ndata}")),
                    ..DotAttrs::default()
                },
            });

            let parents = self.parents(nidx);
            let pdata = self.pdata(nidx);
            assert_eq!(parents.len(), pdata.len());
            for (pidx, pdata) in parents.iter()
                .enumerate()
                .map(|(i, pidx)| (*pidx, &pdata[i]))
            {
                graph.add(DotEdge {
                    src: crate::NodeIdx(*nidx),
                    dst: crate::NodeIdx(*pidx),
                    attrs: DotAttrs {
                        label: Some(format!("{pdata}")),
                        color: Some("purple".to_string()),
                        ..DotAttrs::default()
                    },
                });
            }

            let children = self.children(nidx);
            let cdata = self.cdata(nidx);
            assert_eq!(children.len(), cdata.len());
            for (cidx, cdata) in children.iter()
                .enumerate()
                .map(|(i, cidx)| (*cidx, &cdata[i]))
            {
                graph.add(DotEdge {
                    src: crate::NodeIdx(*nidx),
                    dst: crate::NodeIdx(*cidx),
                    attrs: DotAttrs {
                        label: Some(format!("{cdata}")),
                        color: Some("#36454F".to_string()), // charcoal
                        ..DotAttrs::default()
                    },
                });
            }
        }
        graph
    }
}

impl<I, N, P, C> Serialize for Arena<I, N, P, C>
where
    I: NodeIdx + Serialize,
    N: Default + Serialize,
    P: Serialize,
    C: Serialize,
{
    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        const FIELD_COUNT: usize = 7;
        let mut state = serializer.serialize_struct("Arena", FIELD_COUNT)?;
        state.serialize_field("len", &self._len())?;
        state.serialize_field("ndata", self._ndata())?;
        state.serialize_field("parents", self._parents())?;
        state.serialize_field("pdata", self._pdata())?;
        state.serialize_field("children", self._children())?;
        state.serialize_field("cdata", self._cdata())?;
        state.serialize_field("garbage", self._garbage())?;
        state.end()
    }
}

#[rustfmt::skip]
impl<'de, I, N, P, C> Deserialize<'de> for Arena<I, N, P, C>
where
    I: Clone + Debug + Default + PartialEq + Deserialize<'de> + NodeIdx,
    N: Clone + Debug + Default + PartialEq + Deserialize<'de>,
    P: Clone + Debug + Default + PartialEq + Deserialize<'de>,
    C: Clone + Debug + Default + PartialEq + Deserialize<'de>,
{
    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {

        #[derive(serde::Deserialize)]
        #[serde(field_identifier, rename_all = "lowercase")]
        enum Field {
            Len,
            NodeData,
            Parents,
            ParentData,
            Children,
            ChildData,
            Garbage,
        }

        #[derive(Clone, Debug, PartialEq, serde::Deserialize, serde::Serialize)]
        struct ArenaVisitor<I, N, P, C>(
            std::marker::PhantomData<I>, // len
            std::marker::PhantomData<N>, // node data
            std::marker::PhantomData<I>, // parents
            std::marker::PhantomData<P>, // parent data
            std::marker::PhantomData<I>, // children
            std::marker::PhantomData<C>, // child data
            std::marker::PhantomData<I>, // garbage
        );

        impl<'de, I, N, P, C> Visitor<'de> for ArenaVisitor<I, N, P, C>
        where
            I: Clone + Debug + Default + PartialEq + Deserialize<'de> + NodeIdx,
            N: Clone + Debug + Default + PartialEq + Deserialize<'de>,
            P: Clone + Debug + Default + PartialEq + Deserialize<'de>,
            C: Clone + Debug + Default + PartialEq + Deserialize<'de>,
        {
            type Value = Arena<I, N, P, C>;

            fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
                f.write_str("struct Arena<I, N, P, C>")
            }

            fn visit_seq<V>(
                self,
                mut seq: V
            ) -> std::result::Result<Self::Value, V::Error>
            where
                V: SeqAccess<'de>,
            {
                Ok(Arena {
                    len: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(0, &self))?,
                    ndata: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(1, &self))?,
                    parents: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(2, &self))?,
                    pdata: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(3, &self))?,
                    children: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(4, &self))?,
                    cdata: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(5, &self))?,
                    garbage: seq.next_element()?
                        .ok_or_else(|| de::Error::invalid_length(6, &self))?,
                })
            }

            fn visit_map<A>(
                self,
                mut map: A
            ) -> std::result::Result<Self::Value, A::Error>
            where
                A: MapAccess<'de>,
            {
                let mut len = None;
                let mut ndata = None;
                let mut parents = None;
                let mut pdata = None;
                let mut children = None;
                let mut cdata = None;
                let mut garbage = None;
                while let Some(key) = map.next_key()? {
                    match key {
                        Field::Len =>
                            if len.is_some() {
                                return Err(de::Error::duplicate_field("len"));
                            } else {
                                len = Some(map.next_value()?);
                            },
                        Field::NodeData =>
                            if ndata.is_some() {
                                return Err(de::Error::duplicate_field("ndata"));
                            } else {
                                ndata = Some(map.next_value()?);
                            },
                        Field::Parents =>
                            if parents.is_some() {
                                return Err(de::Error::duplicate_field("parents"));
                            } else {
                                parents = Some(map.next_value()?);
                            },
                        Field::ParentData =>
                            if pdata.is_some() {
                                return Err(de::Error::duplicate_field("pdata"));
                            } else {
                                pdata = Some(map.next_value()?);
                            },
                        Field::Children =>
                            if children.is_some() {
                                return Err(de::Error::duplicate_field("children"));
                            } else {
                                children = Some(map.next_value()?);
                            },
                        Field::ChildData => if cdata.is_some() {
                            return Err(de::Error::duplicate_field("cdata"));
                        } else {
                            cdata = Some(map.next_value()?);
                        },
                        Field::Garbage => if garbage.is_some() {
                            return Err(de::Error::duplicate_field("garbage"));
                        } else {
                            garbage = Some(map.next_value()?);
                        },
                    }
                }
                Ok(Arena {
                    len: len
                        .ok_or_else(|| de::Error::missing_field("len"))?,
                    ndata: ndata
                        .ok_or_else(|| de::Error::missing_field("ndata"))?,
                    parents: parents
                        .ok_or_else(|| de::Error::missing_field("parents"))?,
                    pdata: pdata
                        .ok_or_else(|| de::Error::missing_field("pdata"))?,
                    children: children
                        .ok_or_else(|| de::Error::missing_field("chidlren"))?,
                    cdata: cdata
                        .ok_or_else(|| de::Error::missing_field("cdata"))?,
                    garbage: garbage
                        .ok_or_else(|| de::Error::missing_field("garbage"))?,
                })
            }
        }

        d.deserialize_map(ArenaVisitor(
            std::marker::PhantomData, // len
            std::marker::PhantomData, // node data
            std::marker::PhantomData, // parents
            std::marker::PhantomData, // parent data
            std::marker::PhantomData, // children
            std::marker::PhantomData, // child data
            std::marker::PhantomData, // garbage
        ))
    }
}


// This type is used for 2 purposes:
// 1. To reverse the way in which they are ordered relative to `I`.
//    The utility of that is that `std::collections::BinaryHeap<_>`
//    can then be used as a min-heap rather than as a max-heap.
// 2. To statically mark garbage collected node idxs as such
#[repr(transparent)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[derive(serde::Deserialize, serde::Serialize)]
#[serde(transparent)]
struct Garbage<I>(I);

impl<I> std::cmp::PartialOrd for Garbage<I>
where
    I: NodeIdx
{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<I> std::cmp::Ord for Garbage<I>
where
    I: NodeIdx
{
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}


#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
/// Removal policy for `Arena::remove_tree()`.
pub enum RmPol {
    /// Remove all nodes
    All,
    /// Remove only orphaned nodes i.e. nodes that have no parent nodes.
    Orphan,
    /// Remove only nodes that have at least 1 parent node.
    NonOrphan,
}



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

    use super::*;

    node_idx![TestIdx];

    type TestArena<N> = Arena<TestIdx, N, (), ()>;
    type TestIdxs = Vec<TestIdx>;

    fn make_test_tree() -> (TestArena<&'static str>, TestIdxs) {
        //      -- 0 --
        //     /       \
        //    /         \
        //    1         2
        //   / \      / | \
        //  3   4    5  6  7
        let arena = Arena::<TestIdx, &str, (), ()>::default();
        let nidxs = vec![
            arena.add_node("node 0 (root)"),
            arena.add_node("node 1"),
            arena.add_node("node 2"),
            arena.add_node("node 3"),
            arena.add_node("node 4"),
            arena.add_node("node 5"),
            arena.add_node("node 6"),
            arena.add_node("node 7"),
        ];
        arena.append_edge(nidxs[0], nidxs[1], (), ());
        arena.append_edge(nidxs[0], nidxs[2], (), ());
        arena.append_edge(nidxs[1], nidxs[3], (), ());
        arena.append_edge(nidxs[1], nidxs[4], (), ());
        arena.append_edge(nidxs[2], nidxs[5], (), ());
        arena.append_edge(nidxs[2], nidxs[6], (), ());
        arena.append_edge(nidxs[2], nidxs[7], (), ());
        (arena, nidxs)
    }

    #[test]
    fn allocate_arena() {
        let arena = Arena::<TestIdx, (), (), ()>::default();
        assert_eq!(0, arena.iter_nodes().count());
    }

    #[test]
    fn initialize_arena() -> ArenaResult<(), TestIdx> {
        let (arena, nidxs) = make_test_tree(); // initializes the arena

        macro_rules! assert_edge_exists {
            ($parent:expr, $child:expr) => {{
                assert_edge_exists!(parent: $child, $parent);
                assert_edge_exists!(child:  $parent, $child);
            }};
            (parent: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.parent_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
            (child: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.child_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
        }

        // A list of node idxs can be obtained using Arena::iter_nodes():
        let nodes: Vec<TestIdx> = arena.iter_nodes().collect();
        assert_eq!(&nodes, &nidxs);

        // assert node count:
        assert_eq!(nidxs.len(), arena.count_nodes());

        // assert node identity:
        assert_eq!(0, *nidxs[0]);
        assert_eq!(1, *nidxs[1]);
        assert_eq!(2, *nidxs[2]);
        assert_eq!(3, *nidxs[3]);
        assert_eq!(4, *nidxs[4]);
        assert_eq!(5, *nidxs[5]);
        assert_eq!(6, *nidxs[6]);

        // assert node data:
        assert_eq!("node 0 (root)", *arena.ndata(nidxs[0]));
        assert_eq!("node 1",        *arena.ndata(nidxs[1]));
        assert_eq!("node 2",        *arena.ndata(nidxs[2]));
        assert_eq!("node 3",        *arena.ndata(nidxs[3]));
        assert_eq!("node 4",        *arena.ndata(nidxs[4]));
        assert_eq!("node 5",        *arena.ndata(nidxs[5]));
        assert_eq!("node 6",        *arena.ndata(nidxs[6]));
        assert_eq!("node 7",        *arena.ndata(nidxs[7]));

        // assert bidirectional edge existence:
        assert_edge_exists!(nidxs[0], nidxs[1]);
        assert_edge_exists!(nidxs[0], nidxs[2]);
        assert_edge_exists!(nidxs[1], nidxs[3]);
        assert_edge_exists!(nidxs[1], nidxs[4]);
        assert_edge_exists!(nidxs[2], nidxs[5]);
        assert_edge_exists!(nidxs[2], nidxs[6]);
        assert_edge_exists!(nidxs[2], nidxs[7]);

        // assert parent counts:
        assert_eq!(0, arena.count_parents(nidxs[0]));
        assert_eq!(1, arena.count_parents(nidxs[1]));
        assert_eq!(1, arena.count_parents(nidxs[2]));
        assert_eq!(1, arena.count_parents(nidxs[3]));
        assert_eq!(1, arena.count_parents(nidxs[4]));
        assert_eq!(1, arena.count_parents(nidxs[5]));
        assert_eq!(1, arena.count_parents(nidxs[6]));
        assert_eq!(1, arena.count_parents(nidxs[7]));

        // assert child counts:
        assert_eq!(2, arena.count_children(nidxs[0]));
        assert_eq!(2, arena.count_children(nidxs[1]));
        assert_eq!(3, arena.count_children(nidxs[2]));
        assert_eq!(0, arena.count_children(nidxs[3]));
        assert_eq!(0, arena.count_children(nidxs[4]));
        assert_eq!(0, arena.count_children(nidxs[5]));
        assert_eq!(0, arena.count_children(nidxs[6]));
        assert_eq!(0, arena.count_children(nidxs[7]));

        Ok(())
    }

    #[test]
    fn dfs_traversal() -> ArenaResult<(), TestIdx> {
        let (arena, nidxs) = make_test_tree();
        let root: TestIdx = nidxs[0];

        const CHILD_0: usize = 0;
        const CHILD_1: usize = 1;
        const CHILD_2: usize = 2;

        let nodes: Vec<(TestIdx, Phase)> = arena.dfs(root).collect();
        assert_eq!(nodes, vec![
            (nidxs[0], Phase::Before),
            (nidxs[1], Phase::Before),
            (nidxs[3], Phase::Before),
            (nidxs[3], Phase::After),
            (nidxs[1], Phase::Between(CHILD_0, CHILD_1)),
            (nidxs[4], Phase::Before),
            (nidxs[4], Phase::After),
            (nidxs[1], Phase::After),
            (nidxs[0], Phase::Between(CHILD_0, CHILD_1)),
            (nidxs[2], Phase::Before),
            (nidxs[5], Phase::Before),
            (nidxs[5], Phase::After),
            (nidxs[2], Phase::Between(CHILD_0, CHILD_1)),
            (nidxs[6], Phase::Before),
            (nidxs[6], Phase::After),
            (nidxs[2], Phase::Between(CHILD_1, CHILD_2)),
            (nidxs[7], Phase::Before),
            (nidxs[7], Phase::After),
            (nidxs[2], Phase::After),
            (nidxs[0], Phase::After),
        ]);

        Ok(())
    }

    #[test]
    fn remove_tree() -> ArenaResult<(), TestIdx> {
        let (arena, nidxs) = make_test_tree();
        let root: TestIdx = nidxs[2];
        arena.remove_tree(root, RmPol::All)?;

        let nidx0_children: Vec<TestIdx> = arena.children_of(nidxs[0]).collect();
        assert_eq!(&nidx0_children, &[nidxs[1]]);

        let garbage: Vec<TestIdx> = arena._garbage().iter()
            .map(|&Garbage(nidx)| nidx)
            .sorted() // sort to make the resulting Vec<_> predictable
            .collect();
        assert_eq!(&garbage, &[nidxs[2], nidxs[5], nidxs[6], nidxs[7]]);

        Ok(())
    }

    #[test]
    fn copy_tree() -> ArenaResult<(), TestIdx> {
        //      -- 0 --       ➡︎      -- 0 --
        //     /       \      ➡︎     /       \
        //    /         \     ➡︎    /         \
        //    1         2     ➡︎    1         2
        //   / \      / | \   ➡︎   / \      / | \
        //  3   4    5  6  7  ➡︎  3   4    5  6  7
        //                            |
        //                            8
        //                          / | \
        //                         9 10 11
        let (arena, mut nidxs) = make_test_tree();

        arena.copy_tree(nidxs[4], (&arena, nidxs[2]))?;
        nidxs.extend((8..=11).map(TestIdx::from)); // add copied tree nodes

        // A list of node idxs can be obtained using Arena::iter_nodes():
        let nodes: Vec<TestIdx> = arena.iter_nodes().collect();
        assert_eq!(&nodes, &nidxs);

        macro_rules! assert_edge_exists {
            ($parent:expr, $child:expr) => {{
                assert_edge_exists!(parent: $child, $parent);
                assert_edge_exists!(child:  $parent, $child);
            }};
            (parent: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.parent_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
            (child: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.child_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
        }

        // assert node count:
        assert_eq!(12, arena.count_nodes());

        // assert node identity:
        assert_eq!( 0, *nidxs[ 0]);
        assert_eq!( 1, *nidxs[ 1]);
        assert_eq!( 2, *nidxs[ 2]);
        assert_eq!( 3, *nidxs[ 3]);
        assert_eq!( 4, *nidxs[ 4]);
        assert_eq!( 5, *nidxs[ 5]);
        assert_eq!( 6, *nidxs[ 6]);
        assert_eq!( 7, *nidxs[ 7]);
        assert_eq!( 8, *nidxs[ 8]);
        assert_eq!( 9, *nidxs[ 9]);
        assert_eq!(10, *nidxs[10]);
        assert_eq!(11, *nidxs[11]);

        // assert node data:
        assert_eq!("node 0 (root)", *arena.ndata(nidxs[ 0]));
        assert_eq!("node 1",        *arena.ndata(nidxs[ 1]));
        assert_eq!("node 2",        *arena.ndata(nidxs[ 2]));
        assert_eq!("node 3",        *arena.ndata(nidxs[ 3]));
        assert_eq!("node 4",        *arena.ndata(nidxs[ 4]));
        assert_eq!("node 5",        *arena.ndata(nidxs[ 5]));
        assert_eq!("node 6",        *arena.ndata(nidxs[ 6]));
        assert_eq!("node 7",        *arena.ndata(nidxs[ 7]));
        assert_eq!("node 2",        *arena.ndata(nidxs[ 8]));
        assert_eq!("node 5",        *arena.ndata(nidxs[ 9]));
        assert_eq!("node 6",        *arena.ndata(nidxs[10]));
        assert_eq!("node 7",        *arena.ndata(nidxs[11]));

        // assert bidirectional edge existence:
        assert_edge_exists!(nidxs[0], nidxs[ 1]);
        assert_edge_exists!(nidxs[0], nidxs[ 2]);
        assert_edge_exists!(nidxs[1], nidxs[ 3]);
        assert_edge_exists!(nidxs[1], nidxs[ 4]);
        assert_edge_exists!(nidxs[2], nidxs[ 5]);
        assert_edge_exists!(nidxs[2], nidxs[ 6]);
        assert_edge_exists!(nidxs[2], nidxs[ 7]);
        assert_edge_exists!(nidxs[4], nidxs[ 8]);
        assert_edge_exists!(nidxs[8], nidxs[ 9]);
        assert_edge_exists!(nidxs[8], nidxs[10]);
        assert_edge_exists!(nidxs[8], nidxs[11]);

        // assert parent counts:
        assert_eq!(0, arena.count_parents(nidxs[ 0]));
        assert_eq!(1, arena.count_parents(nidxs[ 1]));
        assert_eq!(1, arena.count_parents(nidxs[ 2]));
        assert_eq!(1, arena.count_parents(nidxs[ 3]));
        assert_eq!(1, arena.count_parents(nidxs[ 4]));
        assert_eq!(1, arena.count_parents(nidxs[ 5]));
        assert_eq!(1, arena.count_parents(nidxs[ 6]));
        assert_eq!(1, arena.count_parents(nidxs[ 7]));
        assert_eq!(1, arena.count_parents(nidxs[ 8]));
        assert_eq!(1, arena.count_parents(nidxs[ 9]));
        assert_eq!(1, arena.count_parents(nidxs[10]));
        assert_eq!(1, arena.count_parents(nidxs[11]));

        // assert child counts:
        assert_eq!(2, arena.count_children(nidxs[ 0]));
        assert_eq!(2, arena.count_children(nidxs[ 1]));
        assert_eq!(3, arena.count_children(nidxs[ 2]));
        assert_eq!(0, arena.count_children(nidxs[ 3]));
        assert_eq!(1, arena.count_children(nidxs[ 4]));
        assert_eq!(0, arena.count_children(nidxs[ 5]));
        assert_eq!(0, arena.count_children(nidxs[ 6]));
        assert_eq!(0, arena.count_children(nidxs[ 7]));
        assert_eq!(3, arena.count_children(nidxs[ 8]));
        assert_eq!(0, arena.count_children(nidxs[ 9]));
        assert_eq!(0, arena.count_children(nidxs[10]));
        assert_eq!(0, arena.count_children(nidxs[11]));

        Ok(())
    }

    #[test]
    fn move_tree() -> ArenaResult<(), TestIdx> {
        //      -- 0 --       ➡︎    0
        //     /       \      ➡︎    |
        //    /         \     ➡︎    1
        //    1         2     ➡︎   / \
        //   / \      / | \   ➡︎  3   4
        //  3   4    5  6  7  ➡︎      |
        //                            2
        //                          / | \
        //                         5  6  7
        let (arena, nidxs) = make_test_tree();
        arena.move_tree(nidxs[4], nidxs[2])?;

        macro_rules! assert_edge_exists {
            ($parent:expr, $child:expr) => {{
                assert_edge_exists!(parent: $child, $parent);
                assert_edge_exists!(child:  $parent, $child);
            }};
            (parent: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.parent_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
            (child: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.child_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
        }

        // assert node count:
        assert_eq!(8, arena.count_nodes());

        // assert node identity:
        assert_eq!( 0, *nidxs[ 0]);
        assert_eq!( 1, *nidxs[ 1]);
        assert_eq!( 2, *nidxs[ 2]);
        assert_eq!( 3, *nidxs[ 3]);
        assert_eq!( 4, *nidxs[ 4]);
        assert_eq!( 5, *nidxs[ 5]);
        assert_eq!( 6, *nidxs[ 6]);
        assert_eq!( 7, *nidxs[ 7]);

        // assert node data:
        assert_eq!("node 0 (root)", *arena.ndata(nidxs[ 0]));
        assert_eq!("node 1",        *arena.ndata(nidxs[ 1]));
        assert_eq!("node 2",        *arena.ndata(nidxs[ 2]));
        assert_eq!("node 3",        *arena.ndata(nidxs[ 3]));
        assert_eq!("node 4",        *arena.ndata(nidxs[ 4]));
        assert_eq!("node 5",        *arena.ndata(nidxs[ 5]));
        assert_eq!("node 6",        *arena.ndata(nidxs[ 6]));
        assert_eq!("node 7",        *arena.ndata(nidxs[ 7]));

        // assert bidirectional edge existence:
        assert_edge_exists!(nidxs[0], nidxs[1]);
        assert_edge_exists!(nidxs[1], nidxs[3]);
        assert_edge_exists!(nidxs[1], nidxs[4]);
        assert_edge_exists!(nidxs[2], nidxs[5]);
        assert_edge_exists!(nidxs[2], nidxs[6]);
        assert_edge_exists!(nidxs[2], nidxs[7]);
        assert_edge_exists!(nidxs[4], nidxs[2]);

        // assert parent counts:
        assert_eq!(0, arena.count_parents(nidxs[ 0]));
        assert_eq!(1, arena.count_parents(nidxs[ 1]));
        assert_eq!(1, arena.count_parents(nidxs[ 2]));
        assert_eq!(1, arena.count_parents(nidxs[ 3]));
        assert_eq!(1, arena.count_parents(nidxs[ 4]));
        assert_eq!(1, arena.count_parents(nidxs[ 5]));
        assert_eq!(1, arena.count_parents(nidxs[ 6]));
        assert_eq!(1, arena.count_parents(nidxs[ 7]));

        // assert child counts:
        assert_eq!(1, arena.count_children(nidxs[ 0]));
        assert_eq!(2, arena.count_children(nidxs[ 1]));
        assert_eq!(3, arena.count_children(nidxs[ 2]));
        assert_eq!(0, arena.count_children(nidxs[ 3]));
        assert_eq!(1, arena.count_children(nidxs[ 4]));
        assert_eq!(0, arena.count_children(nidxs[ 5]));
        assert_eq!(0, arena.count_children(nidxs[ 6]));
        assert_eq!(0, arena.count_children(nidxs[ 7]));

        Ok(())
    }

    #[test]
    fn replace_tree() -> ArenaResult<(), TestIdx> {
        //      -- 0 --       ➡︎    0
        //     /       \      ➡︎    |
        //    /         \     ➡︎    1
        //    1         2     ➡︎   / \
        //   / \      / | \   ➡︎  3   2
        //  3   4    5  6  7  ➡︎    / | \
        //                         5  6  7
        let (arena, nidxs) = make_test_tree();
        arena.replace_tree(nidxs[4], nidxs[2])?;

        macro_rules! assert_edge_exists {
            ($parent:expr, $child:expr) => {{
                assert_edge_exists!(parent: $child, $parent);
                assert_edge_exists!(child:  $parent, $child);
            }};
            (parent: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.parent_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
            (child: $src:expr, $dst:expr) => {{
                let (src, dst) = ($src, $dst);
                let Edge { src: s, dst: d, data } = arena.child_edge(src, dst)?;
                assert_eq!((s, d), (src, dst));
                assert_eq!(data, &());
            }};
        }

        // assert node count:
        assert_eq!(8, arena.count_nodes());

        let garbage = arena.iter_garbage()
            .sorted(/* make the resulting Vec<_> predictable */)
            .collect::<Vec<_>>();
        assert_eq!(garbage, vec![nidxs[4]]);

        // assert node identity:
        assert_eq!(0, *nidxs[0]);
        assert_eq!(1, *nidxs[1]);
        assert_eq!(2, *nidxs[2]);
        assert_eq!(3, *nidxs[3]);
        // skip nidxs[5]
        assert_eq!(5, *nidxs[5]);
        assert_eq!(6, *nidxs[6]);
        assert_eq!(7, *nidxs[7]);

        // assert node data:
        assert_eq!("node 0 (root)", *arena.ndata(nidxs[0]));
        assert_eq!("node 1",        *arena.ndata(nidxs[1]));
        assert_eq!("node 2",        *arena.ndata(nidxs[2]));
        assert_eq!("node 3",        *arena.ndata(nidxs[3]));
        // assert_eq!("node 4",        *arena.ndata(nidxs[4]));
        assert_eq!("node 5",        *arena.ndata(nidxs[5]));
        assert_eq!("node 6",        *arena.ndata(nidxs[6]));
        assert_eq!("node 7",        *arena.ndata(nidxs[7]));

        // assert bidirectional edge existence:
        assert_edge_exists!(nidxs[0], nidxs[1]);
        assert_edge_exists!(nidxs[1], nidxs[2]);
        assert_edge_exists!(nidxs[1], nidxs[3]);
        assert_edge_exists!(nidxs[2], nidxs[5]);
        assert_edge_exists!(nidxs[2], nidxs[6]);
        assert_edge_exists!(nidxs[2], nidxs[7]);

        // assert parent counts:
        assert_eq!(0, arena.count_parents(nidxs[0]));
        assert_eq!(1, arena.count_parents(nidxs[1]));
        assert_eq!(1, arena.count_parents(nidxs[2]));
        assert_eq!(1, arena.count_parents(nidxs[3]));
        // nidxs[4] is garbage
        assert_eq!(1, arena.count_parents(nidxs[5]));
        assert_eq!(1, arena.count_parents(nidxs[6]));
        assert_eq!(1, arena.count_parents(nidxs[7]));

        // assert child counts:
        assert_eq!(1, arena.count_children(nidxs[0]));
        assert_eq!(2, arena.count_children(nidxs[1]));
        assert_eq!(3, arena.count_children(nidxs[2]));
        assert_eq!(0, arena.count_children(nidxs[3]));
        // nidxs[4] is garbage
        assert_eq!(0, arena.count_children(nidxs[5]));
        assert_eq!(0, arena.count_children(nidxs[6]));
        assert_eq!(0, arena.count_children(nidxs[7]));

        Ok(())
    }

    #[test]
    fn existent_parent_edge() -> ArenaResult<(), TestIdx> {
        let (arena, nidxs) = make_test_tree();
        let Edge { src, dst, data } = arena.parent_edge(nidxs[1], nidxs[0])?;
        assert_eq!(src, nidxs[1]); // sanity check
        assert_eq!(dst, nidxs[0]); // sanity check
        assert_eq!(data, &()); // sanity check
        Ok(())
    }

    #[test]
    #[should_panic]
    fn nonexistent_parent_edge() {
        let (arena, nidxs) = make_test_tree();
        let _ = arena.parent_edge(nidxs[1], nidxs[2])
            .unwrap(/* No parent edge @1 -> @2, so ArenaResult goes boom */);
    }

    #[test]
    fn existent_child_edge() -> ArenaResult<(), TestIdx> {
        let (arena, nidxs) = make_test_tree();
        let Edge { src, dst, data } = arena.child_edge(nidxs[0], nidxs[1])?;
        assert_eq!(src, nidxs[0]); // sanity check
        assert_eq!(dst, nidxs[1]); // sanity check
        assert_eq!(data, &()); // sanity check
        Ok(())
    }

    #[test]
    #[should_panic]
    fn nonexistent_child_edge() {
        let (arena, nidxs) = make_test_tree();
        let _ = arena.child_edge(nidxs[1], nidxs[2])
            .unwrap(/* No child edge @1 -> @2, so ArenaResult goes boom */);
    }
}