[−][src]Struct contrail_collections::sparse_set::SparseSet
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,
[src]
M: StorageMode,
pub fn new_full(builder: &mut TrailBuilder, len: usize) -> Self
[src]
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
[src]
&'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
[src]
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
[src]
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
[src]
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)
[src]
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)
[src]
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>
)
[src]
&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> Clone for SparseSet<M>
[src]
fn clone(&self) -> Self
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<M> PartialEq<SparseSet<M>> for SparseSet<M>
[src]
fn eq(&self, other: &Self) -> bool
[src]
#[must_use]
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
#[must_use]
fn ne(&self, other: &Rhs) -> boolThis method tests for !=
.
impl<M> Eq for SparseSet<M>
[src]
impl<M> Copy for SparseSet<M>
[src]
impl<M> Debug for SparseSet<M> where
M: StorageMode,
[src]
M: StorageMode,
Auto Trait Implementations
Blanket Implementations
impl<T, U> Into for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
impl<T, U> TryFrom for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = !
🔬 This is a nightly-only experimental API. (
try_from
)The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T> Borrow for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> BorrowMut for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> TryInto for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,