bumpish 0.2.0

mod iter;

pub use iter::{Drain, IntoIter, Iter};

use crate::map::BumpMap;
use core::fmt::{self, Debug};
use core::hash::{BuildHasher, Hash};
use core::iter::Iterator;
use equivalent::Equivalent;

#[cfg(feature = "std")]
use std::hash::RandomState;

#[cfg(feature = "std")]
pub struct BumpSet<T, S = RandomState> {
    map: BumpMap<T, (), S>,
}

#[cfg(not(feature = "std"))]
pub struct BumpSet<T, S> {
    map: BumpMap<T, (), S>,
}

#[cfg(feature = "std")]
impl<T> BumpSet<T, RandomState> {
    /// Creates an empty `BumpSet`.
    ///
    /// The method will not allocate until it is first inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    /// let set: BumpSet<i32> = BumpSet::new();
    /// ```
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Default::default()
    }

    /// Creates an empty `BumpSet` with at least the specified capacity.
    ///
    /// The hash set will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements than
    /// `capacity`. If `capacity` is zero, the hash set will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    /// let set: BumpSet<i32> = BumpSet::with_capacity(10);
    /// assert!(set.capacity() >= 10);
    /// ```
    #[inline]
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, Default::default())
    }
}

impl<T, S> BumpSet<T, S> {
    /// Creates a new empty hash set which will use the given hasher to hash
    /// keys.
    ///
    /// The hash set does not allocate until the first element is inserted.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    /// use std::hash::RandomState;
    ///
    /// let s = RandomState::new();
    /// let mut set = BumpSet::with_hasher(s);
    /// set.insert(2);
    /// ```
    pub const fn with_hasher(hasher: S) -> Self {
        Self {
            map: BumpMap::with_hasher(hasher),
        }
    }

    /// Creates an empty `BumpSet` with at least the specified capacity, using
    /// `hasher` to hash the keys.
    ///
    /// The hash set will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements than
    /// `capacity`. If `capacity` is zero, the hash set will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    /// use std::hash::RandomState;
    ///
    /// let s = RandomState::new();
    /// let mut set = BumpSet::with_capacity_and_hasher(10, s);
    /// set.insert(1);
    /// ```
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
        Self {
            map: BumpMap::with_capacity_and_hasher(capacity, hash_builder),
        }
    }

    /// Returns the number of elements the set can hold without reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let set: BumpSet<i32> = BumpSet::with_capacity(100);
    /// assert!(set.capacity() >= 100);
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.map.capacity()
    }

    /// Returns the number of elements in the set.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut v = BumpSet::new();
    /// assert_eq!(v.len(), 0);
    /// v.insert(1);
    /// assert_eq!(v.len(), 1);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns `true` if the set contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut v = BumpSet::new();
    /// assert!(v.is_empty());
    /// v.insert(1);
    /// assert!(!v.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Clears the set, removing all values. Can keep some of the allocated
    /// memory for reuse.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut v = BumpSet::new();
    /// v.insert(1);
    /// v.clear();
    /// assert!(v.is_empty());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.map.clear();
    }

    /// An iterator visiting all elements in insertion order.
    ///
    /// The iterator element type is `&'a T`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut set = BumpSet::new();
    /// set.insert("a");
    /// set.insert("b");
    ///
    /// // Will print in an arbitrary order.
    /// for x in set.iter() {
    ///     println!("{x}");
    /// }
    /// ```
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self.map.iter())
    }
}

impl<T: Eq, S> BumpSet<T, S> {
    /// Clears the set, returning all elements as an iterator. Keeps some of the
    /// allocated memory for reuse.
    ///
    /// If the returned iterator is dropped before being fully consumed, it
    /// drops the remaining elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    ///
    /// let mut set = BumpSet::from([1, 2, 3]);
    /// assert!(!set.is_empty());
    ///
    /// // print 1, 2, 3 in an arbitrary order
    /// for i in set.drain() {
    ///     println!("{i}");
    /// }
    ///
    /// assert!(set.is_empty());
    /// ```
    pub fn drain(&mut self) -> Drain<'_, T> {
        Drain::new(self.map.drain())
    }
}

impl<T, S> BumpSet<T, S>
where
    S: BuildHasher,
{
    /// Returns a reference to the set's [`BuildHasher`].
    ///
    /// [`BuildHasher`]: https://doc.rust-lang.org/beta/std/hash/trait.BuildHasher.html
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    /// use std::hash::RandomState;
    ///
    /// let hasher = RandomState::new();
    /// let set: BumpSet<i32> = BumpSet::with_hasher(hasher);
    /// let hasher: &RandomState = set.hasher();
    /// ```
    #[inline]
    pub fn hasher(&self) -> &S {
        self.map.hasher()
    }

    /// Returns `true` if the set contains a value.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let set = BumpSet::from([1, 2, 3]);
    /// assert_eq!(set.contains(&1), true);
    /// assert_eq!(set.contains(&4), false);
    /// ```
    pub fn contains<Q>(&self, value: &Q) -> bool
    where
        Q: ?Sized + Hash + Equivalent<T>,
    {
        self.map.contains_key(value)
    }

    /// Returns a reference to the value in the set, if any, that is equal to
    /// the given value.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let set = BumpSet::from([1, 2, 3]);
    /// assert_eq!(set.get(&2), Some(&2));
    /// assert_eq!(set.get(&4), None);
    /// ```
    pub fn get<Q>(&self, value: &Q) -> Option<&T>
    where
        Q: ?Sized + Hash + Equivalent<T>,
    {
        self.map.get_key_value(value).map(|(k, _)| k)
    }
}

impl<T, S> BumpSet<T, S>
where
    T: Hash + Eq,
    S: BuildHasher,
{
    /// Adds a value to the set.
    ///
    /// Returns whether the value was newly inserted. That is:
    ///
    /// - If the set did not previously contain this value, `true` is returned.
    /// - If the set already contained this value, `false` is returned,
    ///   and the set is not modified: original value is not replaced,
    ///   and the value passed as argument is dropped.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut set = BumpSet::new();
    ///
    /// assert_eq!(set.insert(2), Some(&2));
    /// assert_eq!(set.insert(2), None);
    /// assert_eq!(set.len(), 1);
    /// ```
    #[inline]
    pub fn insert(&self, value: T) -> Option<&T> {
        self.map.insert_full(value, ()).map(|(old, _)| old)
    }

    /// Adds a value to the set, replacing the existing value, if any, that is
    /// equal to the given one. Returns the replaced value.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpSet;
    /// let mut set = BumpSet::new();
    /// assert_eq!(set.replace(Vec::<u32>::new()), None);
    ///
    /// let old_vec = set.replace(Vec::with_capacity(10)).unwrap();
    /// assert_eq!(old_vec.capacity(), 0);
    ///
    /// let new_vec = set.into_iter().next().unwrap();
    /// assert!(new_vec.capacity() >= 10);
    /// ```
    pub fn replace(&mut self, value: T) -> Option<T> {
        self.map.replace_full(value, ()).map(|(old, _)| old)
    }
}

impl<T, S> core::clone::Clone for BumpSet<T, S>
where
    T: Clone,
    S: Clone,
{
    fn clone(&self) -> Self {
        Self {
            map: self.map.clone(),
        }
    }
}

impl<T, S> Debug for BumpSet<T, S>
where
    T: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

impl<T, S> Default for BumpSet<T, S>
where
    S: Default,
{
    /// Creates an empty `BumpSet<K, V, S>`, with the `Default` value for the
    /// hasher.
    #[inline]
    fn default() -> Self {
        Self::with_hasher(Default::default())
    }
}

impl<T, S> PartialEq for BumpSet<T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        self.iter().all(|k| other.contains(k))
    }
}

#[cfg(feature = "std")]
impl<T, const N: usize> From<[T; N]> for BumpSet<T, RandomState>
where
    T: Eq + Hash,
{
    /// Converts a `[T; N]` into a `BumpSet<T>`.
    ///
    /// If the array contains any equal values,
    /// all but one will be dropped.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpSet;
    ///
    /// let set1 = BumpSet::from([1, 2, 3, 4]);
    /// let set2: BumpSet<_> = [1, 2, 3, 4].into();
    /// assert_eq!(set1, set2);
    /// ```
    fn from(arr: [T; N]) -> Self {
        let mut set = Self::with_capacity(N);
        set.extend(arr);
        set
    }
}

impl<T, S> FromIterator<T> for BumpSet<T, S>
where
    T: Eq + Hash,
    S: BuildHasher + Default,
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut set = BumpSet::with_hasher(Default::default());
        set.extend(iter);
        set
    }
}

impl<T, S> Extend<T> for BumpSet<T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for item in iter {
            self.insert(item);
        }
    }
}

impl<'a, T, S> Extend<&'a T> for BumpSet<T, S>
where
    T: 'a + Eq + Hash + Copy,
    S: BuildHasher,
{
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.extend(iter.into_iter().copied());
    }
}

impl<'a, T, S> core::iter::IntoIterator for &'a BumpSet<T, S> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T, S> core::iter::IntoIterator for BumpSet<T, S> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self.map.into_iter())
    }
}