Struct mexset::MexSet

pub struct MexSet<T: Ord + Hash + Copy + Unsigned + Num> { /* fields omitted */ }

The MexSet data structure is an implementation of a set that can quickly find MEX.

The MEX (Minimum EXcluded) of a subset of the set of natural numbers is the minimum natural number missing from this subset. That is, it is the minimum value of the complement set.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
assert_eq!(set.minimum_excluded(), 0);   // The MEX of an empty set is 0

set.insert(2); 
set.insert(1);
assert_eq!(set.minimum_excluded(), 0);   // 0 is the smallest missing number

set.insert(0);
assert_eq!(set.minimum_excluded(), 3);   // mex({0, 1, 2}) = 3

set.insert(4);
assert_eq!(set.minimum_excluded(), 3);   // mex({0, 1, 2, 4}) = 3

set.insert(3);
assert_eq!(set.minimum_excluded(), 5);   // mex({0, 1, 2, 3, 4}) = 5

set.remove(&1);
assert_eq!(set.minimum_excluded(), 1);  // mex({0, 2, 3, 4}) = 1

The insert, remove and minimum_excluded methods have a runtime of O(log(N)), where N is the number of elements in the MexSet.

If you are interested in learning more about MEX, I suggest you watch this video.

Implementations

impl<T: Ord + Hash + Copy + Unsigned + Num> MexSet<T>

pub fn new() -> Self

Create new MexSet.

Examples

use mexset::MexSet;
 
let set: MexSet<u32> = MexSet::new();

pub fn len(&self) -> usize

Get the number of unique elements in a set.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
assert_eq!(set.len(), 0);
 
set.insert(1);
set.insert(1);
set.insert(2);
assert_eq!(set.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
assert!(set.is_empty());

set.insert(1);
assert!(!set.is_empty());

pub fn clear(&mut self)

Clear the MexSet.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
set.insert(1);
set.insert(2);
set.insert(3);

set.clear();
assert_eq!(set.len(), 0);

pub fn insert(&mut self, item: T) -> bool

Adds a value to the set.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

Examples

use mexset::MexSet;
 
let mut set: MexSet<u32> = MexSet::new();

assert!(set.insert(1));
assert!(!set.insert(1));
assert_eq!(set.len(), 1);

pub fn minimum_excluded(&self) -> T

Find set’s MEX.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
assert_eq!(set.minimum_excluded(), 0);   // { }
 
set.extend(vec![0, 1, 2].into_iter());
assert_eq!(set.minimum_excluded(), 3);   // {0, 1, 2, _ }

set.extend(vec![4, 5].into_iter());
assert_eq!(set.minimum_excluded(), 3);   // {0, 1, 2, _ , 4, 5}

set.insert(3);
assert_eq!(set.minimum_excluded(), 6);   // {0, 1, 2, 3, 4, 5, _ }

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

Returns true if the set contains a value.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();
assert!(!set.contains(&1));

set.insert(1);
assert!(set.contains(&1));

pub fn remove(&mut self, value: &T) -> bool

Removes a value from the set. Returns whether the value was present in the set.

Examples

use mexset::MexSet;

let mut set: MexSet<u32> = MexSet::new();

set.insert(1);
assert_eq!(set.remove(&1), true);
assert_eq!(set.remove(&1), false);

pub fn iter(&self) -> Iter<'_, T>

An iterator visiting all elements in arbitrary order. The iterator element type is &'a T.

Examples

use mexset::MexSet;
use std::collections::HashSet;

let mut set: MexSet<u32> = MexSet::new();
set.insert(1);
set.insert(2);

assert_eq!(
    set.iter().collect::<HashSet<&u32>>(),
    vec![&1, &2].into_iter().collect::<HashSet<&u32>>(),
);

pub fn with_range(n: T) -> Self

Create a MexSet with elements [0; n).

This function is a much faster alternative to sequential insert() calls.

Examples

use mexset::MexSet;

assert_eq!(
  MexSet::<u32>::with_range(5),
  vec![0, 1, 2, 3, 4].into_iter().collect::<MexSet<u32>>(),
);

Trait Implementations

impl<T: Clone + Ord + Hash + Copy + Unsigned + Num> Clone for MexSet<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Ord + Hash + Copy + Unsigned + Num> Debug for MexSet<T>

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

Formats the value using the given formatter.

impl<T: Ord + Hash + Copy + Unsigned + Num> Extend<T> for MexSet<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extend the MexSet with elements from an iterator.

Examples

use mexset::MexSet;
 
let mut set: MexSet<u32> = MexSet::new();
set.extend(vec![2, 3, 5].into_iter());

assert!(set.contains(&2));
assert!(set.contains(&3));
assert!(set.contains(&5));

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord + Hash + Copy + Unsigned + Num> FromIterator<T> for MexSet<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Сreating a MexSet from an iterator.

Examples

use mexset::MexSet;
use std::iter::FromIterator;
 
let set: MexSet<u32> = MexSet::from_iter(vec![2, 3, 5].into_iter());
assert!(set.contains(&2));
assert!(set.contains(&3));
assert!(set.contains(&5));
 
let set: MexSet<u32> = vec![5, 3, 2].into_iter().collect();
assert!(set.contains(&2));
assert!(set.contains(&3));
assert!(set.contains(&5));

impl<T: Ord + Hash + Copy + Unsigned + Num> IntoIterator for MexSet<T>

fn into_iter(self) -> IntoIter<T>

Creates a consuming iterator, that is, one that moves each value out of the set in arbitrary order. The set cannot be used after calling this.

Examples

use mexset::MexSet;
use std::collections::HashSet;

let mut set: MexSet<u32> = MexSet::new();
set.insert(1);
set.insert(2);

assert_eq!(
    set.into_iter().collect::<HashSet<u32>>(),
    vec![1, 2].into_iter().collect::<HashSet<u32>>(),
);

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<T: PartialEq + Ord + Hash + Copy + Unsigned + Num> PartialEq<MexSet<T>> for MexSet<T>

fn eq(&self, other: &MexSet<T>) -> bool

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

fn ne(&self, other: &MexSet<T>) -> bool

This method tests for !=.

impl<T: Eq + Ord + Hash + Copy + Unsigned + Num> Eq for MexSet<T>

impl<T: Ord + Hash + Copy + Unsigned + Num> StructuralEq for MexSet<T>

impl<T: Ord + Hash + Copy + Unsigned + Num> StructuralPartialEq for MexSet<T>