non-empty-collections 0.1.9

//! Non-empty hash map implementation.

#[cfg(feature = "serde_support")]
mod deserialize;
mod entry;
mod into_iter;
#[cfg(feature = "serde_support")]
mod serialize;

pub use self::entry::Entry;
pub use self::into_iter::IntoIter;
use indexmap::IndexMap;
use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hash};
use std::iter::Extend;
use std::mem::replace;
use std::{borrow, fmt, iter};
use {estimated_size, Error};

/// A wrapper around [`::indexmap::IndexMap`] that is guaranteed to have at least one element by the
/// Rust's type system: it consists of a **first** element and an indexed map (which could be
/// empty) **rest** elements.
#[derive(Clone)]
pub struct NonEmptyIndexMap<K, V, S = RandomState> {
    first: (K, V),
    rest: IndexMap<K, V, S>,
}

/// A helper enum to easily obtain indexed entries.
#[derive(Clone, Copy)]
enum Index {
    First,
    Rest(usize),
}

impl<K, V> NonEmptyIndexMap<K, V, RandomState> {
    /// Creates a map with a default hasher.
    pub fn new(key: K, value: V) -> Self {
        NonEmptyIndexMap {
            first: (key, value),
            rest: IndexMap::new(),
        }
    }

    /// Creates a map with a given capacity.
    pub fn with_capacity(key: K, value: V, capacity: usize) -> Self {
        NonEmptyIndexMap {
            first: (key, value),
            rest: IndexMap::with_capacity(if capacity == 0 { 0 } else { capacity - 1 }),
        }
    }

    /// Creates a map from an item (a key and a value pair) standart hash map.
    pub fn from_item_and_iterator(key: K, value: V, i: impl IntoIterator<Item = (K, V)>) -> Self
    where
        K: Hash + Eq,
    {
        NonEmptyIndexMap {
            first: (key, value),
            rest: i.into_iter().collect(),
        }
    }

    /// Creates a map from a given iterator with a default hasher.
    pub fn from_iterator(i: impl IntoIterator<Item = (K, V)>) -> Result<Self, Error>
    where
        K: Hash + Eq,
    {
        let mut iter = i.into_iter();
        let first = iter.next().ok_or(Error::EmptyCollection)?;
        Ok(NonEmptyIndexMap {
            first,
            rest: iter.collect(),
        })
    }
}

impl<K, V, S1, S2> PartialEq<NonEmptyIndexMap<K, V, S1>> for NonEmptyIndexMap<K, V, S2>
where
    K: Hash + Eq,
    V: Eq,
    S1: BuildHasher,
    S2: BuildHasher,
{
    fn eq(&self, other: &NonEmptyIndexMap<K, V, S1>) -> bool {
        self.rest.len() == other.rest.len() && self.first == other.first && self.rest == other.rest
    }
}

impl<K, V, S> Eq for NonEmptyIndexMap<K, V, S>
where
    K: Hash + Eq,
    V: Eq,
    S: BuildHasher,
{
}

impl<K, V, S> NonEmptyIndexMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    /// Creates a map with a given hasher.
    pub fn with_hasher(key: K, value: V, hash_builder: S) -> Self {
        NonEmptyIndexMap {
            first: (key, value),
            rest: IndexMap::with_hasher(hash_builder),
        }
    }

    /// Creates a map with a given capacity and a given hasher.
    pub fn with_capacity_and_hasher(key: K, value: V, capacity: usize, hash_builder: S) -> Self {
        NonEmptyIndexMap {
            first: (key, value),
            rest: IndexMap::with_capacity_and_hasher(
                if capacity == 0 { 0 } else { capacity - 1 },
                hash_builder,
            ),
        }
    }

    /// Iterates over key-value pairs of the map in an immutable way.
    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        iter::once((&self.first.0, &self.first.1)).chain(self.rest.iter())
    }

    /// Iterates over key-value pairs of the map in a mutable way.
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
        iter::once((&self.first.0, &mut self.first.1)).chain(self.rest.iter_mut())
    }

    /// Creates a map from a given iterator with a given hasher.
    pub fn from_iter_with_hasher(
        i: impl IntoIterator<Item = (K, V)>,
        hasher: S,
    ) -> Result<Self, Error> {
        let mut iter = i.into_iter();
        let first = iter.next().ok_or(Error::EmptyCollection)?;
        let mut rest = match estimated_size(&iter) {
            None => IndexMap::with_hasher(hasher),
            Some(len) => IndexMap::with_capacity_and_hasher(len, hasher),
        };
        rest.extend(iter);
        Ok(NonEmptyIndexMap { first, rest })
    }

    /// Gets a value associated with a given key, if any.
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.0.borrow() == key {
            Some(&self.first.1)
        } else {
            self.rest.get(key)
        }
    }

    /// Checks whether a given key exists in the map.
    pub fn contains<Q>(&self, key: &Q) -> bool
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.0.borrow() == key {
            true
        } else {
            self.rest.contains_key(key)
        }
    }

    /// Gets a value associated with a given key, if any.
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.0.borrow() == key {
            Some(&mut self.first.1)
        } else {
            self.rest.get_mut(key)
        }
    }

    /// Removes and returns an element associated with a given key, if any.
    ///
    /// An attempt to remove the last element will cause an [`Error`] to be returned.
    pub fn remove_entry<Q>(&mut self, key: &Q) -> Result<Option<(K, V)>, Error>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.0.borrow() == key {
            let intermediate_element = self.rest.pop().ok_or(Error::EmptyCollection)?;
            Ok(Some(replace(&mut self.first, intermediate_element)))
        } else {
            Ok(self
                .rest
                .swap_remove_full(key)
                .map(|(_index, key, value)| (key, value)))
        }
    }

    /// Removes and element associated with a given key and return its value, if any.
    ///
    /// An attempt to remove the last element will cause an [`Error`] to be returned.
    pub fn remove<Q>(&mut self, key: &Q) -> Result<Option<V>, Error>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        self.remove_entry(key).map(|x| x.map(|(_key, value)| value))
    }

    /// Inserts a key-value pair into the map. If the map have already had an element associated
    /// with a given key, the associated value is updated and the old one is returned.
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if self.first.0 == key {
            Some(replace(&mut self.first.1, value))
        } else {
            self.rest.insert(key, value)
        }
    }

    /// Returns the number of elements in the map.
    pub fn len(&self) -> usize {
        self.rest.len() + 1
    }

    /// Checks whether or not the map is empty.
    ///
    /// As one would expect it always evaluates to `false` :)
    ///
    /// ```
    /// # extern crate non_empty_collections;
    /// # use non_empty_collections::NonEmptyIndexMap;
    /// # fn main() {
    /// assert!(!NonEmptyIndexMap::new("key", "value").is_empty());
    /// # }
    /// ```
    pub fn is_empty(&self) -> bool {
        false
    }

    /// Returns an entry that corresponds to a given key.
    pub fn entry(&mut self, key: K) -> Entry<K, V, S> {
        match self.get_index(&key) {
            Some(index) => Entry::Occupied(entry::Occupied {
                key,
                index,
                map: self,
            }),
            None => Entry::Vacant(entry::Vacant { key, map: self }),
        }
    }

    fn get_entry(&self, index: Index) -> &V {
        match index {
            Index::First => &self.first.1,
            Index::Rest(idx) => {
                self.rest
                    .get_index(idx)
                    .expect("The entry exists for sure")
                    .1
            }
        }
    }

    fn get_index<Q>(&mut self, key: &Q) -> Option<Index>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.0.borrow() == key {
            Some(Index::First)
        } else {
            self.rest
                .get_full(key)
                .map(|(index, _, _)| Index::Rest(index))
        }
    }

    fn get_entry_mut(&mut self, index: Index) -> &mut V {
        match index {
            Index::First => &mut self.first.1,
            Index::Rest(idx) => {
                self.rest
                    .get_index_mut(idx)
                    .expect("The entry exists for sure")
                    .1
            }
        }
    }

    /// Gets an immutable reference to the **firs** element (only the *value*).
    pub fn get_first(&self) -> (&K, &V) {
        (&self.first.0, &self.first.1)
    }

    /// Gets a mutable reference to the **firs** element (only the *value*).
    pub fn get_first_mut(&mut self) -> (&mut K, &mut V) {
        (&mut self.first.0, &mut self.first.1)
    }

    /// Gets an immutable reference to the **rest** indexed map of elements.
    pub fn get_rest(&self) -> &IndexMap<K, V, S> {
        &self.rest
    }

    /// Gets a mutable reference to the **rest** indexed map of elements.
    pub fn get_rest_mut(&mut self) -> &mut IndexMap<K, V, S> {
        &mut self.rest
    }

    /// Attempts to remove the first element. Will fail if it is the only one element in the map.
    pub fn remove_first(&mut self) -> Result<(), Error> {
        let (key, value) = self.rest.pop().ok_or(Error::EmptyCollection)?;
        self.first = (key, value);
        Ok(())
    }

    /// Scans the collection and keeps only the items on which the provided `keep` function
    /// returns `true`. Will fail if in the end only one element will remain.
    pub fn retain<F>(&mut self, mut keep: F) -> Result<(), Error>
    where
        F: FnMut(&K, &mut V) -> bool,
    {
        while !(keep)(&self.first.0, &mut self.first.1) {
            self.remove_first()?;
        }
        self.rest.retain(keep);
        Ok(())
    }
}

impl<K: Eq + Hash, V, S: BuildHasher> Into<IndexMap<K, V, S>> for NonEmptyIndexMap<K, V, S> {
    fn into(self) -> IndexMap<K, V, S> {
        let mut map = self.rest;
        map.insert(self.first.0, self.first.1);
        map
    }
}

impl<K, V, S> fmt::Debug for NonEmptyIndexMap<K, V, S>
where
    K: Eq + Hash + fmt::Debug,
    V: fmt::Debug,
    S: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}

impl<K, V, S> Extend<(K, V)> for NonEmptyIndexMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
        self.rest.extend(iter)
    }
}

impl<K, V, S> IntoIterator for NonEmptyIndexMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            iter: iter::once(self.first).chain(self.rest),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn insert_and_get() {
        let mut map = NonEmptyIndexMap::new(0, 1);
        assert_eq!(Some(&1), map.get(&0));
        assert_eq!(None, map.get(&10));

        assert_eq!(None, map.insert(10, 20));
        assert_eq!(Some(&20), map.get(&10));

        // Key `10` already exists in the map.
        assert_eq!(Some(20), map.insert(10, 40));
        assert_eq!(Some(&40), map.get(&10));
    }

    #[test]
    fn insert_and_contains() {
        let mut map = NonEmptyIndexMap::new(0, 1);
        assert!(map.contains(&0));
        assert!(!map.contains(&10));

        assert_eq!(None, map.insert(10, 20));
        assert!(map.contains(&10));

        // Key `10` already exists in the map.
        assert_eq!(Some(20), map.insert(10, 40));
        assert!(map.contains(&10));
    }

    #[test]
    fn remove_entry() {
        let mut map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
        assert_eq!(Ok(Some((1, 2))), map.remove_entry(&1));
        assert_eq!(None, map.get(&1));

        assert_eq!(Ok(Some((3, 4))), map.remove_entry(&3));
        assert_eq!(None, map.get(&3));

        // Entry `&3` doesn't exist anymore.
        assert_eq!(Ok(None), map.remove_entry(&3));

        // Trying to remove the last element is an error.
        assert_eq!(Err(Error::EmptyCollection), map.remove_entry(&5));
    }

    #[test]
    fn remove_first() {
        let mut map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
        assert_eq!(Ok(()), map.remove_first());
        assert_eq!(Ok(()), map.remove_first());
        assert_eq!(Err(Error::EmptyCollection), map.remove_first());
    }

    #[test]
    fn into_std_hashmap() {
        let mut map = NonEmptyIndexMap::new(1, 2);
        assert_eq!(None, map.insert(3, 4));
        assert_eq!(None, map.insert(5, 6));
        assert_eq!(None, map.insert(7, 8));

        let std_map: IndexMap<_, _> = map.into();
        assert_eq!(4, std_map.len());
        assert_eq!(Some(&2), std_map.get(&1));
        assert_eq!(Some(&4), std_map.get(&3));
        assert_eq!(Some(&6), std_map.get(&5));
        assert_eq!(Some(&8), std_map.get(&7));
    }

    #[test]
    fn from_item_and_iterator() {
        let original = vec![(1u8, 2u8), (3, 4), (5, 6)];
        let converted = NonEmptyIndexMap::from_item_and_iterator(7, 8, original);
        let std_map: IndexMap<_, _> = converted.into();
        assert_eq!(4, std_map.len());
        assert_eq!(Some(&2), std_map.get(&1));
        assert_eq!(Some(&4), std_map.get(&3));
        assert_eq!(Some(&6), std_map.get(&5));
        assert_eq!(Some(&8), std_map.get(&7));
    }

    #[test]
    fn into_iter() {
        let original: IndexMap<_, _> = vec![(1u8, 2u8), (3, 4), (10, 12)].into_iter().collect();
        let map = NonEmptyIndexMap::from_iterator(original.clone())
            .map_err(|_| ())
            .unwrap();
        let converted: IndexMap<_, _> = map.into_iter().collect();
        assert_eq!(converted, original);
    }

    #[test]
    fn len() {
        let map = NonEmptyIndexMap::new(1, 2);
        assert_eq!(1, map.len());

        let map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
        assert_eq!(3, map.len());
    }

    #[test]
    fn get_unsized() {
        let map = NonEmptyIndexMap::new("Lol".to_string(), "wut");
        assert_eq!(Some(&"wut"), map.get("Lol"));
    }

    #[test]
    fn retain() {
        let original_map =
            NonEmptyIndexMap::from_iterator(vec![(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]).unwrap();
        let mut map = original_map.clone();
        assert_eq!(Ok(()), map.retain(|key, value| *key < 2 && *value < 'b'));
        assert_eq!(1, map.len());
        assert_eq!(Some(&'a'), map.get(&1));
        assert_eq!(Err(Error::EmptyCollection), map.retain(|_, _| false));

        let mut map = original_map.clone();
        assert_eq!(Ok(()), map.retain(|key, value| *key > 3 && *value > 'c'));
        assert_eq!(1, map.len());
        assert_eq!(Some(&'d'), map.get(&4));
        assert_eq!(Err(Error::EmptyCollection), map.retain(|_, _| false));
    }

    #[test]
    fn comparison() {
        let original_map =
            NonEmptyIndexMap::from_iterator(vec![(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]).unwrap();
        assert_eq!(original_map, original_map);
        for (key, _) in original_map.iter() {
            let mut modified_map = original_map.clone();
            *modified_map.get_mut(&key).unwrap() = 'z';
            assert_ne!(modified_map, original_map);
        }
    }
}