use core::borrow::Borrow;
use core::hint;
use core::ops::RangeBounds;
use core::ptr;

use super::node::{marker, ForceResult::*, Handle, NodeRef};
use super::search::SearchBound;

use crate::alloc::Allocator;
// `front` 和 `back` 始终都是 `None` 或都是 `Some`。
pub struct LeafRange<BorrowType, K, V> {
    front: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
    back: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
}

impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> {
    fn clone(&self) -> Self {
        LeafRange { front: self.front.clone(), back: self.back.clone() }
    }
}

impl<B, K, V> Default for LeafRange<B, K, V> {
    fn default() -> Self {
        LeafRange { front: None, back: None }
    }
}

impl<BorrowType, K, V> LeafRange<BorrowType, K, V> {
    pub fn none() -> Self {
        LeafRange { front: None, back: None }
    }

    fn is_empty(&self) -> bool {
        self.front == self.back
    }

    /// 暂时取出另一个相同范围的不可变值。
    pub fn reborrow(&self) -> LeafRange<marker::Immut<'_>, K, V> {
        LeafRange {
            front: self.front.as_ref().map(|f| f.reborrow()),
            back: self.back.as_ref().map(|b| b.reborrow()),
        }
    }
}

impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> {
    #[inline]
    pub fn next_checked(&mut self) -> Option<(&'a K, &'a V)> {
        self.perform_next_checked(|kv| kv.into_kv())
    }

    #[inline]
    pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> {
        self.perform_next_back_checked(|kv| kv.into_kv())
    }
}

impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
    #[inline]
    pub fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
        self.perform_next_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
    }

    #[inline]
    pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
        self.perform_next_back_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
    }
}

impl<BorrowType: marker::BorrowType, K, V> LeafRange<BorrowType, K, V> {
    /// 如果可能，从下面的 KV 中提取一些结果并移动到超出它的 edge。
    fn perform_next_checked<F, R>(&mut self, f: F) -> Option<R>
    where
        F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
    {
        if self.is_empty() {
            None
        } else {
            super::mem::replace(self.front.as_mut().unwrap(), |front| {
                let kv = front.next_kv().ok().unwrap();
                let result = f(&kv);
                (kv.next_leaf_edge(), Some(result))
            })
        }
    }

    /// 如果可能，从前面的 KV 中提取一些结果并移动到超出它的 edge。
    fn perform_next_back_checked<F, R>(&mut self, f: F) -> Option<R>
    where
        F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
    {
        if self.is_empty() {
            None
        } else {
            super::mem::replace(self.back.as_mut().unwrap(), |back| {
                let kv = back.next_back_kv().ok().unwrap();
                let result = f(&kv);
                (kv.next_back_leaf_edge(), Some(result))
            })
        }
    }
}

enum LazyLeafHandle<BorrowType, K, V> {
    Root(NodeRef<BorrowType, K, V, marker::LeafOrInternal>), // 还没有下降
    Edge(Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>),
}

impl<'a, K: 'a, V: 'a> Clone for LazyLeafHandle<marker::Immut<'a>, K, V> {
    fn clone(&self) -> Self {
        match self {
            LazyLeafHandle::Root(root) => LazyLeafHandle::Root(*root),
            LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(*edge),
        }
    }
}

impl<BorrowType, K, V> LazyLeafHandle<BorrowType, K, V> {
    fn reborrow(&self) -> LazyLeafHandle<marker::Immut<'_>, K, V> {
        match self {
            LazyLeafHandle::Root(root) => LazyLeafHandle::Root(root.reborrow()),
            LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(edge.reborrow()),
        }
    }
}

// `front` 和 `back` 始终都是 `None` 或都是 `Some`。
pub struct LazyLeafRange<BorrowType, K, V> {
    front: Option<LazyLeafHandle<BorrowType, K, V>>,
    back: Option<LazyLeafHandle<BorrowType, K, V>>,
}

impl<B, K, V> Default for LazyLeafRange<B, K, V> {
    fn default() -> Self {
        LazyLeafRange { front: None, back: None }
    }
}

impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> {
    fn clone(&self) -> Self {
        LazyLeafRange { front: self.front.clone(), back: self.back.clone() }
    }
}

impl<BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
    pub fn none() -> Self {
        LazyLeafRange { front: None, back: None }
    }

    /// 暂时取出另一个相同范围的不可变值。
    pub fn reborrow(&self) -> LazyLeafRange<marker::Immut<'_>, K, V> {
        LazyLeafRange {
            front: self.front.as_ref().map(|f| f.reborrow()),
            back: self.back.as_ref().map(|b| b.reborrow()),
        }
    }
}

impl<'a, K, V> LazyLeafRange<marker::Immut<'a>, K, V> {
    #[inline]
    pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
        unsafe { self.init_front().unwrap().next_unchecked() }
    }

    #[inline]
    pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
        unsafe { self.init_back().unwrap().next_back_unchecked() }
    }
}

impl<'a, K, V> LazyLeafRange<marker::ValMut<'a>, K, V> {
    #[inline]
    pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
        unsafe { self.init_front().unwrap().next_unchecked() }
    }

    #[inline]
    pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
        unsafe { self.init_back().unwrap().next_back_unchecked() }
    }
}

impl<K, V> LazyLeafRange<marker::Dying, K, V> {
    fn take_front(
        &mut self,
    ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> {
        match self.front.take()? {
            LazyLeafHandle::Root(root) => Some(root.first_leaf_edge()),
            LazyLeafHandle::Edge(edge) => Some(edge),
        }
    }

    #[inline]
    pub unsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
        &mut self,
        alloc: A,
    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
        debug_assert!(self.front.is_some());
        let front = self.init_front().unwrap();
        unsafe { front.deallocating_next_unchecked(alloc) }
    }

    #[inline]
    pub unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
        &mut self,
        alloc: A,
    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
        debug_assert!(self.back.is_some());
        let back = self.init_back().unwrap();
        unsafe { back.deallocating_next_back_unchecked(alloc) }
    }

    #[inline]
    pub fn deallocating_end<A: Allocator + Clone>(&mut self, alloc: A) {
        if let Some(front) = self.take_front() {
            front.deallocating_end(alloc)
        }
    }
}

impl<BorrowType: marker::BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
    fn init_front(
        &mut self,
    ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
        if let Some(LazyLeafHandle::Root(root)) = &self.front {
            self.front = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.first_leaf_edge()));
        }
        match &mut self.front {
            None => None,
            Some(LazyLeafHandle::Edge(edge)) => Some(edge),
            // SAFETY: 上面的代码将取代它。
            Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
        }
    }

    fn init_back(
        &mut self,
    ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
        if let Some(LazyLeafHandle::Root(root)) = &self.back {
            self.back = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.last_leaf_edge()));
        }
        match &mut self.back {
            None => None,
            Some(LazyLeafHandle::Edge(edge)) => Some(edge),
            // SAFETY: 上面的代码将取代它。
            Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
        }
    }
}

impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    /// 查找限定树中指定范围的不同叶 edges。
    ///
    /// 如果存在这种不同的 edges，则按升序返回它们，这意味着在结果的 `front` 上对 `next_unchecked` 的非零调用次数或者对结果的 `back` 上的 `next_back_unchecked` 调用最终将达到相同的 edge。
    ///
    ///
    /// 如果没有这样的 edges，即，如果树不包含范围内的键，则返回空的 `front` 和 `back`。
    ///
    /// # Safety
    /// 除非 `BorrowType` 是 `Immut`，否则不要使用句柄两次访问同一个 KV。
    ///
    ///
    ///
    ///
    unsafe fn find_leaf_edges_spanning_range<Q: ?Sized, R>(
        self,
        range: R,
    ) -> LeafRange<BorrowType, K, V>
    where
        Q: Ord,
        K: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        match self.search_tree_for_bifurcation(&range) {
            Err(_) => LeafRange::none(),
            Ok((
                node,
                lower_edge_idx,
                upper_edge_idx,
                mut lower_child_bound,
                mut upper_child_bound,
            )) => {
                let mut lower_edge = unsafe { Handle::new_edge(ptr::read(&node), lower_edge_idx) };
                let mut upper_edge = unsafe { Handle::new_edge(node, upper_edge_idx) };
                loop {
                    match (lower_edge.force(), upper_edge.force()) {
                        (Leaf(f), Leaf(b)) => return LeafRange { front: Some(f), back: Some(b) },
                        (Internal(f), Internal(b)) => {
                            (lower_edge, lower_child_bound) =
                                f.descend().find_lower_bound_edge(lower_child_bound);
                            (upper_edge, upper_child_bound) =
                                b.descend().find_upper_bound_edge(upper_child_bound);
                        }
                        _ => unreachable!("BTreeMap has different depths"),
                    }
                }
            }
        }
    }
}

fn full_range<BorrowType: marker::BorrowType, K, V>(
    root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
) -> LazyLeafRange<BorrowType, K, V> {
    LazyLeafRange {
        front: Some(LazyLeafHandle::Root(root1)),
        back: Some(LazyLeafHandle::Root(root2)),
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
    /// 查找在树中划定特定范围的一对叶子 edges。
    ///
    /// 仅当按键对树进行排序 (如 `BTreeMap` 中的树) 时，结果才有意义。
    ///
    pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::Immut<'a>, K, V>
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        // SAFETY: 我们的借用类型是不可变。
        unsafe { self.find_leaf_edges_spanning_range(range) }
    }

    /// 查找界定整个树的一对叶子 edges。
    pub fn full_range(self) -> LazyLeafRange<marker::Immut<'a>, K, V> {
        full_range(self, self)
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::ValMut<'a>, K, V, marker::LeafOrInternal> {
    /// 将一个唯一的 quot 拆分为一对指定范围的叶子 edges。
    /// 结果是非唯一引用，允许 (some) 可变的，必须谨慎使用。
    ///
    /// 仅当按键对树进行排序 (如 `BTreeMap` 中的树) 时，结果才有意义。
    ///
    ///
    /// # Safety
    /// 请勿使用重复的句柄访问同一 KV 两次。
    ///
    pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::ValMut<'a>, K, V>
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        unsafe { self.find_leaf_edges_spanning_range(range) }
    }

    /// 将唯一的 quot 拆分为一对叶子 edges，它们界定了树的整个范围。
    /// 结果是非唯一引用，允许可变的 (仅值)，因此必须小心使用。
    ///
    pub fn full_range(self) -> LazyLeafRange<marker::ValMut<'a>, K, V> {
        // 我们在这里复制根 NodeRef - 我们将永远不会访问同一 KV 两次，也永远不会出现重叠的引用值。
        //
        let self2 = unsafe { ptr::read(&self) };
        full_range(self, self2)
    }
}

impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
    /// 将唯一的 quot 拆分为一对叶子 edges，它们界定了树的整个范围。
    /// 结果是非唯一引用，允许大规模破坏性可变的，因此必须格外小心使用。
    ///
    pub fn full_range(self) -> LazyLeafRange<marker::Dying, K, V> {
        // 我们在这里复制根 NodeRef - 我们将永远不会以与从根获得的引用重叠的方式访问它。
        //
        let self2 = unsafe { ptr::read(&self) };
        full_range(self, self2)
    }
}

impl<BorrowType: marker::BorrowType, K, V>
    Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
{
    /// 给定叶子 edge 句柄，将 [`Result::Ok`] 及其句柄返回到右侧的相邻 KV，该相邻 KV 在同一叶子节点中或在祖先节点中。
    ///
    /// 如果叶子 edge 是树中的最后一个叶子，则返回带有根节点的 [`Result::Err`]。
    pub fn next_kv(
        self,
    ) -> Result<
        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
        NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    > {
        let mut edge = self.forget_node_type();
        loop {
            edge = match edge.right_kv() {
                Ok(kv) => return Ok(kv),
                Err(last_edge) => match last_edge.into_node().ascend() {
                    Ok(parent_edge) => parent_edge.forget_node_type(),
                    Err(root) => return Err(root),
                },
            }
        }
    }

    /// 给定叶子 edge 句柄，将 [`Result::Ok`] 及其句柄返回到左侧的相邻 KV，该相邻 KV 在同一叶子节点中或在祖先节点中。
    ///
    /// 如果叶子 edge 是树中的第一个叶子，则返回带有根节点的 [`Result::Err`]。
    pub fn next_back_kv(
        self,
    ) -> Result<
        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
        NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
    > {
        let mut edge = self.forget_node_type();
        loop {
            edge = match edge.left_kv() {
                Ok(kv) => return Ok(kv),
                Err(last_edge) => match last_edge.into_node().ascend() {
                    Ok(parent_edge) => parent_edge.forget_node_type(),
                    Err(root) => return Err(root),
                },
            }
        }
    }
}

impl<BorrowType: marker::BorrowType, K, V>
    Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
{
    /// 给定内部 edge 句柄，将 [`Result::Ok`] 及其句柄返回到右侧的相邻 KV，该相邻 KV 在同一内部节点中或在祖先节点中。
    ///
    /// 如果内部 edge 是树中的最后一个，则返回带有根节点的 [`Result::Err`]。
    fn next_kv(
        self,
    ) -> Result<
        Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>,
        NodeRef<BorrowType, K, V, marker::Internal>,
    > {
        let mut edge = self;
        loop {
            edge = match edge.right_kv() {
                Ok(internal_kv) => return Ok(internal_kv),
                Err(last_edge) => match last_edge.into_node().ascend() {
                    Ok(parent_edge) => parent_edge,
                    Err(root) => return Err(root),
                },
            }
        }
    }
}

impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
    /// 给定 dying 树的叶子 edge 句柄，返回右侧的下一个叶子 edge，以及中间的键值对 (如果它们存在)。
    ///
    ///
    /// 如果给定的 edge 是叶子中的最后一个，则此方法将释放叶子以及到达最后一个 edge 的所有祖先节点。
    /// 这意味着如果没有更多的键值对跟随，整个树将被释放并且没有任何东西可以返回。
    ///
    /// # Safety
    /// - 给定的 edge 一定不是先前由对方 `deallocating_next_back` 返回的。
    /// - 返回的 KV 句柄仅对访问键和值有效，并且仅在下一次调用 `deallocating_` 方法之前有效。
    ///
    ///
    ///
    ///
    unsafe fn deallocating_next<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
    {
        let mut edge = self.forget_node_type();
        loop {
            edge = match edge.right_kv() {
                Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)),
                Err(last_edge) => {
                    match unsafe { last_edge.into_node().deallocate_and_ascend(alloc.clone()) } {
                        Some(parent_edge) => parent_edge.forget_node_type(),
                        None => return None,
                    }
                }
            }
        }
    }

    /// 给定 dying 树的叶子 edge 句柄，返回左侧的下一个叶子 edge，以及中间的键值对 (如果它们存在)。
    ///
    /// 如果给定的 edge 是叶子中的第一个，则此方法释放叶子节点，以及到达第一个 edge 的任何祖先节点。
    ///
    /// 这意味着如果没有更多的键值对跟随，整个树将被释放并且没有任何东西可以返回。
    ///
    /// # Safety
    /// - 给定的 edge 一定不是先前由对方 `deallocating_next` 返回的。
    /// - 返回的 KV 句柄仅对访问键和值有效，并且仅在下一次调用 `deallocating_` 方法之前有效。
    ///
    ///
    ///
    ///
    unsafe fn deallocating_next_back<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
    {
        let mut edge = self.forget_node_type();
        loop {
            edge = match edge.left_kv() {
                Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)),
                Err(last_edge) => {
                    match unsafe { last_edge.into_node().deallocate_and_ascend(alloc.clone()) } {
                        Some(parent_edge) => parent_edge.forget_node_type(),
                        None => return None,
                    }
                }
            }
        }
    }

    /// 释放从叶子到根的一堆节点。
    /// 这是在 `deallocating_next` 和 `deallocating_next_back` 一直在树的两边蚕食并且击中了相同的 edge 之后，重新分配树的其余部分的唯一方法。
    /// 由于仅在返回所有键和值后才调用它，因此不会对任何键或值进行清理。
    ///
    ///
    ///
    fn deallocating_end<A: Allocator + Clone>(self, alloc: A) {
        let mut edge = self.forget_node_type();
        while let Some(parent_edge) =
            unsafe { edge.into_node().deallocate_and_ascend(alloc.clone()) }
        {
            edge = parent_edge.forget_node_type();
        }
    }
}

impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
    /// 将叶子 edge 句柄移动到下一个叶子 edge，并在其中的键和值之间返回引用。
    ///
    ///
    /// # Safety
    /// 在行进方向上必须有另一个 KV。
    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
        super::mem::replace(self, |leaf_edge| {
            let kv = leaf_edge.next_kv().ok().unwrap();
            (kv.next_leaf_edge(), kv.into_kv())
        })
    }

    /// 将叶子 edge 句柄移动到上一个叶子 edge，并在其中的键和值返回 quot。
    ///
    ///
    /// # Safety
    /// 在行进方向上必须有另一个 KV。
    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
        super::mem::replace(self, |leaf_edge| {
            let kv = leaf_edge.next_back_kv().ok().unwrap();
            (kv.next_back_leaf_edge(), kv.into_kv())
        })
    }
}

impl<'a, K, V> Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge> {
    /// 将叶子 edge 句柄移动到下一个叶子 edge，并在其中的键和值之间返回引用。
    ///
    ///
    /// # Safety
    /// 在行进方向上必须有另一个 KV。
    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
        let kv = super::mem::replace(self, |leaf_edge| {
            let kv = leaf_edge.next_kv().ok().unwrap();
            (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)
        });
        // 根据基准测试，这样做的最后速度更快。
        kv.into_kv_valmut()
    }

    /// 将叶子 edge 句柄移动到上一个叶子，并在其中的键和值之间返回 quot。
    ///
    ///
    /// # Safety
    /// 在行进方向上必须有另一个 KV。
    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
        let kv = super::mem::replace(self, |leaf_edge| {
            let kv = leaf_edge.next_back_kv().ok().unwrap();
            (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)
        });
        // 根据基准测试，这样做的最后速度更快。
        kv.into_kv_valmut()
    }
}

impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
    /// 将叶子 edge 句柄移动到下一个叶子 edge，并返回它们之间的键和值，重新分配留下的任何节点，同时将对应的 edge 保留在其父子节点中。
    ///
    ///
    /// # Safety
    /// - 在行进方向上必须有另一个 KV。
    /// - 该 KV 之前没有由对应的 `deallocating_next_back_unchecked` 在用于遍历树的句柄的任何副本上返回。
    ///
    /// 处理更新后的句柄的唯一安全方法是比较它，丢弃它，或再次调用此方法或对应的 `deallocating_next_back_unchecked`。
    ///
    ///
    ///
    ///
    unsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
        &mut self,
        alloc: A,
    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
        super::mem::replace(self, |leaf_edge| unsafe {
            leaf_edge.deallocating_next(alloc).unwrap()
        })
    }

    /// 将叶子 edge 句柄移动到上一个叶子 edge，并返回它们之间的键和值，重新分配留下的任何节点，同时将对应的 edge 保留在其父子节点中。
    ///
    ///
    /// # Safety
    /// - 在行进方向上必须有另一个 KV。
    /// - 该叶子 edge 之前没有由对应的 `deallocating_next_unchecked` 在用于遍历树的句柄的任何副本上返回。
    ///
    /// 处理更新后的句柄的唯一安全方法是比较它，丢弃它，或再次调用此方法或对应的 `deallocating_next_unchecked`。
    ///
    ///
    ///
    ///
    unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
        &mut self,
        alloc: A,
    ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
        super::mem::replace(self, |leaf_edge| unsafe {
            leaf_edge.deallocating_next_back(alloc).unwrap()
        })
    }
}

impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    /// 返回节点内或节点下最左边的叶子 edge - 换句话说，向前导航时需要首先使用的 edge (向后导航时则需要最后的 edge)。
    ///
    #[inline]
    pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
        let mut node = self;
        loop {
            match node.force() {
                Leaf(leaf) => return leaf.first_edge(),
                Internal(internal) => node = internal.first_edge().descend(),
            }
        }
    }

    /// 返回节点内或节点下最右边的叶子 edge - 换句话说，向前导航时需要最后一个 edge (向后导航时需要第一个 edge)。
    ///
    #[inline]
    pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
        let mut node = self;
        loop {
            match node.force() {
                Leaf(leaf) => return leaf.last_edge(),
                Internal(internal) => node = internal.last_edge().descend(),
            }
        }
    }
}

pub enum Position<BorrowType, K, V> {
    Leaf(NodeRef<BorrowType, K, V, marker::Leaf>),
    Internal(NodeRef<BorrowType, K, V, marker::Internal>),
    InternalKV(Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>),
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
    /// 按键升序访问叶子节点和内部 KV，还按深度优先顺序访问整个内部节点，这意味着内部节点先于其各个 KV 和其子节点。
    ///
    ///
    pub fn visit_nodes_in_order<F>(self, mut visit: F)
    where
        F: FnMut(Position<marker::Immut<'a>, K, V>),
    {
        match self.force() {
            Leaf(leaf) => visit(Position::Leaf(leaf)),
            Internal(internal) => {
                visit(Position::Internal(internal));
                let mut edge = internal.first_edge();
                loop {
                    edge = match edge.descend().force() {
                        Leaf(leaf) => {
                            visit(Position::Leaf(leaf));
                            match edge.next_kv() {
                                Ok(kv) => {
                                    visit(Position::InternalKV(kv));
                                    kv.right_edge()
                                }
                                Err(_) => return,
                            }
                        }
                        Internal(internal) => {
                            visit(Position::Internal(internal));
                            internal.first_edge()
                        }
                    }
                }
            }
        }
    }

    /// 计算 (子) 树中的元素数。
    pub fn calc_length(self) -> usize {
        let mut result = 0;
        self.visit_nodes_in_order(|pos| match pos {
            Position::Leaf(node) => result += node.len(),
            Position::Internal(node) => result += node.len(),
            Position::InternalKV(_) => (),
        });
        result
    }
}

impl<BorrowType: marker::BorrowType, K, V>
    Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>
{
    /// 返回最接近 KV 的叶子 edge，以进行前向导航。
    pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
        match self.force() {
            Leaf(leaf_kv) => leaf_kv.right_edge(),
            Internal(internal_kv) => {
                let next_internal_edge = internal_kv.right_edge();
                next_internal_edge.descend().first_leaf_edge()
            }
        }
    }

    /// 返回最接近 KV 的叶子 edge，以进行向后导航。
    pub fn next_back_leaf_edge(
        self,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
        match self.force() {
            Leaf(leaf_kv) => leaf_kv.left_edge(),
            Internal(internal_kv) => {
                let next_internal_edge = internal_kv.left_edge();
                next_internal_edge.descend().last_leaf_edge()
            }
        }
    }
}

impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    /// 返回对应于给定边界为真的第一个点的叶 edge。
    ///
    pub fn lower_bound<Q: ?Sized>(
        self,
        mut bound: SearchBound<&Q>,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
    where
        Q: Ord,
        K: Borrow<Q>,
    {
        let mut node = self;
        loop {
            let (edge, new_bound) = node.find_lower_bound_edge(bound);
            match edge.force() {
                Leaf(edge) => return edge,
                Internal(edge) => {
                    node = edge.descend();
                    bound = new_bound;
                }
            }
        }
    }

    /// 返回对应于给定边界为真的最后一个点的叶 edge。
    ///
    pub fn upper_bound<Q: ?Sized>(
        self,
        mut bound: SearchBound<&Q>,
    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
    where
        Q: Ord,
        K: Borrow<Q>,
    {
        let mut node = self;
        loop {
            let (edge, new_bound) = node.find_upper_bound_edge(bound);
            match edge.force() {
                Leaf(edge) => return edge,
                Internal(edge) => {
                    node = edge.descend();
                    bound = new_bound;
                }
            }
        }
    }
}