Struct SparseSet 

pub struct SparseSet<K> { /* private fields */ }

A sparse set of keys convertible to indices.

SparseSet provides an efficient storage mechanism for sets where keys can be converted to usize indices. It uses a bitmap to track which indices are present, achieving both memory efficiency and fast lookup times.

The key type K must implement Into<usize> and From<usize> to convert between keys and indices. This makes it ideal for enum keys, small integers, or other types with a natural index representation.

Examples

use omp_core::{sparse_index::TrySparseIndex, sparse_set::SparseSet};

#[repr(usize)]
#[derive(Copy, Clone, Debug, PartialEq)]
enum Status {
	Active  = 0,
	Pending = 1,
	Closed  = 2,
}

#[derive(Debug)]
struct StatusError(&'static str);

impl std::fmt::Display for StatusError {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		write!(f, "{}", self.0)
	}
}

impl std::error::Error for StatusError {}

impl TrySparseIndex for Status {
	type Error = StatusError;

	fn index(&self) -> usize {
		*self as usize
	}

	fn try_from_index(index: usize) -> Result<Self, Self::Error> {
		match index {
			0 => Ok(Status::Active),
			1 => Ok(Status::Pending),
			2 => Ok(Status::Closed),
			_ => Err(StatusError("Invalid status value")),
		}
	}
}

let mut set = SparseSet::new();
set.insert(Status::Active);
set.insert(Status::Closed);

assert!(set.contains(Status::Active));
assert!(!set.contains(Status::Pending));

Implementations

impl<K> SparseSet<K>

pub const fn new() -> Self

Creates a new empty sparse index set.

pub fn with_capacity(capacity: usize) -> Self

Creates a new sparse index set with the specified capacity.

Arguments

• capacity - The maximum index that might be stored

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub const fn capacity(&self) -> usize

Returns the capacity of the underlying bitmap.

pub fn clear(&mut self)

Clears the set, removing all elements.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the set as much as possible.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the set.

pub fn into_parts(self) -> SmolBitmap

Decomposes the set into its raw bitmap.

Returns

The underlying SmolBitmap

pub const fn from_parts(bits: SmolBitmap) -> Self

Constructs a sparse set from its raw bitmap.

Arguments

• bits - The bitmap tracking which indices are present

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

Returns true if the set is a subset of another.

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

Returns true if the set is a superset of another.

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

Returns true if the set has no elements in common with another.

pub fn union(&self, other: &Self) -> Self

Computes the union with another set.

pub fn intersection(&self, other: &Self) -> Self

Computes the intersection with another set.

pub fn difference(&self, other: &Self) -> Self

Computes the difference with another set.

pub fn symmetric_difference(&self, other: &Self) -> Self

Computes the symmetric difference with another set.

impl<K: TrySparseIndex> SparseSet<K>

pub fn contains(&self, key: K) -> bool

Returns true if the set contains the specified key.

Arguments

• key - The key to check for

pub fn insert(&mut self, key: K) -> bool

Adds a key to the set.

If the set did not have this key present, true is returned. If the set did have this key present, false is returned.

Arguments

• key - The key to insert

Returns

true if the key was newly inserted, false if it was already present

pub fn remove(&mut self, key: K) -> bool

Removes a key from the set.

Arguments

• key - The key to remove

Returns

true if the key was present, false otherwise

pub fn retain<F>(&mut self, f: F)

where F: FnMut(K) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all keys k such that f(&k) returns false.

pub fn iter(&self) -> Iter<'_, K>

Returns an iterator over the keys of the set.

The iterator yields keys in the order of their index values.

pub fn first(&self) -> Option<K>

Returns the minimum (first) element in the set, or None if the set is empty.

pub fn last(&self) -> Option<K>

Returns the maximum (last) element in the set, or None if the set is empty.

pub fn is_sparse(&self) -> bool

Returns true if the set has holes (gaps) in its indices.

A set is considered sparse if there are missing indices between the first and last elements. An empty set or a set with a single element is considered non-sparse.

Trait Implementations

impl<K> Clone for SparseSet<K>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: TrySparseIndex + Debug> Debug for SparseSet<K>

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

Formats the value using the given formatter.

impl<K> Default for SparseSet<K>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K: TrySparseIndex + Deserialize<'de>> Deserialize<'de> for SparseSet<K>

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K> Eq for SparseSet<K>

impl<K: TrySparseIndex> Extend<K> for SparseSet<K>

fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: TrySparseIndex> FromIterator<K> for SparseSet<K>

fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self

Creates a value from an iterator.

impl<'a, K: TrySparseIndex> IntoIterator for &'a SparseSet<K>

type IntoIter = impl DoubleEndedIterator + ExactSizeIterator + FusedIterator + Clone

Which kind of iterator are we turning this into?

type Item = K

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: TrySparseIndex> IntoIterator for SparseSet<K>

type IntoIter = impl DoubleEndedIterator + ExactSizeIterator + FusedIterator + Clone

Which kind of iterator are we turning this into?

type Item = K

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K> PartialEq for SparseSet<K>

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

Equality operator ==.

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

Inequality operator !=.

impl<K: TrySparseIndex + Serialize> Serialize for SparseSet<K>

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.