gut 0.8.0

// This is a merge between the CHashMap and std::collections::HashSet.
// As such, credit goes to the authors of those respective libraries.

#![allow(dead_code)]
use std::borrow::Borrow;
use std::fmt;
use std::hash::Hash;

use chashmap::CHashMap;

/// Concurrent hash set. This is a wrapper around `CHashMap` with `()` values.
#[derive(Clone)]
pub struct CHashSet<K> {
    map: CHashMap<K, ()>,
}

pub type ReadGuard<'a, K> = chashmap::ReadGuard<'a, K, ()>;
pub type WriteGuard<'a, K> = chashmap::WriteGuard<'a, K, ()>;

impl<T> CHashSet<T> {
    /// Creates an empty `CHashSet`.
    #[inline]
    pub fn new() -> CHashSet<T> {
        CHashSet {
            map: CHashMap::new(),
        }
    }

    /// Creates an empty `CHashSet` with at least the specified capacity.
    #[inline]
    pub fn with_capacity(capacity: usize) -> CHashSet<T> {
        CHashSet {
            map: CHashMap::with_capacity(capacity),
        }
    }

    /// Returns the number of elements the set can hold without reallocating.
    #[inline]
    pub fn capacity(&self) -> usize {
        self.map.capacity()
    }

    /// Returns the number of elements in the set.
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns `true` if the set contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Clears the set, removing all values.
    #[inline]
    pub fn clear(&self) {
        self.map.clear();
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
    pub fn retain<F>(&self, f: F)
    where
        F: Fn(&T) -> bool,
    {
        self.map.retain(|k, _| f(k));
    }
}

impl<T> CHashSet<T>
where
    T: PartialEq + Hash,
{
    /// Returns a reference to the value in the set, if any, that is equal to the given value.
    #[inline]
    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<ReadGuard<T>>
    where
        T: Borrow<Q>,
        Q: Hash + PartialEq,
    {
        self.map.get(value)
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the `CHashSet`. The collection may reserve more space to avoid
    /// frequent reallocations.
    #[inline]
    pub fn reserve(&self, additional: usize) {
        self.map.reserve(additional)
    }

    /// Shrinks the capacity of the set as much as possible. It will drop
    /// down as much as possible while maintaining the internal rules
    /// and possibly leaving some space in accordance with the resize policy.
    #[inline]
    pub fn shrink_to_fit(&self) {
        self.map.shrink_to_fit()
    }

    /// Returns `true` if the set contains a value.
    #[inline]
    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + PartialEq,
    {
        self.map.contains_key(value)
    }

    /// Insert a new entry.
    ///
    /// This inserts an entry, which the set does not already contain, into the table. If the entry
    /// exists, the old entry won't be replaced, nor will an error be returned. It will possibly
    /// introduce silent bugs.
    ///
    /// To be more specific, it assumes that the entry does not already exist, and will simply skip
    /// to the end of the cluster, even if it does exist.
    ///
    /// This is faster than e.g. insert, but should only be used, if you know that the entry
    /// doesn't already exist.
    ///
    /// # Warning
    ///
    /// Only use this, if you know what you're doing. This can easily introduce very complex logic
    /// errors.
    ///
    /// For most other purposes, use insert.
    ///
    /// # Panics
    ///
    /// This might perform checks in debug mode testing if the key exists already.
    #[inline]
    pub fn insert_new(&self, value: T) {
        self.map.insert_new(value, ())
    }

    /// Adds a value to the set.
    ///
    /// If the set did not have this value present, `true` is returned.
    ///
    /// If the set did have this value present, `false` is returned.
    #[inline]
    pub fn insert(&self, value: T) -> bool {
        self.map.insert(value, ()).is_none()
    }

    /// Removes a value from the set. Returns whether the value was
    /// present in the set.
    #[inline]
    pub fn remove<Q: ?Sized>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + PartialEq,
    {
        self.map.remove(value).is_some()
    }
}

impl<T> fmt::Debug for CHashSet<T>
where
    T: PartialEq + Hash + fmt::Debug + Clone,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.clone().into_iter()).finish()
    }
}

impl<T> std::iter::FromIterator<T> for CHashSet<T>
where
    T: PartialEq + Hash,
{
    #[inline]
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> CHashSet<T> {
        CHashSet {
            map: CHashMap::from_iter(iter.into_iter().map(|k| (k, ()))),
        }
    }
}

impl<T> Default for CHashSet<T>
where
    T: PartialEq + Hash,
{
    /// Creates an empty `CHashSet<T>` with the `Default` value for the hasher.
    #[inline]
    fn default() -> CHashSet<T> {
        CHashSet {
            map: CHashMap::default(),
        }
    }
}

/// An owning iterator over the items of a `HashSet`.
pub struct IntoIter<K> {
    iter: chashmap::IntoIter<K, ()>,
}

impl<T> IntoIterator for CHashSet<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    /// Creates a consuming iterator, that is, one that moves each value out
    /// of the set in arbitrary order. The set cannot be used after calling
    /// this.
    #[inline]
    fn into_iter(self) -> IntoIter<T> {
        IntoIter {
            iter: self.map.into_iter(),
        }
    }
}

impl<K> Iterator for IntoIter<K> {
    type Item = K;

    #[inline]
    fn next(&mut self) -> Option<K> {
        self.iter.next().map(|(k, _)| k)
    }
    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}
impl<K> std::iter::FusedIterator for IntoIter<K> {}

#[cfg(test)]
mod test_set {
    use super::CHashSet;

    #[test]
    fn test_from_iter() {
        let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];

        let set: CHashSet<_> = xs.iter().cloned().collect();

        for x in &xs {
            assert!(set.contains(x));
        }
    }

    #[test]
    fn test_move_iter() {
        let hs = {
            let hs = CHashSet::new();

            hs.insert('a');
            hs.insert('b');

            hs
        };

        let v = hs.into_iter().collect::<Vec<char>>();
        assert!(v == ['a', 'b'] || v == ['b', 'a']);
    }

    #[test]
    fn test_show() {
        let set = CHashSet::new();
        let empty = CHashSet::<i32>::new();

        set.insert(1);
        set.insert(2);

        let set_str = format!("{:?}", set);

        assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
        assert_eq!(format!("{:?}", empty), "{}");
    }

    #[test]
    fn test_retain() {
        let xs = [1, 2, 3, 4, 5, 6];
        let set: CHashSet<i32> = xs.iter().cloned().collect();
        set.retain(|&k| k % 2 == 0);
        assert_eq!(set.len(), 3);
        assert!(set.contains(&2));
        assert!(set.contains(&4));
        assert!(set.contains(&6));
    }
}