non-empty-collections 0.1.9

//! Non-empty hash set implementation.

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

pub use self::into_iter::IntoIter;
use indexmap::IndexSet;
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::IndexSet`] that is guaranteed to have at least one element by the
/// Rust's type system: it consists of a **first** element and an indexed set (which could be
/// empty) **rest** elements.
#[derive(Clone)]
pub struct NonEmptyIndexSet<K, S = RandomState> {
    first: K,
    rest: IndexSet<K, S>,
}

impl<K> NonEmptyIndexSet<K, RandomState> {
    /// Creates a set with a default hasher.
    pub fn new(first: K) -> Self {
        NonEmptyIndexSet {
            first,
            rest: IndexSet::new(),
        }
    }

    /// Creates a set with a given capacity.
    pub fn with_capacity(first: K, capacity: usize) -> Self {
        NonEmptyIndexSet {
            first,
            rest: IndexSet::with_capacity(if capacity == 0 { 0 } else { capacity - 1 }),
        }
    }

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

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

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

impl<K, S> NonEmptyIndexSet<K, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    /// Creates a set with a given hasher.
    pub fn with_hasher(first: K, hash_builder: S) -> Self {
        NonEmptyIndexSet {
            first,
            rest: IndexSet::with_hasher(hash_builder),
        }
    }

    /// Creates a set with a given capacity.
    pub fn with_capacity_and_hasher(first: K, capacity: usize, hash_builder: S) -> Self {
        NonEmptyIndexSet {
            first,
            rest: IndexSet::with_capacity_and_hasher(
                if capacity == 0 { 0 } else { capacity - 1 },
                hash_builder,
            ),
        }
    }

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

    /// Creates a set from a given iterator with a given hasher.
    pub fn from_iter_with_hasher(i: impl IntoIterator<Item = K>, 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 => IndexSet::with_hasher(hasher),
            Some(len) => IndexSet::with_capacity_and_hasher(len, hasher),
        };
        rest.extend(iter);
        Ok(NonEmptyIndexSet { first, rest })
    }

    /// Gets a stored key from the set.
    pub fn get<Q>(&self, key: &Q) -> Option<&K>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.borrow() == key {
            Some(&self.first)
        } else {
            self.rest.get(key)
        }
    }

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

    /// Removes and returns a value from the set that is equal to a given key, if any.
    ///
    /// An attempt to remove the last element will cause an [`Error`] to be returned.
    pub fn take<Q>(&mut self, key: &Q) -> Result<Option<K>, Error>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        if self.first.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_take(key))
        }
    }

    /// Removes a value from the set that is equal to a given key, if any. Returns `true` if the
    /// value was present in the set.
    ///
    /// An attempt to remove the last element will cause an [`Error`] to be returned.
    pub fn remove<Q>(&mut self, key: &Q) -> Result<bool, Error>
    where
        K: borrow::Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        self.take(key).map(|x| x.is_some())
    }

    /// Adds a value to the set.
    ///
    /// If there was no such a value in the set before, `true` is returned.
    ///
    /// If the value is in the set already, it remains unchaged and `false` is returned.
    pub fn insert(&mut self, key: K) -> bool {
        if self.first == key {
            false
        } else {
            self.rest.insert(key)
        }
    }

    /// Replaces a value in the set with a given one. An old value is returned, if any.
    pub fn replace(&mut self, key: K) -> Option<K> {
        if self.first == key {
            Some(replace(&mut self.first, key))
        } else {
            self.rest.replace(key)
        }
    }

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

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

    /// Gets an immutable reference to the **first** element.
    pub fn get_first(&self) -> &K {
        &self.first
    }

    /// Gets a mutable reference to the **first** element.
    pub fn get_first_mut(&mut self) -> &mut K {
        &mut self.first
    }

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

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

    /// Attempts to remove the first element. Will fail if it is the only one element in the set.
    pub fn remove_first(&mut self) -> Result<(), Error> {
        let item = self.rest.pop().ok_or(Error::EmptyCollection)?;
        self.first = item;
        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) -> bool,
    {
        while !(keep)(&self.first) {
            self.remove_first()?;
        }
        self.rest.retain(keep);
        Ok(())
    }
}

impl<K: Eq + Hash, S: BuildHasher> Into<IndexSet<K, S>> for NonEmptyIndexSet<K, S> {
    fn into(self) -> IndexSet<K, S> {
        let mut set = self.rest;
        set.insert(self.first);
        set
    }
}

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

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

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

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

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

    #[test]
    fn new_and_get() {
        let set = NonEmptyIndexSet::new(123);
        assert_eq!(Some(&123), set.get(&123));
        assert_eq!(None, set.get(&1234));
        assert_eq!(1, set.len());
    }

    #[test]
    fn new_and_contains() {
        let set = NonEmptyIndexSet::new(123);
        assert!(set.contains(&123));
        assert!(!set.contains(&1234));
        assert_eq!(1, set.len());
    }

    #[test]
    fn from_iterator() {
        assert!(NonEmptyIndexSet::from_iterator(iter::empty::<u8>()).is_err());
        let set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        assert_eq!(Some(&1), set.get(&1));
        assert_eq!(Some(&2), set.get(&2));
        assert_eq!(Some(&3), set.get(&3));
        assert_eq!(Some(&4), set.get(&4));
        assert_eq!(4, set.len());
    }

    #[test]
    fn take() {
        let mut set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        assert_eq!(Ok(Some(3)), set.take(&3));
        assert_eq!(Ok(None), set.take(&3));
        assert_eq!(Ok(Some(2)), set.take(&2));
        assert_eq!(Ok(Some(4)), set.take(&4));

        assert_eq!(Some(&1), set.get(&1));
        assert_eq!(Err(Error::EmptyCollection), set.take(&1));
    }

    #[test]
    fn remove() {
        let mut set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        assert_eq!(Ok(true), set.remove(&3));
        assert_eq!(Ok(false), set.remove(&3));
        assert_eq!(Ok(true), set.remove(&2));
        assert_eq!(Ok(true), set.remove(&4));

        assert_eq!(Some(&1), set.get(&1));
        assert_eq!(Err(Error::EmptyCollection), set.remove(&1));
    }

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

    #[test]
    fn insert() {
        let mut set = NonEmptyIndexSet::new(1);
        assert!(!set.insert(1));
        assert!(set.insert(2));
        assert_eq!(Some(&2), set.get(&2));
        assert!(!set.insert(2));
    }

    #[test]
    fn len() {
        let set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        assert_eq!(4, set.len());

        let set = NonEmptyIndexSet::new(10);
        assert_eq!(1, set.len());
    }

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

    #[test]
    fn retain() {
        let original_set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        let mut set = original_set.clone();
        assert_eq!(Ok(()), set.retain(|key| *key < 2));
        assert_eq!(1, set.len());
        assert_eq!(Some(&1), set.get(&1));
        assert_eq!(Err(Error::EmptyCollection), set.retain(|_| false));

        let mut set = original_set.clone();
        assert_eq!(Ok(()), set.retain(|key| *key > 3));
        assert_eq!(1, set.len());
        assert_eq!(Some(&4), set.get(&4));
        assert_eq!(Err(Error::EmptyCollection), set.retain(|_| false));
    }

    #[test]
    fn comparison() {
        let original_set = NonEmptyIndexSet::from_iterator(vec![1, 2, 3, 4]).unwrap();
        assert_eq!(original_set, original_set);
        for &key in original_set.iter() {
            let modified_set =
                NonEmptyIndexSet::from_iterator(original_set.clone().into_iter().map(|key2| {
                    if key2 == key {
                        100
                    } else {
                        key2
                    }
                }))
                .unwrap();
            assert_ne!(modified_set, original_set);
        }
    }
}