UnionFind: CEDAR DEFINITIONS = BEGIN SetElementObj: TYPE; -- Opaque type for a set element object. SetElement: TYPE = REF SetElementObj; SetIsDismembered: ERROR; -- Is raised if any attempt is made to perform an operation on a set that has been effectively -- destroyed by "DismemberSet," below. MakeSet: PROC [data: REF ANY] RETURNS [newSetElement: SetElement]; -- Given "data," constructs and returns a new set element representing a singleton set -- containing the data. Find: PROC [setElement: SetElement] RETURNS [canonicalElement: SetElement]; -- Given a set element, returns the canonical element of the set containing the given element. -- Returns NIL if "setElement" is NIL. (! SetIsDismembered) Union: PROC [setElement1, setElement2: SetElement] RETURNS [newCanonicalElement: SetElement]; -- Given two set elements, constructs the union set of their respective containing sets and -- returns the canonical element of the union set. The original sets are effectively destroyed -- by this process. Note that the given set elements need not be the canonical elements of -- their containing sets. If both the given elements are contained in the same -- set or if exactly one of the elements is NIL, the canonical element of the containing set is -- returned. If both elements are NIL, NIL is returned. (! SetIsDismembered) GetData: PROC [setElement: SetElement] RETURNS [data: REF ANY]; -- Given a set elements, returns the corresponding data item. Returns NIL if -- "setElement" is NIL. (! SetIsDismembered) InSameSet: PROC [setElement1, setElement2: SetElement] RETURNS [equal: BOOLEAN]; -- Given two set elements, returns TRUE if they are in the same set, FALSE otherwise. -- (! SetIsDismembered) EnumerateSet: PROC [lastElement: SetElement] RETURNS [nextElement: SetElement]; -- A "stateless enumerator" of set elements. The elements of a set can be thought of as -- stored in a circular list. Given one set element ("lastElement"), the procedure allows the -- next one in the same set to be located ("nextElement"). Any set element will do as -- a starting point, it need not be a canonical element. When the initial element in the -- enumeration is returned as "nextElement," the enumeration is complete. The order in -- which elements are enumerated is effectively random. Returns NIL if "lastELement" -- is NIL. (! SetIsDismembered) DismemberSet: PROC [setElement: SetElement]; -- Given a set element, effectively destroys its containing set by arranging its data structure -- so that it may be recovered by the garbage collector. The data structure is marked in -- such a way that any inadvertent reference to the "dismembered" set will cause the -- !SetIsDismembered SIGNAL to be raised. (! SetIsDismembered) END. âUnionFind.mesa -- Last Edited by Field August 8, 1985 9:58:40 am PDT Implements Set Union and Find (member) operations using Tarjan's almost linear algorithms -- (use "union by rank" and "path compression" heuristics). Each set element is a dynamically -- allocated object with which data may be associated. A set is represented by a canonical -- element in that set, thus in some cases, "set" and "element" may be synonymous. The null -- set is represented by "NIL". Ê3˜JšœE™EJšœ”™”J˜šœ Ïkœ œœ˜%JšœœÏc(˜=Jšœ œœ˜(Jšœœž†˜ŸJš Ïnœœœœœžoœ˜´JšŸœœœ!žœ˜èJš Ÿœœ(œ$žÇœžPœ˜÷Jš Ÿœœœœœž|œ˜½Jš Ÿ œœ(œ œžn˜¿JšŸ œœœžYœž_œžWœžZœžÑœ˜JšŸ œœžÏ˜ü—Jšœ˜—…— Ö ë