Method insert_non_full

src/structures/tree.rs:42–77

(
        &mut self,
        node: &mut Node<K, V>,
        key: K,
        value: V,
    )

    }

    fn insert_non_full(
        &mut self,
        node: &mut Node<K, V>,
        key: K,
        value: V,
    ) -> Result<(), io::Error> {
        match &mut node.node_type {
            NodeType::Leaf => {
                let idx = node.keys.binary_search(&key).unwrap_or_else(|x| x);
                node.keys.insert(idx, key);
                node.values.insert(idx, Some(value));
                Ok(())
            }
            NodeType::Internal => {
                let idx = node.keys.binary_search(&key).unwrap_or_else(|x| x);
                let child_idx = if idx == node.keys.len() || key < node.keys[idx] {
                    idx
                } else {
                    idx + 1
                };

                if self.is_node_full(&node.children[child_idx])? {
                    let (median, sibling) = node.children[child_idx].split()?;
                    node.keys.insert(idx, median);
                    node.children.insert(child_idx + 1, Box::new(sibling));
                    if key >= node.keys[idx] {
                        self.insert_non_full(&mut *node.children[child_idx + 1], key, value)
                    } else {
                        self.insert_non_full(&mut *node.children[child_idx], key, value)
                    }
                } else {
                    self.insert_non_full(&mut *node.children[child_idx], key, value)
                }
            }
        }
    }

    fn is_node_full(&self, node: &Node<K, V>) -> Result<bool, io::Error> {
        Ok(node.keys.len() == node.max_keys)