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]; 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]; 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]; 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. PUnionFindImpl.mesa -- Last Edited by Field August 8, 1985 9:57:58 am PDT Implements UnionFind -- Check given element for validity First find canonical element at root of tree Now go back and perform path compression on all elements on path to root Note that there is no need in a find to change "nextElement" pointers. Find canonical elements of containing sets ("Find" also checks sets for validity) Make sure sets are disjoint and non-null, if not, we're done -- First join circular lists of set elements, ignoring tree structure Perform union by rank Update rank of new set if necessary Check given element for validity Find canonical elements of containing sets ("Find" also checks sets for validity) Check given element for validity -- Mark all elements in set as dismembered Now break pointer loops to facilitate garbage collection ÊQ˜JšœI™IJšœ™šÏk ˜ Jšœ ˜ —šœœœœ ˜1Jš˜šœœœ˜#JšœœœœÏc5˜SJšœœž…˜žJšœœ˜JšœœžÍ˜ìJšœœž9˜IJšœœž’˜°Jšœ˜—Jšœ œœ˜&Jšœœœœ˜'š Ïnœœœœœœ˜JJš˜Jšœœ&˜9Jšœ%˜%J˜*J˜)Jšœ˜—šŸœœœœ!˜SJš˜Jšœž˜4Jšœ#ž;˜^J˜9Jšœ#™#Jšœœœ˜:Jšœ,™,šœ4œ(˜fJšœ˜—Jšœ˜J˜#JšœH™HJ˜!šœ4œ(˜fJ˜.J˜+—Jšœ˜ JšœF™FJšœ˜Jšœ˜—šŸœœœ(œ$˜eJš˜JšœQ™QJ˜>J˜>J˜9J˜:Jšœ<™<šœ˜Jšœ/˜/—šœQ˜QJšœ+˜1—J™EJ˜2J˜2J˜(J˜(J˜Jšœ™šœ1˜7Jš˜J˜(J˜.Jš˜—šœžM˜SJš˜J˜(J˜/Jšœ#™#šœ1˜7J˜7—Jšœ˜—Jšœ˜Jšœ˜—š Ÿœœœœœœ˜GJš˜Jšœ ™ J˜,Jšœœœ˜9Jšœ˜$Jšœ˜—š Ÿ œœœ(œ œ˜XJš˜JšœQ™QJ˜>J˜?Jšœ0˜6Jšœ˜—šŸ œœœœ˜WJš˜Jšœ5˜5Jšœ ™ Jšœœœ˜:Jšœ&˜,Jšœ˜—šŸ œœœ˜4Jš˜Jšœž,˜IJšœ˜J˜J˜ J˜