hashset.alu

use hash::{Hashable, Hasher, DefaultHash};
use option::{Option, try};
use iter::{Iterator, Iterable};
use cmp::Equatable;

/// A hash-based set collection.
///
/// `HashSet<T>` is a wrapper around `HashMap<T, ()>`. Elements must satisfy the
/// [Hashable] and [Equatable] protocols.
///
/// ## Example
/// ```
/// use std::collections::HashSet;
///
/// let set = HashSet::new::<i32>();
/// defer set.free();
///
/// set.insert(1);
/// set.insert(2);
/// set.insert(3);
///
/// assert!(set.contains(&1));
/// assert!(set.contains(&2));
/// assert!(set.contains(&3));
/// ```
struct HashSet<K: Hashable<K, H> + Equatable<K>, H: Hasher<H> = DefaultHash> {
    _inner: hashmap::HashMap<K, (), H>
}

impl HashSet<K: Hashable<K, H> + Equatable<K>, H: Hasher<H> = DefaultHash> {
    /// Creates an empty set
    ///
    /// Will not allocate until the first element is inserted.
    fn new() -> HashSet<K, H> {
        with_capacity(0)
    }

    /// Creates an empty set that can store up to `capacity` items without
    /// reallocating.
    fn with_capacity(capacity: usize) -> HashSet<K, H> {
        HashSet::<K, H> {
            _inner: hashmap::HashMap::with_capacity::<K, (), H>(capacity)
        }
    }

    /// Creates a set with a specific number of buckets.
    ///
    /// As [HashSet] uses amortized growth strategy, prefer to use [with_capacity] unless
    /// you want to strictly control the size of the underlying array.
    fn with_size(size: usize) -> HashSet<K, H> {
        HashSet::<K, H> {
            _inner: hashmap::HashMap::with_size::<K, (), H>(size)
        }
    }

    /// Reserves space for at least `additional` more elements to be inserted without
    /// reallocating.
    ///
    /// This follows the amortized growth strategy.
    #[inline]
    fn reserve(self: &mut HashSet<K, H>, additional: usize) {
        self._inner.reserve(additional);
    }

    /// Resizes the underlying array to exactly the given `new_capacity`.
    ///
    /// Note that this could lead to poor performance if the resulting load factor
    /// is close to 1. Prefer to use [reserve] to grow the map and [shrink_to_fit] to
    /// shrink it.
    ///
    /// Panics if the new capacity is lower than the current size.
    ///
    /// ## Example
    /// ```panics
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    /// set.insert(2);
    /// set.insert(3);
    ///
    /// set.rehash(1); // panics
    /// ```
    #[inline]
    fn rehash(self: &mut HashSet<K, H>, new_capacity: usize) {
        self._inner.rehash(new_capacity);
    }

    /// Reduces the size of underlying storage to fit the contained elements if needed.
    #[inline]
    fn shrink_to_fit(self: &mut HashSet<K, H>) {
        self._inner.shrink_to_fit()
    }

    /// Inserts a value into the set.
    ///
    /// Returns `true` if the value was newly inserted and `false` if the
    /// set already contained the value.
    #[inline]
    fn insert(self: &mut HashSet<K, H>, item: K) -> bool {
        self._inner.insert(item, ()).is_none()
    }

    /// Removes a value from the set.
    ///
    /// Returns `true` if the value was present in the set, `false` otherwise.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    ///
    /// assert!(!set.remove(&2));
    /// assert!(set.remove(&1));
    /// assert!(!set.remove(&1));
    /// ```
    #[inline]
    fn remove(self: &mut HashSet<K, H>, item: &K) -> bool {
        self._inner.remove(item).is_some()
    }

    /// Retreives `true` if the set contains the given value, `false` otherwise.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    ///
    /// assert!(set.contains(&1));
    /// assert!(!set.contains(&2));
    /// ```
    #[inline]
    fn contains(self: &HashSet<K, H>, item: &K) -> bool {
        self._inner.get(item).is_some()
    }

    /// Retreives the number of elements in the set.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    /// set.insert(2);
    /// set.insert(3);
    ///
    /// assert_eq!(set.len(), 3);
    /// ```
    #[inline]
    fn len(self: &HashSet<K, H>) -> usize {
        self._inner.len()
    }

    /// Returns `true` if the set is empty, `false` otherwise.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// assert!(set.is_empty());
    ///
    /// set.insert(1);
    ///
    /// assert!(!set.is_empty());
    /// ```
    #[inline]
    fn is_empty(self: &HashSet<K, H>) -> bool {
        self._inner.is_empty()
    }

    /// Clears the set, removing all values.
    ///
    /// This does not reduce the capacity of the heap (use [shrink_to_fit] afterwards or
    /// use [move] instead).
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    /// set.insert(2);
    /// set.insert(3);
    ///
    /// set.clear();
    ///
    /// assert!(set.is_empty());
    /// ```
    #[inline]
    fn clear(self: &mut HashSet<K, H>) {
        self._inner.clear();
    }

    /// @ iter::Iterable::iter
    #[inline]
    fn iter(self: &HashSet<K, H>) -> HashSetIterator<K> {
        HashSetIterator::<K> {
            inner: self._inner.iter_ref()
        }
    }

    /// @ iter::IterableRef::iter_ref
    #[inline]
    fn iter_ref(self: &HashSet<K, H>) -> HashSetRefIterator<K> {
        HashSetRefIterator::<K> {
            inner: self._inner.iter_ref()
        }
    }

    /// Removes the elements not mathing the given predicate.
    ///
    /// Does not remove excess capacity, call [shrink_to_fit] afterwards, if this
    /// is desired.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    ///
    /// let set = HashSet::new::<i32>();
    /// defer set.free();
    ///
    /// set.insert(1);
    /// set.insert(2);
    /// set.insert(3);
    ///
    /// set.retain(|x: &i32| -> bool { *x % 2 == 0 });
    ///
    /// assert!(!set.contains(&1));
    /// assert!(set.contains(&2));
    /// assert!(!set.contains(&3));
    /// ```
    fn retain<F: Fn(&K) -> bool>(self: &mut HashSet<K, H>, func: F) {
        self._inner.retain(|&func, k: &K, _v: &()| -> bool { func(k) });
    }

    /// @ mem::Freeable::free
    #[inline]
    fn free(self: &mut HashSet<K, H>) {
        self._inner.free();
    }

    /// Helper for collections that own heap-allocated objects. This is used to
    /// be able to do `defer col.free_all()` without much boilerplate.
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    /// use std::string::StringBuf;
    /// use std::fmt::format;
    ///
    /// let v: HashSet<StringBuf> = HashSet::new();
    /// defer v.free_all();
    ///
    /// for i in 1..10 {
    ///     v.insert("{} + {} = {}".format!(i, i, i + i).unwrap());
    /// }
    /// ```
    fn free_all(self: &mut HashSet<K, H>) {
        self._inner.free_all();
    }

    /// @ mem::Movable::move
    fn move(self: &mut HashSet<K, H>) -> HashSet<K, H> {
        HashSet::<K, H> {
            _inner: self._inner.move()
        }
    }

    /// @ mem::Clonable::clone
    fn clone(self: &HashSet<K, H>) -> HashSet<K, H> {
        HashSet::<K, H> {
            _inner: self._inner.clone()
        }
    }
}

impl HashSet<K: Hashable<K, H> + Equatable<K>, I: Iterator<I, K>, H: Hasher<H> = DefaultHash> {
    /// Creates a hash map from an iterator of key-value pairs
    ///
    /// ## Example
    /// ```
    /// use std::collections::HashSet;
    /// let set: HashSet<i32> = HashSet::from_iter(&[1, 2, 3].iter());
    /// defer set.free();
    ///
    /// assert_eq!(set.len(), 3);
    /// assert!(set.contains(&1));
    /// assert!(set.contains(&2));
    /// assert!(set.contains(&3));
    /// ```
    fn from_iter(iter: &mut I) -> HashSet<K, H> {
        let set = HashSet::new::<K, H>();
        set.extend(iter);
        set
    }

    /// Inserts additional elements into the set from an iterator
    /// of key-value pairs.
    fn extend(self: &mut HashSet<K, H>, iter: &mut I) {
        self.reserve(iter.size_hint().unwrap_or(0));

        loop {
            let item = iter.next();
            if item.is_some() {
                self.insert(item.unwrap());
            } else {
                break;
            }
        }
    }
}

impl HashSet<B: Hashable<B, H> + Equatable<B>, K: mem::Borrowable<K, B>, H: Hasher<H> = DefaultHash> {
    /// Checks if the value is present in the map by given borrowing of a key.
    fn contains_borrowed(self: &HashSet<K, H>, key: B) -> bool {
        self._inner.get_borrowed(key).is_some()
    }

    /// Removes the element from the set by given borrowing of a key.
    ///
    /// If the element with the given key was present in the set, it is removed
    /// and returned. Otherwise, `Option::none()` is returned.
    fn remove_borrowed(self: &mut HashSet<K, H>, key: B) -> Option<K> {
        self._inner.remove_borrowed(key).map(|v: (K, ())| -> K { v.0 })
    }
}

/// Iterator over the values in the hashset
struct HashSetIterator<K> {
    inner: hashmap::HashMapRefIterator<K, ()>
}

impl HashSetIterator<K> {
    /// @ iter::Iterator::next
    fn next(self: &mut HashSetIterator<K>) -> Option<K> {
        self.inner.next().map(|v: (&K, &())| -> K { *v.0 })
    }

    /// @ iter::DoubleEndedIterator::next_back
    fn next_back(self: &mut HashSetIterator<K>) -> Option<K> {
        self.inner.next_back().map(|v: (&K, &())| -> K { *v.0 })
    }

    /// @ iter::Iterator::size_hint
    fn size_hint(self: &HashSetIterator<K>) -> Option<usize> {
        self.inner.size_hint()
    }

    mixin iter::Iterator<HashSetIterator<K>, K>;
    mixin iter::IteratorExt<HashSetIterator<K>, K>;
    mixin iter::DoubleEndedIterator<HashSetIterator<K>, K>;
    mixin iter::DoubleEndedIteratorExt<HashSetIterator<K>, K>;
}

/// Iterator over the pointers to the values in the hashset
struct HashSetRefIterator<K> {
    inner: hashmap::HashMapRefIterator<K, ()>
}

impl HashSetRefIterator<K> {
    /// @ iter::Iterator::next
    fn next(self: &mut HashSetRefIterator<K>) -> Option<&K> {
        self.inner.next().map(|v: (&K, &())| -> &K { v.0 })
    }

    /// @ iter::DoubleEndedIterator::next_back
    fn next_back(self: &mut HashSetRefIterator<K>) -> Option<&K> {
        self.inner.next_back().map(|v: (&K, &())| -> &K { v.0 })
    }

    /// @ iter::Iterator::size_hint
    fn size_hint(self: &HashSetRefIterator<K>) -> Option<usize> {
        self.inner.size_hint()
    }

    mixin iter::Iterator<HashSetRefIterator<K>, &K>;
    mixin iter::IteratorExt<HashSetRefIterator<K>, &K>;
    mixin iter::DoubleEndedIterator<HashSetRefIterator<K>, &K>;
    mixin iter::DoubleEndedIteratorExt<HashSetRefIterator<K>, &K>;
}

#[cfg(all(test, test_std))]
#[docs(hide)]
mod tests {
    use hashmap::tests::DummyHasher;

    #[test]
    fn test_hashset_new() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.is_empty());
        assert_eq!(set.len(), 0);
    }

    #[test]
    fn test_hashset_with_capacity() {
        let set = HashSet::with_capacity::<i32>(10);
        defer set.free();

        assert!(set.is_empty());
        assert_eq!(set.len(), 0);
    }

    #[test]
    fn test_hashset_insert() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.insert(1));
        assert!(!set.insert(1));
        assert_eq!(set.len(), 1);
    }

    #[test]
    fn test_hashset_remove() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.insert(1));
        assert!(set.remove(&1));
        assert!(!set.remove(&1));
        assert!(set.is_empty());
    }

    #[test]
    fn test_hashset_contains() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(!set.contains(&1));
        assert!(set.insert(1));
        assert!(set.contains(&1));
    }

    #[test]
    fn test_hashset_len() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert_eq!(set.len(), 0);
        assert!(set.insert(1));
        assert_eq!(set.len(), 1);
        assert!(set.insert(2));
    }

    #[test]
    fn test_hashset_empty() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.is_empty());
        assert!(set.insert(1));
        assert!(!set.is_empty());
        assert!(set.remove(&1));
        assert!(set.is_empty());
    }

    #[test]
    fn test_hashset_clear() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.insert(1));
        assert!(set.insert(2));
        assert!(set.insert(3));
        assert_eq!(set.len(), 3);
        set.clear();
        assert!(set.is_empty());
    }

    #[test]
    fn test_hashset_iter() {
        let set = HashSet::with_capacity::<i32, DummyHasher>(10);
        defer set.free();

        assert!(set.insert(1));
        assert!(set.insert(2));
        assert!(set.insert(3));
        let iter = set.iter();
        assert_eq!(iter.size_hint(), Option::some(3usize));
        assert_eq!(iter.next(), Option::some(1));
        assert_eq!(iter.next(), Option::some(2));
        assert_eq!(iter.next(), Option::some(3));
        assert_eq!(iter.next(), Option::none());

        let iter = set.iter().rev();
        assert_eq!(iter.size_hint(), Option::some(3usize));
        assert_eq!(iter.next(), Option::some(3));
        assert_eq!(iter.next(), Option::some(2));
        assert_eq!(iter.next(), Option::some(1));
        assert_eq!(iter.next(), Option::none());
    }

    #[test]
    fn test_hashset_iter_ref() {
        let set = HashSet::with_capacity::<i32, DummyHasher>(10);
        defer set.free();

        assert!(set.insert(1));
        assert!(set.insert(2));
        assert!(set.insert(3));
        let iter = set.iter_ref();
        assert_eq!(iter.size_hint(), Option::some(3usize));
        assert_eq!(*iter.next().unwrap(), 1);
        assert_eq!(*iter.next().unwrap(), 2);
        assert_eq!(*iter.next().unwrap(), 3);
        assert!(iter.next().is_none());

        let iter = set.iter_ref().rev();
        assert_eq!(iter.size_hint(), Option::some(3usize));
        assert_eq!(*iter.next().unwrap(), 3);
        assert_eq!(*iter.next().unwrap(), 2);
        assert_eq!(*iter.next().unwrap(), 1);
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_hashset_move() {
        let set = HashSet::new::<i32>();
        defer set.free();

        assert!(set.insert(1));
        assert!(set.insert(2));
        assert!(set.insert(3));

        let set2 = set.move();
        defer set2.free();

        assert_eq!(set2.len(), 3);
        assert!(set2.contains(&1));
        assert!(set2.contains(&2));
        assert!(set2.contains(&3));
        assert!(set.is_empty());
    }

    #[test]
    fn test_hashset_from_iter() {
        let set: HashSet<i32> = HashSet::from_iter(&[1, 2, 3].iter());
        defer set.free();

        assert_eq!(set.len(), 3);
        assert!(set.contains(&1));
        assert!(set.contains(&2));
        assert!(set.contains(&3));
    }

    #[test]
    fn test_hashset_extend() {
        let set = HashSet::new::<i32>();
        defer set.free();

        set.extend(&[1, 2, 3].iter());
        assert_eq!(set.len(), 3);
        assert!(set.contains(&1));
        assert!(set.contains(&2));
        assert!(set.contains(&3));
    }

    #[test]
    fn test_hashset_borrowed() {
        use std::string::StringBuf;

        let set = HashSet::new::<StringBuf>();
        defer set.free_all();

        set.insert(StringBuf::from_slice("hello"));
        set.insert(StringBuf::from_slice("world"));

        assert!(set.contains_borrowed("hello"));
        assert!(!set.contains_borrowed("moon"));

        let k = set.remove_borrowed("world").unwrap();
        assert_eq!(k[..] as &[u8], "world");
        k.free();

        assert_eq!(set.len(), 1);
    }
}