Struct cranelift_isle::DisjointSets

source ·

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

Expand description

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§

source §

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

source

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::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);

source

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::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);

source

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.

source

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::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());

source

pub fn is_empty(&self) -> bool

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

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

source

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::default();
sets.merge(1, 2);
assert_eq!(sets.len(), 2);
sets.merge(3, 4);
sets.merge(3, 5);
assert_eq!(sets.len(), 5);