intrex 0.2.0

//! Immutable binary tree accessor.
use core::ops::Bound;

use crate::node_data::{NodesDataLend, NodesDataLendGat};

use super::*;

mod iter;

pub use iter::*;

/// Provides the hidden error type for [`TreeAccessor::validate`].
// FIXME: Replace the return type with RPIT when `precise_capturing_of_types` is
// stabilized (rust-lang/rust#130043)
pub(crate) mod validate_error {
    #[derive(thiserror::Error, Debug)]
    pub enum OpaqueError<Index: core::fmt::Debug> {
        #[error("root node {0:?} has parent {1:?}, expected `None`")]
        RootHasParent(Index, Index),
        #[error("node {0:?} has child {1:?}, but the child's parent is {2:?}")]
        ChildParentMismatch(Index, Index, Option<Index>),
    }

    #[derive(thiserror::Error, Debug)]
    pub enum BstOpaqueError<Index: core::fmt::Debug, Data: core::fmt::Debug> {
        #[error(
            "node {ancestor:?}'s left descendant {node:?} \
            has key {node_data} not less than {ancestor_data:?}"
        )]
        NotLess {
            ancestor: Index,
            ancestor_data: Data,
            node: Index,
            node_data: Data,
        },
        #[error(
            "node {ancestor:?}'s right descendant {node:?} \
            has key {node_data} not greater than {ancestor_data:?}"
        )]
        NotGreater {
            ancestor: Index,
            ancestor_data: Data,
            node: Index,
            node_data: Data,
        },
    }
}

impl<Index> Tree<Index> {
    /// Create an accessor to the tree, using `Nodes: `[`NodesLink`] to access
    /// nodes.
    #[inline]
    pub fn read<Nodes>(&self, nodes: Nodes) -> TreeAccessor<'_, Nodes, Index>
    where
        Nodes: NodesLink<Index>,
    {
        TreeAccessor { tree: self, nodes }
    }
}

/// Accessor to a binary tree.
#[derive(Debug)]
pub struct TreeAccessor<'head, Nodes, Index> {
    tree: &'head Tree<Index>,
    nodes: Nodes,
}

impl<'tree, Nodes, Index> Clone for TreeAccessor<'tree, Nodes, Index>
where
    Nodes: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        TreeAccessor {
            tree: self.tree,
            nodes: self.nodes.clone(),
        }
    }
}

impl<'tree, Nodes, Index> Copy for TreeAccessor<'tree, Nodes, Index> where Nodes: Copy {}

/// # Basic Operations
impl<'tree, Nodes, Index> TreeAccessor<'tree, Nodes, Index>
where
    Nodes: NodesLink<Index>,
    Index: PartialEq + Clone,
{
    /// Borrow the node accessor.
    #[inline]
    pub fn nodes(&self) -> &Nodes {
        &self.nodes
    }

    /// Mutably borrow the node accessor.
    #[inline]
    pub fn nodes_mut(&mut self) -> &mut Nodes {
        &mut self.nodes
    }

    /// Borrow the tree root.
    #[inline]
    pub fn tree(&self) -> &'tree Tree<Index> {
        self.tree
    }

    /// Check if the node is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.tree.is_empty()
    }

    /// Get the first (leftmost) element's index.
    #[inline]
    pub fn front_index(&self) -> Option<Index> {
        self.front_index_in(self.tree.root.clone())
    }

    /// Get the last (rightmost) element's index.
    #[inline]
    pub fn back_index(&self) -> Option<Index> {
        self.back_index_in(self.tree.root.clone())
    }

    /// Get the first (smallest) child's index in `node`'s subtree.
    #[inline]
    fn front_index_in(&self, node: Option<Index>) -> Option<Index>
    where
        Index: Clone,
    {
        core::iter::successors(node, |i| self.nodes.node_left(i.clone())).last()
    }

    /// Get the last (largest) child's index in `node`'s subtree.
    #[inline]
    fn back_index_in(&self, node: Option<Index>) -> Option<Index>
    where
        Index: Clone,
    {
        core::iter::successors(node, |i| self.nodes.node_right(i.clone())).last()
    }

    /// Borrow the first element.
    #[doc(alias = "first")]
    #[inline]
    pub fn front(&self) -> Option<<Nodes as NodesDataLendGat<'_, Index>>::Data>
    where
        Nodes: NodesDataLend<Index>,
    {
        self.front_index().map(|p| self.nodes.node_data_lend(p))
    }

    /// Borrow the last element.
    #[doc(alias = "last")]
    #[inline]
    pub fn back(&self) -> Option<<Nodes as NodesDataLendGat<'_, Index>>::Data>
    where
        Nodes: NodesDataLend<Index>,
    {
        self.back_index().map(|p| self.nodes.node_data_lend(p))
    }

    /// Find the next in-order neighbor of the element at index `node`.
    #[inline]
    pub fn next_index(&self, node: Index) -> Option<Index> {
        next_index(&self.nodes, node)
    }

    /// Find the previous in-order neighbor of the element at index `node`.
    #[inline]
    pub fn prev_index(&self, node: Index) -> Option<Index> {
        prev_index(&self.nodes, node)
    }

    /// Read a [`Slot`].
    #[inline]
    pub fn slot(&self, slot: Slot<Index>) -> Option<Index> {
        match slot {
            Slot::Root => self.tree.root.clone(),
            Slot::Left(node) => self.nodes.node_left(node),
            Slot::Right(node) => self.nodes.node_right(node),
        }
    }

    /// Find the [`Slot`] storing a given in-tree node `node`.
    #[inline]
    pub fn parent_slot(&self, node: Index) -> Slot<Index> {
        match self.nodes.node_parent(node.clone()) {
            None => Slot::Root,
            Some(parent) => {
                if self.nodes.node_left(parent.clone()).as_ref() == Some(&node) {
                    Slot::Left(parent)
                } else {
                    Slot::Right(parent)
                }
            }
        }
    }

    /// Check integrity of the binary tree structure.
    #[track_caller]
    pub fn validate(&self) -> Result<(), validate_error::OpaqueError<Index>>
    where
        Index: core::fmt::Debug,
    {
        use validate_error::OpaqueError as Error;

        let Some(root) = &self.tree.root else {
            return Ok(());
        };

        if let Some(parent) = self.nodes.node_parent(root.clone()) {
            return Err(Error::RootHasParent(root.clone(), parent));
        }

        for index in self.indices() {
            if let Some(left) = self.nodes.node_left(index.clone()) {
                let actual_parent = self.nodes.node_parent(left.clone());
                if actual_parent.as_ref() != Some(&index) {
                    return Err(Error::ChildParentMismatch(index, left, actual_parent));
                }
            }
            if let Some(right) = self.nodes.node_right(index.clone()) {
                let actual_parent = self.nodes.node_parent(right.clone());
                if actual_parent.as_ref() != Some(&index) {
                    return Err(Error::ChildParentMismatch(index, right, actual_parent));
                }
            }
        }

        Ok(())
    }

    /// Normalize `range` into `(inclusive_range, next)`. May panic if it does not
    /// follow [the range rules](self#index-ranges).
    pub(super) fn resolve_index_range(
        &self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> (Option<[Index; 2]>, Option<Index>)
    where
        Index: Clone + PartialEq,
    {
        let [start, end] = [range.start_bound(), range.end_bound()];

        let out_next = match end {
            ops::Bound::Included(Some(i)) => self.next_index(i.clone()),
            ops::Bound::Included(None) => panic!("end bound must not be `Included(None)`"),
            ops::Bound::Excluded(i) => i.clone(),
            ops::Bound::Unbounded => None,
        };

        let Some(start_incl) = (match start {
            ops::Bound::Included(i) => i.clone(),
            ops::Bound::Excluded(Some(i)) => {
                assert!(
                    start != end,
                    "both-exclusive range must not have overlapping endpoints"
                );

                if let ops::Bound::Included(Some(j)) = end
                    && j == i
                {
                    return (None, out_next);
                }

                self.next_index(i.clone())
            }
            ops::Bound::Excluded(None) => panic!("start bound must not be `Excluded(None)`"),
            ops::Bound::Unbounded => self.front_index(),
        }) else {
            return (None, out_next);
        };

        let Some(end_incl) = (match end {
            ops::Bound::Included(Some(i)) => Some(i.clone()),
            ops::Bound::Included(None) => panic!("end bound must not be `Included(None)`"),
            ops::Bound::Excluded(Some(i)) => {
                if *i == start_incl {
                    None
                } else {
                    self.prev_index(i.clone())
                }
            }
            ops::Bound::Unbounded | ops::Bound::Excluded(None) => self.back_index(),
        }) else {
            return (None, out_next);
        };

        (Some([start_incl, end_incl]), out_next)
    }
}

/// # BST Search Operations
///
/// The following methods assume `self` points to a valid binary search tree.
impl<'tree, Nodes, Index> TreeAccessor<'tree, Nodes, Index>
where
    Nodes: NodesLink<Index>,
    Index: PartialEq + Clone,
{
    /// Find the index of the node matching `key` within the BST.
    pub fn bst_find_index<Key>(&self, key: &Key) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        bst_slot_to_insert(
            &self.nodes,
            |nodes, node| nodes.cmp_node_key(node, key),
            self.tree.root.clone(),
        )
        .ok()
    }

    /// Find the slot where a node with `key` should be inserted within the BST.
    ///
    /// Returns `Ok(index)` if the node at `index` has the identical key.
    pub fn bst_slot_to_insert_key<Key>(&self, key: &Key) -> Result<Index, Slot<Index>>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        bst_slot_to_insert(
            &self.nodes,
            |nodes, node| nodes.cmp_node_key(node, key),
            self.tree.root.clone(),
        )
    }

    /// Find the slot where `new_node` should be inserted within the BST.
    ///
    /// Returns `Ok(index)` if the node at `index` has the identical key.
    pub fn bst_slot_to_insert_node<Key>(&self, new_node: Index) -> Result<Index, Slot<Index>>
    where
        Nodes: NodesCmp<Index>,
    {
        bst_slot_to_insert(
            &self.nodes,
            |nodes, node| nodes.cmp_nodes(node, new_node.clone()),
            self.tree.root.clone(),
        )
    }

    /// Find the index of the first node included in the given lower bound.
    ///
    /// See [`crate::rbtree::accessor::TreeAccessor::bst_lower_bound`] for
    /// examples based on a balanced binary search tree.
    pub fn bst_lower_bound<Key>(&self, bound: Bound<&Key>) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        match bound {
            Bound::Included(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Greater),
                    self.tree.root.clone(),
                ) {
                    // The `Ok(_)` arm is unreachable because the comparer
                    // never returns `Ordering::Eq`
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => Some(node),
                    Err(Slot::Right(node)) => self.next_index(node),
                }
            }
            Bound::Excluded(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Less),
                    self.tree.root.clone(),
                ) {
                    // The `Ok(_)` arm is unreachable because the comparer
                    // never returns `Ordering::Eq`
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => Some(node),
                    Err(Slot::Right(node)) => self.next_index(node),
                }
            }
            Bound::Unbounded => self.front_index(),
        }
    }

    /// Find the index of the first node excluded from the given upper bound.
    ///
    /// See [`crate::rbtree::accessor::TreeAccessor::bst_upper_bound`] for
    /// examples based on a balanced binary search tree.
    pub fn bst_upper_bound<Key>(&self, bound: Bound<&Key>) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        match bound {
            Bound::Included(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Less),
                    self.tree.root.clone(),
                ) {
                    // The `Ok(_)` arm is unreachable because the comparer
                    // never returns `Ordering::Eq`
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => Some(node),
                    Err(Slot::Right(node)) => self.next_index(node),
                }
            }
            Bound::Excluded(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Greater),
                    self.tree.root.clone(),
                ) {
                    // The `Ok(_)` arm is unreachable because the comparer
                    // never returns `Ordering::Eq`
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => Some(node),
                    Err(Slot::Right(node)) => self.next_index(node),
                }
            }
            Bound::Unbounded => None,
        }
    }

    /// Find the index of the last node included in the given upper bound.
    fn bst_upper_bound_incl<Key>(&self, bound: Bound<&Key>) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        match bound {
            Bound::Included(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Less),
                    self.tree.root.clone(),
                ) {
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => self.prev_index(node),
                    Err(Slot::Right(node)) => Some(node),
                }
            }
            Bound::Excluded(key) => {
                match bst_slot_to_insert(
                    &self.nodes,
                    |nodes, node| nodes.cmp_node_key(node, key).then(Ordering::Greater),
                    self.tree.root.clone(),
                ) {
                    Ok(_) => unreachable!(),
                    Err(Slot::Root) => None,
                    Err(Slot::Left(node)) => self.prev_index(node),
                    Err(Slot::Right(node)) => Some(node),
                }
            }
            Bound::Unbounded => self.back_index(),
        }
    }

    /// Normalize the key range `range` into `inclusive_range`.
    pub(super) fn bst_resolve_key_range<Key>(
        &self,
        range: impl ops::RangeBounds<Key>,
    ) -> Option<[Index; 2]>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        let [start, end] = [range.start_bound(), range.end_bound()];

        let start = self.bst_lower_bound(start)?;

        // Return an empty range if `start` is excluded by the end bound
        match end {
            Bound::Included(end) => {
                if self.nodes.cmp_node_key(start.clone(), end) == Ordering::Greater {
                    return None;
                }
            }
            Bound::Excluded(end) => {
                if self.nodes.cmp_node_key(start.clone(), end) != Ordering::Less {
                    return None;
                }
            }
            Bound::Unbounded => {}
        }

        let end = self.bst_upper_bound_incl(end)?;

        Some([start, end])
    }
}

/// # BST Validation
impl<'tree, Nodes, Index> TreeAccessor<'tree, Nodes, Index>
where
    Nodes: NodesLink<Index>,
    Index: PartialEq + Clone,
{
    /// Check integrity of the BST structure.
    ///
    /// This method does not check the invariants that are checked by
    /// [`Self::validate`].
    pub fn bst_validate<Data>(
        &self,
        mut map_data: impl FnMut(&Nodes, Index) -> Data,
    ) -> Result<(), validate_error::BstOpaqueError<Index, Data>>
    where
        Nodes: NodesCmp<Index>,
        Index: core::fmt::Debug,
        Data: core::fmt::Debug,
    {
        for ancestor in self.indices() {
            // Check descendants' values
            let mut right = false;
            for node in self.indices_index_range(
                self.front_index_in(Some(ancestor.clone()))
                    ..=self.back_index_in(Some(ancestor.clone())),
            ) {
                if node == ancestor {
                    right = true;
                    continue;
                }

                if right {
                    if self.nodes.cmp_nodes(node.clone(), ancestor.clone())
                        != core::cmp::Ordering::Greater
                    {
                        return Err(validate_error::BstOpaqueError::NotGreater {
                            ancestor_data: map_data(&self.nodes, ancestor.clone()),
                            ancestor,
                            node_data: map_data(&self.nodes, node.clone()),
                            node,
                        });
                    }
                } else if self.nodes.cmp_nodes(node.clone(), ancestor.clone())
                    != core::cmp::Ordering::Less
                {
                    return Err(validate_error::BstOpaqueError::NotLess {
                        ancestor_data: map_data(&self.nodes, ancestor.clone()),
                        ancestor,
                        node_data: map_data(&self.nodes, node.clone()),
                        node,
                    });
                }
            }
        }

        Ok(())
    }
}

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

    #[test]
    fn is_empty() {
        let (nodes, tree) = tree_from_str("_");
        assert!(tree.read(&nodes[..]).is_empty());

        let (nodes, tree) = tree_from_str("(4 _ _)");
        assert!(!tree.read(&nodes[..]).is_empty());
    }

    #[test]
    fn front() {
        let (nodes, tree) = tree_from_str("_");
        assert_eq!(tree.read(&nodes[..]).front(), None);

        let (nodes, tree) = tree_from_str("(1 _ _)");
        assert_eq!(tree.read(&nodes[..]).front(), Some(&1));

        let (nodes, tree) = tree_from_str("(2 (1 _ _) (3 _ _))");
        assert_eq!(tree.read(&nodes[..]).front(), Some(&1));

        let (nodes, tree) = tree_from_str("(3 (1 _ (2 _ _)) (4 _ _))");
        assert_eq!(tree.read(&nodes[..]).front(), Some(&1));
    }

    #[test]
    fn back() {
        let (nodes, tree) = tree_from_str("_");
        assert_eq!(tree.read(&nodes[..]).back(), None);

        let (nodes, tree) = tree_from_str("(1 _ _)");
        assert_eq!(tree.read(&nodes[..]).back(), Some(&1));

        let (nodes, tree) = tree_from_str("(2 (1 _ _) (3 _ _))");
        assert_eq!(tree.read(&nodes[..]).back(), Some(&3));

        let (nodes, tree) = tree_from_str("(3 (1 _ (2 _ _)) (4 _ _))");
        assert_eq!(tree.read(&nodes[..]).back(), Some(&4));
    }

    #[test]
    fn bst_validate() {
        let (nodes, tree) = tree_from_str("_");
        tree.read(&nodes[..])
            .bst_validate(|nodes, i| nodes[i].value)
            .unwrap();

        let (nodes, tree) = tree_from_str("(1 _ _)");
        tree.read(&nodes[..])
            .bst_validate(|nodes, i| nodes[i].value)
            .unwrap();

        let (nodes, tree) = tree_from_str("(2 (1 _ _) (3 _ _))");
        tree.read(&nodes[..])
            .bst_validate(|nodes, i| nodes[i].value)
            .unwrap();

        let (nodes, tree) = tree_from_str("(1 (2 _ _) (3 _ _))");
        assert!(matches!(
            tree.read(&nodes[..])
                .bst_validate(|nodes, i| nodes[i].value),
            Err(validate_error::BstOpaqueError::NotLess { .. })
        ));
    }

    #[test]
    fn bst_find_index() {
        let (nodes, tree) = tree_from_str("_");
        assert_eq!(tree.read(&nodes[..]).bst_find_index(&5), None,);

        let (nodes, tree) = tree_from_str("(30 (10 _ (20 _ _)) (40 _ _))");
        let accessor = tree.read(&nodes[..]);
        assert_eq!(accessor.bst_find_index(&5), None,);
        assert_eq!(accessor.bst_find_index(&35), None,);
        assert_eq!(accessor.bst_find_index(&45), None,);
        for value in [10, 20, 30, 40] {
            assert_eq!(
                nodes[accessor.bst_slot_to_insert_key(&value).unwrap()].value,
                value
            );
        }
    }

    #[test]
    fn bst_slot_to_insert_key() {
        let (nodes, tree) = tree_from_str("_");
        assert_eq!(
            tree.read(&nodes[..]).bst_slot_to_insert_key(&5),
            Err(Slot::Root)
        );

        let (nodes, tree) = tree_from_str("(30 (10 _ (20 _ _)) (40 _ _))");
        let accessor = tree.read(&nodes[..]);
        assert_eq!(
            accessor.bst_slot_to_insert_key(&5),
            Err(Slot::Left(accessor.bst_find_index(&10).unwrap()))
        );
        assert_eq!(
            accessor.bst_slot_to_insert_key(&25),
            Err(Slot::Right(accessor.bst_find_index(&20).unwrap()))
        );
        assert_eq!(
            accessor.bst_slot_to_insert_key(&35),
            Err(Slot::Left(accessor.bst_find_index(&40).unwrap()))
        );
    }
}