use super::map::MIN_LEN;
use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef};
use core::alloc::Allocator;

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
    /// 从树中删除一个键 - 值对，并返回该对，以及对应于该对的叶子 edge。
    /// 这可能会清空内部的根节点，调用者应从保存该树的 map 中弹出该根节点。
    /// 调用者还应减少 map 的长度。
    ///
    pub fn remove_kv_tracking<F: FnOnce(), A: Allocator + Clone>(
        self,
        handle_emptied_internal_root: F,
        alloc: A,
    ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
        match self.force() {
            Leaf(node) => node.remove_leaf_kv(handle_emptied_internal_root, alloc),
            Internal(node) => node.remove_internal_kv(handle_emptied_internal_root, alloc),
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
    fn remove_leaf_kv<F: FnOnce(), A: Allocator + Clone>(
        self,
        handle_emptied_internal_root: F,
        alloc: A,
    ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
        let (old_kv, mut pos) = self.remove();
        let len = pos.reborrow().into_node().len();
        if len < MIN_LEN {
            let idx = pos.idx();
            // 我们必须暂时忘记子类型，因为叶子的直接父级没有明显的节点类型。
            //
            let new_pos = match pos.into_node().forget_type().choose_parent_kv() {
                Ok(Left(left_parent_kv)) => {
                    debug_assert!(left_parent_kv.right_child_len() == MIN_LEN - 1);
                    if left_parent_kv.can_merge() {
                        left_parent_kv.merge_tracking_child_edge(Right(idx), alloc.clone())
                    } else {
                        debug_assert!(left_parent_kv.left_child_len() > MIN_LEN);
                        left_parent_kv.steal_left(idx)
                    }
                }
                Ok(Right(right_parent_kv)) => {
                    debug_assert!(right_parent_kv.left_child_len() == MIN_LEN - 1);
                    if right_parent_kv.can_merge() {
                        right_parent_kv.merge_tracking_child_edge(Left(idx), alloc.clone())
                    } else {
                        debug_assert!(right_parent_kv.right_child_len() > MIN_LEN);
                        right_parent_kv.steal_right(idx)
                    }
                }
                Err(pos) => unsafe { Handle::new_edge(pos, idx) },
            };
            // SAFETY: `new_pos` 是我们开始的叶子或同级。
            pos = unsafe { new_pos.cast_to_leaf_unchecked() };

            // 仅当我们合并时，父级 (如果有的话) 就会缩小，但是跳过以下步骤，否则在基准测试中不会得到回报。
            //
            // SAFETY: 我们不会通过递归处理 `pos` 的父对象来销毁或重新排列 `pos` 所在的叶子。在最坏的情况下，我们将通过祖父母销毁或重新排列父级，从而在叶内更改到父级的链接。
            //
            //
            //
            //
            if let Ok(parent) = unsafe { pos.reborrow_mut() }.into_node().ascend() {
                if !parent.into_node().forget_type().fix_node_and_affected_ancestors(alloc) {
                    handle_emptied_internal_root();
                }
            }
        }
        (old_kv, pos)
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
    fn remove_internal_kv<F: FnOnce(), A: Allocator + Clone>(
        self,
        handle_emptied_internal_root: F,
        alloc: A,
    ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
        // 从其叶子上移除一个相邻的 KV，然后将其放回原处，要求我们将其移除。
        //
        // 由于 `choose_parent_kv` 中列出的原因，请优先选择左侧的相邻 KV。
        let left_leaf_kv = self.left_edge().descend().last_leaf_edge().left_kv();
        let left_leaf_kv = unsafe { left_leaf_kv.ok().unwrap_unchecked() };
        let (left_kv, left_hole) = left_leaf_kv.remove_leaf_kv(handle_emptied_internal_root, alloc);

        // 内部节点可能已从中被窃取或合并。
        // 向右返回以找到原始 KV 的终止位置。
        let mut internal = unsafe { left_hole.next_kv().ok().unwrap_unchecked() };
        let old_kv = internal.replace_kv(left_kv.0, left_kv.1);
        let pos = internal.next_leaf_edge();
        (old_kv, pos)
    }
}