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

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
    /// 通过与同级合并或从同级中窃取来存储可能不足的节点。
    /// 如果成功但代价是缩小父节点，则返回缩小的父节点。
    /// 如果节点为空 root，则返回 `Err`。
    ///
    fn fix_node_through_parent<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> Result<Option<NodeRef<marker::Mut<'a>, K, V, marker::Internal>>, Self> {
        let len = self.len();
        if len >= MIN_LEN {
            Ok(None)
        } else {
            match self.choose_parent_kv() {
                Ok(Left(mut left_parent_kv)) => {
                    if left_parent_kv.can_merge() {
                        let parent = left_parent_kv.merge_tracking_parent(alloc);
                        Ok(Some(parent))
                    } else {
                        left_parent_kv.bulk_steal_left(MIN_LEN - len);
                        Ok(None)
                    }
                }
                Ok(Right(mut right_parent_kv)) => {
                    if right_parent_kv.can_merge() {
                        let parent = right_parent_kv.merge_tracking_parent(alloc);
                        Ok(Some(parent))
                    } else {
                        right_parent_kv.bulk_steal_right(MIN_LEN - len);
                        Ok(None)
                    }
                }
                Err(root) => {
                    if len > 0 {
                        Ok(None)
                    } else {
                        Err(root)
                    }
                }
            }
        }
    }
}

impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
    /// 存储可能不足的节点，如果这导致其父节点缩小，则递归地存储父节点。
    /// 如果固定了树，则返回 `true`; 如果由于根节点为空而不能返回 `false`，则返回 `false`。
    ///
    /// 此方法不希望祖先在输入时就已经未满，如果遇到空祖先，则该方法会出现 panics。
    ///
    ///
    ///
    pub fn fix_node_and_affected_ancestors<A: Allocator + Clone>(mut self, alloc: A) -> bool {
        loop {
            match self.fix_node_through_parent(alloc.clone()) {
                Ok(Some(parent)) => self = parent.forget_type(),
                Ok(None) => return true,
                Err(_) => return false,
            }
        }
    }
}

impl<K, V> Root<K, V> {
    /// 删除顶部的空白层，但是如果整棵树都是空白的，则保留一片空白的叶子。
    pub fn fix_top<A: Allocator + Clone>(&mut self, alloc: A) {
        while self.height() > 0 && self.len() == 0 {
            self.pop_internal_level(alloc.clone());
        }
    }

    /// 存储或合并树右边界上的任何未满的节点。
    /// 其他节点 (既不是根节点，也不是最右边的边) 必须已经至少具有 MIN_LEN 个元素。
    ///
    pub fn fix_right_border<A: Allocator + Clone>(&mut self, alloc: A) {
        self.fix_top(alloc.clone());
        if self.len() > 0 {
            self.borrow_mut().last_kv().fix_right_border_of_right_edge(alloc.clone());
            self.fix_top(alloc);
        }
    }

    /// `fix_right_border` 的对称克隆。
    pub fn fix_left_border<A: Allocator + Clone>(&mut self, alloc: A) {
        self.fix_top(alloc.clone());
        if self.len() > 0 {
            self.borrow_mut().first_kv().fix_left_border_of_left_edge(alloc.clone());
            self.fix_top(alloc);
        }
    }

    /// 在树的右边界存储任何未满的节点。
    /// 其他节点，既不是根节点也不是最右边的节点，必须准备好窃取最多 MIN_LEN 个元素。
    ///
    pub fn fix_right_border_of_plentiful(&mut self) {
        let mut cur_node = self.borrow_mut();
        while let Internal(internal) = cur_node.force() {
            // 检查最右边的子节点是否未满。
            let mut last_kv = internal.last_kv().consider_for_balancing();
            debug_assert!(last_kv.left_child_len() >= MIN_LEN * 2);
            let right_child_len = last_kv.right_child_len();
            if right_child_len < MIN_LEN {
                // 我们需要 steal。
                last_kv.bulk_steal_left(MIN_LEN - right_child_len);
            }

            // 再往下走。
            cur_node = last_kv.into_right_child();
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
    fn fix_left_border_of_left_edge<A: Allocator + Clone>(mut self, alloc: A) {
        while let Internal(internal_kv) = self.force() {
            self = internal_kv.fix_left_child(alloc.clone()).first_kv();
            debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
        }
    }

    fn fix_right_border_of_right_edge<A: Allocator + Clone>(mut self, alloc: A) {
        while let Internal(internal_kv) = self.force() {
            self = internal_kv.fix_right_child(alloc.clone()).last_kv();
            debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
        }
    }
}

impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
    /// 假设左边的子节点还不满，则储存左边的子节点，并提供一个额外的元素以允许依次合并其子节点而不会变得不足。
    ///
    /// 返回左子节点。
    ///
    fn fix_left_child<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
        let mut internal_kv = self.consider_for_balancing();
        let left_len = internal_kv.left_child_len();
        debug_assert!(internal_kv.right_child_len() >= MIN_LEN);
        if internal_kv.can_merge() {
            internal_kv.merge_tracking_child(alloc)
        } else {
            // `MIN_LEN + 1` 以避免在下一级发生合并时重新调整。
            let count = (MIN_LEN + 1).saturating_sub(left_len);
            if count > 0 {
                internal_kv.bulk_steal_right(count);
            }
            internal_kv.into_left_child()
        }
    }

    /// 假设左边的子节点还不完整，则存储右边的子节点，并提供一个额外的元素以允许依次合并其子对象而不会变得不够完整。
    ///
    /// 返回正确的子节点结束的任何地方。
    ///
    fn fix_right_child<A: Allocator + Clone>(
        self,
        alloc: A,
    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
        let mut internal_kv = self.consider_for_balancing();
        let right_len = internal_kv.right_child_len();
        debug_assert!(internal_kv.left_child_len() >= MIN_LEN);
        if internal_kv.can_merge() {
            internal_kv.merge_tracking_child(alloc)
        } else {
            // `MIN_LEN + 1` 以避免在下一级发生合并时重新调整。
            let count = (MIN_LEN + 1).saturating_sub(right_len);
            if count > 0 {
                internal_kv.bulk_steal_left(count);
            }
            internal_kv.into_right_child()
        }
    }
}