Struct petitset::PetitSet

pub struct PetitSet<T, const CAP: usize> { /* private fields */ }

A set-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.

Under the hood, this is a [PetitMap<T, (), CAP>].

Principally, this data structure should be used for relatively small sets, 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 is in the set are 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. Entries in this structure are guaranteed to be unique.

Implementations

impl<T, const CAP: usize> PetitSet<T, CAP>

pub fn new() -> Self

Create a new empty PetitSet.

The capacity is given by the generic parameter CAP.

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 const fn capacity(&self) -> usize

Return the capacity of the PetitSet

pub fn len(&self) -> usize

Returns the current number of elements in the PetitSet

pub fn is_empty(&self) -> bool

Are there exactly 0 elements in the PetitSet?

pub fn is_full(&self) -> bool

Are there exactly CAP elements in the PetitSet?

pub fn iter(&self) -> impl Iterator<Item = &T>

Returns an iterator over the elements of the PetitSet

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

Returns a reference to the provided index of the underlying array

Returns Some(&T) if the index is in-bounds and has an element

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

Returns a mutable reference to the provided index of the underlying array

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

pub fn clear(&mut self)

Removes all elements from the set without allocation

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<T>

Removes the element at the provided index

Returns Some(T) if an element was found at that index, or None if no element was there.

Panics

Panics if the provided index is larger than CAP.

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 insert_unchecked(&mut self, element: T) -> Option<usize>

Inserts an element into the next empty index of the set, 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 PetitSet if you do. Avoid it unless you are guaranteed by construction that no duplicates exist.

impl<T: Eq, const CAP: usize> PetitSet<T, CAP>

pub fn find(&self, element: &T) -> Option<usize>

Returns the index for the provided element, if it exists in the set

pub fn contains(&self, element: &T) -> bool

Is the provided element in the set?

pub fn try_insert(
    &mut self,
    element: T
) -> Result<SuccesfulSetInsertion, CapacityError<T>>

Attempt to insert a new element to the set in the first available slot.

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

pub fn insert(&mut self, element: T) -> SuccesfulSetInsertion

Insert a new element to the set in the first available slot

Returns a SuccesfulSetInsertion, which encodes both the index at which the element is stored and whether the element was already present.

Panics

Panics if the set is full and the item is not a duplicate

pub fn insert_at(&mut self, element: T, index: usize) -> Option<T>

Insert a new element to the set at the provided index

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

Returns Some(T) of any element removed by this operation.

Panics

Panics if the provided index is larger than CAP.

pub fn try_extend(
    &mut self,
    elements: impl IntoIterator<Item = T>
) -> Result<(), CapacityError<T>>

Inserts multiple new elements to the set. Duplicate elements are discarded.

Returns a CapacityError if the extension cannot be completed because the set is full.

pub fn remove(&mut self, element: &T) -> Option<usize>

Removes the element from the set, if it exists

Returns Some(index) if the element was found, or None if no matching element is found

pub fn take(&mut self, element: &T) -> Option<(usize, T)>

Removes an element from the set, if it exists, returning both the value that compared equal and the index at which it was stored.

pub fn swap(&mut self, element_a: &T, element_b: &T) -> bool

Swaps the positions of element_a with the position of element_b

Returns true if both elements were found and succesfully swapped.

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

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

pub fn retain<F>(&mut self, f: F) where
    F: FnMut(&T) -> bool, 

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. The elements are visited in order.

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

Constructs a new PetitSet 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 PetitSet containing all elements up to that point.

Example

use petitset::CapacityError;
use petitset::PetitSet;

let elems = vec![1, 2, 1, 4, 3, 1];
let set = PetitSet::<_, 5>::try_from_iter(elems.iter().copied());
assert_eq!(set, Ok(PetitSet::from_raw_array_unchecked([Some(1), Some(2), Some(4), Some(3), None])));

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

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

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

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

impl<T: Eq + Clone, const CAP: usize> PetitSet<T, CAP>

pub fn is_disjoint<const OTHER_CAP: usize>(
    &self,
    other: &PetitSet<T, OTHER_CAP>
) -> bool

Do the sets contain any common elements?

Examples

use petitset::PetitSet;

let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
let mut set_c: PetitSet<usize, 1> = PetitSet::default();
set_c.insert(42);

assert!(!set_a.is_disjoint(&set_b));
assert!(!set_b.is_disjoint(&set_a));

assert!(set_a.is_disjoint(&set_c));
assert!(set_c.is_disjoint(&set_a));

pub fn is_subset<const OTHER_CAP: usize>(
    &self,
    other: &PetitSet<T, OTHER_CAP>
) -> bool

Are all elements in self contained in other?

Examples

use petitset::PetitSet;

let set_a: PetitSet<usize, 3> = PetitSet::from_iter([1, 2, 3]);
let set_b: PetitSet<usize, 5> = PetitSet::from_iter([2, 3]);

assert!(set_a.is_subset(&set_a));

assert!(!set_a.is_subset(&set_b));
assert!(set_b.is_subset(&set_a));

pub fn is_superset<const OTHER_CAP: usize>(
    &self,
    other: &PetitSet<T, OTHER_CAP>
) -> bool

Are all elements in other contained in self?

Examples

use petitset::PetitSet;

let set_a: PetitSet<usize, 3> = PetitSet::from_iter([1, 2, 3]);
let set_b: PetitSet<usize, 5> = PetitSet::from_iter([2, 3]);

assert!(set_a.is_superset(&set_a));

assert!(set_a.is_superset(&set_b));
assert!(!set_b.is_superset(&set_a));

Trait Implementations

impl<T: Clone, const CAP: usize> Clone for PetitSet<T, CAP>

fn clone(&self) -> PetitSet<T, CAP>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, const CAP: usize> Debug for PetitSet<T, CAP>

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

Formats the value using the given formatter.

impl<T, const CAP: usize> Default for PetitSet<T, CAP>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Eq, const CAP: usize> Extend<T> for PetitSet<T, CAP>

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

Inserts multiple new elements to the set. Duplicate elements are discarded.

Panics

Panics if the set would overflow due to the insertion of non-duplicate items

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<T: Eq, const CAP: usize> FromIterator<T> for PetitSet<T, CAP>

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

Panics if the iterator contains more than CAP distinct elements.

impl<T: Hash, const CAP: usize> Hash for PetitSet<T, 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<T: Eq, const CAP: usize> IntoIterator for PetitSet<T, CAP>

type Item = T

The type of the elements being iterated over.

type IntoIter = PetitSetIter<T, CAP>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Eq, const CAP: usize, const OTHER_CAP: usize> PartialEq<PetitSet<T, OTHER_CAP>> for PetitSet<T, CAP>

fn eq(&self, other: &PetitSet<T, OTHER_CAP>) -> bool

Tests set-equality between the two sets

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<T: Eq, const CAP: usize> Eq for PetitSet<T, CAP>