Struct DisjointSets

pub struct DisjointSets<T> { /* private fields */ }

Stores disjoint sets and provides efficient operations to merge two sets, and to find a representative member of a set given any member of that set. In this implementation, sets always have at least two members, and can only be formed by the merge operation.

Implementations

impl<T: Copy + Debug + Eq + Hash> DisjointSets<T>

pub fn find_mut(&mut self, x: T) -> Option<T>

Find a representative member of the set containing x. If x has not been merged with any other items using merge, returns None. This method updates the data structure to make future queries faster, and takes amortized constant time.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
assert_eq!(sets.find_mut(3).unwrap(), sets.find_mut(4).unwrap());
assert_eq!(sets.find_mut(10), None);

pub fn find(&self, x: T) -> Option<T>

Find a representative member of the set containing x. If x has not been merged with any other items using merge, returns None. This method does not update the data structure to make future queries faster, so find_mut should be preferred.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
assert_eq!(sets.find(3).unwrap(), sets.find(4).unwrap());
assert_eq!(sets.find(10), None);

pub fn merge(&mut self, x: T, y: T)

Merge the set containing x with the set containing y. This method takes amortized constant time.

pub fn in_same_set(&self, x: T, y: T) -> bool

Returns whether the given items have both been merged into the same set. If either is not part of any set, returns false.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
sets.merge(5, 6);
assert!(sets.in_same_set(2, 3));
assert!(sets.in_same_set(1, 4));
assert!(sets.in_same_set(3, 4));
assert!(!sets.in_same_set(4, 5));

pub fn remove_set_of(&mut self, x: T) -> Vec<T>

where T: Ord,

Remove the set containing the given item, and return all members of that set. The set is returned in sorted order. This method takes time linear in the total size of all sets.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
assert_eq!(sets.remove_set_of(4), &[1, 2, 3, 4]);
assert_eq!(sets.remove_set_of(1), &[]);
assert!(sets.is_empty());

pub fn is_empty(&self) -> bool

Returns true if there are no sets. This method takes constant time.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
assert!(sets.is_empty());
sets.merge(1, 2);
assert!(!sets.is_empty());

pub fn len(&self) -> usize

Returns the total number of elements in all sets. This method takes constant time.

let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
sets.merge(1, 2);
assert_eq!(sets.len(), 2);
sets.merge(3, 4);
sets.merge(3, 5);
assert_eq!(sets.len(), 5);

Trait Implementations

impl<T: Clone> Clone for DisjointSets<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for DisjointSets<T>

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

Formats the value using the given formatter.

impl<T: Default> Default for DisjointSets<T>

fn default() -> DisjointSets<T>

Returns the “default value” for a type.