Copyright (C) 1992, Digital Equipment Corporation
All rights reserved.
See the file COPYRIGHT for a full description.
Last modified on Mon Oct 31 09:34:02 PST 1994 by heydon
MODULE Equiv;
This implementation of disjoint sets uses the quick-find algorithm,
in which all trees have depth at most 1. Hence, the Find operation
takes constant time, but the Union operation takes time
proportional to the size of the smaller set being merged.
REVEAL
T = Public BRANDED "EquivQuickFind.T" OBJECT
size: CARDINAL;
link: T;
OVERRIDES
init := Init;
union := Union;
END;
PROCEDURE Init(self: T): T =
BEGIN
self.root := self;
self.size := 1;
self.link := self;
RETURN self
END Init;
PROCEDURE Union(x: T; y: T): T =
BEGIN
<* ASSERT x.root = x AND y.root = y *>
IF x = y THEN RETURN x END;
IF x.size < y.size THEN
VAR t := x; BEGIN x := y; y := t; END
END;
VAR p := y; BEGIN
REPEAT
p.root := x;
p := p.link
UNTIL p = y
END;
VAR t := y.link; BEGIN y.link := x.link; x.link := t END;
INC(x.size, y.size);
RETURN x
END Union;
BEGIN
END Equiv.