Struct disjoint_sets::UnionFindNode
[−]
[src]
pub struct UnionFindNode<Data = ()>(_);
Tree-based union-find representing disjoint sets with associated data.
This union-find implementation uses nodes to represent set elements
in a parent-pointer tree. Each set has associated with it an object
of type Data
, which can be looked up and modified via any
representative of the set.
Construct a new singleton set with UnionFindNode::new
.
Examples
As an example, we perform first-order unification using
UnionFindNode
s to represent
unification variables.
use disjoint_sets::UnionFindNode; // A term is either a variable or a function symbol applied to some // terms. #[derive(Clone, Debug, PartialEq, Eq)] enum Term { Variable(String), Constructor { symbol: String, params: Vec<Term>, } } // Syntactic sugar for terms — write them LISP-style: // // A a variable // // (f) a nullary function symbol // // (f A B (g)) function symbol applied to two variables and a // function symbol // // (arrow (tuple (vector A) (int)) A) // type scheme of a polymorphic vector index function // macro_rules! term { ( ( $symbol:ident $($args:tt)* ) ) => { Term::Constructor { symbol: stringify!($symbol).to_owned(), params: vec![ $(term!($args)),* ], } }; ( $symbol:ident ) => { Term::Variable(stringify!($symbol).to_owned()) }; } // Internally we break terms down into variables about which we have // no information, and variables that have unified with a function // symbol applied to other variables. #[derive(Clone, Debug)] enum Term_ { Indeterminate, Fixed { symbol: String, params: Vec<Variable>, }, } type Variable = UnionFindNode<Term_>; // To convert from external `Term`s to internal `Term_`s we use an // environment mapping variable names to their internal // representations as union-find nodes. use std::collections::HashMap; #[derive(Debug)] struct Environment(HashMap<String, Variable>); // The environment can get Rc-cycles in it (because we don’t do an // occurs check, hence terms can be recursive). To avoid leaking, we // need to clear the references out of it. impl Drop for Environment { fn drop(&mut self) { for (_, v) in self.0.drain() { v.replace_data(Term_::Indeterminate); } } } impl Term { // Analyzes an external `Term`, converting it to internal // `Term_`s and returning a variable mapped to it. fn intern(self, env: &mut Environment) -> Variable { match self { Term::Variable(v) => { env.0.entry(v).or_insert_with(|| { UnionFindNode::new(Term_::Indeterminate) }).clone() } Term::Constructor { symbol, params } => { let params = params.into_iter() .map(|term| Term::intern(term, env)) .collect::<Vec<_>>(); UnionFindNode::new(Term_::Fixed { symbol: symbol, params: params, }) }, } } } // A constraint is a collection of variables that need to unify, // along with an environment mapping names to variables. struct Constraint { eqs: Vec<(Variable, Variable)>, env: Environment, } impl Default for Constraint { // Returns the empty (fully solved) constraint. fn default() -> Self { Constraint { env: Environment(HashMap::new()), eqs: Vec::new(), } } } impl Constraint { // Creates a constraint that unifies two terms. fn new(t1: Term, t2: Term) -> Self { let mut new: Constraint = Default::default(); new.push(t1, t2); new } // Adds two additional terms to unify. fn push(&mut self, t1: Term, t2: Term) { let v1 = t1.intern(&mut self.env); let v2 = t2.intern(&mut self.env); self.eqs.push((v1, v2)) } // Performs a single unification step on a pair of variables. // This may result in more equalities to add to the constraint. fn unify(&mut self, mut v1: Variable, mut v2: Variable) -> Result<(), String> { match (v1.clone_data(), v2.clone_data()) { (Term_::Indeterminate, _) => { v1.union_with(&mut v2, |_, t2| t2); Ok(()) }, (_, Term_::Indeterminate) => { v1.union_with(&mut v2, |t1, _| t1); Ok(()) }, (Term_::Fixed { symbol: symbol1, params: params1 }, Term_::Fixed { symbol: symbol2, params: params2 }) => { if symbol1 != symbol2 { let msg = format!( "Could not unify symbols: {} and {}", symbol1, symbol2); return Err(msg); } if params1.len() != params2.len() { let msg = format!( "Arity mismatch: {}: {} != {}", symbol1, params1.len(), params2.len()); return Err(msg); } for (u1, u2) in params1.into_iter() .zip(params2.into_iter()) { self.eqs.push((u1, u2)); } v1.union(&mut v2); Ok(()) } } } // Unifies equalities until there’s nothing left to do. fn solve(mut self) -> Result<Environment, String> { while let Some((v1, v2)) = self.eqs.pop() { try!(self.unify(v1, v2)); } Ok(self.env) } } // Returns whether a pair of terms is unifiable. fn unifiable(t1: Term, t2: Term) -> bool { Constraint::new(t1, t2).solve().is_ok() } fn main() { assert!(unifiable(term![ A ], term![ A ])); assert!(unifiable(term![ A ], term![ B ])); assert!( unifiable(term![ (a) ], term![ (a) ])); assert!(! unifiable(term![ (a) ], term![ (b) ])); assert!( unifiable(term![ (a A) ], term![ (a A) ])); assert!( unifiable(term![ (a A) ], term![ (a B) ])); assert!(! unifiable(term![ (a A) ], term![ (b A) ])); assert!( unifiable(term![ (a A B) ], term![ (a B A) ])); assert!(! unifiable(term![ (a A B C) ], term![ (a B A) ])); assert!( unifiable(term![ (a (b)) ], term![ (a (b)) ])); assert!(! unifiable(term![ (a (b)) ], term![ (a (c)) ])); assert!( unifiable(term![ (a A A) ], term![ (a (b) (b)) ])); assert!(! unifiable(term![ (a A A) ], term![ (a (b) (c)) ])); assert!( unifiable(term![ (a (f) A B C ) ], term![ (a A B C (f)) ])); assert!(! unifiable(term![ (a (f) A B C ) ], term![ (a A B C (g)) ])); assert!( unifiable(term![ (a (f) A B C ) ], term![ (a A D C (g)) ])); }
Methods
impl<Data> UnionFindNode<Data>
[src]
fn new(data: Data) -> Self
Creates a new singleton set with associated data.
Initially this set is disjoint from all other sets, but can
be joined with other sets using union
.
fn union_with<F>(&mut self, other: &mut Self, f: F) -> bool where F: FnOnce(Data, Data) -> Data
Unions two sets, combining their data as specified.
To determine the data associated with the set resulting from a
union, we pass a closure f
, which will be passed self
’s data
and other
’s data (in that order). Then f
must return the data to
associate with the unioned set.
fn union(&mut self, other: &mut Self) -> Option<Data>
Unions two sets.
Retains the data associated with an arbitrary set, returning the
data of the other. Returns None
if self
and other
are
already elements of the same set.
fn find(&self) -> Self
Finds a node representing the set of a given node.
For two nodes in the same set, find
returns the same node.
fn equiv(&self, other: &Self) -> bool
Are the two nodes representatives of the same set?
fn replace_data(&self, new: Data) -> Data
Replaces the data associated with the set.
fn clone_data(&self) -> Data where Data: Clone
Returns a clone of the data associated with the set.
fn with_data<R, F>(&self, f: F) -> R where F: FnOnce(&mut Data) -> R
Allows modifying the data associated with a set.
Trait Implementations
impl<Data> Debug for UnionFindNode<Data>
[src]
impl<Data> PartialEq for UnionFindNode<Data>
[src]
fn eq(&self, other: &UnionFindNode<Data>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0
This method tests for !=
.
impl<Data> Eq for UnionFindNode<Data>
[src]
impl<Data> PartialOrd for UnionFindNode<Data>
[src]
fn partial_cmp(&self, other: &UnionFindNode<Data>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<Data> Ord for UnionFindNode<Data>
[src]
fn cmp(&self, other: &UnionFindNode<Data>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<Data> Hash for UnionFindNode<Data>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
Feeds this value into the state given, updating the hasher as necessary.
fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher
1.3.0
Feeds a slice of this type into the state provided.
impl<Data> Clone for UnionFindNode<Data>
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more