cranelift_bforest/

map.rs

//! Forest of maps.

use super::{Comparator, Forest, Node, NodeData, NodePool, Path, INNER_SIZE};
use crate::packed_option::PackedOption;
#[cfg(test)]
use alloc::string::String;
#[cfg(test)]
use core::fmt;
use core::marker::PhantomData;

/// Tag type defining forest types for a map.
struct MapTypes<K, V>(PhantomData<(K, V)>);

impl<K, V> Forest for MapTypes<K, V>
where
    K: Copy,
    V: Copy,
{
    type Key = K;
    type Value = V;
    type LeafKeys = [K; INNER_SIZE - 1];
    type LeafValues = [V; INNER_SIZE - 1];

    fn splat_key(key: Self::Key) -> Self::LeafKeys {
        [key; INNER_SIZE - 1]
    }

    fn splat_value(value: Self::Value) -> Self::LeafValues {
        [value; INNER_SIZE - 1]
    }
}

/// Memory pool for a forest of `Map` instances.
pub struct MapForest<K, V>
where
    K: Copy,
    V: Copy,
{
    nodes: NodePool<MapTypes<K, V>>,
}

impl<K, V> MapForest<K, V>
where
    K: Copy,
    V: Copy,
{
    /// Create a new empty forest.
    pub fn new() -> Self {
        Self {
            nodes: NodePool::new(),
        }
    }

    /// Clear all maps in the forest.
    ///
    /// All `Map` instances belong to this forest are invalidated and should no longer be used.
    pub fn clear(&mut self) {
        self.nodes.clear();
    }
}

/// B-tree mapping from `K` to `V`.
///
/// This is not a general-purpose replacement for `BTreeMap`. See the [module
/// documentation](index.html) for more information about design tradeoffs.
///
/// Maps can be cloned, but that operation should only be used as part of cloning the whole forest
/// they belong to. *Cloning a map does not allocate new memory for the clone*. It creates an alias
/// of the same memory.
#[derive(Clone)]
pub struct Map<K, V>
where
    K: Copy,
    V: Copy,
{
    root: PackedOption<Node>,
    unused: PhantomData<(K, V)>,
}

impl<K, V> Map<K, V>
where
    K: Copy,
    V: Copy,
{
    /// Make an empty map.
    pub fn new() -> Self {
        Self {
            root: None.into(),
            unused: PhantomData,
        }
    }

    /// Is this an empty map?
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    /// Get the value stored for `key`.
    pub fn get<C: Comparator<K>>(&self, key: K, forest: &MapForest<K, V>, comp: &C) -> Option<V> {
        self.root
            .expand()
            .and_then(|root| Path::default().find(key, root, &forest.nodes, comp))
    }

    /// Look up the value stored for `key`.
    ///
    /// If it exists, return the stored key-value pair.
    ///
    /// Otherwise, return the last key-value pair with a key that is less than or equal to `key`.
    ///
    /// If no stored keys are less than or equal to `key`, return `None`.
    pub fn get_or_less<C: Comparator<K>>(
        &self,
        key: K,
        forest: &MapForest<K, V>,
        comp: &C,
    ) -> Option<(K, V)> {
        self.root.expand().and_then(|root| {
            let mut path = Path::default();
            match path.find(key, root, &forest.nodes, comp) {
                Some(v) => Some((key, v)),
                None => path.prev(root, &forest.nodes),
            }
        })
    }

    /// Insert `key, value` into the map and return the old value stored for `key`, if any.
    pub fn insert<C: Comparator<K>>(
        &mut self,
        key: K,
        value: V,
        forest: &mut MapForest<K, V>,
        comp: &C,
    ) -> Option<V> {
        self.cursor(forest, comp).insert(key, value)
    }

    /// Remove `key` from the map and return the removed value for `key`, if any.
    pub fn remove<C: Comparator<K>>(
        &mut self,
        key: K,
        forest: &mut MapForest<K, V>,
        comp: &C,
    ) -> Option<V> {
        let mut c = self.cursor(forest, comp);
        if c.goto(key).is_some() {
            c.remove()
        } else {
            None
        }
    }

    /// Remove all entries.
    pub fn clear(&mut self, forest: &mut MapForest<K, V>) {
        if let Some(root) = self.root.take() {
            forest.nodes.free_tree(root);
        }
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// Remove all key-value pairs where the predicate returns false.
    ///
    /// The predicate is allowed to update the values stored in the map.
    pub fn retain<F>(&mut self, forest: &mut MapForest<K, V>, mut predicate: F)
    where
        F: FnMut(K, &mut V) -> bool,
    {
        let mut path = Path::default();
        if let Some(root) = self.root.expand() {
            path.first(root, &forest.nodes);
        }
        while let Some((node, entry)) = path.leaf_pos() {
            let keep = {
                let (ks, vs) = forest.nodes[node].unwrap_leaf_mut();
                predicate(ks[entry], &mut vs[entry])
            };
            if keep {
                path.next(&forest.nodes);
            } else {
                self.root = path.remove(&mut forest.nodes).into();
            }
        }
    }

    /// Create a cursor for navigating this map. The cursor is initially positioned off the end of
    /// the map.
    pub fn cursor<'a, C: Comparator<K>>(
        &'a mut self,
        forest: &'a mut MapForest<K, V>,
        comp: &'a C,
    ) -> MapCursor<'a, K, V, C> {
        MapCursor::new(self, forest, comp)
    }

    /// Create an iterator traversing this map. The iterator type is `(K, V)`.
    pub fn iter<'a>(&'a self, forest: &'a MapForest<K, V>) -> MapIter<'a, K, V> {
        MapIter {
            root: self.root,
            pool: &forest.nodes,
            path: Path::default(),
        }
    }
}

impl<K, V> Default for Map<K, V>
where
    K: Copy,
    V: Copy,
{
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
impl<K, V> Map<K, V>
where
    K: Copy + fmt::Display,
    V: Copy,
{
    /// Verify consistency.
    fn verify<C: Comparator<K>>(&self, forest: &MapForest<K, V>, comp: &C)
    where
        NodeData<MapTypes<K, V>>: fmt::Display,
    {
        if let Some(root) = self.root.expand() {
            forest.nodes.verify_tree(root, comp);
        }
    }

    /// Get a text version of the path to `key`.
    fn tpath<C: Comparator<K>>(&self, key: K, forest: &MapForest<K, V>, comp: &C) -> String {
        use alloc::string::ToString;
        match self.root.expand() {
            None => "map(empty)".to_string(),
            Some(root) => {
                let mut path = Path::default();
                path.find(key, root, &forest.nodes, comp);
                path.to_string()
            }
        }
    }
}

/// A position in a `Map` used to navigate and modify the ordered map.
///
/// A cursor always points at a key-value pair in the map, or "off the end" which is a position
/// after the last entry in the map.
pub struct MapCursor<'a, K, V, C>
where
    K: 'a + Copy,
    V: 'a + Copy,
    C: 'a + Comparator<K>,
{
    root: &'a mut PackedOption<Node>,
    pool: &'a mut NodePool<MapTypes<K, V>>,
    comp: &'a C,
    path: Path<MapTypes<K, V>>,
}

impl<'a, K, V, C> MapCursor<'a, K, V, C>
where
    K: Copy,
    V: Copy,
    C: Comparator<K>,
{
    /// Create a cursor with a default (off-the-end) location.
    fn new(container: &'a mut Map<K, V>, forest: &'a mut MapForest<K, V>, comp: &'a C) -> Self {
        Self {
            root: &mut container.root,
            pool: &mut forest.nodes,
            comp,
            path: Path::default(),
        }
    }

    /// Is this cursor pointing to an empty map?
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    /// Move cursor to the next key-value pair and return it.
    ///
    /// If the cursor reaches the end, return `None` and leave the cursor at the off-the-end
    /// position.
    pub fn next(&mut self) -> Option<(K, V)> {
        self.path.next(self.pool)
    }

    /// Move cursor to the previous key-value pair and return it.
    ///
    /// If the cursor is already pointing at the first entry, leave it there and return `None`.
    pub fn prev(&mut self) -> Option<(K, V)> {
        self.root
            .expand()
            .and_then(|root| self.path.prev(root, self.pool))
    }

    /// Get the current key, or `None` if the cursor is at the end.
    pub fn key(&self) -> Option<K> {
        self.path
            .leaf_pos()
            .and_then(|(node, entry)| self.pool[node].unwrap_leaf().0.get(entry).cloned())
    }

    /// Get the current value, or `None` if the cursor is at the end.
    pub fn value(&self) -> Option<V> {
        self.path
            .leaf_pos()
            .and_then(|(node, entry)| self.pool[node].unwrap_leaf().1.get(entry).cloned())
    }

    /// Get a mutable reference to the current value, or `None` if the cursor is at the end.
    pub fn value_mut(&mut self) -> Option<&mut V> {
        self.path
            .leaf_pos()
            .and_then(move |(node, entry)| self.pool[node].unwrap_leaf_mut().1.get_mut(entry))
    }

    /// Move this cursor to `key`.
    ///
    /// If `key` is in the map, place the cursor at `key` and return the corresponding value.
    ///
    /// If `key` is not in the set, place the cursor at the next larger element (or the end) and
    /// return `None`.
    pub fn goto(&mut self, elem: K) -> Option<V> {
        self.root.expand().and_then(|root| {
            let v = self.path.find(elem, root, self.pool, self.comp);
            if v.is_none() {
                self.path.normalize(self.pool);
            }
            v
        })
    }

    /// Move this cursor to the first element.
    pub fn goto_first(&mut self) -> Option<V> {
        self.root.map(|root| self.path.first(root, self.pool).1)
    }

    /// Insert `(key, value))` into the map and leave the cursor at the inserted pair.
    ///
    /// If the map did not contain `key`, return `None`.
    ///
    /// If `key` is already present, replace the existing with `value` and return the old value.
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        match self.root.expand() {
            None => {
                let root = self.pool.alloc_node(NodeData::leaf(key, value));
                *self.root = root.into();
                self.path.set_root_node(root);
                None
            }
            Some(root) => {
                // TODO: Optimize the case where `self.path` is already at the correct insert pos.
                let old = self.path.find(key, root, self.pool, self.comp);
                if old.is_some() {
                    *self.path.value_mut(self.pool) = value;
                } else {
                    *self.root = self.path.insert(key, value, self.pool).into();
                }
                old
            }
        }
    }

    /// Remove the current entry (if any) and return the mapped value.
    /// This advances the cursor to the next entry after the removed one.
    pub fn remove(&mut self) -> Option<V> {
        let value = self.value();
        if value.is_some() {
            *self.root = self.path.remove(self.pool).into();
        }
        value
    }
}

/// An iterator visiting the key-value pairs of a `Map`.
pub struct MapIter<'a, K, V>
where
    K: 'a + Copy,
    V: 'a + Copy,
{
    root: PackedOption<Node>,
    pool: &'a NodePool<MapTypes<K, V>>,
    path: Path<MapTypes<K, V>>,
}

impl<'a, K, V> Iterator for MapIter<'a, K, V>
where
    K: 'a + Copy,
    V: 'a + Copy,
{
    type Item = (K, V);

    fn next(&mut self) -> Option<Self::Item> {
        // We use `self.root` to indicate if we need to go to the first element. Reset to `None`
        // once we've returned the first element. This also works for an empty tree since the
        // `path.next()` call returns `None` when the path is empty. This also fuses the iterator.
        match self.root.take() {
            Some(root) => Some(self.path.first(root, self.pool)),
            None => self.path.next(self.pool),
        }
    }
}

#[cfg(test)]
impl<'a, K, V, C> MapCursor<'a, K, V, C>
where
    K: Copy + fmt::Display,
    V: Copy + fmt::Display,
    C: Comparator<K>,
{
    fn verify(&self) {
        self.path.verify(self.pool);
        self.root.map(|root| self.pool.verify_tree(root, self.comp));
    }

    /// Get a text version of the path to the current position.
    fn tpath(&self) -> String {
        use alloc::string::ToString;
        self.path.to_string()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use alloc::vec::Vec;
    use core::mem;

    #[test]
    fn node_size() {
        // check that nodes are cache line sized when keys and values are 32 bits.
        type F = MapTypes<u32, u32>;
        assert_eq!(mem::size_of::<NodeData<F>>(), 64);
    }

    #[test]
    fn empty() {
        let mut f = MapForest::<u32, f32>::new();
        f.clear();

        let mut m = Map::<u32, f32>::new();
        assert!(m.is_empty());
        m.clear(&mut f);

        assert_eq!(m.get(7, &f, &()), None);
        assert_eq!(m.iter(&f).next(), None);
        assert_eq!(m.get_or_less(7, &f, &()), None);
        m.retain(&mut f, |_, _| unreachable!());

        let mut c = m.cursor(&mut f, &());
        assert!(c.is_empty());
        assert_eq!(c.key(), None);
        assert_eq!(c.value(), None);
        assert_eq!(c.next(), None);
        assert_eq!(c.prev(), None);
        c.verify();
        assert_eq!(c.tpath(), "<empty path>");
        assert_eq!(c.goto_first(), None);
        assert_eq!(c.tpath(), "<empty path>");
    }

    #[test]
    fn inserting() {
        let f = &mut MapForest::<u32, f32>::new();
        let mut m = Map::<u32, f32>::new();

        // The first seven values stay in a single leaf node.
        assert_eq!(m.insert(50, 5.0, f, &()), None);
        assert_eq!(m.insert(50, 5.5, f, &()), Some(5.0));
        assert_eq!(m.insert(20, 2.0, f, &()), None);
        assert_eq!(m.insert(80, 8.0, f, &()), None);
        assert_eq!(m.insert(40, 4.0, f, &()), None);
        assert_eq!(m.insert(60, 6.0, f, &()), None);
        assert_eq!(m.insert(90, 9.0, f, &()), None);
        assert_eq!(m.insert(200, 20.0, f, &()), None);

        m.verify(f, &());

        assert_eq!(
            m.iter(f).collect::<Vec<_>>(),
            [
                (20, 2.0),
                (40, 4.0),
                (50, 5.5),
                (60, 6.0),
                (80, 8.0),
                (90, 9.0),
                (200, 20.0),
            ]
        );

        assert_eq!(m.get(0, f, &()), None);
        assert_eq!(m.get(20, f, &()), Some(2.0));
        assert_eq!(m.get(30, f, &()), None);
        assert_eq!(m.get(40, f, &()), Some(4.0));
        assert_eq!(m.get(50, f, &()), Some(5.5));
        assert_eq!(m.get(60, f, &()), Some(6.0));
        assert_eq!(m.get(70, f, &()), None);
        assert_eq!(m.get(80, f, &()), Some(8.0));
        assert_eq!(m.get(100, f, &()), None);

        assert_eq!(m.get_or_less(0, f, &()), None);
        assert_eq!(m.get_or_less(20, f, &()), Some((20, 2.0)));
        assert_eq!(m.get_or_less(30, f, &()), Some((20, 2.0)));
        assert_eq!(m.get_or_less(40, f, &()), Some((40, 4.0)));
        assert_eq!(m.get_or_less(200, f, &()), Some((200, 20.0)));
        assert_eq!(m.get_or_less(201, f, &()), Some((200, 20.0)));

        {
            let mut c = m.cursor(f, &());
            assert_eq!(c.prev(), Some((200, 20.0)));
            assert_eq!(c.prev(), Some((90, 9.0)));
            assert_eq!(c.prev(), Some((80, 8.0)));
            assert_eq!(c.prev(), Some((60, 6.0)));
            assert_eq!(c.prev(), Some((50, 5.5)));
            assert_eq!(c.prev(), Some((40, 4.0)));
            assert_eq!(c.prev(), Some((20, 2.0)));
            assert_eq!(c.prev(), None);
        }

        // Test some removals where the node stays healthy.
        assert_eq!(m.tpath(50, f, &()), "node0[2]");
        assert_eq!(m.tpath(80, f, &()), "node0[4]");
        assert_eq!(m.tpath(200, f, &()), "node0[6]");

        assert_eq!(m.remove(80, f, &()), Some(8.0));
        assert_eq!(m.tpath(50, f, &()), "node0[2]");
        assert_eq!(m.tpath(80, f, &()), "node0[4]");
        assert_eq!(m.tpath(200, f, &()), "node0[5]");
        assert_eq!(m.remove(80, f, &()), None);
        m.verify(f, &());

        assert_eq!(m.remove(20, f, &()), Some(2.0));
        assert_eq!(m.tpath(50, f, &()), "node0[1]");
        assert_eq!(m.tpath(80, f, &()), "node0[3]");
        assert_eq!(m.tpath(200, f, &()), "node0[4]");
        assert_eq!(m.remove(20, f, &()), None);
        m.verify(f, &());

        // [ 40 50 60 90 200 ]

        {
            let mut c = m.cursor(f, &());
            assert_eq!(c.goto_first(), Some(4.0));
            assert_eq!(c.key(), Some(40));
            assert_eq!(c.value(), Some(4.0));
            assert_eq!(c.next(), Some((50, 5.5)));
            assert_eq!(c.next(), Some((60, 6.0)));
            assert_eq!(c.next(), Some((90, 9.0)));
            assert_eq!(c.next(), Some((200, 20.0)));
            c.verify();
            assert_eq!(c.next(), None);
            c.verify();
        }

        // Removals from the root leaf node beyond underflow.
        assert_eq!(m.remove(200, f, &()), Some(20.0));
        assert_eq!(m.remove(40, f, &()), Some(4.0));
        assert_eq!(m.remove(60, f, &()), Some(6.0));
        m.verify(f, &());
        assert_eq!(m.remove(50, f, &()), Some(5.5));
        m.verify(f, &());
        assert_eq!(m.remove(90, f, &()), Some(9.0));
        m.verify(f, &());
        assert!(m.is_empty());
    }

    #[test]
    fn split_level0_leaf() {
        // Various ways of splitting a full leaf node at level 0.
        let f = &mut MapForest::<u32, f32>::new();

        fn full_leaf(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
            let mut m = Map::new();
            for n in 1..8 {
                m.insert(n * 10, n as f32 * 1.1, f, &());
            }
            m
        }

        // Insert at front of leaf.
        let mut m = full_leaf(f);
        m.insert(5, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(5, f, &()), Some(4.2));

        // Retain even entries, with altered values.
        m.retain(f, |k, v| {
            *v = (k / 10) as f32;
            (k % 20) == 0
        });
        assert_eq!(
            m.iter(f).collect::<Vec<_>>(),
            [(20, 2.0), (40, 4.0), (60, 6.0)]
        );

        // Insert at back of leaf.
        let mut m = full_leaf(f);
        m.insert(80, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(80, f, &()), Some(4.2));

        // Insert before middle (40).
        let mut m = full_leaf(f);
        m.insert(35, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(35, f, &()), Some(4.2));

        // Insert after middle (40).
        let mut m = full_leaf(f);
        m.insert(45, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(45, f, &()), Some(4.2));

        m.clear(f);
        assert!(m.is_empty());
    }

    #[test]
    fn split_level1_leaf() {
        // Various ways of splitting a full leaf node at level 1.
        let f = &mut MapForest::<u32, f32>::new();

        // Return a map whose root node is a full inner node, and the leaf nodes are all full
        // containing:
        //
        // 110, 120, ..., 170
        // 210, 220, ..., 270
        // ...
        // 810, 820, ..., 870
        fn full(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
            let mut m = Map::new();

            // Start by inserting elements in order.
            // This should leave 8 leaf nodes with 4 elements in each.
            for row in 1..9 {
                for col in 1..5 {
                    m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &());
                }
            }

            // Then top up the leaf nodes without splitting them.
            for row in 1..9 {
                for col in 5..8 {
                    m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &());
                }
            }

            m
        }

        let mut m = full(f);
        // Verify geometry. Get get node2 as the root and leaves node0, 1, 3, ...
        m.verify(f, &());
        assert_eq!(m.tpath(110, f, &()), "node2[0]--node0[0]");
        assert_eq!(m.tpath(140, f, &()), "node2[0]--node0[3]");
        assert_eq!(m.tpath(210, f, &()), "node2[1]--node1[0]");
        assert_eq!(m.tpath(270, f, &()), "node2[1]--node1[6]");
        assert_eq!(m.tpath(310, f, &()), "node2[2]--node3[0]");
        assert_eq!(m.tpath(810, f, &()), "node2[7]--node8[0]");
        assert_eq!(m.tpath(870, f, &()), "node2[7]--node8[6]");

        {
            let mut c = m.cursor(f, &());
            assert_eq!(c.goto_first(), Some(1.1));
            assert_eq!(c.key(), Some(110));
        }

        // Front of first leaf.
        m.insert(0, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(0, f, &()), Some(4.2));

        // First leaf split 4-4 after appending to LHS.
        f.clear();
        m = full(f);
        m.insert(135, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(135, f, &()), Some(4.2));

        // First leaf split 4-4 after prepending to RHS.
        f.clear();
        m = full(f);
        m.insert(145, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(145, f, &()), Some(4.2));

        // First leaf split 4-4 after appending to RHS.
        f.clear();
        m = full(f);
        m.insert(175, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(175, f, &()), Some(4.2));

        // Left-middle leaf split, ins LHS.
        f.clear();
        m = full(f);
        m.insert(435, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(435, f, &()), Some(4.2));

        // Left-middle leaf split, ins RHS.
        f.clear();
        m = full(f);
        m.insert(445, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(445, f, &()), Some(4.2));

        // Right-middle leaf split, ins LHS.
        f.clear();
        m = full(f);
        m.insert(535, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(535, f, &()), Some(4.2));

        // Right-middle leaf split, ins RHS.
        f.clear();
        m = full(f);
        m.insert(545, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(545, f, &()), Some(4.2));

        // Last leaf split, ins LHS.
        f.clear();
        m = full(f);
        m.insert(835, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(835, f, &()), Some(4.2));

        // Last leaf split, ins RHS.
        f.clear();
        m = full(f);
        m.insert(845, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(845, f, &()), Some(4.2));

        // Front of last leaf.
        f.clear();
        m = full(f);
        m.insert(805, 4.2, f, &());
        m.verify(f, &());
        assert_eq!(m.get(805, f, &()), Some(4.2));

        m.clear(f);
        m.verify(f, &());
    }

    // Make a tree with two barely healthy leaf nodes:
    // [ 10 20 30 40 ] [ 50 60 70 80 ]
    fn two_leaf(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
        f.clear();
        let mut m = Map::new();
        for n in 1..9 {
            m.insert(n * 10, n as f32, f, &());
        }
        m
    }

    #[test]
    fn remove_level1() {
        let f = &mut MapForest::<u32, f32>::new();
        let mut m = two_leaf(f);

        // Verify geometry.
        m.verify(f, &());
        assert_eq!(m.tpath(10, f, &()), "node2[0]--node0[0]");
        assert_eq!(m.tpath(40, f, &()), "node2[0]--node0[3]");
        assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(50, f, &()), "node2[1]--node1[0]");
        assert_eq!(m.tpath(80, f, &()), "node2[1]--node1[3]");

        // Remove the front entry from a node that stays healthy.
        assert_eq!(m.insert(55, 5.5, f, &()), None);
        assert_eq!(m.remove(50, f, &()), Some(5.0));
        m.verify(f, &());
        assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(55, f, &()), "node2[1]--node1[0]");

        // Remove the front entry from the first leaf node: No critical key to update.
        assert_eq!(m.insert(15, 1.5, f, &()), None);
        assert_eq!(m.remove(10, f, &()), Some(1.0));
        m.verify(f, &());

        // [ 15 20 30 40 ] [ 55 60 70 80 ]

        // Remove the front entry from a right-most node that underflows.
        // No rebalancing for the right-most node. Still need critical key update.
        assert_eq!(m.remove(55, f, &()), Some(5.5));
        m.verify(f, &());
        assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]");

        // [ 15 20 30 40 ] [ 60 70 80 ]

        // Replenish the right leaf.
        assert_eq!(m.insert(90, 9.0, f, &()), None);
        assert_eq!(m.insert(100, 10.0, f, &()), None);
        m.verify(f, &());
        assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]");

        // [ 15 20 30 40 ] [ 60 70 80 90 100 ]

        // Removing one entry from the left leaf should trigger a rebalancing from the right
        // sibling.
        assert_eq!(m.remove(20, f, &()), Some(2.0));
        m.verify(f, &());

        // [ 15 30 40 60 ] [ 70 80 90 100 ]
        // Check that the critical key was updated correctly.
        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[3]");
        assert_eq!(m.tpath(60, f, &()), "node2[0]--node0[3]");
        assert_eq!(m.tpath(70, f, &()), "node2[1]--node1[0]");

        // Remove front entry from the left-most leaf node, underflowing.
        // This should cause two leaf nodes to be merged and the root node to go away.
        assert_eq!(m.remove(15, f, &()), Some(1.5));
        m.verify(f, &());
    }

    #[test]
    fn remove_level1_rightmost() {
        let f = &mut MapForest::<u32, f32>::new();
        let mut m = two_leaf(f);

        // [ 10 20 30 40 ] [ 50 60 70 80 ]

        // Remove entries from the right leaf. This doesn't trigger a rebalancing.
        assert_eq!(m.remove(60, f, &()), Some(6.0));
        assert_eq!(m.remove(80, f, &()), Some(8.0));
        assert_eq!(m.remove(50, f, &()), Some(5.0));
        m.verify(f, &());

        // [ 10 20 30 40 ] [ 70 ]
        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[4]");
        assert_eq!(m.tpath(70, f, &()), "node2[1]--node1[0]");

        // Removing the last entry from the right leaf should cause a collapse.
        assert_eq!(m.remove(70, f, &()), Some(7.0));
        m.verify(f, &());
    }

    // Make a 3-level tree with barely healthy nodes.
    // 1 root, 8 inner nodes, 7*4+5=33 leaf nodes, 4 entries each.
    fn level3_sparse(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
        f.clear();
        let mut m = Map::new();
        for n in 1..133 {
            m.insert(n * 10, n as f32, f, &());
        }
        m
    }

    #[test]
    fn level3_removes() {
        let f = &mut MapForest::<u32, f32>::new();
        let mut m = level3_sparse(f);
        m.verify(f, &());

        // Check geometry.
        // Root: node11
        // [ node2 170 node10 330 node16 490 node21 650 node26 810 node31 970 node36 1130 node41 ]
        // L1: node11
        assert_eq!(m.tpath(0, f, &()), "node11[0]--node2[0]--node0[0]");
        assert_eq!(m.tpath(10000, f, &()), "node11[7]--node41[4]--node40[4]");

        // 650 is a critical key in the middle of the root.
        assert_eq!(m.tpath(640, f, &()), "node11[3]--node21[3]--node19[3]");
        assert_eq!(m.tpath(650, f, &()), "node11[4]--node26[0]--node20[0]");

        // Deleting 640 triggers a rebalance from node19 to node 20, cascading to n21 -> n26.
        assert_eq!(m.remove(640, f, &()), Some(64.0));
        m.verify(f, &());
        assert_eq!(m.tpath(650, f, &()), "node11[3]--node26[3]--node20[3]");

        // 1130 is in the first leaf of the last L1 node. Deleting it triggers a rebalance node35
        // -> node37, but no rebalance above where there is no right sibling.
        assert_eq!(m.tpath(1130, f, &()), "node11[6]--node41[0]--node35[0]");
        assert_eq!(m.tpath(1140, f, &()), "node11[6]--node41[0]--node35[1]");
        assert_eq!(m.remove(1130, f, &()), Some(113.0));
        m.verify(f, &());
        assert_eq!(m.tpath(1140, f, &()), "node11[6]--node41[0]--node37[0]");
    }

    #[test]
    fn insert_many() {
        let f = &mut MapForest::<u32, f32>::new();
        let mut m = Map::<u32, f32>::new();

        let mm = 4096;
        let mut x = 0;

        for n in 0..mm {
            assert_eq!(m.insert(x, n as f32, f, &()), None);
            m.verify(f, &());

            x = (x + n + 1) % mm;
        }

        x = 0;
        for n in 0..mm {
            assert_eq!(m.get(x, f, &()), Some(n as f32));
            x = (x + n + 1) % mm;
        }

        x = 0;
        for n in 0..mm {
            assert_eq!(m.remove(x, f, &()), Some(n as f32));
            m.verify(f, &());

            x = (x + n + 1) % mm;
        }

        assert!(m.is_empty());
    }
}