intrex 0.2.0

//! Intrusive binary tree with items addressed by indices.
//!
//! # Node Access Traits
//!
//! The tree accessors manipulate nodes through application-provided types
//! (supplied through a `Nodes` generic parameter) implementing *node access
//! traits*.
//!
//! ## Links
//!
//! The following traits provide access to binary tree node fields:
//!
//! | Trait            | Receiver         | Read | Write |
//! | ---------------- | ---------------- | ---- | ----- |
//! | [`NodesLink`]    | `&self`          | x    |       |
//! | [`NodesLinkMut`] | `&mut self`      |      | x     |
//!
//! They have straightforward forwarding implementations for reference types
//! (`&T`, `&mut T`).
//!
//! ## Key Comparison
//!
//! [`NodesCmp`] provides a method to compare two nodes by their stored keys.
//!
//! [`NodesCmpKey`] provides a method to compare a node's stored key against a
//! provided search key.
//! The key is parameterized by `Key` because its type may differ from what is
//! stored in the nodes (e.g., `String` vs `&str`).
//!
//! ## Values
//!
//! This module uses the node value access traits defined in
//! [`crate::node_data`].
//!
//! # Index Ranges
//!
//! Methods, such as [`accessor::TreeAccessor::indices_index_range`], receive an
//! index range of nodes inside the tree's particular traversal order.
//! The range is specified by a value of a type implementing
//! [`ops::RangeBounds`]`<`[`Option`]`<Index>>`.
//!
//! See the documentation of [`crate::list`] for specific semantics.
#![warn(missing_docs)]
use core::{cmp::Ordering, ops};

pub mod accessor;
pub mod accessor_mut;
mod nodes;

pub use nodes::*;

/// Binary tree root reference.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Tree<Index = usize> {
    /// The index of the root element, if the tree is not empty.
    pub root: Option<Index>,
}

impl<Index> Default for Tree<Index> {
    #[inline]
    fn default() -> Self {
        Self { root: None }
    }
}

impl<Index> Tree<Index> {
    /// Construct an empty tree.
    #[inline]
    pub fn new() -> Self {
        Self::default()
    }

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

/// A place within a binary tree that can contain a node reference.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum Slot<Index> {
    /// [`Tree::root`]
    Root,
    /// [`NodesLink::node_left`]
    Left(Index),
    /// [`NodesLink::node_right`]
    Right(Index),
}

impl<Index> Slot<Index> {
    /// Get the owner of a given [`Slot`].
    #[inline]
    pub fn parent(self) -> Option<Index> {
        match self {
            Slot::Root => None,
            Slot::Left(node) | Slot::Right(node) => Some(node),
        }
    }
}

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

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

/// Find the next in-order neighbor of the element at index `node`.
#[inline]
fn next_index<Index>(nodes: &impl NodesLink<Index>, node: Index) -> Option<Index>
where
    Index: Clone + PartialEq,
{
    if let child = nodes.node_right(node.clone())
        && let Some(node) = front_index_in(nodes, child)
    {
        Some(node)
    } else {
        let mut cur = node;
        loop {
            let parent = nodes.node_parent(cur.clone())?;
            if nodes.node_left(parent.clone()).as_ref() == Some(&cur) {
                return Some(parent);
            }
            cur = parent;
        }
    }
}

/// Find the previous in-order neighbor of the element at index `node`.
#[inline]
fn prev_index<Index>(nodes: &impl NodesLink<Index>, node: Index) -> Option<Index>
where
    Index: Clone + PartialEq,
{
    if let child = nodes.node_left(node.clone())
        && let Some(node) = back_index_in(nodes, child)
    {
        Some(node)
    } else {
        let mut cur = node;
        loop {
            let parent = nodes.node_parent(cur.clone())?;
            if nodes.node_right(parent.clone()).as_ref() == Some(&cur) {
                return Some(parent);
            }
            cur = parent;
        }
    }
}

/// Find the slot where a new node should be inserted, assuming the tree is a
/// binary search tree (BST).
///
/// `cmp_new_key(nodes, index)` evaluates [`Ord::cmp`]`(nodes[index].key,
/// new_key)`.
///
/// Returns `Ok(index)` if the node at `index` has the identical key.
#[inline]
fn bst_slot_to_insert<Nodes, Index>(
    nodes: &Nodes,
    mut cmp_new_key: impl FnMut(&Nodes, Index) -> Ordering,
    root: Option<Index>,
) -> Result<Index, Slot<Index>>
where
    Nodes: NodesLink<Index>,
    Index: Clone,
{
    let Some(mut cur) = root else {
        return Err(Slot::Root);
    };

    loop {
        match cmp_new_key(nodes, cur.clone()) {
            Ordering::Less => {
                if let Some(next) = nodes.node_right(cur.clone()) {
                    cur = next;
                } else {
                    return Err(Slot::Right(cur));
                }
            }
            Ordering::Equal => return Ok(cur),
            Ordering::Greater => {
                if let Some(next) = nodes.node_left(cur.clone()) {
                    cur = next;
                } else {
                    return Err(Slot::Left(cur));
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::node_data::{
        NodesDataLend, NodesDataLendGat, NodesDataLendMut, NodesDataLendMutGat,
    };
    use proptest::prelude::*;
    use std::prelude::rust_2024::*;

    #[derive(Default, Debug, Clone, Copy, PartialEq)]
    pub(crate) struct Node<T> {
        pub value: T,
        pub left: Option<usize>,
        pub right: Option<usize>,
        pub parent: Option<usize>,
    }

    impl<T> NodesLink<usize> for [Node<T>] {
        fn node_parent(&self, node: usize) -> Option<usize> {
            self[node].parent
        }

        fn node_left(&self, node: usize) -> Option<usize> {
            self[node].left
        }

        fn node_right(&self, node: usize) -> Option<usize> {
            self[node].right
        }
    }

    impl<T> NodesLinkMut<usize> for [Node<T>] {
        fn set_node_parent(&mut self, node: usize, parent: Option<usize>) {
            self[node].parent = parent;
        }

        fn set_node_left(&mut self, node: usize, left: Option<usize>) {
            self[node].left = left;
        }

        fn set_node_right(&mut self, node: usize, right: Option<usize>) {
            self[node].right = right;
        }
    }

    impl<T> NodesCmp<usize> for [Node<T>]
    where
        T: Ord,
    {
        fn cmp_nodes(&self, lhs: usize, rhs: usize) -> core::cmp::Ordering {
            Ord::cmp(&self[lhs].value, &self[rhs].value)
        }
    }

    impl<T: Ord> NodesCmpKey<usize, T> for [Node<T>] {
        fn cmp_node_key(&self, node: usize, key: &T) -> Ordering {
            Ord::cmp(&self[node].value, key)
        }
    }

    impl<'this, T> NodesDataLendGat<'this, usize> for [Node<T>] {
        type Data = &'this T;
    }

    impl<T> NodesDataLend<usize> for [Node<T>] {
        fn node_data_lend(&self, node: usize) -> <Self as NodesDataLendGat<'_, usize>>::Data {
            &self[node].value
        }
    }

    impl<'this, T> NodesDataLendMutGat<'this, usize> for [Node<T>] {
        type Data = &'this mut T;
    }

    impl<T> NodesDataLendMut<usize> for [Node<T>] {
        fn node_data_lend_mut(
            &mut self,
            node: usize,
        ) -> <Self as NodesDataLendMutGat<'_, usize>>::Data {
            &mut self[node].value
        }
    }

    /// Construct a proptest strategy producing random binary trees.
    pub(crate) fn any_tree() -> impl Strategy<Value = (Vec<Node<u8>>, Tree)> {
        #[derive(Debug, Default)]
        struct INode {
            value: u8,
            left: Option<Box<INode>>,
            right: Option<Box<INode>>,
        }
        ((|| None) as fn() -> Option<INode>)
            .prop_recursive(5, 64, 2, |child| {
                (
                    prop::array::uniform(child.prop_map(|c| c.map(Box::new))),
                    any::<u8>(),
                )
                    .prop_map(|([left, right], value)| Some(INode { value, left, right }))
            })
            .prop_map(|root| {
                struct State {
                    nodes: Vec<Node<u8>>,
                }

                fn convert_node(state: &mut State, node: Option<&INode>) -> Option<usize> {
                    let node = node?;

                    let left = convert_node(state, node.left.as_deref());

                    let right = convert_node(state, node.right.as_deref());

                    let i = state.nodes.len();
                    state.nodes.push(Node {
                        value: node.value,
                        left,
                        right,
                        parent: None,
                    });

                    for k in [left, right].into_iter().flatten() {
                        state.nodes[k].parent = Some(i);
                    }

                    Some(i)
                }

                let mut state = State { nodes: Vec::new() };
                let tree = Tree {
                    root: convert_node(&mut state, root.as_ref()),
                };

                (state.nodes, tree)
            })
    }

    /// Construct a proptest strategy producing random BSTs.
    pub(crate) fn any_bst() -> impl Strategy<Value = (Vec<Node<u8>>, Tree)> {
        #[derive(Debug, Default)]
        struct INode {
            left: Option<Box<INode>>,
            right: Option<Box<INode>>,
        }
        ((|| None) as fn() -> Option<INode>)
            .prop_recursive(5, 64, 2, |child| {
                prop::array::uniform(child.prop_map(|c| c.map(Box::new)))
                    .prop_map(|[left, right]| Some(INode { left, right }))
            })
            .prop_map(|root| {
                struct State {
                    next_value: u8,
                    nodes: Vec<Node<u8>>,
                }

                fn convert_node(state: &mut State, node: Option<&INode>) -> Option<usize> {
                    let node = node?;

                    let left = convert_node(state, node.left.as_deref());

                    let value = state.next_value;
                    state.next_value += 1;

                    let right = convert_node(state, node.right.as_deref());

                    let i = state.nodes.len();
                    state.nodes.push(Node {
                        value,
                        left,
                        right,
                        parent: None,
                    });

                    for k in [left, right].into_iter().flatten() {
                        state.nodes[k].parent = Some(i);
                    }

                    Some(i)
                }

                let mut state = State {
                    next_value: 1,
                    nodes: Vec::new(),
                };
                let tree = Tree {
                    root: convert_node(&mut state, root.as_ref()),
                };

                (state.nodes, tree)
            })
    }

    /// Check that [`any_bst`] produces valid trees.
    #[proptest::property_test]
    fn pt_any_bst_validate(#[strategy = any_bst()] (nodes, root): (Vec<Node<u8>>, Tree)) {
        root.read(&nodes[..]).validate().unwrap();
        root.read(&nodes[..])
            .bst_validate(|nodes, i| nodes[i].value)
            .unwrap();
        assert!(root.read(&nodes[..]).values().is_sorted());
    }

    /// Construct a binary tree from a given in-order string.
    pub(crate) fn tree_from_str(s: &str) -> (Vec<Node<u8>>, Tree) {
        struct State<'a> {
            nodes: Vec<Node<u8>>,
            s: &'a [u8],
        }

        fn make_node(state: &mut State<'_>) -> Option<usize> {
            state.s = state.s.trim_ascii_start();

            match *state.s.split_off_first().unwrap() {
                b'_' => None,
                b'(' => {
                    // Parse a number
                    let i = state
                        .s
                        .iter()
                        .position(|b| !b.is_ascii_digit())
                        .unwrap_or(state.s.len());
                    if i == 0 {
                        panic!("invalid char: {:?}", state.s);
                    }

                    let value = std::str::from_utf8(state.s.split_off(..i).unwrap())
                        .unwrap()
                        .parse()
                        .unwrap();

                    let left = make_node(state);
                    let right = make_node(state);

                    state.s = state.s.trim_ascii_start();
                    assert_eq!(state.s.split_off_first(), Some(&b')'));

                    let i = state.nodes.len();
                    state.nodes.push(Node {
                        value,
                        left,
                        right,
                        parent: None,
                    });
                    for k in [left, right].into_iter().flatten() {
                        state.nodes[k].parent = Some(i);
                    }

                    Some(i)
                }
                c => panic!("invalid char: {:?}", char::from(c)),
            }
        }

        let mut state = State {
            nodes: Vec::new(),
            s: s.as_bytes(),
        };
        let tree = Tree {
            root: make_node(&mut state),
        };

        tree.read(&state.nodes[..]).validate().unwrap();

        (state.nodes, tree)
    }
}