rbt_rs/

lib.rs

//! This module implements a binary search tree in the form of a [Red-black tree](https://en.wikipedia.org/wiki/Red–black_tree), which is an approximately balanced binary search tree.
//!
//! All [`RedBlackTree`] tree binary search tree operations: [`insert`], [`remove`], [`contains`], [`min`], [`max`], [`predecessor`], [`successor`] have a worst case time complexity of `O(log n)`.
//!
//! [`insert`]: RedBlackTree::insert
//! [`remove`]: RedBlackTree::remove
//! [`contains`]: RedBlackTree::contains
//! [`min`]: RedBlackTree::min
//! [`max`]: RedBlackTree::max
//! [`predecessor`]: RedBlackTree::predecessor
//! [`successor`]: RedBlackTree::successor
//!
//! # Examples:
//!
//! #### Binary Search Tree Operations
//! ```
//! use rbt_rs::RedBlackTree;
//!
//! let mut rbt: RedBlackTree<i64> = (0..100).map(|x| x * x).collect();
//!
//! rbt.insert(-12);
//! assert!(rbt.contains(&-12));
//! assert_eq!(rbt.min(), Some(&-12));
//!
//! assert_eq!(rbt.remove(&0), Some(0));
//! assert!(!rbt.contains(&0));
//!
//! assert_eq!(*rbt.min().unwrap(), -12);
//! assert_eq!(*rbt.max().unwrap(), 99 * 99);
//!
//! assert_eq!(*rbt.successor(&100).unwrap(), 121);
//! assert_eq!(*rbt.predecessor(&100).unwrap(), 81);
//! ```
//!
//! #### Iteration
//! Iterate nodes of the tree in-order (sorted), as `&T`, `&Node<T>` or `T`.
//! ```
//! use rbt_rs::{RedBlackTree, Node};
//!
//! let rbt = RedBlackTree::from_iter([5, 2, 8, 9, 1]);
//!
//! let first_val: Option<&i64> = rbt.iter().next();
//! assert_eq!(first_val, Some(&1));
//! let first_node: Option<&Node<i64>> = rbt.iter_node().next();
//! assert_eq!(first_node.map(|x| **x), Some(1));
//! let first_owned_val: Option<i64> = rbt.into_iter().next();
//! assert_eq!(first_owned_val, Some(1));
//! ```
//!
//! #### Subtrees
//! Work with subtrees using the node API.
//! ```
//! use rbt_rs::{RedBlackTree, Node};
//!
//! let mut rbt: RedBlackTree<i64> = (0..100).map(|x| x * x).collect();
//!
//! let subtree: &Node<i64> = rbt.get_node(&144).unwrap();
//! assert!(subtree.min().val() <= &144);
//! assert!(subtree.max().val() >= &144);
//!
//! // This also allows for (on average), faster predecessor/successor operations,
//! // since traversal starts from the node directly.
//! let predecessor: &Node<i64> = subtree.predecessor().unwrap();
//! assert_eq!(**predecessor, 121);
//! assert_eq!(predecessor.successor().unwrap().val(), &144);
//! ```
//!
//! #### [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) in a single line 😀.
//! Due to the Red-black tree being approximately balanced, this runs in `O(n log n)`.
//! Though it is still not very efficient, since it requires `n` separate allocations (one per node) and it is also not in-place.
//! ```
//! use rbt_rs::RedBlackTree;
//!
//! fn treesort<T: Ord>(unsorted: impl IntoIterator<Item = T>) -> Vec<T> {
//!     RedBlackTree::from_iter(unsorted).into_iter().collect()
//! }
//! ```

#![feature(box_into_inner, dropck_eyepatch)]
#![warn(missing_debug_implementations, missing_docs)]

use std::{
    borrow::Borrow,
    fmt::{Debug, Display},
    marker::PhantomData,
    ops::{Deref, DerefMut},
    ptr::NonNull,
};

use crate::{
    Color::{Black, Red},
    NodeKind::Sentinel,
};

/// Iterators over the nodes or values of a [RedBlackTree].
pub mod iter;
pub use iter::{IntoIter, Iter, IterNode};

/// A [Red-black tree](https://en.wikipedia.org/wiki/Red–black_tree) which is an approximately balanced binary search tree.
///
/// All [`RedBlackTree`] tree binary search tree operations: [`insert`], [`remove`], [`contains`], [`min`], [`max`], [`predecessor`], [`successor`] have a worst case time complexity of `O(log n)`.
///
/// [`insert`]: RedBlackTree::insert
/// [`remove`]: RedBlackTree::remove
/// [`contains`]: RedBlackTree::contains
/// [`min`]: RedBlackTree::min
/// [`max`]: RedBlackTree::max
/// [`predecessor`]: RedBlackTree::predecessor
/// [`successor`]: RedBlackTree::successor
pub struct RedBlackTree<T> {
    root: NodeKind<T>,
    len: usize,
    // Tell the dropck that we will drop a T.
    _owns_t: PhantomData<T>,
}

// SAFETY: We don't access the T itself.
unsafe impl<#[may_dangle] T> Drop for RedBlackTree<T> {
    fn drop(&mut self) {
        self.clear();
    }
}

impl<T> RedBlackTree<T> {
    /// Returns an empty RedBlackTree.
    pub fn new() -> Self {
        Self {
            root: NodeKind::Sentinel,
            len: 0,
            _owns_t: PhantomData,
        }
    }

    /// Inserts the given value into the tree. Duplicates are permitted and will lead to duplicate values in the tree.
    ///
    /// This operation is `O(log n)`.
    pub fn insert(&mut self, t: T)
    where
        T: Ord,
    {
        let mut parent = Sentinel;
        let mut x = self.root.clone();
        while let NodeKind::Node(node) = x.clone() {
            parent = x;
            if t <= node.t {
                x = node.left.clone();
            } else {
                x = node.right.clone();
            }
        }

        self.len += 1;
        let node = match parent {
            Sentinel => {
                self.root = NodeKind::Node(Node::new(Sentinel, t));
                self.root.clone().unwrap()
            }
            NodeKind::Node(mut parent) => {
                if t <= parent.t {
                    parent.left = NodeKind::Node(Node::new(NodeKind::Node(parent.clone()), t));
                    parent.left.clone().unwrap()
                } else {
                    parent.right = NodeKind::Node(Node::new(NodeKind::Node(parent.clone()), t));
                    parent.right.clone().unwrap()
                }
            }
        };
        self.insert_fixup(node);
        assert_eq!(self.root.color(), Black);
    }

    /// Removes the first pre-order node with the given value from the tree, returning the removed value, if there was one to remove.
    ///
    /// This operation is `O(log n)`.
    pub fn remove<Q>(&mut self, q: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: Ord + Eq + ?Sized,
    {
        let node = self.find_nodeptr(q)?;
        Some(self.remove_nodeptr(node))
    }

    /// Returns the minimum value, returning `None` if the tree is empty.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the node with the minimum value `&Node<T>` use `max_node()`.
    pub fn min(&self) -> Option<&T> {
        self.min_node().map(|n| &n.t)
    }

    /// Removes and returns the minimum value, returning `None` if the tree is empty.
    ///
    /// This operation is `O(log n)`.
    /// If the minimum value is not unique in the tree, the first pre-order node is removed.
    /// To obtain the value without removing it use `min()`.
    pub fn extract_min(&mut self) -> Option<T>
    where
        T: Ord,
    {
        let NodeKind::Node(root) = self.root.clone() else {
            return None;
        };

        let mut min = root;
        while let NodeKind::Node(left) = min.left.clone() {
            min = left;
        }
        Some(self.remove_nodeptr(min))
    }

    /// Returns the maximum value, returning `None` if the tree is empty.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the node with the maximum value, use `max_node()`.
    pub fn max(&self) -> Option<&T> {
        self.max_node().map(|n| &n.t)
    }

    /// Removes and returns the maximum value, returning `None` if the tree is empty.
    ///
    /// This operation is `O(log n)`.
    /// If the maximum value is not unique in the tree, the first pre-order node is removed.
    /// To obtain the value without removing it use `max()`.
    pub fn extract_max(&mut self) -> Option<T>
    where
        T: Ord,
    {
        let NodeKind::Node(root) = self.root.clone() else {
            return None;
        };

        let mut max = root;
        while let NodeKind::Node(right) = max.right.clone() {
            max = right;
        }
        Some(self.remove_nodeptr(max))
    }

    /// Returns the predecessor value, which is the previous in-order value, of the given value.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the predecessor node, use `get_node(t).map_or_default(|n| n.predecessor())`.
    pub fn predecessor<'t>(&self, t: &'t T) -> Option<&T>
    where
        T: Ord,
    {
        self.get_node(t)
            .map_or_default(|n| n.predecessor())
            .map(|n| &n.t)
    }

    /// Returns the successor value, which is the next in-order value, of the given value.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the successor node, use `get_node(t).map_or_default(|n| n.successor())`.
    pub fn successor<'t>(&self, t: &'t T) -> Option<&T>
    where
        T: Ord,
    {
        self.get_node(t)
            .map_or_default(|n| n.successor())
            .map(|n| &n.t)
    }

    /// Returns `true` if the tree contains the given value.
    ///
    /// This operation is `O(log n)`.
    pub fn contains(&self, t: &T) -> bool
    where
        T: Ord,
    {
        self.get_node(t).is_some()
    }

    /// Removes all values from the tree.
    ///
    /// This operation is `O(n)` and is equivalent to dropping the tree and creating a new one.
    pub fn clear(&mut self) {
        let mut stack = Vec::new();
        if let NodeKind::Node(root) = self.root.clone() {
            stack.push(root);
        }
        self.root = Sentinel;
        while let Some(mut top) = stack.pop() {
            if let NodeKind::Node(left) = top.left.clone() {
                stack.push(left);
            }
            if let NodeKind::Node(right) = top.right.clone() {
                stack.push(right);
            }
            drop(unsafe { Box::from_raw(NonNull::from_mut(top.0.as_mut()).as_ptr()) });
        }
        self.len = 0;
    }

    /// Returns the root value of the tree.
    ///
    /// This operation is `O(1)`.
    /// To obtain the root node, use `root_node()`.
    pub fn root(&self) -> Option<&T> {
        self.root_node().map(|ro| &ro.t)
    }

    /// Returns the number of elements in the tree.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the tree contains no elements.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns an in-order iterator over shared references of the values in the tree.
    ///
    /// Iterator creation is `O(1)`.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            iter_node: self.iter_node(),
        }
    }
}

impl<T> RedBlackTree<T> {
    /// Finds the node with the given value in the tree and returns it, if it exists.
    ///
    /// This operation is `O(n)`.
    /// If you only need to know whether the value exists, use `contains()`.
    pub fn get_node<'a, Q>(&'a self, q: &Q) -> Option<&'a Node<T>>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut x = self.root.clone();
        while let NodeKind::Node(node) = x {
            match q.cmp(node.t.borrow()) {
                std::cmp::Ordering::Less => x = node.left.clone(),
                std::cmp::Ordering::Equal => return Some(unsafe { node.as_ref() }),
                std::cmp::Ordering::Greater => x = node.right.clone(),
            }
        }
        None
    }

    /// Returns the node with the minimum value.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the value directly, use `min`.
    pub fn min_node(&self) -> Option<&Node<T>> {
        self.root
            .clone()
            .node()
            .map(|ro| unsafe { ro.as_ref() }.min())
    }

    /// Returns the node with the maximum value.
    ///
    /// This operation is `O(log n)`.
    /// To obtain the value directly, use `max`.
    pub fn max_node(&self) -> Option<&Node<T>> {
        self.root
            .clone()
            .node()
            .map(|ro| unsafe { ro.as_ref() }.max())
    }

    /// Returns the root value of the tree.
    ///
    /// This operation is `O(1)`.
    pub fn root_node(&self) -> Option<&Node<T>> {
        self.root.clone().node().map(|ro| unsafe { ro.as_ref() })
    }

    /// Returns an in-order iterator over shared references of the nodes in the tree.
    ///
    /// Iterator creation is `O(1)`.
    pub fn iter_node(&self) -> IterNode<'_, T> {
        if let NodeKind::Node(root) = self.root.clone() {
            unsafe { root.as_ref() }.iter_node()
        } else {
            IterNode { stack: vec![] }
        }
    }
}

impl<T> RedBlackTree<T> {
    fn find_nodeptr<Q>(&self, q: &Q) -> Option<NodePtr<T>>
    where
        T: Borrow<Q>,
        Q: Ord + Eq + ?Sized,
    {
        let mut x = self.root.clone();
        while let NodeKind::Node(ref node) = x {
            match q.cmp(node.t.borrow()) {
                std::cmp::Ordering::Less => x = node.left.clone(),
                std::cmp::Ordering::Equal => return Some(node.clone()),
                std::cmp::Ordering::Greater => x = node.right.clone(),
            }
        }
        None
    }

    fn transplant(
        &mut self,
        node: NodePtr<T>,
        mut with: NodeKind<T>,
    ) -> (NodeKind<T>, NodeKind<T>) {
        match node.parent() {
            Sentinel => self.root = with.clone(),
            NodeKind::Node(mut parent) => {
                if parent.left.clone().map_or_default(|l| l == node) {
                    parent.left = with.clone();
                } else {
                    parent.right = with.clone();
                }
            }
        };
        if let NodeKind::Node(ref mut with) = with {
            with.p = node.parent();
        }
        (with, node.parent())
    }

    fn remove_nodeptr(&mut self, z: NodePtr<T>) -> T {
        let mut y_original_color = z.color;

        // If z had less than two children, replacement is the node we moved in place of z.
        // Otherwise, replacement is the original right node of the successor of z, before we moved zs successor in place of z.
        // It might be the sentinel, but we still need its parent for remove_fixup, so we carry it.
        let (replacement, replacement_parent) = if z.left.is_sentinel() {
            self.transplant(z.clone(), z.right.clone())
        } else if z.right.is_sentinel() {
            self.transplant(z.clone(), z.left.clone())
        } else {
            let mut left = z.left.clone().unwrap();
            let mut right = z.right.clone().unwrap();

            let mut successor = {
                let mut succ = right.clone();
                while let NodeKind::Node(left) = succ.left.clone() {
                    succ = left;
                }
                succ
            };
            y_original_color = successor.color;

            let successor_right = successor.right.clone();
            let (replacement, replacement_parent) = if successor != right {
                let (successor_right, successor_right_parent) =
                    self.transplant(successor.clone(), successor_right);
                successor.right = NodeKind::Node(right.clone());
                right.p = NodeKind::Node(successor.clone());
                (successor_right, successor_right_parent)
            } else {
                (successor_right, NodeKind::Node(successor.clone()))
            };

            self.transplant(z.clone(), NodeKind::Node(successor.clone()));
            successor.left = NodeKind::Node(left.clone());
            left.p = NodeKind::Node(successor.clone());
            successor.color = z.color;
            (replacement, replacement_parent)
        };

        if y_original_color == Black {
            self.remove_fixup(replacement, replacement_parent);
        };
        self.len -= 1;
        Box::into_inner(unsafe { Box::from_raw(z.0.as_ptr()) }).t
    }

    fn rotate_left(&mut self, mut x: NodePtr<T>) {
        //    x
        //  a   y
        //     b g
        // turns into
        //    y
        //  x   g
        // a b

        let mut y = x.right.clone().unwrap();

        // x.right points to y.left and y.left to x
        x.right = y.left.clone();
        if let NodeKind::Node(ref mut y_left) = y.left {
            y_left.p = NodeKind::Node(x.clone());
        }

        // x.p.{left/right} points to y instead of x
        // y.p points to x.p
        if let NodeKind::Node(mut x_parent) = x.p.clone() {
            if x_parent.left.clone().map_or_default(|l| l == x) {
                x_parent.left = NodeKind::Node(y.clone());
            } else {
                x_parent.right = NodeKind::Node(y.clone());
            }
        } else {
            self.root = NodeKind::Node(y.clone());
        }
        y.p = x.p.clone();

        // y.left points to x and x.p to y
        y.left = NodeKind::Node(x.clone());
        x.p = NodeKind::Node(y);
    }

    fn rotate_right(&mut self, mut y: NodePtr<T>) {
        //    y
        //  x   g
        // a b
        // turns into
        //    x
        //  a   y
        //     b g

        let mut x = y.left.clone().unwrap();

        // y.left points to x.right and y.right to x
        y.left = x.right.clone();
        if let NodeKind::Node(ref mut x_right) = x.right {
            x_right.p = NodeKind::Node(y.clone());
        }

        // y.p.{left/right} points to x instead of y
        // x.p points to y.p
        if let NodeKind::Node(mut y_parent) = y.p.clone() {
            if y_parent.left.clone().map_or_default(|l| l == y) {
                y_parent.left = NodeKind::Node(x.clone());
            } else {
                y_parent.right = NodeKind::Node(x.clone());
            }
        } else {
            self.root = NodeKind::Node(x.clone());
        }
        x.p = y.p.clone();

        // x.right points to y and y.p to x
        x.right = NodeKind::Node(y.clone());
        y.p = NodeKind::Node(x);
    }

    fn insert_fixup(&mut self, mut node: NodePtr<T>) {
        while node.p.color() == Red {
            // If the parent is red, it can't be the sentinel.
            let mut parent = node.parent().unwrap();
            // It can also not be the root, since the root is black, so the grandparent must exist.
            let mut grandparent = node.grandparent().unwrap();

            if grandparent.left.clone().map_or_default(|l| l == parent) {
                let uncle = grandparent.right.clone();
                // case 1
                if uncle.color() == Red {
                    parent.color = Black;
                    // If the uncle is red, it must not be the sentinel.
                    uncle.unwrap().color = Black;
                    grandparent.color = Red;
                    node = grandparent;
                } else {
                    // case 2
                    if parent.right.clone().map_or_default(|r| r == node) {
                        node = parent;
                        self.rotate_left(node.clone());
                    }
                    // case 3
                    node.parent().unwrap().color = Black;
                    node.grandparent().unwrap().color = Red;
                    self.rotate_right(node.grandparent().unwrap());
                }
            } else {
                let uncle = grandparent.left.clone();
                if uncle.color() == Red {
                    parent.color = Black;
                    // If the uncle is red, it must not be the sentinel.
                    uncle.unwrap().color = Black;
                    grandparent.color = Red;
                    node = grandparent;
                } else {
                    if parent.left.clone().map_or_default(|l| l == node) {
                        node = parent;
                        self.rotate_right(node.clone());
                    }
                    node.parent().unwrap().color = Black;
                    node.grandparent().unwrap().color = Red;
                    self.rotate_left(node.grandparent().unwrap());
                }
            }
        }

        self.root.clone().unwrap().color = Black;
    }

    fn remove_fixup(&mut self, mut node: NodeKind<T>, mut parent_outer: NodeKind<T>) {
        while node.color() == Black && self.root != node {
            // Node is not the root, so its parent must exist.
            let mut parent = parent_outer.clone().unwrap();
            if parent.left == node {
                // Node is doubly black, so its sibling cannot be the sentinel, since that would violate the simple path property.
                let mut sibling = parent.right.clone().unwrap();
                // case 1
                if sibling.color == Red {
                    sibling.color = Black;
                    parent.color = Red;
                    self.rotate_left(parent.clone());
                    sibling = parent.right.clone().unwrap();
                }
                // case 2
                if sibling.left.color() == Black && sibling.right.color() == Black {
                    sibling.color = Red;
                    node = NodeKind::Node(parent.clone());
                    parent_outer = parent.p.clone();
                } else {
                    // case 3
                    if sibling.right.color() == Black {
                        sibling.left.clone().unwrap().color = Red;
                        sibling.color = Red;
                        self.rotate_right(sibling);
                        sibling = parent.right.clone().unwrap();
                    }
                    // case 4
                    sibling.color = parent.color;
                    parent.color = Black;
                    sibling.right.clone().unwrap().color = Black;
                    self.rotate_left(parent);
                    node = self.root.clone();
                }
            } else {
                // Node is doubly black, so its sibling cannot be the sentinel, since that would violate the simple path property.
                let mut sibling = parent.left.clone().unwrap();
                // case 1
                if sibling.color == Red {
                    sibling.color = Black;
                    parent.color = Red;
                    self.rotate_right(parent.clone());
                    sibling = parent.left.clone().unwrap();
                }
                // case 2
                if sibling.right.color() == Black && sibling.left.color() == Black {
                    sibling.color = Red;
                    node = NodeKind::Node(parent.clone());
                    parent_outer = parent.p.clone();
                } else {
                    // case 3
                    if sibling.left.color() == Black {
                        sibling.right.clone().unwrap().color = Red;
                        sibling.color = Red;
                        self.rotate_left(sibling);
                        sibling = parent.left.clone().unwrap();
                    }
                    // case 4
                    sibling.color = parent.color;
                    parent.color = Black;
                    sibling.left.clone().unwrap().color = Black;
                    self.rotate_right(parent);
                    node = self.root.clone();
                }
            }
        }
        if let NodeKind::Node(mut x) = node {
            x.color = Black;
        }
    }
}

impl<T> Default for RedBlackTree<T> {
    fn default() -> Self {
        Self::new()
    }
}

// SAFETY: The nodes are allocated via Box, which is Send if T: Send.
unsafe impl<T: Send> Send for RedBlackTree<T> {}
// SAFETY: There is no interior mutability of T.
// Mutation requires &mut RedBlackTree, so &T can be shared accross threads.
unsafe impl<T: Sync> Sync for RedBlackTree<T> {}

impl<T: Clone> Clone for RedBlackTree<T> {
    fn clone(&self) -> Self {
        let NodeKind::Node(root) = self.root.clone() else {
            return Self::new();
        };

        fn clone_node<T: Clone>(p: NodeKind<T>, node: &Node<T>) -> NodeKind<T> {
            let mut new = Node::as_node_ptr(Node {
                p,
                t: node.t.clone(),
                left: Sentinel,
                right: Sentinel,
                color: node.color,
            });
            new.left = node
                .left
                .clone()
                .map_or_default(|l| clone_node(NodeKind::Node(new.clone()), &l));
            new.right = node
                .right
                .clone()
                .map_or_default(|r| clone_node(NodeKind::Node(new.clone()), &r));
            NodeKind::Node(new)
        }

        let root = clone_node(Sentinel, &root);
        Self {
            len: self.len,
            root: root,
            _owns_t: PhantomData,
        }
    }
}

impl<T: PartialEq> PartialEq for RedBlackTree<T> {
    fn eq(&self, other: &Self) -> bool {
        self.iter().eq(other.iter())
    }
}

impl<T: Eq> Eq for RedBlackTree<T> {}

impl<T: Display> Display for RedBlackTree<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "RedBlackTree({})",
            self.root
                .clone()
                .map_or_default(|ro| format!("{}", unsafe { ro.as_ref() }))
        )
    }
}

impl<T: Debug> Debug for RedBlackTree<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("RedBlackTree")
            .field(
                "root",
                &self
                    .root
                    .clone()
                    .map_or_default(|ro| format!("{:?}", unsafe { ro.as_ref() })),
            )
            .field("len", &self.len)
            .finish()
    }
}

impl<A: Ord> Extend<A> for RedBlackTree<A> {
    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
        for t in iter {
            self.insert(t);
        }
    }
}

impl<A: Ord> FromIterator<A> for RedBlackTree<A> {
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
        let mut rbt = RedBlackTree::new();
        for t in iter {
            rbt.insert(t);
        }
        rbt
    }
}

/// A node in a [RedBlackTree].
///
/// The only publically available field is the contained value `t`, which can also be obtained through `val()`.
/// `Node<T>` implements `Deref<Target = T>`, so you can use `&Node<T>` in place of `&T` through deref-coercion.
pub struct Node<T> {
    p: NodeKind<T>,
    /// The value contained in the Node.
    pub t: T,
    left: NodeKind<T>,
    right: NodeKind<T>,
    color: Color,
}

impl<T> Node<T> {
    /// Returns a shared reference to the value contained in the node.
    pub fn val(&self) -> &T {
        &self.t
    }

    /// Returns the minimum value in this subtree.
    ///
    /// This operation is `O(log n)`.
    pub fn min(&self) -> &Node<T> {
        let mut x = self;
        while let NodeKind::Node(left) = x.left.clone() {
            x = unsafe { left.as_ref() };
        }
        x
    }

    /// Returns the maximum value in this subtree.
    ///
    /// This operation is `O(log n)`.
    pub fn max(&self) -> &Node<T> {
        let mut x = self;
        while let NodeKind::Node(right) = x.right.clone() {
            x = unsafe { right.as_ref() };
        }
        x
    }

    /// Returns the predecessor node, which is the previous in-order node and is not necessarily within the sub-tree defined by the current node.
    ///
    /// This operation is at-worst `O(log n)`.
    pub fn predecessor(&self) -> Option<&Node<T>> {
        match self.left {
            NodeKind::Node(ref left) => Some(Node::max(left)),
            Sentinel => {
                // If we dont have a left subtree, there are two options:
                // 1. If we, or one of our ancestors, forms a right-subtree, then that ancestor is the predecessor.
                //    This will also be first ancestor that has a value <= us.
                // 2. If we are in no right-subtrees, we are the smallest node in the tree and have no predecessor.
                let mut x = self;
                while let NodeKind::Node(p) = x.p.clone() {
                    if p.right
                        .clone()
                        .map_or_default(|r| r == NodePtr(NonNull::from_ref(x)))
                    {
                        return Some(unsafe { p.as_ref() });
                    }
                    x = unsafe { p.as_ref() };
                }
                None
            }
        }
    }

    /// Returns the successor node, which is the previous in-order node and is not necessarily within the sub-tree defined by the current node.
    ///
    /// This operation is at-worst `O(log n)`.
    pub fn successor(&self) -> Option<&Node<T>> {
        match self.right {
            NodeKind::Node(ref right) => Some(Node::min(right)),
            Sentinel => {
                // If we dont have a right subtree, there are two options:
                // 1. If we are, or one of our ancestors, forms a left-subtree, then that ancestor is the successor.
                //    This will also be the first ancestor that has a value > us.
                // 2. If we are in no left-subtrees, we are the largest node in the tree and have no successor.
                let mut x = self;
                while let NodeKind::Node(p) = x.p.clone() {
                    if p.left
                        .clone()
                        .map_or_default(|l| l == NodePtr(NonNull::from_ref(x)))
                    {
                        return Some(unsafe { p.as_ref() });
                    }
                    x = unsafe { p.as_ref() };
                }

                None
            }
        }
    }

    /// Returns an in-order iterator over shared references of the values in this sub-tree.
    ///
    /// Iterator creation is `O(1)`.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            iter_node: self.iter_node(),
        }
    }

    /// Returns an in-order iterator over shared references of the nodes in this sub-tree.
    ///
    /// Iterator creation is `O(1)`.
    pub fn iter_node(&self) -> IterNode<'_, T> {
        IterNode {
            stack: vec![(self, false)],
        }
    }
}

impl<T> Node<T> {
    fn new(p: NodeKind<T>, t: T) -> NodePtr<T> {
        Node::as_node_ptr(Self {
            left: Sentinel,
            right: Sentinel,
            p,
            t,
            color: Red,
        })
    }

    fn as_node_ptr(node: Node<T>) -> NodePtr<T> {
        NodePtr(NonNull::new(Box::into_raw(Box::new(node))).expect("allocate node"))
    }

    fn parent(&self) -> NodeKind<T> {
        self.p.clone()
    }

    fn grandparent(&self) -> NodeKind<T> {
        self.p.clone().map_or_default(|p| p.parent())
    }
}

impl<T> Deref for Node<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.t
    }
}

impl<T: PartialEq> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        self.t == other.t
    }
}

impl<T: Eq> Eq for Node<T> {}

impl<T: Ord> Ord for Node<T> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.t.cmp(&other.t)
    }
}

impl<T: Ord> PartialOrd for Node<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: Display> Display for Node<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let NodeKind::Node(ref left) = self.left {
            write!(f, "({})", unsafe { left.as_ref() })?;
        }
        write!(f, " {} ", self.t)?;
        if let NodeKind::Node(ref right) = self.right {
            write!(f, "({})", unsafe { right.as_ref() })?;
        }
        Ok(())
    }
}

impl<T: Debug> Debug for Node<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let NodeKind::Node(ref left) = self.left {
            write!(f, "({:?})", left)?;
        }
        write!(f, " <{:?}, {:?}> ", self.t, self.color)?;
        if let NodeKind::Node(ref right) = self.right {
            write!(f, "({:?})", right)?;
        }
        Ok(())
    }
}

struct NodePtr<T>(NonNull<Node<T>>);

impl<T> PartialEq for NodePtr<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl<T> Eq for NodePtr<T> {}

impl<T> Clone for NodePtr<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone())
    }
}

impl<T> DerefMut for NodePtr<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { self.0.as_mut() }
    }
}

impl<T> Deref for NodePtr<T> {
    type Target = Node<T>;

    fn deref(&self) -> &Self::Target {
        unsafe { self.0.as_ref() }
    }
}

impl<T: Debug> Debug for NodePtr<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", unsafe { self.0.as_ref() })
    }
}

impl<T> NodePtr<T> {
    /// Returns the NodePtr as a reference with arbitrary lifetime.
    /// Invariant: The caller must ensure that the lifetime is tied to a shared reference to the tree.
    unsafe fn as_ref<'a>(&self) -> &'a Node<T> {
        // SAFETY: If the caller upholds the invariant, the reference cannot be stale and we cannot violate aliasing rules, since deallocating a node requires &mut RedBlackTree.
        // The reference is guaranteed to be aligned and non-null, since it the backing Node<T> was allocated using Box::new.
        unsafe { self.0.as_ref() }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Color {
    Red,
    Black,
}

#[derive(Debug, Default)]
enum NodeKind<T> {
    #[default]
    Sentinel,
    Node(NodePtr<T>),
}

impl<T> NodeKind<T> {
    fn color(&self) -> Color {
        match self {
            NodeKind::Sentinel => Black,
            NodeKind::Node(node) => node.color,
        }
    }

    fn is_sentinel(&self) -> bool {
        match self {
            Sentinel => true,
            NodeKind::Node(_) => false,
        }
    }

    /// Equivalent to Result::ok.
    fn node(self) -> Option<NodePtr<T>> {
        match self {
            Sentinel => None,
            NodeKind::Node(node) => Some(node),
        }
    }

    fn map_or_default<U: Default>(self, f: impl FnOnce(NodePtr<T>) -> U) -> U {
        match self {
            Sentinel => U::default(),
            NodeKind::Node(node) => f(node),
        }
    }

    fn unwrap(self) -> NodePtr<T> {
        match self {
            Sentinel => panic!("expected Node, but got Sentinel"),
            NodeKind::Node(node) => node,
        }
    }
}

impl<T> Clone for NodeKind<T> {
    fn clone(&self) -> Self {
        match self {
            Self::Sentinel => Self::Sentinel,
            Self::Node(node_ptr) => Self::Node(node_ptr.clone()),
        }
    }
}

impl<T> PartialEq for NodeKind<T> {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Self::Node(l), Self::Node(r)) => l == r,
            _ => core::mem::discriminant(self) == core::mem::discriminant(other),
        }
    }
}

#[cfg(test)]
mod tests {

    mod rbt {
        use super::super::*;
        use std::collections::VecDeque;

        fn assert_tree_equal<T: PartialEq + Debug + Clone>(
            tree: &RedBlackTree<T>,
            want: &[&[Option<(T, Color)>]],
        ) {
            let mut queue = VecDeque::new();
            queue.push_back(tree.root.clone());

            let mut d = 0;
            while !queue.is_empty() {
                let mut level = Vec::with_capacity(2usize.pow(d as u32) as usize);
                for _ in 0..queue.len() {
                    let front = queue.pop_front().unwrap().node();
                    level.push(front.as_ref().map(|f| (f.t.clone(), f.color)));
                    if let Some(front) = front.clone() {
                        queue.push_back(front.left.clone());
                        queue.push_back(front.right.clone());
                    }
                }
                if d >= want.len() {
                    return;
                }
                assert_eq!(&level, want[d]);
                d += 1;
            }
        }

        #[test]
        fn insert_with_all_fixup_cases() {
            let mut rbt = RedBlackTree::from_iter([11, 2, 14, 1, 7, 15, 5, 8]);
            #[rustfmt::skip]
            assert_tree_equal(
                &rbt,
                &[
                    &[Some((11, Black))],
                    &[Some((2, Red)), Some((14, Black))],
                    &[Some((1, Black)), Some((7, Black)), None, Some((15, Red))],
                    &[None, None, Some((5, Red)), Some((8, Red)), None, None],
                ],
            );

            // when
            rbt.insert(4);

            // then
            #[rustfmt::skip]
            assert_tree_equal(
                &rbt,
                &[
                    &[Some((7, Black))],
                    &[Some((2, Red)), Some((11, Red))],
                    &[Some((1, Black)), Some((5, Black)), Some((8, Black)), Some((14, Black))],
                    &[None, None, Some((4, Red)), None, None, None, None, Some((15, Red))],
                ],
            );
            assert_eq!(rbt.root.color(), Black);
        }

        #[test]
        fn clear() {
            // This test is mostly interesting to see that we don't leak with miri.
            let mut rbt = RedBlackTree::from_iter([2, 4]);
            rbt.clear();
            assert!(rbt.is_empty());
        }
    }

    mod node {
        use super::super::*;

        #[test]
        fn successor_has_right() {
            let rbt = RedBlackTree::from_iter([2, 4, 3]);
            let four = rbt.get_node(&2).unwrap();
            assert_eq!(four.successor().map(|s| s.t), Some(3));
        }

        #[test]
        fn successor_largest() {
            let rbt = RedBlackTree::from_iter([4, 3, 5]);
            let four = rbt.get_node(&5).unwrap();
            assert_eq!(four.successor().map(|s| s.t), None);
        }

        #[test]
        fn successor_left_subtree_immediate() {
            let rbt = RedBlackTree::from_iter([5, 3]);
            let four = rbt.get_node(&3).unwrap();
            assert_eq!(four.successor().map(|s| s.t), Some(5));
        }

        #[test]
        fn successor_left_subtree_ancestor() {
            let rbt = RedBlackTree::from_iter([5, 3, 4]);
            let four = rbt.get_node(&4).unwrap();
            assert_eq!(four.successor().map(|s| s.t), Some(5));
        }

        #[test]
        fn predecessor_has_left() {
            let rbt = RedBlackTree::from_iter([4, 3, 2]);
            let four = rbt.get_node(&3).unwrap();
            assert_eq!(four.predecessor().map(|s| s.t), Some(2));
        }

        #[test]
        fn predecessor_smallest() {
            let rbt = RedBlackTree::from_iter([4, 3, 2]);
            let four = rbt.get_node(&2).unwrap();
            assert_eq!(four.predecessor().map(|s| s.t), None);
        }

        #[test]
        fn predecessor_right_subtree_immediate() {
            let rbt = RedBlackTree::from_iter([4, 5]);
            let four = rbt.get_node(&5).unwrap();
            assert_eq!(four.predecessor().map(|s| s.t), Some(4));
        }

        #[test]
        fn predecessor_right_subtree_ancestor() {
            let rbt = RedBlackTree::from_iter([1, 3, 2]);
            let four = rbt.get_node(&2).unwrap();
            assert_eq!(four.predecessor().map(|s| s.t), Some(1));
        }
    }

    mod quickcheck {
        use super::super::*;
        use quickcheck::QuickCheck;
        use rand::seq::SliceRandom;

        fn rbt_property(rbt: &RedBlackTree<i64>) -> bool {
            fn dfs(node: NodeKind<i64>, le: i64, ge: i64) -> bool {
                if let NodeKind::Node(node) = node {
                    if node.t > le || node.t < ge {
                        return false;
                    }
                    dfs(node.left.clone(), node.t, ge) && dfs(node.right.clone(), le, node.t)
                } else {
                    true
                }
            }
            dfs(rbt.root.clone(), i64::MAX, i64::MIN)
        }

        fn rb_property_root_is_black(rbt: &RedBlackTree<i64>) -> bool {
            rbt.root.color() == Black
        }

        fn rb_property_red_parent_has_black_children(rbt: &RedBlackTree<i64>) -> bool {
            fn dfs(node: NodeKind<i64>) -> bool {
                match node {
                    Sentinel => true,
                    NodeKind::Node(node) => {
                        if node.color == Red
                            && !(node.left.color() == Black && node.right.color() == Black)
                        {
                            return false;
                        }
                        dfs(node.left.clone()) && dfs(node.right.clone())
                    }
                }
            }
            dfs(rbt.root.clone())
        }

        fn rb_property_black_height_of_simple_paths(rbt: &RedBlackTree<i64>) -> bool {
            fn black_height(node: NodeKind<i64>) -> (usize, bool) {
                match node {
                    Sentinel => (1, true),
                    NodeKind::Node(node) => {
                        let (left, lok) = black_height(node.left.clone());
                        let (_, rok) = black_height(node.right.clone());
                        if node.color == Black {
                            (left + 1, lok && rok)
                        } else {
                            (left, lok && rok)
                        }
                    }
                }
            }
            black_height(rbt.root.clone()).1
        }

        fn rb_lg_height(rbt: &RedBlackTree<i64>) -> bool {
            fn max_edge_count(node: NodeKind<i64>) -> u32 {
                match node {
                    Sentinel => 1,
                    NodeKind::Node(node) => {
                        max_edge_count(node.left.clone()).max(max_edge_count(node.right.clone()))
                            + 1
                    }
                }
            }
            let height = max_edge_count(rbt.root.clone()) - 1;
            let maximum_expected = 2 * (rbt.len + 1).ilog2();
            height <= maximum_expected
        }

        fn all_rb_properties(rbt: &RedBlackTree<i64>) -> bool {
            rbt_property(rbt)
                && rb_property_root_is_black(rbt)
                && rb_property_red_parent_has_black_children(rbt)
                && rb_property_black_height_of_simple_paths(rbt)
                && rb_lg_height(rbt)
        }

        fn min(values: Vec<i64>) -> bool {
            let rbt = RedBlackTree::from_iter(values);
            let rbt_min = rbt.min_node().map(|n| n.t);
            let min_iter = rbt.iter_node().map(|n| n.t).min();
            rbt_min == min_iter
        }

        fn max(values: Vec<i64>) -> bool {
            let rbt = RedBlackTree::from_iter(values);
            let rbt_max = rbt.max_node().map(|n| n.t);
            let max_iter = rbt.iter_node().map(|n| n.t).max();
            rbt_max == max_iter
        }

        fn clone_works(values: Vec<i64>) -> bool {
            let rbt = RedBlackTree::from_iter(values);
            let clone = rbt.clone();
            fn dfs(lhs: NodeKind<i64>, rhs: NodeKind<i64>) -> bool {
                match (lhs, rhs) {
                    (Sentinel, Sentinel) => true,
                    (Sentinel, NodeKind::Node(_)) => false,
                    (NodeKind::Node(_), Sentinel) => false,
                    (NodeKind::Node(lhs), NodeKind::Node(rhs)) => {
                        if !lhs.t == rhs.t {
                            return false;
                        }
                        // Pointers should never be equal.
                        if lhs == rhs {
                            return false;
                        }
                        dfs(lhs.left.clone(), rhs.left.clone())
                            && dfs(lhs.right.clone(), rhs.right.clone())
                    }
                }
            }
            dfs(rbt.root.clone(), clone.root.clone())
        }

        fn insert_upholds_properties(values: Vec<i64>) -> bool {
            let rbt = RedBlackTree::from_iter(values.clone());
            all_rb_properties(&rbt)
                && rbt.len == values.len()
                && values.into_iter().all(|v| rbt.contains(&v))
        }

        fn remove_upholds_properties(mut values: Vec<i64>) -> bool {
            let mut rbt = RedBlackTree::from_iter(values.clone());
            values.shuffle(&mut rand::rng());

            for v in values.iter() {
                if !rbt.remove(&v).is_some_and(|x| x == *v) {
                    return false;
                }
                if !all_rb_properties(&rbt) {
                    return false;
                }
            }

            true
        }

        fn insert_remove_interleaved_upholds_properties(mut values: Vec<i64>) -> bool {
            let mut rbt = RedBlackTree::from_iter(values.clone());
            values.shuffle(&mut rand::rng());

            for v in values.iter() {
                if !rbt.remove(&v).is_some_and(|x| x == *v) {
                    return false;
                }
                if !all_rb_properties(&rbt) {
                    return false;
                }

                rbt.insert(rand::random());
                if !all_rb_properties(&rbt) {
                    return false;
                }
            }

            true
        }

        fn extract_min_works(mut values: Vec<i64>) -> bool {
            let mut rbt = RedBlackTree::from_iter(values.iter().cloned());
            values.sort();
            for v in values {
                if rbt.extract_min().is_none_or(|min| min != v) {
                    return false;
                }

                if !all_rb_properties(&rbt) {
                    return false;
                }
            }

            rbt.extract_min().is_none()
        }

        fn extract_max_works(mut values: Vec<i64>) -> bool {
            let mut rbt = RedBlackTree::from_iter(values.iter().cloned());
            values.sort_by(|l, r| std::cmp::Reverse(l).cmp(&std::cmp::Reverse(r)));
            for v in values {
                if rbt.extract_max().is_none_or(|max| max != v) {
                    return false;
                }

                if !all_rb_properties(&rbt) {
                    return false;
                }
            }

            rbt.extract_max().is_none()
        }

        #[test]
        fn quickcheck() {
            let mut qc = QuickCheck::new().tests(cfg_select!(miri => 10, _ => 1000));
            // RedBlackTree
            qc.quickcheck(min as fn(Vec<i64>) -> bool);
            qc.quickcheck(max as fn(Vec<i64>) -> bool);
            qc.quickcheck(clone_works as fn(Vec<i64>) -> bool);
            qc.quickcheck(insert_upholds_properties as fn(Vec<i64>) -> bool);
            qc.quickcheck(remove_upholds_properties as fn(Vec<i64>) -> bool);
            qc.quickcheck(insert_remove_interleaved_upholds_properties as fn(Vec<i64>) -> bool);
            qc.quickcheck(extract_min_works as fn(Vec<i64>) -> bool);
            qc.quickcheck(extract_max_works as fn(Vec<i64>) -> bool);
        }
    }
}