Union-find sets

In union-find-set.diesel:

Union_find_set is a framework for fast union-find data structures, where two union_find_set instances can be merged into a single equivalence class (union_set) and the canonical equivalence class representative can be determined from any member (find_set), in near-linear time. The parameter refers to the specific subclass of union_find_set being manipulated, so that e.g. find_set on a specific subclass returns the same kind of specific subclass rather than a generic union_find_set.

extend module Stdlib;

module UnionFindSet;
abstract class union_find_set[T <= union_find_set[T]]
                                        isa comparable[union_find_set[T]];

find the equivalence class representative

fun find_set(x:`T <= union_find_set[T]):T;

unify two sets

fun union_set(x:`T <= union_find_set[T], y:`T <= union_find_set[T]):T;

when two union_find_sets are merged, the helper function merge_set is called with the chosen representative as the first argument and the other representative as the other argument. subclasses of union_find_set are expected to override this default method if they want to take action when two equivalence classes are merged.

end module UnionFindSet;

In dominant-union-find-set.diesel:

Dominant_union_find_set is a subclass of union_find_set where its instances are known to always become the representative member of the equivalence class.

extend module Stdlib;

module DominantUnionFindSet;
abstract class dominant_union_find_set[T <= union_find_set[T]]
                isa union_find_set[T];

end module DominantUnionFindSet;