Struct petitset::PetitMap

pub struct PetitMap<K, V, const CAP: usize> { /* private fields */ }

A map-like data structure with a fixed maximum size

This data structure does not require the Hash or Ord traits, and instead uses linear iteration to find entries. Iteration order is guaranteed to be stable, and elements are not re-compressed upon removal.

Only CAP entries may be stored at once.

Principally, this data structure should be used for relatively small maps, where iteration performance, stable-order, stack-allocation and uniqueness are more important than insertion or look-up speed. Iteration, insertion and checking whether an element are in the map are O(CAP). Retrieving a specific element is O(CAP). Indexing into a particular element is O(1), as is removing an element at a specific index.

The values are stored as Options within an array, so niche optimization can significantly reduce memory footprint.

The maximum size of this type is given by the const-generic type parameter CAP. Keys are guaranteed to be unique.

Implementations

impl<K, V, const CAP: usize> PetitMap<K, V, CAP>

pub fn new() -> Self

Create a new empty PetitMap.

The capacity is given by the generic parameter CAP.

pub fn get_at(&self, index: usize) -> Option<(&K, &V)>

Returns a reference to the value at the provided index.

Returns Some((K, V)) if the index is in-bounds and has an element.

Panics

Panics if the provided index is larger than CAP.

pub fn get_at_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)>

Returns a mutable reference to the value at the provided index.

Returns Some((&mut K, &mut V)) if the index is in-bounds and has an element

Panics

Panics if the provided index is larger than CAP.

pub fn remove_at(&mut self, index: usize) -> bool

Removes the element at the provided index

Returns true if an element was found

Panics

Panics if the provided index is larger than CAP.

pub fn take_at(&mut self, index: usize) -> Option<(K, V)>

Removes the key-value pair at the provided index

Returns Some((K, V)) if the index was full.

Panics

Panics if the provided index is larger than CAP.

pub fn iter(&self) -> impl Iterator<Item = &(K, V)>

Returns an iterator over the key value pairs

pub fn keys(&self) -> impl Iterator<Item = &K>

An iterator visiting all keys in in a first-in, first-out order

pub fn values(&self) -> impl Iterator<Item = &V>

An iterator visiting all values in in a first-in, first-out order

The item type is a &'a V

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

An iterator visiting all values in in a first-in, first-out order

The item type is a &'a mut V

pub fn next_filled_index(&self, cursor: usize) -> Option<usize>

Returns the index of the next filled slot, if any

Returns None if the cursor is larger than CAP

pub fn next_empty_index(&self, cursor: usize) -> Option<usize>

Returns the index of the next empty slot, if any

Returns None if the cursor is larger than CAP

pub fn len(&self) -> usize

Returns the current number of key-value pairs in the PetitMap

pub const fn capacity(&self) -> usize

Returns the maximum number of elements that can be stored in the PetitMap

pub fn is_empty(&self) -> bool

Are there exactly 0 elements in the PetitMap?

pub fn is_full(&self) -> bool

Are there exactly CAP elements in the PetitMap?

pub fn swap_at(&mut self, index_a: usize, index_b: usize)

Swaps the element in index_a with the element in index_b

Panics

Panics if either index is greater than CAP.

pub fn clear(&mut self)

Removes all elements from the map without de-allocation

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

Inserts a key-value pair into the next empty index of the map, without checking for uniqueness

Returns Some(index) if the operation succeeded, or None if it failed.

Warning

This API is very easy to misuse and will completely break your PetitMap if you do. Avoid it unless you are guaranteed by construction that no duplicates exist.

impl<K: Eq, V, const CAP: usize> PetitMap<K, V, CAP>

pub fn try_insert(
    &mut self,
    key: K,
    value: V
) -> Result<SuccesfulMapInsertion<V>, CapacityError<(K, V)>>

Attempts to store the value into the map, which can be looked up by the key

Inserts the element if able, then returns the Result of that operation. This is either a SuccesfulMapInsertion or a CapacityError.

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

Stores the value in the map, which can be looked up by the key

Returns a SuccesfulMapInsertion, which encodes both the index at which the element is stored and whether the key was already present. If a key was already present, the previous value is also returned.

Panics

Panics if the map was full and the key was a non-duplicate.

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

Insert a new key-value pair at the provided index

If a matching key already existed in the set, it will be moved to the supplied index. Any key-value pair that was previously there will be moved to the matching key’s original index.

Returns Some((K, V)) of any element removed by this operation.

Panics

Panics if the provided index is larger than CAP.

pub fn find(&self, key: &K) -> Option<usize>

Returns the index for the provided key, if it exists in the map

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

Does the map contain the provided key?

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

Returns a reference to the value corresponding to the key.

Returns Some(&V) if the key is found

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

Returns the key-value pair corresponding to the supplied key.

Returns Some(&K, &V) if the key is found

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

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

Returns Some(&mut V) if the key is found

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

Removes the key-value pair from the map if the key is found

Returns Some((index)) if it was found

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

Removes and returns the key-value pair from the map if the key is found

Returns Some((index, (K,V))) if it was found

pub fn swap(&mut self, key_a: &K, key_b: &K) -> bool

Swaps the positions of element_a with the position of element_b

Returns true if both keys were found and succesfully swapped.

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. The elements are visited in order.

pub fn try_from_iter<I: IntoIterator<Item = (K, V)>>(
    element_iter: I
) -> Result<Self, CapacityError<(Self, (K, V))>>

Constructs a new PetitMap by consuming values from an iterator.

The consumed values will be stored in order, with duplicate elements discarded.

Returns an error if the iterator produces more than CAP distinct elements. The returned error will include both the element that could not be inserted, and a PetitMap containing all elements up to that point.

Example

use petitset::CapacityError;
use petitset::PetitMap;

let elems = vec![(1, 11), (2, 21), (1, 12), (4, 41), (3, 31), (1, 13)];
let set = PetitMap::<_,_, 5>::try_from_iter(elems.iter().copied());
assert_eq!(set, Ok(PetitMap::from_raw_array_unchecked([Some((1,13)), Some((2, 21)), Some((4, 41)), Some((3, 31)), None])));

let failed = PetitMap::<_,_, 3>::try_from_iter(elems.iter().copied());
assert_eq!(failed, Err(CapacityError((PetitMap::from_raw_array_unchecked([Some((1,12)), Some((2, 21)), Some((4, 41))]), (3, 31)))));

pub fn from_raw_array_unchecked(values: [Option<(K, V)>; CAP]) -> Self

Construct a PetitMap directly from an array, without checking for duplicates.

It is a logic error if the keys of any two non-None values in the array are equal, as keys are expected to be unique. If this occurs, the PetitMap returned may behave unpredictably.

impl<K: Eq, V: PartialEq, const CAP: usize> PetitMap<K, V, CAP>

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

Are the two PetitMaps element-for-element identical, in the same order?

Trait Implementations

impl<K: Clone, V: Clone, const CAP: usize> Clone for PetitMap<K, V, CAP>

fn clone(&self) -> PetitMap<K, V, CAP>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, const CAP: usize> Debug for PetitMap<K, V, CAP>

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

Formats the value using the given formatter.

impl<K, V, const CAP: usize> Default for PetitMap<K, V, CAP>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Eq, V, const CAP: usize> Extend<(K, V)> for PetitMap<K, V, CAP>

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

Inserts multiple new key-value pairs to the map.

Duplicate keys will overwrite existing values.

Panics

Panics if the map would overflow due to the insertion of non-duplicate keys

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: Eq, V, const CAP: usize> FromIterator<(K, V)> for PetitMap<K, V, CAP>

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

Panics if the iterator contains more than CAP distinct elements.

impl<K: Hash, V: Hash, const CAP: usize> Hash for PetitMap<K, V, CAP>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<K: Eq, V, const CAP: usize> IntoIterator for PetitMap<K, V, CAP>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = PetitMapIter<K, V, CAP>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Eq, V: PartialEq, const CAP: usize, const OTHER_CAP: usize> PartialEq<PetitMap<K, V, OTHER_CAP>> for PetitMap<K, V, CAP>

fn eq(&self, other: &PetitMap<K, V, OTHER_CAP>) -> bool

Tests set-equality between the two maps

This is order and cap size-independent. Use the equivalent method for elementwise-equality.

Uses an inefficient O(n^2) algorithm due to minimal trait bounds.

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

This method tests for !=.

impl<K: Eq, V: Eq, const CAP: usize> Eq for PetitMap<K, V, CAP>