intrex 0.2.0

//! Immutable red-black tree accessor.
use core::ops::Bound;

use crate::{
    bintree::{NodesCmp, NodesCmpKey},
    node_data::{NodesDataLend, NodesDataLendGat},
};

use super::*;

mod 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)
mod validate_error {
    #[derive(thiserror::Error, Debug)]
    pub enum OpaqueError<Index: core::fmt::Debug> {
        #[error(transparent)]
        BinaryTree(crate::bintree::accessor::validate_error::OpaqueError<Index>),
        #[error("red node {0:?} has a red child {1:?}")]
        RedNodeHasRedChild(Index, Index),
        #[error("black height mismatch at node {0:?}: left = {1}, right = {2}")]
        BlackHeightMismatch(Index, usize, usize),
    }
}

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

/// Accessor to a red-black tree.
#[derive(Debug)]
pub struct TreeAccessor<'head, Nodes, Index> {
    raw: crate::bintree::accessor::TreeAccessor<'head, Nodes, Index>,
}

impl<'tree, Nodes, Index> Clone for TreeAccessor<'tree, Nodes, Index>
where
    Nodes: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        TreeAccessor {
            raw: self.raw.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: NodesRb<Index>,
    Index: PartialEq + Clone,
{
    /// Borrow the node accessor.
    #[inline]
    pub fn nodes(&self) -> &Nodes {
        self.raw.nodes()
    }

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

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

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

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

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

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

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

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

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

        self.raw.validate().map_err(Error::BinaryTree)?;

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

        self.validate_inner(root)?;

        Ok(())
    }

    fn validate_inner(&self, node: Index) -> Result<usize, validate_error::OpaqueError<Index>>
    where
        Index: core::fmt::Debug,
    {
        use validate_error::OpaqueError as Error;

        let color = self.nodes().node_color(node.clone());
        let left = self.nodes().node_left(node.clone());
        let right = self.nodes().node_right(node.clone());

        if color == Color::Red {
            if let Some(child) = &left
                && self.nodes().node_color(child.clone()) == Color::Red
            {
                return Err(Error::RedNodeHasRedChild(node, child.clone()));
            }

            if let Some(child) = &right
                && self.nodes().node_color(child.clone()) == Color::Red
            {
                return Err(Error::RedNodeHasRedChild(node, child.clone()));
            }
        }

        let left_black_height = match left {
            Some(child) => self.validate_inner(child)?,
            None => 0,
        };
        let right_black_height = match right {
            Some(child) => self.validate_inner(child)?,
            None => 0,
        };

        if left_black_height != right_black_height {
            return Err(Error::BlackHeightMismatch(
                node,
                left_black_height,
                right_black_height,
            ));
        }

        Ok(left_black_height + (color == Color::Black) as usize)
    }
}

/// # Red-Black Search Tree Operations
impl<'tree, Nodes, Index> TreeAccessor<'tree, Nodes, Index>
where
    Nodes: NodesRb<Index>,
    Index: PartialEq + Clone,
{
    /// Find the index of the node matching `key`.
    pub fn bst_find_index<Key>(&self, key: &Key) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        self.raw.bst_find_index(key)
    }

    /// Find the index of the first node included in the given lower bound.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use std::ops::Bound;
    /// use intrex::rbtree::{Tree, Link, map_link_cmp_mut};
    ///
    /// type Node = (i32, Link);
    ///
    /// // Key = index * 10
    /// let mut nodes: Vec<Node> = (0..=3)
    ///     .map(|i| (i * 10, Link::default()))
    ///     .collect();
    /// let mut tree = Tree::default();
    ///
    /// let mut callbacks = map_link_cmp_mut(
    ///     &mut nodes,
    ///     |x: &Node| &x.1,
    ///     |x: &mut Node| &mut x.1,
    ///     |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
    ///     |x: &Node, y: &i32| Ord::cmp(&x.0, y),
    /// );
    ///
    /// for i in 0..=3 {
    ///     tree.write(&mut callbacks).bst_insert_node(i);
    /// }
    ///
    /// let accessor = tree.read(&callbacks);
    /// assert_eq!(accessor.bst_lower_bound(Bound::Included(&-5)), Some(0));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Included(&0)), Some(0));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Included(&20)), Some(2));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Included(&25)), Some(3));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Included(&35)), None);
    ///
    /// assert_eq!(accessor.bst_lower_bound(Bound::Excluded(&-5)), Some(0));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Excluded(&0)), Some(1));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Excluded(&20)), Some(3));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Excluded(&25)), Some(3));
    /// assert_eq!(accessor.bst_lower_bound(Bound::Excluded(&30)), None);
    ///
    /// assert_eq!(accessor.bst_lower_bound(Bound::Unbounded), Some(0));
    /// ```
    #[inline]
    pub fn bst_lower_bound<Key>(&self, bound: Bound<&Key>) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        self.raw.bst_lower_bound(bound)
    }

    /// Find the index of the first node excluded from the given upper bound.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use std::ops::Bound;
    /// use intrex::rbtree::{Tree, Link, map_link_cmp_mut};
    ///
    /// type Node = (i32, Link);
    ///
    /// // Key = index * 10
    /// let mut nodes: Vec<Node> = (0..=3)
    ///     .map(|i| (i * 10, Link::default()))
    ///     .collect();
    /// let mut tree = Tree::default();
    ///
    /// let mut callbacks = map_link_cmp_mut(
    ///     &mut nodes,
    ///     |x: &Node| &x.1,
    ///     |x: &mut Node| &mut x.1,
    ///     |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
    ///     |x: &Node, y: &i32| Ord::cmp(&x.0, y),
    /// );
    ///
    /// for i in 0..=3 {
    ///     tree.write(&mut callbacks).bst_insert_node(i);
    /// }
    ///
    /// let accessor = tree.read(&callbacks);
    /// assert_eq!(accessor.bst_upper_bound(Bound::Included(&-5)), Some(0));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Included(&0)), Some(1));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Included(&20)), Some(3));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Included(&25)), Some(3));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Included(&35)), None);
    ///
    /// assert_eq!(accessor.bst_upper_bound(Bound::Excluded(&-5)), Some(0));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Excluded(&0)), Some(0));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Excluded(&20)), Some(2));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Excluded(&25)), Some(3));
    /// assert_eq!(accessor.bst_upper_bound(Bound::Excluded(&35)), None);
    ///
    /// assert_eq!(accessor.bst_upper_bound(Bound::Unbounded), None);
    /// ```
    #[inline]
    pub fn bst_upper_bound<Key>(&self, bound: Bound<&Key>) -> Option<Index>
    where
        Nodes: NodesCmpKey<Index, Key>,
    {
        self.raw.bst_upper_bound(bound)
    }
}

/// # BST Validation
impl<'tree, Nodes, Index> TreeAccessor<'tree, Nodes, Index>
where
    Nodes: NodesRb<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,
        map_data: impl FnMut(&Nodes, Index) -> Data,
    ) -> Result<(), crate::bintree::accessor::validate_error::BstOpaqueError<Index, Data>>
    where
        Nodes: NodesCmp<Index>,
        Index: core::fmt::Debug,
        Data: core::fmt::Debug,
    {
        self.raw.bst_validate(map_data)
    }
}