Struct disjoint_sets::UnionFindNode

pub struct UnionFindNode<Data = ()>(_);

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

pub 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.

pub 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.

pub 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.

pub 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.

pub fn equiv(&self, other: &Self) -> bool

Are the two nodes representatives of the same set?

pub fn replace_data(&self, new: Data) -> Data

Replaces the data associated with the set.

pub fn clone_data(&self) -> Data where
    Data: Clone, 

Returns a clone of the data associated with the set.

pub 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: Default> Default for UnionFindNode<Data>

fn default() -> UnionFindNode<Data>

Returns the "default value" for a type.

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

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<Data> Hash for UnionFindNode<Data>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].