Struct smolset::SmolSet

pub struct SmolSet<A: Array> where
    A::Item: PartialEq + Eq,  { /* fields omitted */ }

A SmolSet is an unordered set of elements. It is designed to work best for very small sets (no more than ten or so elements). In order to support small sets very efficiently, it stores elements in a simple unordered array. When the set is smaller than the size of the array A, all elements are stored inline, without heap allocation. This is accomplished by using a smallvec::SmallVec.

The insert, remove, and query methods on SmolSet have O(n) time complexity in the current set size: they perform a linear scan to determine if the element in question is present. This is inefficient for large sets, but fast and cache-friendly for small sets.

Example usage:

use smolset::SmolSet;

// `s` and its elements will be completely stack-allocated in this example.
let mut s: SmolSet<[u32; 4]> = SmolSet::new();
s.insert(1);
s.insert(2);
s.insert(3);
assert_eq!(s.len(), 3);
assert!(s.contains(&1));

TODO: Add the ability to switch modes explicitly.

Implementations

impl<A: Array> SmolSet<A> where
    A::Item: PartialEq + Eq + Hash, 

pub fn new() -> SmolSet<A>

Creates a new, empty SmolSet.

pub fn mode(&self) -> SetMode

pub fn is_empty(&self) -> bool

Returns the number of elements in this set.

pub fn insert(&mut self, elem: A::Item) -> bool

Inserts elem into the set if not yet present. Returns true if the set did not have this element present, or false if it already had this element present.

pub fn remove(&mut self, elem: &A::Item) -> bool

Removes elem from the set. Returns true if the element was removed, or false if it was not found.

pub fn contains(&self, elem: &A::Item) -> bool

Tests whether elem is present. Returns true if it is present, or false if not.

pub fn iter(&self) -> SmolSetIter<'_, A>

Returns an iterator over the set elements. Elements will be returned in an arbitrary (unsorted) order.

pub fn len(&self) -> usize

Returns the current length of the set.

pub fn clear(&mut self)

Clears the set.

pub fn get(&self, elem: &A::Item) -> Option<&A::Item>

If the given elem exists in the set, returns the reference to the value inside the set. Where they are equal (in the case where the set is in stack mode) or they hash equally (if the set is in heap mode).

pub fn take(&mut self, value: &A::Item) -> Option<A::Item>

If the given elem exists in the set, returns the value inside the set where they are either equal or hash equally. Then, remove that value from the set.

pub fn replace(&mut self, value: A::Item) -> Option<A::Item>

Adds a value to the set, replacing the existing value, if any, that is equal to the given one. Returns the replaced value.

pub fn drain(&mut self) -> SmallDrain<A::Item>

Empties the set and returns an iterator over it.

pub fn retain<F>(&mut self, f: F) where
    F: FnMut(&mut A::Item) -> bool + for<'r> FnMut(&'r <A as Array>::Item) -> bool, 

Removes all elements in the set that does not satisfy the given predicate f.

pub fn intersection<'a>(
    &'a self,
    other: &'a Self
) -> SmallIntersection<'a, A::Item>

Returns an iterator over the intersection of the 2 sets.

pub fn union<'a>(&'a self, other: &'a Self) -> SmallUnion<'a, A::Item>

Returns an iterator over the union of the 2 sets.

pub fn difference<'a>(&'a self, other: &'a Self) -> SmallDifference<'a, A::Item>

Returns an iterator over the difference of the 2 sets.

pub fn symmetric_difference<'a>(
    &'a self,
    other: &'a Self
) -> SmallSymmetricDifference<'a, A::Item>

Returns an iterator over the symmetric difference of the 2 sets.

Trait Implementations

impl<A: Array> Clone for SmolSet<A> where
    A::Item: PartialEq + Eq + Clone, 

fn clone(&self) -> SmolSet<A>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A: Array> Debug for SmolSet<A> where
    A::Item: PartialEq + Eq + Debug, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<A: Array> Default for SmolSet<A> where
    A::Item: PartialEq + Eq + Hash, 

fn default() -> Self

Returns the “default value” for a type.

impl<A: Array> FromIterator<<A as Array>::Item> for SmolSet<A> where
    A::Item: PartialEq + Eq + Hash, 

fn from_iter<T>(iter: T) -> Self where
    T: IntoIterator<Item = A::Item>, 

Creates a value from an iterator.

impl<A> IntoIterator for SmolSet<A> where
    A: Array,
    A::Item: PartialEq + Eq + Hash, 

Implement into iterator for the SmolSet

type Item = A::Item

The type of the elements being iterated over.

type IntoIter = SmolSetIntoIter<A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A> IntoIterator for &'a SmolSet<A> where
    A: Array,
    A::Item: PartialEq + Eq + Hash, 

Implement into iterator for borrowed SmolSet

type Item = &'a A::Item

The type of the elements being iterated over.

type IntoIter = SmolSetIter<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A: Array> PartialEq<SmolSet<A>> for SmolSet<A> where
    A::Item: Eq + PartialEq + Hash, 

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.