TestUnionFindImpl.mesa
-- Last Edited by Field June 27, 1985 12:05:01 pm PDT

Tests Union/Find Algorithms

DIRECTORY

TestUnionFindImpl: CEDAR PROGRAM
IMPORTS UnionFind, Commander, IO

SHARES UnionFindImpl =

BEGIN

DoTest: Commander.CommandProc =
BEGIN

PrintPath: PROC [on: IO.STREAM, properSetElement: UnionFind.SetElement] =
TRUSTED BEGIN
currentElement: UnionFindImpl.SetElement;
setElement: UnionFindImpl.SetElement ← LOOPHOLE[properSetElement];

IO.PutF[on, "Path: "];
FOR currentElement ← setElement, setElement.parent
UNTIL currentElement = currentElement.parent DO
IO.PutF[on, "%g ",
IO.int[(NARROW[UnionFind.GetData[
LOOPHOLE[currentElement, UnionFind.SetElement]], REF INT])^]]

ENDLOOP;
IO.PutF[on, "%g\n",
IO.int[(NARROW[UnionFind.GetData[
LOOPHOLE[currentElement, UnionFind.SetElement]], REF INT])^]];
END;

PrintSet: PROC [on: IO.STREAM, setElement: UnionFind.SetElement] =
BEGIN

canonicalElement: UnionFind.SetElement ← UnionFind.Find[setElement];

IO.PutF[on, "Contents of set, root first:"];
IO.PutF[on, "%g, ",
IO.int[(NARROW[UnionFind.GetData[canonicalElement], REF INT])^]];
FOR currentElement: UnionFind.SetElement ← UnionFind.EnumerateSet[canonicalElement],
UnionFind.EnumerateSet[currentElement] UNTIL currentElement = canonicalElement DO

END;

int1, int2, int3, int4: REF INT;

set1, set2, set3, set4, set5, set6, set7: UnionFind.SetElement;

stdout: IO.STREAM ← cmd.out;

int1 ← NEW[INT ← 1];

int2 ← NEW[INT ← 2];

int3 ← NEW[INT ← 3];

int4 ← NEW[INT ← 4];

set1 ← UnionFind.MakeSet[int1];

set2 ← UnionFind.MakeSet[int2];

set3 ← UnionFind.MakeSet[int3];

set4 ← UnionFind.MakeSet[int4];

IO.PutF[stdout, "set1: %g, set2: %g, set3: %g, set4: %g\n",

set5 ← UnionFind.Union[set1, set2];

IO.PutF[stdout, "Union of 1 and 2, "]; PrintSet[stdout, set5];

IO.PutF[stdout, "After union of set1 and set2: set1: %g, set2: %g, union: %g\n",

IF UnionFind.InSameSet[set1, set5] THEN
IO.PutF[stdout, "set1 and set5 are the same\n"];

IF UnionFind.InSameSet[set2, set5] THEN
IO.PutF[stdout, "set2 and set5 are the same\n"];

IF UnionFind.InSameSet[set1, set2] THEN
IO.PutF[stdout, "set1 and set2 are the same\n"];

-- UnionFind.DismemberSet[set5];

set6 ← UnionFind.Union[set3, set4];

IO.PutF[stdout, "Union of 3 and 4, "]; PrintSet[stdout, set6];

set7 ← UnionFind.Union[set5, set6];

IO.PutF[stdout, "Union of 1, 2, 3 and 4, "]; PrintSet[stdout, set7];

IO.PutF[stdout, "set1: %g, set2: %g, set3: %g, set4: %g, " ,
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set1]], REF INT])^],
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set2]], REF INT])^],
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set3]], REF INT])^],
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set4]], REF INT])^]];

IO.PutF[stdout, "set5: %g, set6: %g, set7: %g\n" ,
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set5]], REF INT])^],
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set6]], REF INT])^],
IO.int[(NARROW[UnionFind.GetData[UnionFind.Find[set7]], REF INT])^]];

IO.PutF[stdout, "set1: "]; PrintPath[stdout, set1];

IO.PutF[stdout, "set2: "]; PrintPath[stdout, set2];

IO.PutF[stdout, "set3: "]; PrintPath[stdout, set3];

IO.PutF[stdout, "set4: "]; PrintPath[stdout, set4];

IO.PutF[stdout, "set5: "]; PrintPath[stdout, set5];

IO.PutF[stdout, "set6: "]; PrintPath[stdout, set6];

IO.PutF[stdout, "set7: "]; PrintPath[stdout, set7];

IO.PutF[stdout, "\n"];

IO.PutF[stdout, "set1: "]; PrintSet[stdout, set1];

IO.PutF[stdout, "set2: "]; PrintSet[stdout, set2];

IO.PutF[stdout, "set3: "]; PrintSet[stdout, set3];

IO.PutF[stdout, "set4: "]; PrintSet[stdout, set4];

IO.PutF[stdout, "set5: "]; PrintSet[stdout, set5];

IO.PutF[stdout, "set6: "]; PrintSet[stdout, set6];

IO.PutF[stdout, "set7: "]; PrintSet[stdout, set7];

END;

Commander.Register["TestUnionFind", DoTest];

END.