use crate::{IndexTreeMap, Item, Key, Node, Value, ARRAY_SIZE};
use std::cmp::Ordering::{Equal, Greater, Less};

impl<K: Key, V: Value> IndexTreeMap<K, V> {
    pub fn insert(&mut self, key: K, value: V) {
        if !self.root.insert(key, Some(value)) {
            self.size += 1;
        }
    }
}

impl<K: Key, V: Value> Node<K, V> {
    pub fn insert(&mut self, key: K, value: Option<V>) -> bool {
        let mut contains = false;

        'search: for (index, item) in self.items.iter().enumerate() {
            match item {
                None => {
                    self.items[index] = Some(Box::new(Item::new(key, value)));
                    break;
                }
                Some(item) => match key.compare_keys(item.key.as_ref()) {
                    Less => {
                        if index == 0 {
                            match self.children[0].as_deref_mut() {
                                None => {
                                    if self.is_full() {
                                        self.insert_with_overflow(index, key, value);
                                    } else {
                                        self.insert_item(index, key, value);
                                    }
                                }
                                Some(child) => {
                                    contains = child.insert(key, value);
                                    if !contains {
                                        self.children_size[0] += 1;
                                        self.balance();
                                    }
                                }
                            }
                        } else if self.is_full() {
                            contains = self.insert_with_overflow(index, key, value);
                        } else {
                            self.insert_item(index, key, value);
                        }

                        break;
                    }
                    Equal => {
                        self.items[index].replace(Box::new(Item::new(key, value)));
                        contains = true;
                        break;
                    }
                    Greater => {
                        if index == ARRAY_SIZE - 1 {
                            match self.children[1].as_deref_mut() {
                                None => {
                                    self.children[1] = Some({
                                        let mut node = Node::new();
                                        node.insert(key, value);
                                        node
                                    });
                                    self.children_size[1] += 1;
                                }
                                Some(child) => {
                                    contains = child.insert(key, value);
                                    if !contains {
                                        self.children_size[1] += 1;
                                        self.balance();
                                    }
                                }
                            }
                            break;
                        } else {
                            continue 'search;
                        }
                    }
                },
            }
        }
        self.balance();
        contains
    }

    pub fn insert_with_overflow(&mut self, index: usize, key: K, value: Option<V>) -> bool {
        let side = if index < ARRAY_SIZE / 2 { 0 } else { 1 };
        let mut contains = false;

        if index == 0 {
            match self.children[0].as_deref_mut() {
                None => {
                    self.children[0] = Some({
                        let mut node = Node::new();
                        node.insert(key, value);
                        node
                    });
                    self.children_size[0] += 1;
                }
                Some(child) => {
                    contains = child.insert(key, value);
                    if !contains {
                        self.children_size[0] += 1;
                        self.balance();
                    }
                }
            }
        } else {
            let overflow = match side {
                0 => {
                    let overflow = self.items[0].take();
                    'insert: for id in 0..ARRAY_SIZE {
                        if id == index {
                            self.items[id - 1] = Some(Box::new(Item::new(key, value)));
                            break 'insert;
                        } else {
                            self.items[id - 1] = self.items[id].take();
                            continue 'insert;
                        }
                    }
                    overflow
                }
                _ => {
                    let overflow = self.items[ARRAY_SIZE - 1].take();
                    self.bias_right();
                    'insert: for id in 0..ARRAY_SIZE {
                        if id == index {
                            self.items[id - 1] = Some(Box::new(Item::new(key, value)));
                            break 'insert;
                        } else {
                            self.items[id - 1] = self.items[id].take();
                            continue 'insert;
                        }
                    }
                    overflow
                }
            };

            match overflow {
                None => {}
                Some(item) => {
                    let key = item.key.as_ref().to_owned();
                    let value = item.value.map(|value| value.as_ref().to_owned());
                    match self.children[side].as_deref_mut() {
                        None => {
                            self.children[side] = Some({
                                let mut node = Node::new();
                                node.insert(key, value);
                                node
                            });
                            self.children_size[side] += 1;
                        }
                        Some(child) => {
                            contains = child.insert(key, value);
                            if !contains {
                                self.children_size[1] += 1;
                                self.balance();
                            }
                        }
                    }
                }
            }
        }

        contains
    }

    pub fn insert_item(&mut self, index: usize, key: K, value: Option<V>) {
        if index < ARRAY_SIZE {
            self.bias_left();
            self.items.rotate_right(1);
            'insert: for id in 0..ARRAY_SIZE {
                if id == index {
                    self.items[id] = Some(Box::new(Item::new(key, value)));
                    break 'insert;
                } else {
                    self.items[id] = self.items[id + 1].take();
                    continue 'insert;
                }
            }
        }
    }
}