use super::map::MIN_LEN;
use super::node::{ForceResult::*, Root};
use super::search::{search_node, SearchResult::*};
use core::borrow::Borrow;

impl<K, V> Root<K, V> {
    pub fn split_off<Q: ?Sized + Ord>(&mut self, right_root: &mut Self, key: &Q)
    where
        K: Borrow<Q>,
    {
        debug_assert!(right_root.height() == 0);
        debug_assert!(right_root.len() == 0);

        let left_root = self;
        for _ in 0..left_root.height() {
            right_root.push_internal_level();
        }

        {
            let mut left_node = left_root.borrow_mut();
            let mut right_node = right_root.borrow_mut();

            loop {
                let mut split_edge = match search_node(left_node, key) {
                    // key is going to the right tree
                    Found(kv) => kv.left_edge(),
                    GoDown(edge) => edge,
                };

                split_edge.move_suffix(&mut right_node);

                match (split_edge.force(), right_node.force()) {
                    (Internal(edge), Internal(node)) => {
                        left_node = edge.descend();
                        right_node = node.first_edge().descend();
                    }
                    (Leaf(_), Leaf(_)) => {
                        break;
                    }
                    _ => unreachable!(),
                }
            }
        }

        left_root.fix_right_border();
        right_root.fix_left_border();
    }

    /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.
    fn fix_top(&mut self) {
        while self.height() > 0 && self.len() == 0 {
            self.pop_internal_level();
        }
    }

    /// Stock up or merge away any underfull nodes on the right border of the
    /// tree. The other nodes, those that are not the root nor a rightmost edge,
    /// must already have at least MIN_LEN elements.
    fn fix_right_border(&mut self) {
        self.fix_top();

        {
            let mut cur_node = self.borrow_mut();

            while let Internal(node) = cur_node.force() {
                let mut last_kv = node.last_kv().consider_for_balancing();

                if last_kv.can_merge() {
                    cur_node = last_kv.merge_tracking_child();
                } else {
                    let right_len = last_kv.right_child_len();
                    // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
                    if right_len < MIN_LEN + 1 {
                        last_kv.bulk_steal_left(MIN_LEN + 1 - right_len);
                    }
                    cur_node = last_kv.into_right_child();
                }
                debug_assert!(cur_node.len() > MIN_LEN);
            }
        }

        self.fix_top();
    }

    /// The symmetric clone of `fix_right_border`.
    fn fix_left_border(&mut self) {
        self.fix_top();

        {
            let mut cur_node = self.borrow_mut();

            while let Internal(node) = cur_node.force() {
                let mut first_kv = node.first_kv().consider_for_balancing();

                if first_kv.can_merge() {
                    cur_node = first_kv.merge_tracking_child();
                } else {
                    let left_len = first_kv.left_child_len();
                    // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
                    if left_len < MIN_LEN + 1 {
                        first_kv.bulk_steal_right(MIN_LEN + 1 - left_len);
                    }
                    cur_node = first_kv.into_left_child();
                }
                debug_assert!(cur_node.len() > MIN_LEN);
            }
        }

        self.fix_top();
    }
}