Struct ShrinkSet 

pub struct ShrinkSet { /* private fields */ }

A ShrinkSet is a set of integers that supports efficient removal and refilling.

ShrinkSets are automatically initialized such that they contain all integers up to, but not including, their capacity. For example, a ShrinkSet with a capacity of 5 will contain the integers 0, 1, 2, 3, and 4 upon initialization.

A ShrinkSet supports the following additional operations with the associated time complexity:

• remove - remove an integer from the set in O(1) time
• refill - adds all removed elements back into the set in O(1) time
• pop - remove and return a random member of the set in O(1) time

ShrinkSets are useful for situations where we want to prune search spaces or work queues (for example) and then reset them to their initial state efficiently.

The algorithm used by ShrinkSet is believed to be novel, but if there is existing literature, please let me know so I can reference it here.

Implementations

impl<'a> ShrinkSet

pub fn new(size: usize) -> Self

Returns a ShrinkSet with the given capacity.

Arguments

• size - at creation time, the set will contain all integers up to, but not including, this value

Examples

// This set stores all integers 0..=4.
use intset::ShrinkSet;
let mut set = ShrinkSet::new(5);
assert!(set.contains(3));
assert!(set.contains(4));

pub fn capacity(&self) -> usize

Returns one greater than the largest integer that can be stored in this set. That is, a set that can store integers from 0 to 5 will have a capacity of 6.

pub fn len(&self) -> usize

Return the number of integers in the set.

Examples

use intset::ShrinkSet;
let mut set = ShrinkSet::new(5);
set.remove(1);
set.remove(4);
assert_eq!(set.len(), 3);

pub fn contains(&self, value: usize) -> bool

Returns true if the specified value is in the set.

Arguments

• value - the element to test

Examples

use intset::ShrinkSet;
let mut set = ShrinkSet::new(5);
set.remove(1);
assert!(!set.contains(1));
assert!(set.contains(3));

pub fn refill(&mut self)

Refills the set by adding all removed elements back.

Examples

use intset::ShrinkSet;
let mut set = ShrinkSet::new(5);
set.remove(0);
set.remove(2);
assert!(set.contains(1));
assert!(set.contains(3));
assert!(set.contains(4));
assert!(!set.contains(0));
assert!(!set.contains(2));

set.refill();
assert!(set.contains(1));
assert!(set.contains(3));
assert!(set.contains(4));
assert!(set.contains(0));
assert!(set.contains(2));

pub fn iter(&'a self) -> impl Iterator<Item = &usize> + 'a

Returns an iterator over the values in the set. Uniqueness is guaranteed; ordering is not.

pub fn remove(&mut self, item: usize) -> usize

Remove an element from the set.

Arguments

• item - the item to remove

Examples

use intset::ShrinkSet;
let mut set = ShrinkSet::new(5);
set.remove(0);
set.remove(2);
assert!(set.contains(1));
assert!(set.contains(3));
assert!(!set.contains(0));
assert!(!set.contains(2));

pub fn pop(&mut self) -> Option<usize>

Remove and return a random element from the set in constant time, or None if the set is empty.

Trait Implementations

impl Debug for ShrinkSet

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

Formats the value using the given formatter.