use crate::{IndexTreeMap, Item, Key, Node, Value, ARRAY_SIZE};

use std::cmp::Ordering::{Equal, Greater, Less};

impl<K: Key, V: Value> IndexTreeMap<K, V> {
    /// Returns a reference to the value corresponding to the key.
    ///
    /// The key may be any borrowed form of the map’s key type, but the
    /// ordering on the borrowed form must match the ordering on the key type.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get(&1), Some(&"a".to_string()));
    /// assert_eq!(tree.get(&2), None);
    /// ```
    pub fn get(&self, key: &K) -> Option<&V> {
        match self.root.get_item(key) {
            None => None,
            Some(item) => match &item.value {
                None => None,
                Some(value) => Some(value),
            },
        }
    }

    /// Returns the key-value pair corresponding to the supplied key.
    ///
    /// The supplied key may be any borrowed form of the map’s key type, but
    /// the ordering on the borrowed form must match the ordering on the key type.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_key_value(&1), (Some(&1), Some(&"a".to_string())));
    /// assert_eq!(tree.get_key_value(&2), (None, None));
    /// ```
    pub fn get_key_value(&self, key: &K) -> (Option<&K>, Option<&V>) {
        match self.root.get_item(key) {
            None => (None, None),
            Some(item) => (
                Some(item.key.as_ref()),
                match &item.value {
                    None => None,
                    Some(value) => Some(value.as_ref()),
                },
            ),
        }
    }

    /// Returns a reference to the value corresponding to the index.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_from_index(0), Some(&"a".to_string()));
    /// assert_eq!(tree.get_from_index(1), None);
    /// ```
    pub fn get_from_index(&self, id: usize) -> Option<&V> {
        match self.root.get_item_from_index(id) {
            None => None,
            Some(item) => match &item.value {
                None => None,
                Some(value) => Some(value),
            },
        }
    }

    /// Returns a reference to the key corresponding to the index.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_key_from_index(0), Some(&1));
    /// assert_eq!(tree.get_key_from_index(1), None);
    /// ```
    pub fn get_key_from_index(&self, id: usize) -> Option<&K> {
        if self.contains_index(id) {
            match self.root.get_item_from_index(id) {
                None => None,
                Some(item) => Some(item.key.as_ref()),
            }
        } else {
            None
        }
    }

    /// Returns a reference to the key-value pair corresponding to the index.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_key_value_from_index(0), (Some(&1), Some(&"a".to_string())));
    /// assert_eq!(tree.get_key_value_from_index(1), (None, None));
    /// ```
    pub fn get_key_value_from_index(&self, id: usize) -> (Option<&K>, Option<&V>) {
        if self.contains_index(id) {
            match self.root.get_item_from_index(id) {
                None => return (None, None),
                Some(item) => {
                    return (
                        Some(item.key.as_ref()),
                        match &item.value {
                            None => None,
                            Some(value) => Some(value.as_ref()),
                        },
                    )
                }
            }
        }
        (None, None)
    }

    /// Returns a reference to the first key in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_first_key(), Some(&1));
    /// ```
    pub fn get_first_key(&self) -> Option<&K> {
        self.get_key_from_index(0)
    }

    /// Returns a reference to the first value in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_first_value(), Some(&"a".to_string()));
    /// ```
    pub fn get_first_value(&self) -> Option<&V> {
        self.get_from_index(0)
    }

    /// Returns a reference to the first key-value pair in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// assert_eq!(tree.get_first_key_value(), (Some(&1),Some(&"a".to_string())));
    /// ```
    pub fn get_first_key_value(&self) -> (Option<&K>, Option<&V>) {
        self.get_key_value_from_index(0)
    }

    /// Returns a reference to the last key in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// tree.insert(2, "b".to_string());
    /// assert_eq!(tree.get_last_key(), Some(&2));
    /// ```
    pub fn get_last_key(&self) -> Option<&K> {
        self.get_key_from_index(self.size - 1)
    }

    /// Returns a reference to the first value in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// tree.insert(2, "b".to_string());
    /// assert_eq!(tree.get_last_value(), Some(&"b".to_string()));
    /// ```
    pub fn get_last_value(&self) -> Option<&V> {
        self.get_from_index(self.size - 1)
    }

    /// Returns a reference to the last key-value pair in the map.
    ///
    /// # Example
    ///
    /// Basic usage:
    /// ```rust
    /// use indextreemap::IndexTreeMap;
    ///
    /// let mut tree = IndexTreeMap::new();
    /// tree.insert(1, "a".to_string());
    /// tree.insert(2, "b".to_string());
    /// assert_eq!(tree.get_last_key_value(), (Some(&2),Some(&"b".to_string())));
    /// ```
    pub fn get_last_key_value(&self) -> (Option<&K>, Option<&V>) {
        self.get_key_value_from_index(self.size - 1)
    }
}

impl<K: Key, V: Value> Node<K, V> {
    pub fn get_item(&self, key: &K) -> Option<&Item<K, V>> {
        for (index, item) in self.items.iter().enumerate() {
            match item {
                None => return None,
                Some(item) => match key.compare_keys(item.key.as_ref()) {
                    Less => {
                        if index == 0 {
                            match &self.children[0] {
                                None => return None,
                                Some(child) => return child.get_item(key),
                            }
                        }
                    }
                    Equal => return Some(item.as_ref()),
                    Greater => {
                        if index == ARRAY_SIZE - 1 {
                            match &self.children[1] {
                                None => return None,
                                Some(child) => return child.get_item(key),
                            }
                        }
                    }
                },
            }
        }
        None
    }

    pub fn get_item_from_index(&self, mut id: usize) -> Option<&Item<K, V>> {
        if let Some(child) = self.children[0].as_deref() {
            if id < self.children_size[0] {
                return child.get_item_from_index(id);
            } else {
                id -= self.children_size[0]
            }
        }

        if id < ARRAY_SIZE {
            match self.items[id].as_deref() {
                None => return None,
                Some(item) => return Some(item),
            }
        } else {
            id -= ARRAY_SIZE;
        }

        match self.children[1].as_deref() {
            None => return None,
            Some(child) => {
                if id < self.children_size[1] {
                    return child.get_item_from_index(id);
                }
            }
        }
        None
    }
}