Union-find sets

In union-find-set.cecil:

abstract object union_find_set[T <= union_find_set[T]]
                                        isa comparable[union_find_set[T]];
  var field parent(x@:`T <= union_find_set[T]):T;
  var field rank(@:union_find_set[`T]):int;
method union_set(x@:`T <= union_find_set[T],
                        y@:`T <= union_find_set[T]):T;

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.

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. instances of union_find_set are expected to override this default method if they want to take action when two equivalence classes are merged.

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

find the equivalence class representative In dominant-union-find-set.cecil:

abstract object dominant_union_find_set[T <= union_find_set[T]]
                isa union_find_set[T];
method link_set(x@:`T <= dominant_union_find_set[T],
                y@:`T <= union_find_set[T]):T;
method link_set(x@:`T <= union_find_set[T],
                y@:`T <= dominant_union_find_set[T]):T;
method link_set(x@:dominant_union_find_set[`T],
                y@:dominant_union_find_set[`T]):T;

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.