//! 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.
#[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, 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,
    {
        if self.first.borrow() == key {
            Some(&self.first)
        } else {
            self.rest.get(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,
    {
        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.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,
    {
        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
    }
}

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 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 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());
    }
}