intrex 0.2.0

use crate::bintree::{NodesCmp, NodesCmpKey, NodesLink, NodesLinkMut, Slot};
use crate::node_data::{
    NodesData, NodesDataLend, NodesDataLendGat, NodesDataLendMut, NodesDataLendMutGat,
};

use super::*;

/// Read access for red-black tree node fields.
///
/// The parent and child node fields are accessed via the supertrait
/// [`NodesLink`].
///
/// This is one of [the node access traits](crate::rbtree#node-access-traits).
pub trait NodesRb<Index>: NodesLink<Index> {
    /// Get the color of a node.
    fn node_color(&self, node: Index) -> Color;
}

/// Forwarding implementation
impl<T, Index> NodesRb<Index> for &T
where
    T: ?Sized + NodesRb<Index>,
{
    #[inline]
    #[track_caller]
    fn node_color(&self, node: Index) -> Color {
        (**self).node_color(node)
    }
}

/// Forwarding implementation
impl<T, Index> NodesRb<Index> for &mut T
where
    T: ?Sized + NodesRb<Index>,
{
    #[inline]
    #[track_caller]
    fn node_color(&self, node: Index) -> Color {
        (**self).node_color(node)
    }
}

/// Write access for red-black tree node fields.
///
/// The parent and child node fields are accessed via the supertrait
/// [`NodesLinkMut`].
///
/// This is one of [the node access traits](crate::rbtree#node-access-traits).
pub trait NodesRbMut<Index>: NodesLinkMut<Index> + NodesRb<Index> {
    /// Set the color of a node.
    fn set_node_color(&mut self, node: Index, color: Color);

    /// Called before left rotation is performed by
    /// [`accessor_mut::TreeAccessorMut`] on `node`.
    #[inline]
    fn pre_rotate_left(&mut self, node: Index) {
        _ = node;
    }

    /// Called before right rotation is performed by
    /// [`accessor_mut::TreeAccessorMut`] on `node`.
    #[inline]
    fn pre_rotate_right(&mut self, node: Index) {
        _ = node;
    }

    /// Called after an empty [`Slot`] is filled with a new childless node.
    #[inline]
    fn post_set_slot(&mut self, node: Index) {
        _ = node;
    }

    /// Called before a childless node is removed.
    #[inline]
    fn pre_clear_slot(&mut self, node: Index, parent_slot: Slot<Index>) {
        _ = (node, parent_slot);
    }

    /// Called before two in-tree nodes are swapped while preserving the tree
    /// structure
    /// ([`crate::bintree::accessor_mut::TreeAccessorMut::swap_nodes`]).
    ///
    /// `node1` is never equal to `node2`.
    #[inline]
    fn pre_swap_nodes(&mut self, node1: Index, node2: Index) {
        _ = (node1, node2);
    }

    /// Called after an in-tree node is replaced with an out-of-tree node while
    /// preserving the tree structure
    /// ([`crate::bintree::accessor_mut::TreeAccessorMut::replace_node`]).
    #[inline]
    fn post_replace_node(&mut self, node: Index, new_node: Index) {
        _ = (node, new_node);
    }
}

/// Forwarding implementation
impl<T, Index> NodesRbMut<Index> for &mut T
where
    T: ?Sized + NodesRbMut<Index>,
{
    #[inline]
    #[track_caller]
    fn set_node_color(&mut self, node: Index, color: Color) {
        (**self).set_node_color(node, color)
    }

    #[inline]
    fn pre_rotate_left(&mut self, node: Index) {
        (**self).pre_rotate_left(node)
    }

    #[inline]
    fn pre_rotate_right(&mut self, node: Index) {
        (**self).pre_rotate_right(node)
    }

    #[inline]
    fn post_set_slot(&mut self, node: Index) {
        (**self).post_set_slot(node)
    }

    #[inline]
    fn pre_clear_slot(&mut self, node: Index, parent_slot: Slot<Index>) {
        (**self).pre_clear_slot(node, parent_slot)
    }

    #[inline]
    fn pre_swap_nodes(&mut self, node1: Index, node2: Index) {
        (**self).pre_swap_nodes(node1, node2)
    }

    #[inline]
    fn post_replace_node(&mut self, node: Index, new_node: Index) {
        (**self).post_replace_node(node, new_node)
    }
}

/// A [`NodesRb`] implementation that looks up a red-black tree node by
/// `pool[index]` and uses provided closures to borrow its [`Link`] and
/// compare elements.
#[derive(Debug)]
pub struct NodesWithMapLink<'pool, Pool: ?Sized, MapLink, Cmp, CmpKey> {
    /// The underlying node pool.
    pub pool: &'pool Pool,
    /// The link borrow function.
    pub map_link: MapLink,
    /// The node-node comparison function.
    pub cmp: Cmp,
    /// The node-key comparison function.
    pub cmp_key: CmpKey,
}

/// A [`NodesRbMut`] implementation that looks up a red-black tree node by
/// `pool[index]` and uses provided closures to mutably borrow its
/// [`Link`] and compare elements.
#[derive(Debug)]
pub struct NodesWithMapLinkMut<'pool, Pool: ?Sized, MapLink, MapLinkMut, Cmp, CmpKey> {
    /// The underlying node pool.
    pub pool: &'pool mut Pool,
    /// The link borrow function.
    pub map_link: MapLink,
    /// The mutable link borrow function.
    pub map_link_mut: MapLinkMut,
    /// The node-node comparison function.
    pub cmp: Cmp,
    /// The node-key comparison function.
    pub cmp_key: CmpKey,
}

/// Construct a [`NodesWithMapLink`].
///
/// # Rationale
///
/// This may look equivalent to direct construction of [`NodesWithMapLink`],
/// but it is actually necessary for the compiler to deduce the correct lifetime
/// relationship for closures in some cases.
///
/// # Examples
///
/// Using `map_link_cmp` to construct a read accessor and call
/// [`accessor::TreeAccessor::bst_find_index`]:
///
/// ```rust
/// use intrex::rbtree::{Tree, Link, map_link_cmp, map_link_cmp_mut};
/// use std::ops::Bound;
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = (0..4).map(|i| (i, Link::default())).collect();
/// let mut tree = Tree::default();
///
/// // Insert nodes using the mutable accessor
/// {
///     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..4 {
///         tree.write(&mut callbacks).bst_insert_node(i);
///     }
/// }
///
/// // Read using the immutable accessor
/// let callbacks = map_link_cmp(
///     &mut nodes,
///     |x: &Node| &x.1,
///     |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
///     |x: &Node, y: &i32| Ord::cmp(&x.0, y),
/// );
/// assert_eq!(tree.read(&callbacks).bst_find_index(&2), Some(2));
/// ```
///
/// Direct construction fails:
///
/// ```compile_fail,E0599
/// use intrex::rbtree::{Tree, Link, NodesWithMapLink};
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = (0..4).map(|i| (i, Link::default())).collect();
/// let tree = Tree::default();
///
/// let callbacks = NodesWithMapLink {
///     pool: &mut nodes,
///     map_link: |x: &Node| &x.1,
///     cmp: |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
///     cmp_key: |x: &Node, y: &i32| Ord::cmp(&x.0, y),
/// };
/// let _ = tree.read(&callbacks);
/// ```
///
/// Fully specifying the closure signature does not resolve the error:
///
/// ```compile_fail,E0599
/// use intrex::rbtree::{Tree, Link, NodesWithMapLink};
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = (0..4).map(|i| (i, Link::default())).collect();
/// let tree = Tree::default();
///
/// let callbacks = NodesWithMapLink {
///     pool: &nodes,
///     map_link: |x: &Node| -> &Link { &x.1 },
///     cmp: |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
///     cmp_key: |x: &Node, y: &i32| Ord::cmp(&x.0, y),
/// };
/// let _ = tree.read(&callbacks);
/// ```
#[inline]
pub fn map_link_cmp<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element, Key>(
    pool: &'pool Pool,
    map_link: MapLink,
    cmp: Cmp,
    cmp_key: CmpKey,
) -> NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Link<Index>,
    Cmp: Fn(&'pool Element, &'pool Element) -> core::cmp::Ordering,
    CmpKey: Fn(&'pool Element, &Key) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    NodesWithMapLink {
        pool,
        map_link,
        cmp,
        cmp_key,
    }
}

/// Construct a [`NodesWithMapLinkMut`].
///
/// # Rationale
///
/// This may look equivalent to direct construction of [`NodesWithMapLinkMut`],
/// but it is actually necessary for the compiler to deduce the correct lifetime
/// relationship for closures in some cases.
///
/// # Examples
///
/// Using `map_link_cmp_mut` to construct a mutable accessor and call
/// [`accessor_mut::TreeAccessorMut::bst_insert_node`]:
///
/// ```rust
/// use intrex::rbtree::{Tree, Link, map_link_cmp_mut};
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = vec![(0, Link::default())];
/// 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),
/// );
/// tree.write(&mut callbacks).bst_insert_node(0);
/// ```
///
/// Direct construction fails:
///
/// ```compile_fail,E0599
/// use intrex::rbtree::{Tree, Link, NodesWithMapLinkMut};
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = vec![(0, Link::default())];
/// let mut tree = Tree::default();
///
/// let mut callbacks = NodesWithMapLinkMut {
///     pool: &mut nodes,
///     map_link: |x: &Node| &x.1,
///     map_link_mut: |x: &mut Node| &mut x.1,
///     cmp: |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
///     cmp_key: |x: &Node, y: &i32| Ord::cmp(&x.0, y),
/// };
/// tree.write(&mut callbacks).bst_insert_node(0);
/// ```
///
/// Fully specifying the closure signature does not resolve the error:
///
/// ```compile_fail,E0599
/// use intrex::rbtree::{Tree, Link, NodesWithMapLinkMut};
///
/// type Node = (i32, Link);
/// let mut nodes: Vec<Node> = vec![(0, Link::default())];
/// let mut tree = Tree::default();
///
/// let mut callbacks = NodesWithMapLinkMut {
///     pool: &mut nodes,
///     map_link: |x: &Node| -> &Link { &x.1 },
///     map_link_mut: |x: &mut Node| -> &mut Link { &mut x.1 },
///     cmp: |x: &Node, y: &Node| Ord::cmp(&x.0, &y.0),
///     cmp_key: |x: &Node, y: &i32| Ord::cmp(&x.0, y),
/// };
/// tree.write(&mut callbacks).bst_insert_node(0);
/// ```
#[inline]
pub fn map_link_cmp_mut<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element, Key>(
    pool: &'pool mut Pool,
    map_link: MapLink,
    map_link_mut: MapLinkMut,
    cmp: Cmp,
    cmp_key: CmpKey,
) -> NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    MapLink: Fn(&Element) -> &Link<Index>,
    MapLinkMut: Fn(&mut Element) -> &mut Link<Index>,
    Cmp: Fn(&Element, &Element) -> core::cmp::Ordering,
    CmpKey: Fn(&Element, &Key) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    NodesWithMapLinkMut {
        pool,
        map_link,
        map_link_mut,
        cmp,
        cmp_key,
    }
}

impl<'pool, Pool: ?Sized, MapLink, Cmp, CmpKey> Clone
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    MapLink: Clone,
    Cmp: Clone,
    CmpKey: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        NodesWithMapLink {
            pool: self.pool,
            map_link: self.map_link.clone(),
            cmp: self.cmp.clone(),
            cmp_key: self.cmp_key.clone(),
        }
    }
}

impl<'pool, Pool: ?Sized, MapLink, Cmp, CmpKey> Copy
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    MapLink: Copy,
    Cmp: Copy,
    CmpKey: Copy,
{
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesLink<Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn node_parent(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).parent.clone()
    }

    #[inline]
    #[track_caller]
    fn node_left(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).left.clone()
    }

    #[inline]
    #[track_caller]
    fn node_right(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).right.clone()
    }
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesCmp<Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    Cmp: Fn(&'pool Element, &'pool Element) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn cmp_nodes(&self, a: Index, b: Index) -> core::cmp::Ordering {
        (self.cmp)(&self.pool[a], &self.pool[b])
    }
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Key, Element> NodesCmpKey<Index, Key>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    CmpKey: Fn(&'pool Element, &Key) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn cmp_node_key(&self, node: Index, key: &Key) -> core::cmp::Ordering {
        (self.cmp_key)(&self.pool[node], key)
    }
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesRb<Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn node_color(&self, node: Index) -> Color {
        (self.map_link)(&self.pool[node]).color
    }
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesData<Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Link<Index>,
    Element: 'pool,
    Index: 'pool,
{
    type Data = &'pool Element;

    #[inline]
    #[track_caller]
    fn node_data(&self, node: Index) -> Self::Data {
        &self.pool[node]
    }
}

impl<'this, 'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesDataLendGat<'this, Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    type Data = &'pool Element;
}

impl<'pool, Index, Pool, MapLink, Cmp, CmpKey, Element> NodesDataLend<Index>
    for NodesWithMapLink<'pool, Pool, MapLink, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    #[inline]
    #[track_caller]
    fn node_data_lend(&self, node: Index) -> &'pool Element {
        &self.pool[node]
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesLink<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    MapLink: Fn(&Element) -> &Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn node_parent(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).parent.clone()
    }

    #[inline]
    #[track_caller]
    fn node_left(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).left.clone()
    }

    #[inline]
    #[track_caller]
    fn node_right(&self, node: Index) -> Option<Index> {
        (self.map_link)(&self.pool[node]).right.clone()
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesCmp<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    Cmp: Fn(&Element, &Element) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn cmp_nodes(&self, a: Index, b: Index) -> core::cmp::Ordering {
        (self.cmp)(&self.pool[a], &self.pool[b])
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Key, Element> NodesCmpKey<Index, Key>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    CmpKey: Fn(&Element, &Key) -> core::cmp::Ordering,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn cmp_node_key(&self, node: Index, key: &Key) -> core::cmp::Ordering {
        (self.cmp_key)(&self.pool[node], key)
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesLinkMut<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    MapLink: Fn(&Element) -> &Link<Index>,
    MapLinkMut: Fn(&mut Element) -> &mut Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn set_node_parent(&mut self, node: Index, parent: Option<Index>) {
        (self.map_link_mut)(&mut self.pool[node]).parent = parent;
    }

    #[inline]
    #[track_caller]
    fn set_node_left(&mut self, node: Index, left: Option<Index>) {
        (self.map_link_mut)(&mut self.pool[node]).left = left;
    }

    #[inline]
    #[track_caller]
    fn set_node_right(&mut self, node: Index, right: Option<Index>) {
        (self.map_link_mut)(&mut self.pool[node]).right = right;
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesRb<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    MapLink: Fn(&Element) -> &Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn node_color(&self, node: Index) -> Color {
        (self.map_link)(&self.pool[node]).color
    }
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesRbMut<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    MapLink: Fn(&Element) -> &Link<Index>,
    MapLinkMut: Fn(&mut Element) -> &mut Link<Index>,
    Element: 'pool,
    Index: Clone + 'pool,
{
    #[inline]
    #[track_caller]
    fn set_node_color(&mut self, node: Index, color: Color) {
        (self.map_link_mut)(&mut self.pool[node]).color = color;
    }
}

impl<'this, 'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element>
    NodesDataLendGat<'this, Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    type Data = &'this Element;
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesDataLend<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::Index<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    #[inline]
    #[track_caller]
    fn node_data_lend(&self, node: Index) -> &Element {
        &self.pool[node]
    }
}

impl<'this, 'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element>
    NodesDataLendMutGat<'this, Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    type Data = &'this mut Element;
}

impl<'pool, Index, Pool, MapLink, MapLinkMut, Cmp, CmpKey, Element> NodesDataLendMut<Index>
    for NodesWithMapLinkMut<'pool, Pool, MapLink, MapLinkMut, Cmp, CmpKey>
where
    Pool: ?Sized + core::ops::IndexMut<Index, Output = Element>,
    Element: 'pool,
    Index: 'pool,
{
    #[inline]
    #[track_caller]
    fn node_data_lend_mut(&mut self, node: Index) -> &mut Element {
        &mut self.pool[node]
    }
}