<> <> DIRECTORY UnionFind; 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 the root pointer of containing set 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; <> FOR currentElement _ setElement, currentElement.parent UNTIL currentElement = currentElement.parent DO NULL; ENDLOOP; canonicalElement _ currentElement; <> nextElementToUnlink _ setElement; FOR currentElement _ setElement, currentElement.parent UNTIL currentElement = currentElement.parent DO nextElementToUnlink.parent _ canonicalElement; nextElementToUnlink _ currentElement.parent ENDLOOP; <> RETURN[canonicalElement]; END; Union: PUBLIC PROC [setElement1, setElement2: SetElement] RETURNS [newCanonicalElement: SetElement] = BEGIN <> canonicalElement1: SetElement _ Find[setElement: setElement1]; canonicalElement2: SetElement _ Find[setElement: setElement2]; tempElement1: SetElement _ canonicalElement1.prevElement; tempElement2: SetElement _ canonicalElement2.nextElement; <> 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; <> 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; <> 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 <> 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 <> 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]; <> 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 canonicalElement: SetElement; -- is it already "dismembered" ? IF setElement = NIL OR setElement.isDismembered THEN RETURN; canonicalElement _ Find[setElement]; <<-- Mark all elements in set as dismembered>> currentElement _ canonicalElement; currentElement.isDismembered _ TRUE; currentElement _ currentElement.nextElement; WHILE currentElement # canonicalElement DO currentElement.isDismembered _ TRUE; currentElement _ currentElement.nextElement; ENDLOOP; <> canonicalElement.parent _ NIL; canonicalElement.nextElement _ NIL; canonicalElement.prevElement _ NIL END; END.