-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--DOC

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

--)

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 := x;
  var field rank(@:union_find_set[`T]):int := 0;

public method union_set(x@:`T <= union_find_set[T],
			y@:`T <= union_find_set[T]):T {
    let xr := x.find_set;
    let yr := y.find_set;
    if(xr = yr, {
	-- already in same equivalence class
	xr
    }, {
	-- merge equivalence classes
	link_set(xr, yr)
    }) }

-- here, x and y are assumed to be ec representatives
private method link_set(x@:`T <= union_find_set[T],
			y@:`T <= union_find_set[T]):T {
    if(x.rank > y.rank, {
	y.parent := x;
	merge_set(x, y);
	x
    }, {
	x.parent := y;
	if(x.rank = y.rank, {
	    y.rank := y.rank + 1;
	});
	merge_set(y, x);
	y
    }) }

--DOC when two union_find_sets are merged, the helper function `merge_set' is
--DOC called with the chosen representative as the first argument and the other
--DOC representative as the other argument.  instances of union_find_set are
--DOC expected to override this default method if they want to take action when
--DOC two equivalence classes are merged.
private method merge_set(new_representative@:`T <= union_find_set[T],
			 other_representative@:`T <= union_find_set[T]):void {
    -- default to doing nothing
}

--DOC find the equivalence class representative
public method find_set(x@:`T <= union_find_set[T]):T {
    if_false(x = x.parent, {
	x.parent := find_set(x.parent);
    });
    x.parent }