Struct contrail_collections::sparse_set::SparseSet

pub struct SparseSet<M> { /* fields omitted */ }

A specialized backtrackable data structure for storing subsets of the range 0..n that can only decrease in size.

Features O(1) contains() and remove() as well as fast value iteration.

Methods

impl<M> SparseSet<M> where
    M: StorageMode, 

pub fn new_full(builder: &mut TrailBuilder, len: usize) -> Self

Creates a new SparseSet initialized with the values 0..len.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

assert_eq!(sparse_set.len(&trail), 10);

pub fn iter<'s, 't: 's>(
    &'s self,
    trail: &'t Trail
) -> impl Iterator<Item = usize> + 's

Returns an iterator over the elements of the SparseSet in arbitrary order.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

// remove some values
sparse_set.remove(&mut trail, 2);
sparse_set.remove(&mut trail, 3);
sparse_set.remove(&mut trail, 6);

for value in sparse_set.iter(&trail) {
    assert!(value != 2 && value != 3 && value != 6);
}

pub fn len(&self, trail: &Trail) -> usize

Returns the length of the SparseSet.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

assert_eq!(sparse_set.len(&trail), 10);

sparse_set.remove(&mut trail, 5);

assert_eq!(sparse_set.len(&trail), 9);

pub fn is_empty(&self, trail: &Trail) -> bool

Returns true if the sparse set is empty and false otherwise.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 1);
let mut trail = builder.finish();

assert!(!sparse_set.is_empty(&trail));

sparse_set.remove(&mut trail, 0);

assert!(sparse_set.is_empty(&trail));

pub fn contains(&self, trail: &Trail, val: usize) -> bool

Checks if the sparse set contains the given value.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

assert!(sparse_set.contains(&trail, 5));
assert!(!sparse_set.contains(&trail, 15));

pub fn remove(&self, trail: &mut Trail, val: usize)

Removes a value from the sparse set.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

assert!(sparse_set.contains(&trail, 5));
assert_eq!(sparse_set.len(&trail), 10);

sparse_set.remove(&mut trail, 5);

assert!(!sparse_set.contains(&trail, 5));
assert_eq!(sparse_set.len(&trail), 9);

pub fn filter(&self, trail: &mut Trail, f: impl Fn(usize) -> bool)

Filters the elements in the sparse set according to the predicate function.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

// create a sparse set initialized with the values 0..10
let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

// keep only the odd numbers
sparse_set.filter(&mut trail, |x| x % 2 == 1);

// make sure we kept only the odd numbers
let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
// we have to sort the values because a sparse set is unordered
values.sort();
assert_eq!(values, vec![1, 3, 5, 7, 9]);

pub fn intersect(
    &self,
    trail: &mut Trail,
    vals: impl IntoIterator<Item = usize>
)

Intersects the sparse set with the given values.

Examples

use contrail::TrailBuilder;
use contrail_collections::sparse_set::BacktrackableSparseSet;

// create a sparse set initialized with the elements 0..10
let mut builder = TrailBuilder::new();
let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
let mut trail = builder.finish();

// keep only the fibonacci numbers
sparse_set.intersect(&mut trail, vec![0, 1, 1, 2, 3, 5, 8, 13]);

// make sure we kept only the fibonacci numbers
let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
// we have to sort the values because a sparse set is unordered
values.sort();
assert_eq!(values, vec![0, 1, 2, 3, 5, 8]);

Trait Implementations

impl<M> PartialEq<SparseSet<M>> for SparseSet<M>

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]

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

This method tests for !=.

impl<M> Clone for SparseSet<M>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<M> Eq for SparseSet<M>

impl<M> Copy for SparseSet<M>

impl<M> Debug for SparseSet<M> where
    M: StorageMode, 

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

Formats the value using the given formatter.