Crate unionfind

Unionfind

A union find library made for building type inference engines. Can be used as general purpose datastructure.

License

This code is dually licensed under the Apache 2.0 and MIT licences

Usage

Generally, there are two types of union supported by this library.

1. Union by rank: useful if you want to use a union find simply as a disjoint set with logarithmic lookup time
2. Custom unioning: likely what you want when you are, for example, implementing a type checker.

This library abstracts over the backing storage of the union find. There are three options

1. Vec: very fast lookups as long as keys are usize. Other keys are not supported.
2. HashMap: works for any key that implements Hash and Eq
3. BTreeMap: works for any key that implements Ord

Internally, a union find contains one ore more of these datastructures. One if you use custom unioning, and two if you use union by rank (the ranks are stored separately). However, even with custom unioning you could have a second HashMap for custom additional information stored alongside the union find keys, similar to how union by rank works.

Path shortening is optionally performed during find operations by calling find_shorten instead of find. By using find_shorten, subsequent finds become faster than the first. However, an advantage to find is that it does not need mutable access to the datastructure

Modules

• extra
• generic
• mapping
• union

Type Aliases

• BTreeUnionFind
• BTreeUnionFindByRank
• HashUnionFind
• HashUnionFindByRank
• VecUnionFind
• VecUnionFindByRank