
<<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".
  >>

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.