//! A map based on a splay tree.
use std;
use std::mem;
use std::borrow::Borrow;
use tree_core;
use iter;

/// A map based on a splay tree.
///
/// A splay tree based map is a self-adjusting data structure.
/// It performs insertion, removal and look-up in `O(log n)` amortized time.
///
/// It is a logic error for a key to be modified in such a way that
/// the key's ordering relative to any other key,
/// as determined by the `Ord` trait, changes while it is in the map.
/// This is normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
///
/// # Examples
/// ```
/// use splay_tree::SplayMap;
///
/// let mut map = SplayMap::new();
///
/// map.insert("foo", 1);
/// map.insert("bar", 2);
/// map.insert("baz", 3);
///
/// assert_eq!(map.get("foo"), Some(&1));
/// assert_eq!(map.remove("foo"), Some(1));
/// assert_eq!(map.get("foo"), None);
///
/// for (k, v) in &map {
///     println!("{}: {}", k, v);
/// }
/// ```
///
/// `SplayMap` implements an [Entry API](#method.entry) which allows for
/// more complex methods of getting, setting, updating and removing keys and their values:
/// ```
/// extern crate rand;
/// extern crate splay_tree;
///
/// use splay_tree::SplayMap;
///
/// # fn main() {
/// let mut count = SplayMap::new();
/// for _ in 0..1000 {
///     let k = rand::random::<u8>();
///     *count.entry(k).or_insert(0) += 1;
/// }
/// for k in 0..0x100 {
///     println!("{}: {}", k, count.get(&k).unwrap_or(&0));
/// }
/// # }
/// ```
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct SplayMap<K, V> {
    tree: tree_core::Tree<K, V>,
}
impl<K, V> SplayMap<K, V>
where
    K: Ord,
{
    /// Makes a new empty `SplayMap`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// assert_eq!(map.len(), 1);
    /// ```
    pub fn new() -> Self {
        SplayMap {
            tree: tree_core::Tree::new(),
        }
    }

    /// Clears the map, removing all values.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// map.clear();
    /// assert!(map.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.tree = tree_core::Tree::new();
    }

    /// Returns true if the map contains a value for the specified 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.
    ///
    /// # Notice
    ///
    /// Because `SplayMap` is a self-adjusting amortized data structure,
    /// this function requires the `mut` qualifier for `self`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// assert!(map.contains_key("foo"));
    /// assert!(!map.contains_key("bar"));
    /// ```
    pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.tree.contains_key(key)
    }

    /// 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.
    ///
    /// # Notice
    ///
    /// Because `SplayMap` is a self-adjusting amortized data structure,
    /// this function requires the `mut` qualifier for `self`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// assert_eq!(map.get("foo"), Some(&1));
    /// assert_eq!(map.get("bar"), None);
    /// ```
    pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.get_mut(key).map(|v| &*v)
    }

    /// Returns a mutable 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.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// map.get_mut("foo").map(|v| *v = 2);
    /// assert_eq!(map.get("foo"), Some(&2));
    /// ```
    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.tree.get(key)
    }

    /// Finds a minimum key which satisfies "greater than or equal to `key`" condition in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.find_lower_bound_key(&0), Some(&1));
    /// assert_eq!(map.find_lower_bound_key(&1), Some(&1));
    /// assert_eq!(map.find_lower_bound_key(&4), None);
    /// ```
    pub fn find_lower_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_lower_bound(key)
    }

    /// Finds a minimum key which satisfies "greater than `key`" condition in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.find_upper_bound_key(&0), Some(&1));
    /// assert_eq!(map.find_upper_bound_key(&1), Some(&3));
    /// assert_eq!(map.find_upper_bound_key(&4), None);
    /// ```
    pub fn find_upper_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_upper_bound(key)
    }

    /// Gets the entry which have the minimum key in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.smallest(), Some((&1, &())));
    /// ```
    pub fn smallest(&mut self) -> Option<(&K, &V)> {
        self.tree.get_lftmost()
    }

    /// Takes the entry which have the minimum key in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.take_smallest(), Some((1, ())));
    /// assert_eq!(map.take_smallest(), Some((3, ())));
    /// assert_eq!(map.take_smallest(), None);
    /// ```
    pub fn take_smallest(&mut self) -> Option<(K, V)> {
        self.tree.take_lftmost()
    }

    /// Gets the entry which have the maximum key in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.largest(), Some((&3, &())));
    /// ```
    pub fn largest(&mut self) -> Option<(&K, &V)> {
        self.tree.get_rgtmost()
    }

    /// Takes the entry which have the maximum key in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert(1, ());
    /// map.insert(3, ());
    ///
    /// assert_eq!(map.take_largest(), Some((3, ())));
    /// assert_eq!(map.take_largest(), Some((1, ())));
    /// assert_eq!(map.take_largest(), None);
    /// ```
    pub fn take_largest(&mut self) -> Option<(K, V)> {
        self.tree.take_rgtmost()
    }

    /// Inserts a key-value pair into the map.
    ///
    /// If the map did not have this key present, `None` is  returned.
    ///
    /// If the map did have this key present, the value is updated,
    /// and the old value is returned.
    /// The key is not updated, though;
    /// this matters for types that can be `==` without being identical.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// assert_eq!(map.insert("foo", 1), None);
    /// assert_eq!(map.get("foo"), Some(&1));
    /// assert_eq!(map.insert("foo", 2), Some(1));
    /// assert_eq!(map.get("foo"), Some(&2));
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        self.tree.insert(key, value)
    }

    /// Removes a key from the map,
    /// returning the value at the key if the key was previously in the map.
    ///
    /// 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.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// assert_eq!(map.remove("foo"), Some(1));
    /// assert_eq!(map.remove("foo"), None);
    /// ```
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord,
    {
        self.tree.remove(key)
    }

    /// Gets the given key's corresponding entry in the map for in-place manipulation.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut count = SplayMap::new();
    ///
    /// // count the number of occurrences of letters in the vec
    /// for x in vec!["a", "b", "a", "c", "a", "b"] {
    ///     *count.entry(x).or_insert(0) += 1;
    /// }
    ///
    /// assert_eq!(count.get("a"), Some(&3));
    /// ```
    pub fn entry(&mut self, key: K) -> Entry<K, V> {
        if self.contains_key(&key) {
            Entry::Occupied(OccupiedEntry {
                tree: &mut self.tree,
            })
        } else {
            Entry::Vacant(VacantEntry {
                key: key,
                tree: &mut self.tree,
            })
        }
    }
}
impl<K, V> SplayMap<K, V> {
    /// Returns the number of elements in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// map.insert("foo", 1);
    /// map.insert("bar", 2);
    /// assert_eq!(map.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.tree.len()
    }

    /// Returns true if the map contains no elements.
    ///
    /// #  Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map = SplayMap::new();
    /// assert!(map.is_empty());
    ///
    /// map.insert("foo", 1);
    /// assert!(!map.is_empty());
    ///
    /// map.clear();
    /// assert!(map.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Gets an iterator over the entries of the map, sorted by key.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let map: SplayMap<_, _> =
    ///     vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
    /// assert_eq!(vec![(&"bar", &2), (&"baz", &3), (&"foo", &1)],
    ///            map.iter().collect::<Vec<_>>());
    /// ```
    pub fn iter(&self) -> Iter<K, V> {
        Iter::new(&self.tree)
    }

    /// Gets a mutable iterator over the entries of the map, soretd by key.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map: SplayMap<_, _> =
    ///     vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
    /// for (_, v) in map.iter_mut() {
    ///    *v += 10;
    /// }
    /// assert_eq!(map.get("bar"), Some(&12));
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        IterMut::new(&mut self.tree)
    }

    /// Gets an iterator over the keys of the map, in sorted order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let map: SplayMap<_, _> =
    ///     vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
    /// assert_eq!(vec!["bar", "baz", "foo"],
    ///            map.keys().cloned().collect::<Vec<_>>());
    /// ```
    pub fn keys(&self) -> Keys<K, V> {
        Keys::new(&self.tree)
    }

    /// Gets an iterator over the values of the map, in order by key.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let map: SplayMap<_, _> =
    ///     vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
    /// assert_eq!(vec![2, 3, 1],
    ///            map.values().cloned().collect::<Vec<_>>());
    /// ```
    pub fn values(&self) -> Values<K, V> {
        Values::new(&self.tree)
    }

    /// Gets a mutable iterator over the values of the map, in order by key.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplayMap;
    ///
    /// let mut map: SplayMap<_, _> =
    ///     vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
    /// for v in map.values_mut() {
    ///     *v += 10;
    /// }
    /// assert_eq!(vec![12, 13, 11],
    ///            map.values().cloned().collect::<Vec<_>>());
    /// ```
    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
        ValuesMut::new(&mut self.tree)
    }
}
impl<K, V> Default for SplayMap<K, V>
where
    K: Ord,
{
    fn default() -> Self {
        SplayMap::new()
    }
}
impl<K, V> std::iter::FromIterator<(K, V)> for SplayMap<K, V>
where
    K: Ord,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = (K, V)>,
    {
        let mut map = SplayMap::new();
        for (k, v) in iter {
            map.insert(k, v);
        }
        map
    }
}
impl<'a, K, V> IntoIterator for &'a SplayMap<K, V>
where
    K: 'a,
    V: 'a,
{
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;
    fn into_iter(self) -> Self::IntoIter {
        Iter::new(&self.tree)
    }
}
impl<'a, K, V> IntoIterator for &'a mut SplayMap<K, V>
where
    K: 'a,
    V: 'a,
{
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;
    fn into_iter(self) -> Self::IntoIter {
        IterMut::new(&mut self.tree)
    }
}
impl<K, V> IntoIterator for SplayMap<K, V> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self.tree)
    }
}
impl<K, V> Extend<(K, V)> for SplayMap<K, V>
where
    K: Ord,
{
    fn extend<T>(&mut self, iter: T)
    where
        T: IntoIterator<Item = (K, V)>,
    {
        for (k, v) in iter {
            self.insert(k, v);
        }
    }
}
impl<'a, K, V> Extend<(&'a K, &'a V)> for SplayMap<K, V>
where
    K: 'a + Copy + Ord,
    V: 'a + Copy,
{
    fn extend<T>(&mut self, iter: T)
    where
        T: IntoIterator<Item = (&'a K, &'a V)>,
    {
        for (k, v) in iter {
            self.insert(*k, *v);
        }
    }
}

/// An iterator over a SplayMap's entries.
pub struct Iter<'a, K: 'a, V: 'a>(iter::Iter<'a, K, V>);
impl<'a, K: 'a, V: 'a> Iter<'a, K, V> {
    fn new(tree: &'a tree_core::Tree<K, V>) -> Self {
        Iter(tree.iter())
    }
}
impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

/// A mutable iterator over a SplayMap's entries.
pub struct IterMut<'a, K: 'a, V: 'a>(iter::IterMut<'a, K, V>);
impl<'a, K: 'a, V: 'a> IterMut<'a, K, V> {
    fn new(tree: &'a mut tree_core::Tree<K, V>) -> Self {
        IterMut(tree.iter_mut())
    }
}
impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

/// An owning iterator over a SplayMap's entries.
pub struct IntoIter<K, V>(iter::IntoIter<K, V>);
impl<K, V> IntoIter<K, V> {
    fn new(tree: tree_core::Tree<K, V>) -> Self {
        IntoIter(tree.into_iter())
    }
}
impl<K, V> Iterator for IntoIter<K, V> {
    type Item = (K, V);
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

/// An iterator over a SplayMap's keys.
pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
impl<'a, K: 'a, V: 'a> Keys<'a, K, V> {
    fn new(tree: &'a tree_core::Tree<K, V>) -> Self {
        Keys(Iter::new(tree))
    }
}
impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
    type Item = &'a K;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(k, _)| k)
    }
}

/// An iterator over a SplayMap's values.
pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
impl<'a, K: 'a, V: 'a> Values<'a, K, V> {
    fn new(tree: &'a tree_core::Tree<K, V>) -> Self {
        Values(Iter::new(tree))
    }
}
impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
    type Item = &'a V;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, v)| v)
    }
}

/// A mutable iterator over a SplayMap's values.
pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);
impl<'a, K: 'a, V: 'a> ValuesMut<'a, K, V> {
    fn new(tree: &'a mut tree_core::Tree<K, V>) -> Self {
        ValuesMut(IterMut::new(tree))
    }
}
impl<'a, K: 'a, V: 'a> Iterator for ValuesMut<'a, K, V> {
    type Item = &'a mut V;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, v)| v)
    }
}

/// A view into a single entry in a map, which may either be vacant or occupied.
pub enum Entry<'a, K: 'a, V: 'a> {
    /// An occupied entry
    Occupied(OccupiedEntry<'a, K, V>),
    /// A vacant entry
    Vacant(VacantEntry<'a, K, V>),
}
impl<'a, K: 'a, V: 'a> Entry<'a, K, V>
where
    K: Ord,
{
    /// Returns a reference to this entry's key.
    pub fn key(&self) -> &K {
        match *self {
            Entry::Occupied(ref e) => e.key(),
            Entry::Vacant(ref e) => e.key(),
        }
    }

    /// Ensures a value is in the entry by inserting the default if empty,
    /// and returns a mutable reference to the value in the entry.
    pub fn or_insert(self, default: V) -> &'a mut V {
        match self {
            Entry::Occupied(e) => e.into_mut(),
            Entry::Vacant(e) => e.insert(default),
        }
    }

    /// Ensures a value is in the entry by inserting the result of the default function if empty,
    /// and returns a mutable reference to the value in the entry.
    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
        match self {
            Entry::Occupied(e) => e.into_mut(),
            Entry::Vacant(e) => e.insert(default()),
        }
    }
}

/// An occupied Entry.
pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
    tree: &'a mut tree_core::Tree<K, V>,
}
impl<'a, K: 'a, V: 'a> OccupiedEntry<'a, K, V>
where
    K: Ord,
{
    /// Gets a reference to the key in the entry.
    pub fn key(&self) -> &K {
        &self.tree.root_ref().key
    }

    /// Gets a reference to the value in the entry.
    pub fn get(&self) -> &V {
        &self.tree.root_ref().val
    }

    /// Gets a mutable reference to the value in the entry.
    pub fn get_mut(&mut self) -> &mut V {
        &mut self.tree.root_mut().val
    }

    /// Converts the entry into a mutable reference to its value.
    pub fn into_mut(self) -> &'a mut V {
        &mut self.tree.root_mut().val
    }

    /// Sets the value of the entry with the OccupiedEntry's key,
    /// and returns the entry's old value.
    pub fn insert(&mut self, value: V) -> V {
        mem::replace(self.get_mut(), value)
    }

    /// Takes the value of the entry out of the map, and returns it.
    pub fn remove(self) -> V {
        self.tree.pop_root().unwrap().1
    }
}

/// A vacant Entry.
pub struct VacantEntry<'a, K: 'a, V: 'a> {
    key: K,
    tree: &'a mut tree_core::Tree<K, V>,
}
impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V>
where
    K: Ord,
{
    /// Gets a reference to the key that would be used
    /// when inserting a value through the VacantEntry.
    pub fn key(&self) -> &K {
        &self.key
    }

    /// Sets the value of the entry with the VacantEntry's key,
    /// and returns a mutable reference to it.
    pub fn insert(self, value: V) -> &'a mut V {
        self.tree.insert(self.key, value);
        &mut self.tree.root_mut().val
    }
}