bbtree 0.1.1

//! Cutting a tree in two at a key: [`Tree::split_off_at`], for the map's
//! `split_off` and `extract_if`.
//!
//! A search finds the leaf edge on the given side of the key
//! ([`KeySide`]), where the cut goes; for a key that is a separator, the
//! edge before it is the end of the rightmost leaf left of it. Up the node
//! stack from there, each node is cut at the node stack's edge
//! (`Leaf::cut_off_at`, `Internal::cut_off_at`): it keeps what lies left of
//! the node stack, and what lies right of it goes into a new node, after the
//! part cut off from the node below as its first child. The new nodes make a
//! tree as tall as the old one, with the keys past the cut.
//!
//! The nodes on the node stack become the borders of the two trees, whose
//! prefix is what every key of the tree shares (D50): before the cut, their
//! prefixes go back to the root's, from the root down, reading no key. Both
//! trees keep what the tree's keys shared; their keys share at least that.
//!
//! Along the cut, nodes on both sides may hold fewer keys than their
//! minimum, down to none. Fixing the left tree's right border and the right
//! tree's left border, from the top down, brings them back
//! ([`Tree::fix_border`]). A separator left at the start of the right
//! tree, with nothing left of it, comes down along that border, by a merge
//! or a move, into the tree's first leaf, with its value, the head of the
//! leaf right of it (D17).
//!
//! The nodes beside the borders, which entries moved over from, then fit
//! their prefixes to their new fences, reading keys: once both trees are
//! where a panic can't lose them, and counted. So the cut hands out the
//! right tree only through [`Cut::finish`], which puts it there, and fits
//! both.
//!
//! That touches the nodes along the node stack and the two borders: O(log n)
//! of them. The two maps' lengths come from counting the entries of the
//! shorter tree, a node at a time, as std's do ([`Cut::lengths`]).
//!
//! # Borders
//!
//! Bringing the nodes along one edge of a tree up to their minimum (D22),
//! from the top down: [`Tree::fix_border`]. A tree cut in two needs it
//! along both sides of the cut, and a tree built from the left (`build.rs`)
//! along its right edge: there, nodes may hold any number of keys, down to
//! none, where every other node holds its minimum.
//!
//! It reads no key: the nodes beside the border that give it entries keep
//! their prefixes, which still fit their narrower fences, until the
//! operation fits them, once it is done ([`Tree::refit_border_siblings`]).

#![forbid(unsafe_code)]

use core::borrow::Borrow;

use super::node::inline_keys::SearchKey;
use super::node::internal::Internal;
use super::node::leaf::Leaf;
use super::node::page::FreshPage;
use super::node::siblings::Siblings;
use super::node::{Child, Node};
use super::node_stack::{FirstEdge, KeySide, LastEdge, NodeEnd, NodeStackMut};
use super::root::Tree;
use crate::allocator::Allocator;
use crate::inline_key::InlineKeyStrategy;

impl<K, V, S: InlineKeyStrategy<K>> Tree<K, V, S> {
    /// Cuts the tree at the leaf edge on `side` of `key`: keeps what lies
    /// before it, and returns what lies after, both with their borders along
    /// the cut brought up to their minimum ([`Self::fix_border`]), in a
    /// [`Cut`], which hands it out once it fits the nodes beside those
    /// borders.
    ///
    /// Every `Ord` call happens first, in the search, before anything
    /// changes. Pages come from and go back to `alloc`, the map's allocator,
    /// which owns both trees' pages.
    pub(crate) fn split_off_at<Q>(
        &mut self,
        key: &Q,
        side: KeySide,
        alloc: &impl Allocator,
    ) -> Cut<K, V, S>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut stack = NodeStackMut::new(self);
        stack.search_to_edge(&SearchKey::new(key), side);
        let upper = stack.cut(alloc);
        // As tall as the tree; every key of both parts shares what the
        // tree's keys did (D50).
        let mut upper = Tree::from_node(upper, self.shared_prefix().clone(), alloc);
        self.fix_border::<LastEdge>(alloc);
        upper.fix_border::<FirstEdge>(alloc);
        Cut { upper }
    }
}

/// A tree just cut in two ([`Tree::split_off_at`]): the part after the cut,
/// which it hands out only once the nodes beside both borders along the
/// cut, which gave the borders entries, fit their prefixes to their new
/// fences. Until then they keep prefixes that still fit, as searches
/// allow, but shorter than their fences share.
#[must_use = "the part after the cut comes out only through `finish`"]
pub(crate) struct Cut<K, V, S> {
    upper: Tree<K, V, S>,
}

impl<K, V, S: InlineKeyStrategy<K>> Cut<K, V, S> {
    /// The number of entries before the cut, in `lower`, and after it, of
    /// `length` in all: counts the entries of the shorter tree, a node at a
    /// time, as std's map does.
    pub(crate) fn lengths(&self, lower: &Tree<K, V, S>, length: usize) -> (usize, usize) {
        if lower.leaf_depth() < self.upper.leaf_depth() {
            let lower_length = lower.root().count_entries();
            (lower_length, length - lower_length)
        } else {
            let upper_length = self.upper.root().count_entries();
            (length - upper_length, upper_length)
        }
    }

    /// Puts the part after the cut into `upper`, a tree without a root
    /// page, and then fits the prefixes of the nodes beside the borders
    /// along the cut, reading keys: `lower`'s, the part before it, if
    /// given, and `upper`'s. Both trees should be where a panic can't lose
    /// them, and counted. A `lower` that is only taken apart needs no
    /// fitting.
    pub(crate) fn finish(self, lower: Option<&mut Tree<K, V, S>>, upper: &mut Tree<K, V, S>) {
        debug_assert!(!upper.has_root(), "the part after a cut replaced a tree");
        *upper = self.upper;
        if let Some(lower) = lower {
            lower.refit_border_siblings::<LastEdge>();
        }
        upper.refit_border_siblings::<FirstEdge>();
    }
}

impl<K, V, S: InlineKeyStrategy<K>> NodeStackMut<'_, K, V, S> {
    /// Cuts the tree along the node stack, which ends at a leaf edge: each
    /// node on it, from the leaf up, keeps what lies left of the node stack,
    /// and what lies right of it goes into a new node, after the part cut off
    /// from the node below. Returns the top of the new nodes, as tall as the
    /// root, on plain pages from `alloc`, which nothing owns until the caller
    /// makes it a tree's root. Nodes on either side of the cut may be left
    /// with fewer keys than their minimum, down to none. Compares no keys.
    ///
    /// The nodes on the node stack become the two trees' borders: first, their
    /// prefixes move back to what every key shares (D50).
    ///
    /// # Panics
    ///
    /// If the node stack ends at no leaf edge.
    fn cut(mut self, alloc: &impl Allocator) -> Node<K, V, S> {
        self.move_prefixes_back_to_root();
        let index = self.index();
        let mut right = Node::Leaf(self.leaf().cut_off_at(index, FreshPage::allocate(alloc)));
        while !self.is_at_root() {
            let node = self.ascend();
            let index = self.index();
            right = Node::Internal(node.cut_off_at(index, right, FreshPage::allocate(alloc)));
        }
        right
    }
}

impl<K, V, S: InlineKeyStrategy<K>> Node<K, V, S> {
    /// The number of entries under this node, leaf entries and separators,
    /// counted a node at a time.
    fn count_entries(self) -> usize {
        match self {
            Node::Leaf(leaf) => leaf.len(),
            Node::Internal(internal) => {
                let below: usize = (0..=internal.len())
                    .map(|index| internal.child(index).count_entries())
                    .sum();
                internal.len() + below
            }
        }
    }
}

impl<K, V, S: InlineKeyStrategy<K>> Tree<K, V, S> {
    /// Makes every node along the tree's `End` edge, its last children for
    /// [`LastEdge`] or its first for [`FirstEdge`], hold at least
    /// its minimum, by merging it with its sibling or moving keys over from
    /// it, from the root down; and lowers the tree while its root is left
    /// without keys, until the root has some or is a leaf. Every other node
    /// must hold its minimum already. Emptied pages go back to `alloc`.
    ///
    /// Going down, each node on the edge is brought to one key more than its
    /// minimum, so that a merge one level down, which takes one of its keys,
    /// leaves it at its minimum still.
    pub(in crate::tree) fn fix_border<End: NodeEnd>(&mut self, alloc: &impl Allocator) {
        self.lower_while_root_empty(alloc);
        if let Node::Internal(mut node) = self.root_mut() {
            loop {
                let len = node.len();
                assert!(len > 0, "a node on the border holds a key once stocked");
                let separator = if End::IS_LAST { len - 1 } else { 0 };
                if node.has_leaf_children() {
                    node.siblings::<Leaf<K, V, S>>(separator)
                        .stock_border_child::<End>(alloc);
                    break;
                }
                node = node
                    .siblings::<Internal<K, V, S>>(separator)
                    .stock_border_child::<End>(alloc);
            }
        }
        self.lower_while_root_empty(alloc);
    }

    /// Lowers the tree while its root is internal without keys, until the
    /// root has some or is a leaf ([`Tree::lower`]), giving each page
    /// emptied back to `alloc`.
    pub(super) fn lower_while_root_empty(&mut self, alloc: &impl Allocator) {
        while matches!(self.root(), Node::Internal(root) if root.len() == 0) {
            self.lower().deallocate(alloc);
        }
    }
}

impl<K, V, S: InlineKeyStrategy<K>, C: Child<K, V, S>> Siblings<K, V, S, C> {
    /// Brings the child on the `End` side, the right one for
    /// [`LastEdge`], to at least one key more than its minimum: merges
    /// the two children if they fit in one node with their separator, or
    /// else moves keys over from the other child, which, too full to merge
    /// and holding its minimum, can spare them. Returns the child on the
    /// `End` side, merged or not.
    fn stock_border_child<End: NodeEnd>(mut self, alloc: &impl Allocator) -> C {
        let target = C::min_len() + 1;
        let border_len = |siblings: &Self| {
            if End::IS_LAST {
                siblings.right_len()
            } else {
                siblings.left_len()
            }
        };
        if border_len(&self) < target {
            if self.can_merge() {
                let merged = self.left();
                self.merge().deallocate(alloc);
                return merged;
            }
            while border_len(&self) < target {
                if End::IS_LAST {
                    self.steal_left()
                } else {
                    self.steal_right()
                }
                .expect("a sibling too full to merge with can spare a key");
            }
        }
        self.border_child::<End>()
    }

    /// The child on the `End` side.
    fn border_child<End: NodeEnd>(&self) -> C {
        if End::IS_LAST {
            self.right()
        } else {
            self.left()
        }
    }
}