UnionFindImpl:
CEDAR
PROGRAM
EXPORTS UnionFind =
BEGIN
SetElementObj:
PUBLIC
TYPE =
RECORD
[elementData: REF ANY ← NIL, -- pointer to data to be associated with this element
parent: SetElement ← NIL,
-- Pointer to parent in set data structure. If it points to itself, this element is the
-- canonical element of its containing set.
nextElement: SetElement ← NIL,
prevElement: SetElement ← NIL,
-- Pointers to next and previous elements in a doubly linked circular list of elements
-- in the same set. Members of singleton sets have pointers to themselves. Note that
-- this list is completely independent of the tree structure used by the algorithm. A
-- doubly linked list of all elements is overkill, but is simple to use.
rank: NAT ← 0, -- upper bound on depth of subtree rooted at this element
isDismembered: BOOLEAN ← FALSE
-- TRUE if this is a canonical element and its root pointer has been "unlatched"
-- to facilitate garbage collection. Effectively marks the set as "destroyed"
];
SetElement: TYPE = REF SetElementObj;
SetIsDismembered: PUBLIC ERROR = CODE;
MakeSet:
PUBLIC
PROC [data:
REF
ANY]
RETURNS [newSetElement: SetElement] =
BEGIN
newSetElement ← NEW[SetElementObj ← [elementData: data]];
newSetElement.parent ← newSetElement;
newSetElement.nextElement ← newSetElement;
newSetElement.prevElement ← newSetElement
END;
Find:
PUBLIC
PROC [setElement: SetElement]
RETURNS [canonicalElement: SetElement] =
BEGIN
currentElement: SetElement; -- used to walk up tree
nextElementToUnlink: SetElement;
-- next element whose path to the root is to be compressed
IF setElement = NIL THEN RETURN [canonicalElement: NIL];
-- Check given element for validity
IF setElement.isDismembered THEN ERROR SetIsDismembered;
First find canonical element at root of tree
FOR currentElement ← setElement, currentElement.parent
UNTIL currentElement = currentElement.parent
DO
NULL;
ENDLOOP;
canonicalElement ← currentElement;
Now go back and perform path compression on all elements on path to root
nextElementToUnlink ← setElement;
FOR currentElement ← setElement, currentElement.parent
UNTIL currentElement = currentElement.parent
DO
nextElementToUnlink.parent ← canonicalElement;
nextElementToUnlink ← currentElement.parent
ENDLOOP;
Note that there is no need in a find to change "nextElement" pointers.
RETURN[canonicalElement];
END;
Union:
PUBLIC
PROC [setElement1, setElement2: SetElement]
RETURNS [newCanonicalElement: SetElement] =
BEGIN
Find canonical elements of containing sets ("Find" also checks sets for validity)
canonicalElement1: SetElement ← Find[setElement: setElement1];
canonicalElement2: SetElement ← Find[setElement: setElement2];
tempElement1: SetElement ← canonicalElement1.prevElement;
tempElement2: SetElement ← canonicalElement2.nextElement;
Make sure sets are disjoint and non-null, if not, we're done
IF canonicalElement1 = NIL THEN
RETURN [newCanonicalElement: canonicalElement2]
ELSE IF (canonicalElement2 = NIL) OR (canonicalElement1 = canonicalElement2) THEN
RETURN [newCanonicalElement: canonicalElement1];
-- First join circular lists of set elements, ignoring tree structure
canonicalElement1.prevElement ← canonicalElement2;
canonicalElement2.nextElement ← canonicalElement1;
tempElement1.nextElement ← tempElement2;
tempElement2.prevElement ← tempElement1;
Perform union by rank
IF canonicalElement1.rank > canonicalElement2.rank
THEN
BEGIN
newCanonicalElement ← canonicalElement1;
canonicalElement2.parent ← newCanonicalElement
END
ELSE
-- canonicalElement1.rank < canonicalElement2.rank or they have the same rank
BEGIN
newCanonicalElement ← canonicalElement2;
canonicalElement1.parent ← newCanonicalElement;
Update rank of new set if necessary
IF canonicalElement1.rank = canonicalElement2.rank
THEN
newCanonicalElement.rank ← newCanonicalElement.rank + 1
END;
RETURN[newCanonicalElement]
END;
GetData:
PUBLIC
PROC [setElement: SetElement]
RETURNS [data:
REF
ANY] =
BEGIN
Check given element for validity
IF setElement = NIL THEN RETURN [data: NIL];
IF setElement.isDismembered THEN ERROR SetIsDismembered;
RETURN[data: setElement.elementData]
END;
InSameSet:
PUBLIC
PROC [setElement1, setElement2: SetElement]
RETURNS [equal:
BOOLEAN] =
BEGIN
Find canonical elements of containing sets ("Find" also checks sets for validity)
canonicalElement1: SetElement ← Find[setElement: setElement1];
canonicalElement2: SetElement ← Find[setElement: setElement2];
RETURN[equal: (canonicalElement1 = canonicalElement2)]
END;
EnumerateSet:
PUBLIC
PROC [lastElement: SetElement]
RETURNS [nextElement: SetElement] =
BEGIN
IF lastElement = NIL THEN RETURN [nextElement: NIL];
Check given element for validity
IF lastElement.isDismembered THEN ERROR SetIsDismembered;
RETURN[nextElement: lastElement.nextElement]
END;
DismemberSet:
PUBLIC
PROC [setElement: SetElement] =
BEGIN
currentElement: SetElement; -- used to walk through list of set elements
-- Find canonical element of set ("Find" checks set to see if previously dismembered);
canonicalElement: SetElement ← Find[setElement];
-- IF set is null, it is already "dismembered"
IF setElement = NIL THEN RETURN;
-- Mark all elements in set as dismembered
FOR currentElement ← canonicalElement, currentElement.nextElement
UNTIL currentElement.nextElement = canonicalElement
DO
currentElement.isDismembered ← TRUE
ENDLOOP;
currentElement.nextElement.isDismembered ← TRUE; -- get last element on list
Now break pointer loops to facilitate garbage collection
canonicalElement.parent ← NIL;
canonicalElement.nextElement ← NIL;
canonicalElement.prevElement ← NIL
END;
END.