Struct SparseSet 

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

A set for keeping track of which values are still part of the original domain based on [1]. See the module level documentation for more information.

It provides O(1) removals of values from the domain and O(|D|) traversal of the domain (where D are the values which are currently in the domain).

Note that it is required that each element contained in the domain can be uniquely mapped to an index via the provided mapping.

Bibliography

[1] V. le C. de Saint-Marcq, P. Schaus, C. Solnon, and C. Lecoutre, ‘Sparse-sets for domain implementation’, in CP workshop on Techniques foR Implementing Constraint programming Systems (TRICS), 2013, pp. 1–10.

Implementations

impl<T> SparseSet<T>

where T: StorageKey,

pub fn new(input: Vec<T>) -> SparseSet<T>

Creates a new SparseSet, using StorageKey::index as the index for the elements.

If StorageKey::index returns the same index for two elements, then this method will panic.

impl<T> SparseSet<T>

pub fn new_with_mapping(input: Vec<T>, mapping: fn(&T) -> i32) -> SparseSet<T>

Creates a new SparseSet, using the provided mapping to map the elements to indices.

If the provided mapping maps two elements in input to the same element then this method will panic.

For performance, it is recommended to provide a mapping which maps all elements to the range [0, |domain|].

pub fn set_to_empty(&mut self)

pub fn restore_temporarily_removed(&mut self)

pub fn is_empty(&self) -> bool

Determines whether the domain represented by the SparseSet is empty

pub fn len(&self) -> usize

Returns how many elements are part of the domain

pub fn get(&self, index: usize) -> &T

Returns the indexth element in the domain; if index is larger than or equal to SparseSet::len then this method will panic.

pub fn remove(&mut self, to_remove: &T)

Remove the value of to_remove from the domain; if the value is not in the domain then this method does not perform any operations.

pub fn remove_temporarily(&mut self, to_remove: &T)

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

Determines whehter the element is contained in the domain of the sparse-set.

pub fn accommodate(&mut self, element: &T)

Accomodates the element.

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

Inserts the element if it is not already contained in the sparse set.

Note that this method does not check whether the insertion of this element causes clashes in the provided mapping (i.e., it does not check whether two elements are now mapped to the same index).

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

Returns an iterator which goes over the values in the domain of the sparse-set

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

Trait Implementations

impl<T> Clone for SparseSet<T>

where T: Clone,

fn clone(&self) -> SparseSet<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for SparseSet<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> IntoIterator for SparseSet<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = Take<IntoIter<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <SparseSet<T> as IntoIterator>::IntoIter

Creates an iterator from a value.