Struct SparseMap 

pub struct SparseMap<K, V> { /* private fields */ }

A sparse map from keys convertible to indices to values.

SparseMap provides an efficient storage mechanism for mappings where keys can be converted to usize indices. It uses a bitmap to track which indices are occupied and a packed vector to store only the present values, 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_map::SparseMap};

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

#[derive(Debug)]
struct StatusError(String);

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".to_string())),
		}
	}
}

let mut map = SparseMap::new();
map.insert(Status::Active, "running");
map.insert(Status::Closed, "finished");

assert_eq!(map.get(Status::Active), Some(&"running"));
assert_eq!(map.get(Status::Pending), None);
assert_eq!(map[Status::Active], "running");

Implementations

impl<K, V> SparseMap<K, V>

pub fn from_sequence(values: Vec<V>) -> Self

Creates a sparse index map from a sequence of values.

The values are assigned indices starting from 0. This is equivalent to inserting each value with its position as the key.

Arguments

• values - A sequence of values to insert

pub const fn new() -> Self

Creates a new empty sparse index map.

pub fn with_capacity(capacity: usize) -> Self

Creates a new sparse index map with the specified capacity.

Arguments

• capacity - The maximum index that might be stored

pub const fn len(&self) -> usize

Returns the number of key-value pairs in the map.

pub const fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub const fn capacity(&self) -> usize

Returns the capacity of the underlying bitmap.

pub fn clear(&mut self)

Clears the map, removing all key-value pairs.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the map as much as possible.

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

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

pub const fn key_set(&self) -> &SparseSet<K>

Returns a set of all keys in the map.

pub fn into_parts(self) -> (SmolBitmap, Vec<V>)

Decomposes the map into its raw parts: bitmap and values vector.

Returns

A tuple of (SmolBitmap, Vec<V>) representing the bitmap and values

pub fn from_parts(bits: SmolBitmap, values: Vec<V>) -> Self

Constructs a sparse map from its raw parts: bitmap and values vector.

Arguments

• bits - The bitmap tracking which indices have values
• values - The packed vector of values corresponding to set bits

Safety

The caller must ensure that the bitmap and values vector are consistent:

• The number of set bits in the bitmap must equal the length of the values vector
• The values must be in the order corresponding to the set bits in the bitmap

impl<K: TrySparseIndex, V> SparseMap<K, V>

pub fn get(&self, key: K) -> Option<&V>

Gets a reference to the value corresponding to the key.

Arguments

• key - The key to look up

Returns

A reference to the value, or None if the key is not present

pub fn get_mut(&mut self, key: K) -> Option<&mut V>

Gets a mutable reference to the value corresponding to the key.

Arguments

• key - The key to look up

Returns

A mutable reference to the value, or None if the key is not present

pub fn get_or_insert(&mut self, key: K, value: V) -> &mut V

Gets the value corresponding to the key, or inserts a default value if not present.

If the key exists in the map, returns a mutable reference to the existing value. If the key does not exist, inserts the provided value and returns a mutable reference to it.

Arguments

• key - The key to look up or insert
• value - The value to insert if the key is not present

Returns

A mutable reference to the value (either existing or newly inserted)

pub fn get_or_insert_with<F>(&mut self, key: K, f: F) -> &mut V

where F: FnOnce() -> V,

Gets the value corresponding to the key, or inserts a computed default value if not present.

If the key exists in the map, returns a mutable reference to the existing value. If the key does not exist, calls the provided closure to compute a value, inserts it, and returns a mutable reference to it.

Arguments

• key - The key to look up or insert
• f - A closure that computes the value to insert if the key is not present

Returns

A mutable reference to the value (either existing or newly inserted)

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

Returns true if the map contains a value for the specified key.

Arguments

• key - The key to check for

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned. If the map did have this key present, the value is updated and the old value is returned.

Arguments

• key - The key to insert
• value - The value to associate with the key

Returns

The previous value associated with the key, if any

pub fn remove(&mut self, key: K) -> Option<V>

Removes a key from the map, returning the value at the key if the key was previously in the map.

Arguments

• key - The key to remove

Returns

The removed value, or None if the key was not present

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

where F: FnMut(K, &mut V) -> bool,

Retains only the elements specified by the predicate.

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

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

Returns an iterator over the key-value pairs of the map.

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

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Returns a mutable iterator over the key-value pairs of the map.

pub fn keys(&self) -> KeyIter<'_, K>

Returns an iterator over the keys of the map.

pub fn values(&self) -> Iter<'_, V>

Returns an iterator over the values of the map.

pub fn values_mut(&mut self) -> IterMut<'_, V>

Returns a mutable iterator over the values of the map.

pub fn rank(&self, key: K) -> usize

Finds the position in the values vector for the given index.

This counts the number of set bits before the given index to determine where the corresponding value is stored in the packed values vector.

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

Returns the first (minimum) key-value pair in the map, or None if the map is empty.

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

Returns the last (maximum) key-value pair in the map, or None if the map is empty.

pub fn is_sparse(&self) -> bool

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

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

Trait Implementations

impl<K, V: Clone> Clone for SparseMap<K, V>

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, V: Debug> Debug for SparseMap<K, V>

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

Formats the value using the given formatter.

impl<K, V> Default for SparseMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

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

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

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V: Eq> Eq for SparseMap<K, V>

impl<K: TrySparseIndex, V> Extend<(K, V)> for SparseMap<K, V>

fn extend<T: IntoIterator<Item = (K, V)>>(&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, V> FromIterator<(K, V)> for SparseMap<K, V>

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

Creates a value from an iterator.

impl<K: TrySparseIndex, V> Index<K> for SparseMap<K, V>

type Output = V

The returned type after indexing.

fn index(&self, key: K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: TrySparseIndex, V> IndexMut<K> for SparseMap<K, V>

fn index_mut(&mut self, key: K) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

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

type IntoIter = impl DoubleEndedIterator + ExactSizeIterator + FusedIterator + Clone

Which kind of iterator are we turning this into?

type Item = (K, &'a V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K: TrySparseIndex, V> IntoIterator for &'a mut SparseMap<K, V>

type IntoIter = impl DoubleEndedIterator + ExactSizeIterator + FusedIterator

Which kind of iterator are we turning this into?

type Item = (K, &'a mut V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: TrySparseIndex, V> IntoIterator for SparseMap<K, V>

type IntoIter = impl DoubleEndedIterator + ExactSizeIterator + FusedIterator

Which kind of iterator are we turning this into?

type Item = (K, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V: PartialEq> PartialEq for SparseMap<K, V>

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

Equality operator ==.

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

Inequality operator !=.

impl<K: TrySparseIndex + Serialize, V: Serialize> Serialize for SparseMap<K, V>

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

where S: Serializer,

Serialize this value into the given Serde serializer.