use super::merge_iter::MergeIterInner;
use super::node::{self, Root};
use core::alloc::Allocator;
use core::iter::FusedIterator;

impl<K, V> Root<K, V> {
    /// 从两个升序的迭代器的并集追加所有键值对，并在此过程中递增 `length` 变量。后者使调用者在丢弃处理程序 panic 时更容易避免泄漏。
    ///
    /// 如果两个迭代器都产生相同的键，则此方法将从左迭代器中丢弃 pair，并从右迭代器中追加 pair。
    ///
    /// 如果要使树以严格的升序结束 (例如 `BTreeMap`)，则两个迭代器都应以严格的升序生成键，每个键都大于树中的所有键，包括输入时树中已存在的任何键。
    ///
    ///
    ///
    ///
    ///
    ///
    pub fn append_from_sorted_iters<I, A: Allocator + Clone>(
        &mut self,
        left: I,
        right: I,
        length: &mut usize,
        alloc: A,
    ) where
        K: Ord,
        I: Iterator<Item = (K, V)> + FusedIterator,
    {
        // 我们准备在线性时间内将 `left` 和 `right` 合并为一个排序的序列。
        let iter = MergeIter(MergeIterInner::new(left, right));

        // 同时，我们根据线性时间中的排序序列构建一棵树。
        self.bulk_push(iter, length, alloc)
    }

    /// 将所有键值对推入树的末尾，并在此过程中递增 `length` 变量。
    /// 后者使调用者在迭代器出现 panic 时更容易避免泄漏。
    ///
    pub fn bulk_push<I, A: Allocator + Clone>(&mut self, iter: I, length: &mut usize, alloc: A)
    where
        I: Iterator<Item = (K, V)>,
    {
        let mut cur_node = self.borrow_mut().last_leaf_edge().into_node();
        // 遍历所有键值对，将它们推入正确级别的节点。
        for (key, value) in iter {
            // 尝试将键值对推入当前的叶子节点。
            if cur_node.len() < node::CAPACITY {
                cur_node.push(key, value);
            } else {
                // 没有剩余空间了，上去推一下。
                let mut open_node;
                let mut test_node = cur_node.forget_type();
                loop {
                    match test_node.ascend() {
                        Ok(parent) => {
                            let parent = parent.into_node();
                            if parent.len() < node::CAPACITY {
                                // 找到一个剩余空间的节点，将其推入此处。
                                open_node = parent;
                                break;
                            } else {
                                // 再上去
                                test_node = parent.forget_type();
                            }
                        }
                        Err(_) => {
                            // 我们在顶部，创建一个新的根节点并推送到那里。
                            open_node = self.push_internal_level(alloc.clone());
                            break;
                        }
                    }
                }

                // push 键值对和新的右子树。
                let tree_height = open_node.height() - 1;
                let mut right_tree = Root::new(alloc.clone());
                for _ in 0..tree_height {
                    right_tree.push_internal_level(alloc.clone());
                }
                open_node.push(key, value, right_tree);

                // 再次下降到最右边的叶子。
                cur_node = open_node.forget_type().last_leaf_edge().into_node();
            }

            // 每次迭代都增加长度，以确保即使推进迭代器出现 panic，map 也会丢弃附加的元素。
            //
            *length += 1;
        }
        self.fix_right_border_of_plentiful();
    }
}

// 用于将两个排序的序列合并为一个的迭代器
struct MergeIter<K, V, I: Iterator<Item = (K, V)>>(MergeIterInner<I>);

impl<K: Ord, V, I> Iterator for MergeIter<K, V, I>
where
    I: Iterator<Item = (K, V)> + FusedIterator,
{
    type Item = (K, V);

    /// 如果两个键相等，则从正确的源返回键值对。
    fn next(&mut self) -> Option<(K, V)> {
        let (a_next, b_next) = self.0.nexts(|a: &(K, V), b: &(K, V)| K::cmp(&a.0, &b.0));
        b_next.or(a_next)
    }
}