sorbus 0.13.0

//! This crate implements a tree data structure.
//!
//! A tree is a directed acyclic graph of nodes, all of them
//! carrying an optional payload, as well as an optional
//! annotation to the edge linking them to their parent.
//!
//! Internally, nodes are stored in a vec, and the topology of the tree
//!
//! Each node in the tree may contain an arbitratry number of
//! children.
use derive_more::{Deref, Display, From, Into};
use errors::Error;
use identity_hash::{IdentityHashable, IntMap, IntSet};
use std::{
    fmt::Display,
    io::{self, Write},
};

pub mod errors;
pub mod render;

#[derive(Copy, Clone, PartialEq, Eq, From, Into, Deref, Default, Hash, Debug, Display)]
pub struct NodeHandle(usize);
impl IdentityHashable for NodeHandle {}

/// A node in the tree. A [`Node`] can carry a `Payload`, and can annotate the
/// branch to its parent with an `Edge`.
#[derive(Clone)]
pub struct Node<Payload, Edge> {
    parent: Option<NodeHandle>,
    children: Vec<NodeHandle>,
    branch: Option<Edge>,
    data: Payload,
}
impl<Payload, Edge> Node<Payload, Edge> {
    /// If this node has a `Payload`, return a reference to it.
    pub fn data(&self) -> &Payload {
        &self.data
    }

    /// If this node has a `Payload`, return a mutable reference to it.
    pub fn data_mut(&mut self) -> &mut Payload {
        &mut self.data
    }

    /// Set the `Payload` of this `Node`.
    pub fn set_data(&mut self, e: Payload) {
        self.data = e
    }

    /// Returns a reference to this node parent branch `Edge`.
    pub fn branch(&self) -> Option<&Edge> {
        self.branch.as_ref()
    }

    /// Set the `Edge` of this node parent branch.
    pub fn set_branch(&mut self, e: Edge) {
        self.branch = Some(e)
    }

    /// Unset the `Edge` of this node parent branch.
    pub fn unset_branch(&mut self) {
        self.branch = None
    }
}

#[derive(Clone, Default)]
pub struct Tree<Payload = (), MetaData = (), Edge = ()> {
    current_id: NodeHandle,
    metadata: MetaData,
    nodes: IntMap<NodeHandle, Node<Payload, Edge>>,
    arity: Option<usize>,
    _spans_set: IntMap<NodeHandle, IntSet<NodeHandle>>,
    _descendants: IntMap<NodeHandle, Vec<NodeHandle>>,
}
impl<P, D, E> std::ops::Index<NodeHandle> for Tree<P, D, E> {
    type Output = Node<P, E>;
    fn index(&self, i: NodeHandle) -> &Self::Output {
        &self.nodes[&i]
    }
}
impl<P, D, E> std::ops::IndexMut<NodeHandle> for Tree<P, D, E> {
    fn index_mut(&mut self, i: NodeHandle) -> &mut Self::Output {
        self.nodes.get_mut(&i).unwrap()
    }
}

impl<P, D: Default, E> Tree<P, D, E> {
    /// Create a new tree
    pub fn new() -> Self {
        Self {
            current_id: Default::default(),
            metadata: D::default(),
            nodes: Default::default(),
            arity: None,
            _spans_set: Default::default(),
            _descendants: Default::default(),
        }
    }

    /// Create a new binary tree, i.e. of arity 2
    pub fn binary() -> Self {
        Self {
            current_id: Default::default(),
            metadata: D::default(),
            nodes: Default::default(),
            arity: Some(2),
            _spans_set: Default::default(),
            _descendants: Default::default(),
        }
    }

    /// Create a new tree with as most `arity` children per node
    pub fn with_arity(arity: usize) -> Self {
        Self {
            current_id: Default::default(),
            metadata: D::default(),
            nodes: Default::default(),
            arity: Some(arity),
            _spans_set: Default::default(),
            _descendants: Default::default(),
        }
    }

    /// Create a new tree with as most `arity` children per node
    pub fn with_metadata(metadata: D) -> Self {
        Self {
            current_id: Default::default(),
            metadata,
            nodes: Default::default(),
            arity: None,
            _spans_set: Default::default(),
            _descendants: Default::default(),
        }
    }
}
impl<P, D, E> Tree<P, D, E> {
    /// Assign the given `metadata` as the meta-data associated to this tree.
    pub fn set_metadata(&mut self, metadata: D) {
        self.metadata = metadata;
    }

    /// Return a reference to the meta-data associated to this tree.
    pub fn metadata(&self) -> &D {
        &self.metadata
    }

    /// Return a mutable reference to the meta-data associated to this tree.
    pub fn metadata_mut(&mut self) -> &mut D {
        &mut self.metadata
    }

    /// Return a reference the node identified by `n` if it exists, or
    /// [`Error::NodeNotFound`] otherwise.
    pub fn get(&self, n: NodeHandle) -> Result<&Node<P, E>, Error> {
        self.nodes.get(&n).ok_or(Error::NodeNotFound(n))
    }

    /// Return a mutable reference the node identified by `n` if it exists, or
    /// [`Error::NodeNotFound`] otherwise.
    pub fn get_mut(&mut self, n: NodeHandle) -> Result<&mut Node<P, E>, Error> {
        self.nodes.get_mut(&n).ok_or(Error::NodeNotFound(n))
    }

    /// Return `true` if the node `n` has no children.
    pub fn is_leaf(&self, n: NodeHandle) -> bool {
        self.children(n).unwrap().is_empty()
    }

    /// Return a reference to the children of the node `n`.
    pub fn children(&self, n: NodeHandle) -> Result<&[NodeHandle], Error> {
        self.get(n).map(|node| node.children.as_slice())
    }

    /// Return a mutable reference to the children of the node `n`.
    fn children_mut(&mut self, n: NodeHandle) -> Result<&mut Vec<NodeHandle>, Error> {
        self.get_mut(n).map(|node| &mut node.children)
    }

    pub fn root(&self) -> NodeHandle {
        self.roots().next().unwrap()
    }

    pub fn roots(&self) -> impl Iterator<Item = NodeHandle> + '_ {
        self.nodes
            .iter()
            .filter_map(|(i, n)| if n.parent.is_none() { Some(i) } else { None })
            .cloned()
    }

    /// Return true if the given node is root; panic if it does not exist.
    pub fn is_root(&self, n: NodeHandle) -> bool {
        self[n].parent.is_none()
    }

    /// Provide an iterator over all the node handles in the tree.
    pub fn nodes(&self) -> impl Iterator<Item = NodeHandle> + '_ {
        self.nodes.keys().cloned()
    }

    /// Return an iterator over mutable reference to the nodes of the tree.
    pub fn nodes_mut(&mut self) -> impl Iterator<Item = &mut Node<P, E>> {
        self.nodes.values_mut()
    }

    /// Provide an iterator over the handles of all the leaves of this tree.
    pub fn leaves(&self) -> impl Iterator<Item = NodeHandle> + '_ {
        self.nodes.keys().filter(|&&n| self.is_leaf(n)).copied()
    }

    /// Return the number of nodes in this tree.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Return true if the tree is empty.
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    fn insert_node(&mut self, parent: Option<NodeHandle>, n: Node<P, E>) -> NodeHandle {
        self.current_id = (*self.current_id)
            .checked_add(1)
            .expect("Tree is too big")
            .into();
        let id = self.current_id;
        assert!(!self.nodes.contains_key(&id), "{} already exists", id);
        assert!(parent.is_none() || self.nodes.contains_key(&parent.unwrap()));
        self.nodes.insert(id, n);
        if let Some(parent) = parent {
            if let Some(arity) = self.arity {
                assert!(self.children(parent).unwrap().len() < arity)
            }
            self.children_mut(parent).unwrap().push(id);
        }

        id
    }

    pub fn add_node(&mut self, parent: Option<NodeHandle>, data: P) -> NodeHandle {
        if let Some(parent) = parent {
            assert!(self.nodes.contains_key(&parent));
        }

        self.insert_node(
            parent,
            Node {
                parent,
                children: Vec::new(),
                branch: None,
                data,
            },
        )
    }

    /// Connect the free-standing node `n` under `target`.
    ///
    /// Panic if `n` is not free-standing or if the arity constraints are broken.
    pub fn plug(&mut self, n: NodeHandle, target: NodeHandle) -> Result<(), Error> {
        assert!(self[n].parent.is_none());
        assert!(!self.children(target)?.contains(&n));
        if let Some(arity) = self.arity {
            assert!(self.children(target)?.len() < arity)
        }
        self.nodes.get_mut(&n).unwrap().parent = Some(target);
        self.children_mut(target)?.push(n);
        Ok(())
    }

    /// Disconnect the node `n` from its parent.
    pub fn unplug(&mut self, n: NodeHandle) -> Result<(), Error> {
        let parent = self.nodes[&n].parent;
        assert!(parent.is_none() || self.children(parent.unwrap())?.contains(&n));

        self.nodes.get_mut(&n).unwrap().parent = None;
        if let Some(parent) = parent {
            self.children_mut(parent)?.retain(|nn| *nn != n);
        }
        Ok(())
    }

    /// Make `n` a child of `new_parent`
    pub fn move_to(&mut self, n: NodeHandle, new_parent: NodeHandle) -> Result<(), Error> {
        self.unplug(n)?;
        self.plug(n, new_parent)
    }

    /// Delete the node `n`, and all its children recursively.
    ///
    /// Panic if `n` does not exist in the tree.
    pub fn delete_node(&mut self, n: NodeHandle) -> Result<(), Error> {
        if !self.nodes.contains_key(&n) {
            return Err(Error::NodeNotFound(n));
        }

        for c in self.children_mut(n)?.clone().into_iter() {
            self.delete_node(c)?;
        }
        self.unplug(n)?;
        self.nodes.remove(&n);
        Ok(())
    }

    /// Delete the nodes `ns`, and all their children recursively.
    ///
    /// Panic if any node in `ns` does not exist.
    pub fn delete_nodes(&mut self, ns: &[NodeHandle]) -> Result<(), Error> {
        for n in ns {
            self.delete_node(*n)?;
        }
        Ok(())
    }

    /// Move `n` from its current position to under `target`.
    ///
    /// Panic if `n` is free-standing or if arity constraints is broken.
    pub fn move_node(&mut self, n: NodeHandle, target: NodeHandle) -> Result<(), Error> {
        self.unplug(n)?;
        self.plug(n, target)?;

        Ok(())
    }

    /// Insert the existing node `between` between the nodes `a` and `b`;
    /// turning `a <-- b` into `a <-- between <-- b`.
    ///
    /// Panic if a is not the parent of b or if arity constraint is broken.
    pub fn insert_between(
        &mut self,
        between: NodeHandle,
        a: NodeHandle,
        b: NodeHandle,
    ) -> Result<(), Error> {
        if let Some(b_parent) = self.parent(b) {
            assert!(b_parent == a);
        } else {
            panic!("a is not the parent of b");
        }

        self.unplug(b)?;
        self.plug(between, a)?;
        self.plug(b, between)?;

        Ok(())
    }

    /// Return the parent of `n`, or `None` if `n` is a root.
    pub fn parent(&self, n: NodeHandle) -> Option<NodeHandle> {
        self[n].parent
    }

    /// Return, if it exists, the first leaf in tree satisfying the predicate.
    ///
    /// # Arguments
    ///
    /// * f - A predicate taking a reference to a node payload
    pub fn find_leaf<F>(&self, f: F) -> Option<NodeHandle>
    where
        F: Fn(&P) -> bool,
    {
        self.nodes
            .iter()
            .filter(|(i, _)| self.is_leaf(**i))
            .find(|(_i, n)| f(&n.data))
            .map(|(i, _)| *i)
    }

    /// Return, if it exists, the first node in tree satisfying the predicate.
    ///
    /// # Arguments
    ///
    /// * f - A predicate taking a reference to a node payload
    pub fn find_node<F>(&self, f: F) -> Option<NodeHandle>
    where
        F: Fn(&P) -> bool,
    {
        self.nodes
            .iter()
            .find(|(_i, n)| f(&n.data))
            .map(|(i, _)| *i)
    }

    /// Return, if it exists, the first child of `n` tree satisfying the predicate.
    ///
    /// # Arguments
    ///
    /// * n - The reference node
    /// * f - A predicate taking a reference to a node payload
    pub fn find_child<F>(&self, n: NodeHandle, f: F) -> Result<Option<NodeHandle>, Error>
    where
        F: Fn(&P) -> bool,
    {
        Ok(self
            .children(n)?
            .iter()
            .cloned()
            .find(|&n| f(self[n].data())))
    }

    /// Compute the Most Recent Common Ancestor of a set of nodes.
    /// If the set is empty, return the tree root.
    pub fn mrca(&self, nodes: impl IntoIterator<Item = NodeHandle>) -> Result<NodeHandle, Error> {
        let mut nodes = nodes.into_iter();
        let first = if let Some(node) = nodes.next() {
            node
        } else {
            return Ok(self.root());
        };

        let ancestors = self.ascendance(first);
        let ranks = ancestors
            .iter()
            .copied()
            .enumerate()
            .map(|(i, j)| (j, i))
            .collect::<IntMap<_, _>>();
        let mut checked = IntSet::<NodeHandle>::from_iter(ancestors.iter().copied());
        let mut oldest: NodeHandle = 0.into();

        for species in nodes {
            let mut species: NodeHandle = species;
            while !checked.contains(&species) {
                checked.insert(species);
                species = self.nodes[&species].parent.unwrap();
            }
            oldest = oldest.max(*ranks.get(&species).unwrap_or(&0)).into();
        }

        Ok(ancestors[*oldest])
    }

    /// Return the lineage of n, i.e. the direct path from `n` to the root.
    ///
    /// Panic if `n` does not exist in the tree.
    pub fn ascendance(&self, n: NodeHandle) -> Vec<NodeHandle> {
        let mut r = Vec::new();
        let mut parent = Some(n);

        while let Some(me) = parent {
            r.push(me);
            parent = self.parent(me);
        }

        r
    }

    /// Find all the descendants of `n`, i.e. all the nodes below `n` in the
    /// tree, not including `n`.
    ///
    /// Panic if `n` does not exist in the tree.
    pub fn descendants(&self, n: NodeHandle) -> Vec<NodeHandle> {
        fn find_descendants<PP, DD, EE>(
            t: &Tree<PP, DD, EE>,
            n: NodeHandle,
            ax: &mut Vec<NodeHandle>,
        ) {
            ax.push(n);
            for &c in t.children(n).unwrap().iter() {
                find_descendants(t, c, ax);
            }
        }

        let mut r = vec![];
        for &c in self.children(n).unwrap().iter() {
            find_descendants(self, c, &mut r);
        }
        r
    }

    /// Return a [`Vec`] containing all the leaves being descendant of `n`.
    pub fn leaves_of(&self, n: NodeHandle) -> Vec<NodeHandle> {
        self.leave_set_of(n).into_iter().collect()
    }

    /// Return a set containing all the leaves being descendant of `n`.
    pub fn leave_set_of(&self, n: NodeHandle) -> IntSet<NodeHandle> {
        fn find_descendants_leaves<PP, DD, EE>(
            t: &Tree<PP, DD, EE>,
            n: NodeHandle,
            ax: &mut IntSet<NodeHandle>,
        ) {
            if t.is_leaf(n) {
                ax.insert(n);
            } else {
                for &c in t.children(n).unwrap().iter() {
                    find_descendants_leaves(t, c, ax);
                }
            }
        }

        let mut r = Default::default();
        find_descendants_leaves(self, n, &mut r);
        r
    }

    pub fn cache_descendants(&mut self) {
        let mut me = self.root();
        let todo = self.descendants(me);
        self._descendants.insert(me, todo.to_owned());
        for n in todo {
            self._descendants.insert(n, self.descendants(n));
        }
        while let Some(parent) = self[me].parent {
            self._descendants.insert(parent, self.descendants(parent));
            me = parent;
        }
    }

    pub fn cache_descendants_of(&mut self, from: NodeHandle) {
        let mut me = from;
        let todo = self.descendants(me);
        self._descendants.insert(me, todo.to_owned());
        for n in todo {
            self._descendants.insert(n, self.descendants(n));
        }
        while let Some(parent) = self[me].parent {
            self._descendants.insert(parent, self.descendants(parent));
            me = parent;
        }
    }

    pub fn cached_descendants(&self, n: NodeHandle) -> Option<&Vec<NodeHandle>> {
        self._descendants.get(&n)
    }

    pub fn cache_leaves(&mut self) {
        for &k in self.nodes.keys() {
            self._spans_set.insert(k, self.leave_set_of(k));
        }
    }

    pub fn cached_leaves_of(&self, n: NodeHandle) -> &IntSet<NodeHandle> {
        &self._spans_set[&n]
    }

    pub fn cached_leaves_of_vec(&self, n: NodeHandle) -> Vec<NodeHandle> {
        let mut r = Vec::with_capacity(self._spans_set[&n].len());
        r.extend(self._spans_set[&n].iter().copied());
        r
    }

    /// Compute the depth of `n` according to the given measure.
    ///
    /// # Arguments
    ///
    /// * `n` - The node to compute the depth of.
    /// * `f` - A function associating a length to a an edge.
    pub fn depth_of<Measure: Fn(&E) -> f32>(&self, n: NodeHandle, f: &Measure) -> f32 {
        let mut depth = 0.0;
        let mut n = n;
        while let Some(parent) = self[n].parent {
            depth += self[n].branch.as_ref().map(f).unwrap_or(0.);
            n = parent;
        }
        depth
    }

    /// Return the topological depth of `n`, i.e. its distance to the root of
    /// the tree.
    pub fn topological_depth_of(&self, n: NodeHandle) -> Result<i64, Error> {
        if !self.nodes.contains_key(&n) {
            return Err(Error::NodeNotFound(n));
        }
        let mut depth = 0;
        let mut n = n;
        while let Some(parent) = self.nodes[&n].parent {
            depth += 1;
            n = parent;
        }
        Ok(depth)
    }

    /// Compute the topological depth of the tree, i.e. the depth of the deepest node.
    pub fn topological_depth(&self) -> Option<(NodeHandle, usize)> {
        fn _rec_depth<PP, DD, EE>(t: &Tree<PP, DD, EE>, n: NodeHandle) -> (NodeHandle, usize) {
            if t.is_leaf(n) {
                (n, 0)
            } else {
                let (n, d) = t
                    .children(n)
                    .unwrap()
                    .iter()
                    .map(|&c| _rec_depth(t, c))
                    .max_by_key(|(_, d)| *d)
                    .unwrap_or_default();
                (n, d + 1)
            }
        }

        if self.is_empty() {
            None
        } else {
            Some(_rec_depth(self, self.root()))
        }
    }

    /// Execute a function over all the leaves of the tree.
    ///
    /// # Arguments
    ///
    /// * `f` - a function taking a reference to a node
    pub fn for_each_leave<F: FnMut(&Node<P, E>)>(&self, f: &mut F) {
        self.nodes
            .iter()
            .filter_map(|(i, n)| if self.is_leaf(*i) { Some(n) } else { None })
            .for_each(f);
    }

    /// Execute a function over all the leaves of the tree.
    ///
    /// # Arguments
    ///
    /// * `f` - a function taking a mutable reference to a node
    pub fn for_each_leave_mut<F: FnMut(&mut Node<P, E>)>(&mut self, f: &mut F) {
        let to_process = self
            .nodes
            .keys()
            .filter(|i| self.is_leaf(**i))
            .copied()
            .collect::<Vec<_>>();

        to_process
            .into_iter()
            .for_each(|i| f(self.nodes.get_mut(&i).unwrap()));
    }

    /// Return an iterator over all the non-leaf nodes of the tree.
    pub fn inners(&self) -> impl Iterator<Item = NodeHandle> + '_ {
        self.nodes
            .keys()
            .filter(move |n| !self.is_leaf(**n))
            .copied()
    }

    /// Recursively delete all the nodes satisfying the given predicate.
    /// The children of the removed nodes are anchored to the parent of the removed node instead.
    ///
    /// # Arguments
    ///
    /// * `is_useless` - A predicate taking a node, and returning whether it
    ///   should be removed.
    pub fn collapse_if(&mut self, is_useless: impl Fn(&Node<P, E>) -> bool) {
        loop {
            let todo = self
                .nodes
                .keys()
                .find(|i| is_useless(&self[**i]) && self.parent(**i).is_some())
                .copied();

            if let Some(i) = todo {
                let children = self.children(i).unwrap().to_vec();
                for c in children {
                    self.move_node(c, self.parent(i).unwrap()).unwrap();
                }
                self.delete_node(i).unwrap();
            } else {
                break;
            }
        }
    }

    /// Remove empty inner nodes (i.e. nodes without content nor children) and
    /// compress redundant inner nodes (i.e. nodes with a single child and no
    /// content).
    pub fn consolidate(&mut self, is_empty: impl Fn(&P) -> bool) {
        loop {
            let todo = self
                .nodes
                .iter()
                .find_map(|(i, n)| {
                    if self.parent(*i).is_some()
                        && ((self.is_leaf(*i) && is_empty(&n.data))
                            || (self.children(*i).unwrap().len() == 1 && is_empty(&n.data)))
                    {
                        Some(i)
                    } else {
                        None
                    }
                })
                .copied();

            if let Some(i) = todo {
                let children = self.children(i).unwrap().to_vec();
                for c in children {
                    self.move_node(c, self.parent(i).expect("has a parent by construction"))
                        .unwrap();
                }
                self.delete_node(i).unwrap();
            } else {
                break;
            }
        }
    }

    /// Remove all the nodes not satisfying the predicate `keep` and their descendence.
    pub fn filter(&mut self, keep: impl Fn(&Node<P, E>) -> bool) {
        loop {
            let todo = self.nodes.keys().find(|k| !keep(&self[**k]));

            if let Some(k) = todo {
                self.delete_node(*k).unwrap();
            } else {
                break;
            }
        }
    }

    /// Remove all the nodes not satisfying the predicate `keep` and their descendence.
    pub fn filter_nodes(&mut self, keep: impl Fn(NodeHandle) -> bool) {
        loop {
            let todo = self.nodes.keys().find(|k| !keep(**k));

            if let Some(k) = todo {
                self.delete_node(*k).unwrap();
            } else {
                break;
            }
        }
    }

    fn rec_sort_by<K: Ord + Clone + std::fmt::Debug>(
        &mut self,
        n: NodeHandle,
        k: &impl Fn(&P) -> K,
        by_leaves: bool,
    ) -> K {
        let mut children = std::mem::take(self.children_mut(n).unwrap());
        // The recursive call can't be placed in `sort_by_cached_key`, as it would be short-circuited for single-child
        // nodes.
        for c in &children {
            self.rec_sort_by(*c, k, by_leaves);
        }
        children.sort_by_cached_key(|&c| k(self[c].data()));
        self[n].children = children;

        if by_leaves || self.children(n).unwrap().is_empty() {
            k(self[n].data())
        } else {
            k(&self[self.children(n).unwrap()[0]].data)
        }
    }

    /// Sort all sibling nodes according to the given key function.
    ///
    /// # Arguments
    ///
    /// * k - a function producing a [`Ord`] sorting criterion from a node data
    pub fn sort_by<K: std::fmt::Debug + Ord + Clone>(&mut self, k: impl Fn(&P) -> K) {
        let _ = self.rec_sort_by(self.root(), &k, false);
    }

    /// Sort sibling leave nodes according to the given key function.
    ///
    /// # Arguments
    ///
    /// * k - a function producing a [`Ord`] sorting criterion from a node data
    pub fn sort_leaves_by<K: std::fmt::Debug + Ord + Clone>(&mut self, k: impl Fn(&P) -> K) {
        let _ = self.rec_sort_by(self.root(), &k, true);
    }

    fn print_node<
        NodeFormatter: Fn(&P) -> S1,
        S1: Default + Display,
        EdgeFormatter: Fn(&E) -> S2,
        S2: Default + Display,
        O: Write,
    >(
        &self,
        o: &mut O,
        n: NodeHandle,
        indent: usize,
        f: &NodeFormatter,
        g: &EdgeFormatter,
    ) {
        writeln!(
            o,
            "{}{}{}",
            str::repeat(" ", indent),
            f(&self[n].data),
            self[n]
                .branch
                .as_ref()
                .map(|x| format!(":{}", g(x)))
                .unwrap_or_default(),
        )
        .unwrap();
        self.children(n)
            .unwrap()
            .iter()
            .for_each(|c| self.print_node(o, *c, indent + 4, f, g))
    }

    /// Print a text representation of the tree to the standard output, leveraging the given formatting functions.
    ///
    /// # Arguments
    ///
    /// * `node_printer` - A function producing a [`Display`]-able value from a node.
    /// * `edge_printer` - A function producing a [`Display`]-able value from an edge.
    pub fn print<
        NodeFormatter: Fn(&P) -> S1,
        S1: Default + Display,
        EdgeFormatter: Fn(&E) -> S2,
        S2: Default + Display,
    >(
        &self,
        node_printer: NodeFormatter,
        edge_printer: EdgeFormatter,
    ) {
        if !self.nodes.is_empty() {
            for root in self.roots() {
                self.print_node(
                    &mut io::stdout().lock(),
                    root,
                    0,
                    &node_printer,
                    &edge_printer,
                );
            }
        }
    }

    /// Print a text representation of the tree to the standard error, leveraging the given formatting functions.
    ///
    /// # Arguments
    ///
    /// * `node_printer` - A function producing a [`Display`]-able value from a node.
    /// * `edge_printer` - A function producing a [`Display`]-able value from an edge.
    pub fn eprint<
        NodeFormatter: Fn(&P) -> S1,
        S1: Default + Display,
        EdgeFormatter: Fn(&E) -> S2,
        S2: Default + Display,
    >(
        &self,
        node_printer: NodeFormatter,
        edge_printer: EdgeFormatter,
    ) {
        if !self.nodes.is_empty() {
            for root in self.roots() {
                self.print_node(
                    &mut io::stderr().lock(),
                    root,
                    0,
                    &node_printer,
                    &edge_printer,
                );
            }
        }
    }
}
impl<'a, P: Clone + Ord, D, E> Tree<P, D, E> {
    fn rec_sort(&'a mut self, n: NodeHandle, by_leaves: bool) -> P {
        let mut children = std::mem::take(self.children_mut(n).unwrap());
        for c in &children {
            self.rec_sort(*c, by_leaves);
        }
        children.sort_by_cached_key(|&c| self[c].data().clone());
        self[n].children = children;

        if by_leaves || self.children(n).unwrap().is_empty() {
            self[n].data().clone()
        } else {
            self[self.children(n).unwrap()[0]].data().clone()
        }
    }

    pub fn sort(&'a mut self) {
        let _ = self.rec_sort(self.root(), false);
    }

    pub fn sort_leaves(&'a mut self) {
        let _ = self.rec_sort(self.root(), true);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    // Standard test tree used across most tests:
    //
    //        root
    //       /    \
    //      a      b
    //     / \      \
    //    c   d      e
    //
    // root, a, b are inner nodes; c, d, e are leaves.
    // P = &'static str, D = (), E = f32
    fn sample() -> (
        Tree<&'static str, (), f32>,
        NodeHandle,
        NodeHandle,
        NodeHandle,
        NodeHandle,
        NodeHandle,
        NodeHandle,
    ) {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        let root = t.add_node(None, "root");
        let a = t.add_node(Some(root), "a");
        let b = t.add_node(Some(root), "b");
        let c = t.add_node(Some(a), "c");
        let d = t.add_node(Some(a), "d");
        let e = t.add_node(Some(b), "e");
        (t, root, a, b, c, d, e)
    }

    fn fmt_node(d: &&'static str) -> &'static str {
        *d
    }
    fn fmt_edge(e: &f32) -> String {
        format!("{e}")
    }

    #[test]
    fn new_tree_is_empty() {
        let t: Tree<i32, (), f32> = Tree::new();
        assert!(t.is_empty());
        assert_eq!(t.len(), 0);
    }

    #[test]
    fn default_tree_is_empty() {
        let t: Tree<i32, (), f32> = Tree::default();
        assert!(t.is_empty());
    }

    #[test]
    fn with_metadata_stores_value() {
        let t: Tree<i32, &str, f32> = Tree::with_metadata("hello");
        assert_eq!(*t.metadata(), "hello");
    }

    #[test]
    fn metadata_mut_updates_value() {
        let mut t: Tree<i32, i32, f32> = Tree::with_metadata(1);
        *t.metadata_mut() = 42;
        assert_eq!(*t.metadata(), 42);
    }

    #[test]
    fn first_node_becomes_root() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let id = t.add_node(None, 99);
        assert_eq!(t.root(), id);
        assert!(t.is_root(id));
    }

    #[test]
    fn add_node_increments_len() {
        let (t, _, _, _, _, _, _) = sample();
        assert_eq!(t.len(), 6);
    }

    #[test]
    fn add_child_records_parent() {
        let (t, root, a, _, _, _, _) = sample();
        assert_eq!(t.parent(a), Some(root));
    }

    #[test]
    fn add_child_appears_in_parent_children() {
        let (t, root, a, b, _, _, _) = sample();
        let ch = t.children(root).unwrap();
        assert!(ch.contains(&a));
        assert!(ch.contains(&b));
    }

    #[test]
    fn get_existing_node_ok() {
        let (t, root, _, _, _, _, _) = sample();
        assert!(t.get(root).is_ok());
    }

    #[test]
    fn get_missing_node_returns_err() {
        let (t, _, _, _, _, _, _) = sample();
        assert!(t.get(9999.into()).is_err());
    }

    #[test]
    fn get_mut_allows_modification() {
        let (mut t, _, _, _, c, _, _) = sample();
        t.get_mut(c).unwrap().set_data("modified");
        assert_eq!(*t[c].data(), "modified");
    }

    #[test]
    fn index_returns_correct_node() {
        let (t, root, _, _, _, _, _) = sample();
        assert_eq!(*t[root].data(), "root");
    }

    #[test]
    fn index_mut_modifies_node() {
        let (mut t, _, _, _, c, _, _) = sample();
        t[c].set_data("new");
        assert_eq!(*t[c].data(), "new");
    }

    #[test]
    fn nodes_iter_count() {
        let (t, _, _, _, _, _, _) = sample();
        assert_eq!(t.nodes().count(), 6);
    }

    #[test]
    fn leaves_iter_returns_only_leaves() {
        let (t, _, _, _, c, d, e) = sample();
        let mut leaves: Vec<_> = t.leaves().collect();
        leaves.sort_by_key(|n| **n);
        let mut expected = vec![c, d, e];
        expected.sort_by_key(|n| **n);
        assert_eq!(leaves, expected);
    }

    #[test]
    fn inners_returns_non_leaf_nodes() {
        let (t, root, a, b, _, _, _) = sample();
        let mut inners: Vec<_> = t.inners().collect();
        inners.sort_by_key(|n| **n);
        let mut expected = vec![root, a, b];
        expected.sort_by_key(|n| **n);
        assert_eq!(inners, expected);
    }

    #[test]
    fn nodes_mut_covers_all_nodes_and_allows_mutation() {
        let (mut t, _, _, _, c, _, _) = sample();
        assert_eq!(t.nodes_mut().count(), 6);
        for n in t.nodes_mut() {
            n.set_data("x");
        }
        assert_eq!(*t[c].data(), "x");
    }

    #[test]
    fn is_leaf_distinguishes_leaves_from_inner_nodes() {
        let (t, root, _, _, c, _, _) = sample();
        assert!(!t.is_leaf(root));
        assert!(t.is_leaf(c));
    }

    #[test]
    fn node_data_returns_payload() {
        let (t, _, a, _, _, _, _) = sample();
        assert_eq!(*t[a].data(), "a");
    }

    #[test]
    fn node_data_mut_modifies_payload() {
        let (mut t, _, a, _, _, _, _) = sample();
        *t[a].data_mut() = "changed";
        assert_eq!(*t[a].data(), "changed");
    }

    #[test]
    fn node_set_data_replaces_payload() {
        let (mut t, _, _, _, c, _, _) = sample();
        t[c].set_data("new_c");
        assert_eq!(*t[c].data(), "new_c");
    }

    #[test]
    fn node_children_slice_matches_added_children() {
        let (t, root, a, b, _, _, _) = sample();
        let ch = t.children(root).unwrap();
        assert_eq!(ch.len(), 2);
        assert!(ch.contains(&a) && ch.contains(&b));
    }

    #[test]
    fn node_branch_set_get_unset() {
        let (mut t, _, _, _, c, _, _) = sample();
        assert!(t[c].branch().is_none());
        t[c].set_branch(1.5_f32);
        assert_eq!(*t[c].branch().unwrap(), 1.5_f32);
        t[c].unset_branch();
        assert!(t[c].branch().is_none());
    }

    #[test]
    fn parent_of_root_is_none() {
        let (t, root, _, _, _, _, _) = sample();
        assert_eq!(t.parent(root), None);
    }

    #[test]
    fn parent_of_grandchild() {
        let (t, _, a, _, c, _, _) = sample();
        assert_eq!(t.parent(c), Some(a));
    }

    #[test]
    fn children_method_returns_direct_children() {
        let (t, _, a, _, c, d, _) = sample();
        let ch = t.children(a).unwrap();
        assert!(ch.contains(&c) && ch.contains(&d));
    }

    #[test]
    fn children_of_missing_node_is_err() {
        let (t, _, _, _, _, _, _) = sample();
        assert!(t.children(9999.into()).is_err());
    }

    #[test]
    fn new_node_is_leaf() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let root = t.add_node(None, 0);
        assert!(t.is_leaf(root));
        assert!(t.children(root).unwrap().is_empty());
    }

    #[test]
    fn plug_connects_free_standing_node() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let root = t.add_node(None, 0);
        let child = t.add_node(None, 1);
        t.plug(child, root).unwrap();
        assert_eq!(t.parent(child), Some(root));
        assert!(t.children(root).unwrap().contains(&child));
    }

    #[test]
    fn unplug_detaches_node_from_parent() {
        let (mut t, root, a, _, _, _, _) = sample();
        t.unplug(a).unwrap();
        assert_eq!(t.parent(a), None);
        assert!(!t.children(root).unwrap().contains(&a));
    }

    #[test]
    fn move_to_reparents_correctly() {
        let (mut t, _, a, b, c, _, _) = sample();
        t.move_to(c, b).unwrap();
        assert_eq!(t.parent(c), Some(b));
        assert!(!t.children(a).unwrap().contains(&c));
        assert!(t.children(b).unwrap().contains(&c));
    }

    #[test]
    fn move_node_reparents_correctly() {
        let (mut t, _, a, b, c, _, _) = sample();
        t.move_node(c, b).unwrap();
        assert_eq!(t.parent(c), Some(b));
        assert!(!t.children(a).unwrap().contains(&c));
        assert!(t.children(b).unwrap().contains(&c));
    }

    #[test]
    fn insert_between_intercepts_parent_child_edge() {
        let (mut t, root, a, _, _, _, _) = sample();
        let mid = t.add_node(None, "mid");
        t.insert_between(mid, root, a).unwrap();
        assert_eq!(t.parent(mid), Some(root));
        assert!(t.children(root).unwrap().contains(&mid));
        assert_eq!(t.parent(a), Some(mid));
        assert!(t.children(mid).unwrap().contains(&a));
    }

    #[test]
    fn delete_cleans_up_children_map() {
        let (mut t, _, a, _, c, _, _) = sample();
        t.delete_node(c).unwrap();
        assert!(t.get(c).is_err());
        assert!(!t.children(a).unwrap().contains(&c));
    }

    #[test]
    fn delete_leaf_removes_it_from_parent() {
        let (mut t, _, a, _, c, _, _) = sample();
        t.delete_node(c).unwrap();
        assert!(t.get(c).is_err());
        assert!(!t.children(a).unwrap().contains(&c));
    }

    #[test]
    fn delete_inner_node_removes_entire_subtree() {
        let (mut t, root, a, _, c, d, _) = sample();
        t.delete_node(a).unwrap();
        assert!(t.get(a).is_err());
        assert!(t.get(c).is_err());
        assert!(t.get(d).is_err());
        assert!(!t.children(root).unwrap().contains(&a));
    }

    #[test]
    fn delete_nodes_removes_multiple_leaves() {
        let (mut t, _, a, _, c, d, _) = sample();
        t.delete_nodes(&[c, d]).unwrap();
        assert!(t.get(c).is_err());
        assert!(t.get(d).is_err());
        assert!(t.children(a).unwrap().is_empty());
    }

    #[test]
    fn find_leaf_by_data() {
        let (t, _, _, _, c, _, _) = sample();
        assert_eq!(t.find_leaf(|d| *d == "c"), Some(c));
    }

    #[test]
    fn find_leaf_skips_inner_nodes() {
        let (t, _, _, _, _, _, _) = sample();
        assert_eq!(t.find_leaf(|d| *d == "root"), None);
    }

    #[test]
    fn find_leaf_returns_none_when_absent() {
        let (t, _, _, _, _, _, _) = sample();
        assert_eq!(t.find_leaf(|d| *d == "zzz"), None);
    }

    #[test]
    fn find_node_finds_inner_node() {
        let (t, _, a, _, _, _, _) = sample();
        assert_eq!(t.find_node(|d| *d == "a"), Some(a));
    }

    #[test]
    fn find_node_returns_none_when_absent() {
        let (t, _, _, _, _, _, _) = sample();
        assert_eq!(t.find_node(|d| *d == "zzz"), None);
    }

    #[test]
    fn find_child_returns_matching_direct_child() {
        let (t, root, a, _, _, _, _) = sample();
        assert_eq!(t.find_child(root, |d| *d == "a").unwrap(), Some(a));
    }

    #[test]
    fn find_child_returns_none_for_non_direct_descendant() {
        // "c" is a grandchild of root, not a direct child
        let (t, root, _, _, _, _, _) = sample();
        assert!(t.find_child(root, |d| *d == "c").unwrap().is_none());
    }

    #[test]
    fn find_child_on_missing_node_is_err() {
        let (t, _, _, _, _, _, _) = sample();
        assert!(t.find_child(9999.into(), |d| *d == "c").is_err());
    }

    #[test]
    fn ascendance_from_leaf_goes_to_root() {
        let (t, root, a, _, c, _, _) = sample();
        assert_eq!(t.ascendance(c), vec![c, a, root]);
    }

    #[test]
    fn ascendance_from_root_is_singleton() {
        let (t, root, _, _, _, _, _) = sample();
        assert_eq!(t.ascendance(root), vec![root]);
    }

    #[test]
    fn descendants_of_root_contains_all_other_nodes() {
        let (t, root, a, b, c, d, e) = sample();
        let desc = t.descendants(root);
        assert_eq!(desc.len(), 5);
        for id in [a, b, c, d, e] {
            assert!(desc.contains(&id));
        }
    }

    #[test]
    fn descendants_of_leaf_is_empty() {
        let (t, _, _, _, c, _, _) = sample();
        assert!(t.descendants(c).is_empty());
    }

    #[test]
    fn descendants_of_inner_node_covers_subtree() {
        let (t, _, a, _, c, d, _) = sample();
        let desc = t.descendants(a);
        assert_eq!(desc.len(), 2);
        assert!(desc.contains(&c) && desc.contains(&d));
    }

    #[test]
    fn leave_set_of_root_contains_all_leaves() {
        let (t, root, _, _, c, d, e) = sample();
        let ls = t.leave_set_of(root);
        assert_eq!(ls.len(), 3);
        assert!(ls.contains(&c) && ls.contains(&d) && ls.contains(&e));
    }

    #[test]
    fn leaves_of_subtree() {
        let (t, _, a, _, c, d, _) = sample();
        let mut lo = t.leaves_of(a);
        lo.sort_by_key(|n| **n);
        let mut expected = vec![c, d];
        expected.sort_by_key(|n| **n);
        assert_eq!(lo, expected);
    }

    #[test]
    fn cache_leaves_and_retrieve() {
        let (mut t, root, _, _, c, d, e) = sample();
        t.cache_leaves();
        let cached = t.cached_leaves_of(root);
        assert_eq!(cached.len(), 3);
        assert!(cached.contains(&c) && cached.contains(&d) && cached.contains(&e));
    }

    #[test]
    fn cached_leaves_of_vec_matches_leaves_of() {
        let (mut t, _, a, _, c, d, _) = sample();
        t.cache_leaves();
        let mut v = t.cached_leaves_of_vec(a);
        v.sort_by_key(|n| **n);
        let mut expected = vec![c, d];
        expected.sort_by_key(|n| **n);
        assert_eq!(v, expected);
    }

    #[test]
    fn cached_descendants_absent_before_any_cache_call() {
        let (t, root, _, _, _, _, _) = sample();
        assert!(t.cached_descendants(root).is_none());
    }

    #[test]
    fn cache_descendants_populates_all_nodes() {
        let (mut t, root, a, b, c, d, e) = sample();
        t.cache_descendants();
        let desc = t.cached_descendants(root).unwrap();
        assert_eq!(desc.len(), 5);
        for id in [a, b, c, d, e] {
            assert!(desc.contains(&id));
        }
    }

    #[test]
    fn cache_descendants_of_populates_subtree() {
        let (mut t, _, a, _, c, d, _) = sample();
        t.cache_descendants_of(a);
        let desc = t.cached_descendants(a).unwrap();
        assert!(desc.contains(&c) && desc.contains(&d));
    }

    #[test]
    fn mrca_empty_input_returns_root() {
        let (t, root, _, _, _, _, _) = sample();
        assert_eq!(t.mrca(std::iter::empty()).unwrap(), root);
    }

    #[test]
    fn mrca_single_node_returns_itself() {
        let (t, _, _, _, c, _, _) = sample();
        assert_eq!(t.mrca([c]).unwrap(), c);
    }

    #[test]
    fn mrca_of_two_siblings_is_their_parent() {
        let (t, _, a, _, c, d, _) = sample();
        assert_eq!(t.mrca([c, d]).unwrap(), a);
    }

    #[test]
    fn mrca_across_subtrees_is_root() {
        let (t, root, _, _, c, _, e) = sample();
        assert_eq!(t.mrca([c, e]).unwrap(), root);
    }

    #[test]
    fn mrca_when_queried_node_is_ancestor_of_first() {
        let (t, _, a, _, c, _, _) = sample();
        assert_eq!(t.mrca([c, a]).unwrap(), a);
    }

    #[test]
    fn node_depth_sums_branch_lengths_to_root() {
        let (mut t, _, _, _, c, _, _) = sample();
        let a = t.parent(c).unwrap();
        t[c].set_branch(1.0_f32);
        t[a].set_branch(2.0_f32);
        let depth = t.depth_of(c, &|e: &f32| *e);
        assert!((depth - 3.0_f32).abs() < 1e-6);
    }

    #[test]
    fn node_depth_without_branches_is_zero() {
        let (t, _, _, _, c, _, _) = sample();
        assert_eq!(t.depth_of(c, &|e: &f32| *e), 0.0);
    }

    #[test]
    fn node_depth_ignores_root_branch() {
        let (mut t, root, _, _, c, _, _) = sample();
        let a = t.parent(c).unwrap();
        t[c].set_branch(1.0_f32);
        t[a].set_branch(2.0_f32);
        t[root].set_branch(100.0_f32); // root has no parent edge; must not contribute
        let depth = t.depth_of(c, &|e: &f32| *e);
        assert!((depth - 3.0_f32).abs() < 1e-6);
    }

    #[test]
    fn topological_depth_of_root_is_zero() {
        let (t, root, _, _, _, _, _) = sample();
        assert_eq!(t.topological_depth_of(root).unwrap(), 0);
    }

    #[test]
    fn topological_depth_of_child_is_one() {
        let (t, _, a, _, _, _, _) = sample();
        assert_eq!(t.topological_depth_of(a).unwrap(), 1);
    }

    #[test]
    fn topological_depth_of_grandchild_is_two() {
        let (t, _, _, _, c, _, _) = sample();
        assert_eq!(t.topological_depth_of(c).unwrap(), 2);
    }

    #[test]
    fn topological_depth_of_missing_node_is_err() {
        let (t, _, _, _, _, _, _) = sample();
        assert!(t.topological_depth_of(9999.into()).is_err());
    }

    #[test]
    fn tree_topological_depth_of_sample() {
        let (t, _, _, _, _, _, _) = sample();
        let (_, d) = t.topological_depth().unwrap();
        assert_eq!(d, 2);
    }

    #[test]
    fn topological_depth_of_empty_tree_is_none() {
        let t: Tree<i32, (), f32> = Tree::new();
        assert!(t.topological_depth().is_none());
    }

    #[test]
    fn for_each_leave_visits_all_leaves() {
        let (t, _, _, _, _, _, _) = sample();
        let mut labels: Vec<&str> = Vec::new();
        t.for_each_leave(&mut |n: &Node<&'static str, f32>| {
            labels.push(*n.data());
        });
        labels.sort();
        assert_eq!(labels, vec!["c", "d", "e"]);
    }

    #[test]
    fn for_each_leave_mut_modifies_all_leaves() {
        let (mut t, _, _, _, c, d, e) = sample();
        t.for_each_leave_mut(&mut |n: &mut Node<&'static str, f32>| {
            n.set_data("leaf");
        });
        assert_eq!(*t[c].data(), "leaf");
        assert_eq!(*t[d].data(), "leaf");
        assert_eq!(*t[e].data(), "leaf");
    }

    #[test]
    fn collapse_if_reattaches_children_to_grandparent() {
        let (mut t, root, _, b, _, _, e) = sample();
        let a = t.find_node(|d| *d == "a").unwrap();
        t.delete_node(a).unwrap();
        t.collapse_if(&|n: &Node<&'static str, f32>| *n.data() == "b");
        assert!(t.get(b).is_err(), "b should have been collapsed");
        assert_eq!(t.parent(e), Some(root), "e should be re-attached to root");
    }

    #[test]
    fn collapse_if_never_selects_root() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let root = t.add_node(None, 0);
        let _child = t.add_node(Some(root), 1);
        t.collapse_if(&|_: &Node<i32, f32>| true); // matches root — must be skipped
        assert!(t.get(root).is_ok());
    }

    #[test]
    fn filter_removes_non_matching_subtree() {
        let (mut t, root, a, b, c, d, e) = sample();
        t.filter(|n: &Node<&'static str, f32>| *n.data() != "b");
        assert!(t.get(root).is_ok() && t.get(a).is_ok());
        assert!(t.get(c).is_ok() && t.get(d).is_ok());
        assert!(t.get(b).is_err() && t.get(e).is_err());
    }

    #[test]
    fn filter_nodes_removes_by_id() {
        let (mut t, root, a, b, c, d, e) = sample();
        t.filter_nodes(|id| id != b);
        assert!(t.get(root).is_ok() && t.get(a).is_ok());
        assert!(t.get(c).is_ok() && t.get(d).is_ok());
        assert!(t.get(b).is_err() && t.get(e).is_err());
    }

    #[test]
    fn consolidate_removes_empty_leaf() {
        let mut t: Tree<Option<i32>, (), f32> = Tree::new();
        let root = t.add_node(None, Some(1));
        let _empty = t.add_node(Some(root), None);
        let real = t.add_node(Some(root), Some(2));
        t.consolidate(|p| p.is_none());
        assert!(t.get(real).is_ok());
        assert_eq!(t.children(root).unwrap().len(), 1);
    }

    #[test]
    fn consolidate_compresses_single_child_pass_through() {
        // root -> pass (empty, 1 child) -> leaf  =>  root -> leaf
        let mut t: Tree<Option<i32>, (), f32> = Tree::new();
        let root = t.add_node(None, Some(1));
        let pass = t.add_node(Some(root), None);
        let leaf = t.add_node(Some(pass), Some(2));
        t.consolidate(|p| p.is_none());
        assert!(
            t.get(pass).is_err(),
            "pass-through node should be collapsed"
        );
        assert_eq!(t.parent(leaf), Some(root));
    }

    #[test]
    fn sort_orders_root_children() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let root = t.add_node(None, 0);
        t.add_node(Some(root), 3);
        t.add_node(Some(root), 1);
        t.add_node(Some(root), 2);
        t.sort();
        let vals: Vec<i32> = t
            .children(root)
            .unwrap()
            .iter()
            .map(|&id| *t[id].data())
            .collect();
        assert_eq!(vals, vec![1, 2, 3]);
    }

    #[test]
    fn sort_leaves_orders_root_children() {
        let mut t: Tree<i32, (), f32> = Tree::new();
        let root = t.add_node(None, 0);
        t.add_node(Some(root), 3);
        t.add_node(Some(root), 1);
        t.add_node(Some(root), 2);
        t.sort_leaves();
        let vals: Vec<i32> = t
            .children(root)
            .unwrap()
            .iter()
            .map(|&id| *t[id].data())
            .collect();
        assert_eq!(vals, vec![1, 2, 3]);
    }

    #[test]
    fn sort_by_orders_root_children_by_key() {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        let root = t.add_node(None, "root");
        t.add_node(Some(root), "b");
        t.add_node(Some(root), "a");
        t.add_node(Some(root), "c");
        t.sort_by(|&s| s);
        let labels: Vec<_> = t
            .children(root)
            .unwrap()
            .iter()
            .map(|&id| *t[id].data())
            .collect();
        assert_eq!(labels, vec!["a", "b", "c"]);
    }

    #[test]
    fn sort_leaves_by_orders_root_children_by_key() {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        let root = t.add_node(None, "root");
        t.add_node(Some(root), "b");
        t.add_node(Some(root), "a");
        t.add_node(Some(root), "c");
        t.sort_leaves_by(|&s| s);
        let labels: Vec<_> = t
            .children(root)
            .unwrap()
            .iter()
            .map(|&id| *t[id].data())
            .collect();
        assert_eq!(labels, vec!["a", "b", "c"]);
    }

    #[test]
    fn sort_by_is_fully_recursive() {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        let root = t.add_node(None, "root");
        let a = t.add_node(Some(root), "a");
        t.add_node(Some(a), "d");
        t.add_node(Some(a), "b");
        t.add_node(Some(a), "c");
        t.sort_by(|d: &&'static str| *d);
        let labels: Vec<_> = t
            .children(a)
            .unwrap()
            .iter()
            .map(|&id| *t[id].data())
            .collect();
        assert_eq!(labels, vec!["b", "c", "d"]);
    }

    #[test]
    fn to_newick_single_leaf() {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        t.add_node(None, "A");
        assert_eq!(t.to_newick(fmt_node, |e: &f32| *e), "A;");
    }

    #[test]
    fn to_newick_contains_leaf_names_and_ends_with_semicolon() {
        let (t, _, _, _, _, _, _) = sample();
        let s = t.to_newick(fmt_node, |e: &f32| *e);
        assert!(s.ends_with(';'));
        for name in ["c", "d", "e"] {
            assert!(s.contains(name), "missing {name} in newick: {s}");
        }
    }

    #[test]
    fn to_newick_includes_branch_lengths() {
        let mut t: Tree<&'static str, (), f32> = Tree::new();
        let root = t.add_node(None, "root");
        let leaf = t.add_node(Some(root), "leaf");
        t[leaf].set_branch(2.5_f32);
        let s = t.to_newick(fmt_node, |e: &f32| *e);
        assert!(s.contains("2.5"), "branch length missing from: {s}");
    }

    #[test]
    fn render_to_string_contains_all_node_labels() {
        let (t, _, _, _, _, _, _) = sample();
        let s = t.to_string(fmt_node, fmt_edge, false);
        for name in ["root", "a", "b", "c", "d", "e"] {
            assert!(s.contains(name), "missing {name}");
        }
    }

    #[test]
    fn render_to_string_leaves_only_omits_inner_node_labels() {
        let (t, _, _, _, _, _, _) = sample();
        let s = t.to_string(fmt_node, fmt_edge, true);
        assert!(!s.contains("root"), "inner node 'root' should not appear");
        for leaf in ["c", "d", "e"] {
            assert!(s.contains(leaf), "missing leaf {leaf}");
        }
    }
}