Struct lattices::union_find::UnionFind

pub struct UnionFind<Map>(/* private fields */);

Union-find lattice.

Each value of K in the map represents an item in a set. When two lattices instances are merged, any sets with common elements will be unioned together.

[Self::union(a, b)] unions two sets together, which is equivalent to merging in a UnionFindSingletonMap atom of (a, b) (or (b, a)).

Any union-find consisting only of singleton sets is bottom.

Hasse diagram of partitions of a set of size four:

Implementations

impl<Map> UnionFind<Map>

pub fn new(val: Map) -> Self

Create a new UnionFind from a Map.

pub fn new_from(val: impl Into<Map>) -> Self

Create a new UnionFind from an Into<Map>.

pub fn as_reveal_ref(&self) -> &Map

Reveal the inner value as a shared reference.

pub fn as_reveal_mut(&mut self) -> &mut Map

Reveal the inner value as an exclusive reference.

pub fn into_reveal(self) -> Map

Gets the inner by value, consuming self.

impl<Map, K> UnionFind<Map>

where Map: MapMut<K, Cell<K>, Key = K, Item = Cell<K>>, K: Copy + Eq,

pub fn union(&mut self, a: K, b: K) -> Min<bool>

Union the sets containg a and b.

Returns true if the sets changed, false if a and b were already in the same set. Once this returns false it will always return false for the same a and b, therefore it returns a Min<bool> lattice.

impl<MapSelf, K> UnionFind<MapSelf>

where MapSelf: Map<K, Cell<K>, Key = K, Item = Cell<K>>, K: Copy + Eq,

pub fn same(&self, a: K, b: K) -> Max<bool>

Returns if a and b are in the same set.

This method is monotonic: once this returns true it will always return true for the same a and b, therefore it returns a Max<bool> lattice.

Trait Implementations

impl<Map, K> Atomize for UnionFind<Map>

where Map: 'static + MapMut<K, Cell<K>, Key = K, Item = Cell<K>> + IntoIterator<Item = (K, Cell<K>)>, K: 'static + Copy + Eq,

type Atom = UnionFind<SingletonMap<K, Cell<K>>>

The type of atoms for this lattice.

type AtomIter = Box<dyn Iterator<Item = <UnionFind<Map> as Atomize>::Atom>>

The iter type iterating the antichain atoms.

fn atomize(self) -> Self::AtomIter

Atomize self: convert into an iter of atoms.

impl<Map: Clone> Clone for UnionFind<Map>

fn clone(&self) -> UnionFind<Map>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Map: Debug> Debug for UnionFind<Map>

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

Formats the value using the given formatter.

impl<Map> DeepReveal for UnionFind<Map>

type Revealed = Map

The underlying type when revealed.

fn deep_reveal(self) -> Self::Revealed

Reveals the underlying lattice types recursively.

impl<Map: Default> Default for UnionFind<Map>

fn default() -> UnionFind<Map>

Returns the “default value” for a type.

impl<'de, Map> Deserialize<'de> for UnionFind<Map>

where Map: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<Map, K> IsBot for UnionFind<Map>

where Map: MapIter<Key = K, Item = Cell<K>>, K: Copy + Eq,

fn is_bot(&self) -> bool

Returns if self is lattice bottom (⊥).

impl<Map> IsTop for UnionFind<Map>

fn is_top(&self) -> bool

Returns if self is lattice top (⊤).

impl<MapSelf, MapOther, K> LatticeFrom<UnionFind<MapOther>> for UnionFind<MapSelf>

where MapSelf: Keyed<Key = K, Item = Cell<K>> + FromIterator<(K, Cell<K>)>, MapOther: IntoIterator<Item = (K, Cell<K>)>, K: Copy + Eq,

fn lattice_from(other: UnionFind<MapOther>) -> Self

Convert from the Other lattice into Self.

impl<MapSelf, MapOther, K> Merge<UnionFind<MapOther>> for UnionFind<MapSelf>

where MapSelf: MapMut<K, Cell<K>, Key = K, Item = Cell<K>>, MapOther: IntoIterator<Item = (K, Cell<K>)>, K: Copy + Eq,

fn merge(&mut self, other: UnionFind<MapOther>) -> bool

Merge other into the self lattice.

fn merge_owned(this: Self, delta: Other) -> Self

where Self: Sized,

Merge this and delta together, returning the new value.

impl<MapSelf, MapOther, K> PartialEq<UnionFind<MapOther>> for UnionFind<MapSelf>

where MapSelf: MapMut<K, Cell<K>, Key = K, Item = Cell<K>> + MapIter, MapOther: MapMut<K, Cell<K>, Key = K, Item = Cell<K>> + MapIter, K: Copy + Eq,

fn eq(&self, other: &UnionFind<MapOther>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<MapSelf, MapOther, K> PartialOrd<UnionFind<MapOther>> for UnionFind<MapSelf>

where MapSelf: MapMut<K, Cell<K>, Key = K, Item = Cell<K>> + MapIter, MapOther: MapMut<K, Cell<K>, Key = K, Item = Cell<K>> + MapIter, K: Copy + Eq,

fn partial_cmp(&self, other: &UnionFind<MapOther>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<Map> Serialize for UnionFind<Map>

where Map: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<Map: Copy> Copy for UnionFind<Map>

impl<Map> Eq for UnionFind<Map>

where Self: PartialEq,

impl<MapSelf, MapOther> LatticeOrd<UnionFind<MapOther>> for UnionFind<MapSelf>

where Self: PartialOrd<UnionFind<MapOther>>,