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 in the range [0, |D|) (i.e. the mapping function is bijective)

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>

pub fn new(input: Vec<T>, mapping: fn(&T) -> usize) -> SparseSet<T>

Assumption: It is assumed that mapping is a bijective function which will return an index which is in the range [0, |D_{original}|) (where D_{original} is the initial domain before any operations have been performed).

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.

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.