Struct disjoint_sets::UnionFindNode

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 UnionFindNodes 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>

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>

fn fmt(&self, formatter: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<Data> PartialEq for UnionFindNode<Data>

fn eq(&self, other: &UnionFindNode<Data>) -> bool

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

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

This method tests for !=.

impl<Data> Eq for UnionFindNode<Data>

impl<Data> PartialOrd for UnionFindNode<Data>

fn partial_cmp(&self, other: &UnionFindNode<Data>) -> Option<Ordering>

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

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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl<Data> Ord for UnionFindNode<Data>

fn cmp(&self, other: &UnionFindNode<Data>) -> Ordering

This method returns an Ordering between self and other.

impl<Data> Hash for UnionFindNode<Data>

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

Feeds a slice of this type into the state provided.

impl<Data> Clone for UnionFindNode<Data>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Data: Default> Default for UnionFindNode<Data>

fn default() -> Self

Returns the "default value" for a type.