Union-find implementation. The main type is
You can define your own type for the keys in the table, but you
UnifyKey for that type. The assumption is that
keys will be newtyped integers, hence we require that they
Keys can have values associated with them. The assumption is that
these values are cheaply cloneable (ideally,
Copy), and some of
the interfaces are oriented around that assumption. If you just
want the classical “union-find” algorithm where you group things
into sets, use the
Value type of
When you have keys with non-trivial values, you must also define
how those values can be merged. As part of doing this, you can
define the “error” type to return on error; if errors are not
NoError (an uninstantiable struct). Using this
type also unlocks various more ergonomic methods (e.g.,
in place of
The best way to see how it is used is to read the
search for e.g.
- Backing store for an in-place unification table. Not typically used directly.
- A struct which can never be instantiated. Used for the error type for infallible cases.
- At any time, users may snapshot a unification table. The changes made during the snapshot may either be committed or rolled back.
- Table of unification keys and their values. You must define a key type K that implements the
UnifyKeytrait. Unification tables can be used in two-modes:
- Value of a unification key. We implement Tarjan’s union-find algorithm: when two keys are unified, one of them is converted into a “redirect” pointing at the other. These redirects form a DAG: the roots of the DAG (nodes that are not redirected) are each associated with a value of type
Vand a rank. The rank is used to keep the DAG relatively balanced, which helps keep the running time of the algorithm under control. For more information, see http://en.wikipedia.org/wiki/Disjoint-set_data_structure.
- A convenient helper for unification values which must be equal or else an error occurs. For example, if you are unifying types in a simple functional language, this may be appropriate, since (e.g.) you can’t unify a type variable bound to
intwith one bound to
float(but you can unify two type variables both bound to
- Largely internal trait implemented by the unification table backing store types. The most common such type is
InPlace, which indicates a standard, mutable unification table.
- This trait is implemented by any type that can serve as a type variable. We call such variables unification keys. For example, this trait is implemented by
IntVid, which represents integral variables.
- Trait implemented for values associated with a unification key. This trait defines how to merge the values from two keys that are unioned together. This merging can be fallible. If you attempt to union two keys whose values cannot be merged, then the error is propagated up and the two keys are not unioned.
- A unification table that uses an “in-place” vector.