DIRECTORY UnionFind USING [SetElement, MakeSet, Find, Union, GetData, InSameSet, EnumerateSet--, DismemberSet--], UnionFindImpl USING [SetElement], Commander USING [Register, CommandProc], IO USING [int, PutF, STREAM]; 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 IO.PutF[on, "%g, ", IO.int[(NARROW[UnionFind.GetData[currentElement], REF INT])^]] ENDLOOP; IO.PutF[on, "\n"]; 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", IO.int[(NARROW[UnionFind.GetData[set1], REF INT])^], IO.int[(NARROW[UnionFind.GetData[set2], REF INT])^], IO.int[(NARROW[UnionFind.GetData[set3], REF INT])^], IO.int[(NARROW[UnionFind.GetData[set4], REF INT])^]]; 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", 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[set5]], REF INT])^]]; 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. ЦTestUnionFindImpl.mesa -- Last Edited by Field June 27, 1985 12:05:01 pm PDT Tests Union/Find Algorithms Sturgis, May 19, 1986 3:09:09 pm PDT Э╩ШJЪЬMЩMЪЬЩIcodeЩ$ЧJШЪ╧k Ш JЪЬ ЭЬXШgJЪЬЭЬШ!JЪЬ ЭЬШ(JЪЭЬЭЬ ЭЬШJШЧJЪЬЭЬЭЬЭЬЭШAJЪЬЭЬШJЪЭШJШJЪ%Ь ЭЬ╧n ЬЭЬЭЬЭЬ.ЭЬЭЬVЭЬЭЬЭЬ5ЭЬ(ЭЬЭЬЭЬЭЬ ЭЬ)ЭЬЭЬШЮJЪЬЭЬЭЬЭЬЭЬЭЬ)ЭЬЭЬЭЬШЫJЪ ЮЬЭЬЭЬЭЬ(ЭШJЪЬMЭЬ-ЭЬЭЬЭЬ&ЭЬЭЬЭЬ}ЭЬ#ЭШЗJЪЬЭЬЭЬЭЬ$ЭЬЭЬШbJЪЭЬШJШЧJЪЭЬШJЪЬШJЪЬЭЬЭЬШ!JШ?JЪЬЭЬЭЬШJЪЬЭЬЭЬШJЪЬЭЬЭЬШJЪЬЭЬЭЬШJЪЬЭЬЭЬШJШJШJШJШJШ ЪЭЬ:ШЪЬЭЬOШRJЪЭЬЭЬ*ЭЬЭЬШDJЪЭЬЭЬ*ЭЬЭЬШDJЪЭЬЭЬ*ЭЬЭЬШFЧJЪЭЬ!ЭЬЭЬ.ШXJШJЪЭЬ!ЭЬЭЬ.ШXJШJЪЭЬ!ЭЬЭЬ.ШXJШ JШJШ#JШ>JШ#JШEJЪ"ЭЬ<ЭЬЭЬ*ЭЬЭЬЭЬЭЬ*ЭЬЭЬЭЬЭЬ*ЭЬЭЬЭЬЭЬ*ЭЬЭЬШ╫JЪЭЬ2ЭЬЭЬ*ЭЬЭЬЭЬЭЬ*ЭЬЭЬЭЬЭЬ*ЭЬЭЬШЕJШJЪЭЬ2Ш4JЪЭЬ2Ш4JЪЭЬ2Ш4JЪЭЬ2Ш4JЪЭЬ2Ш4JЪЭЬ2Ш4JЪЭЬ2Ш4JЪЬШJЪЭЬ1Ш3JЪЭЬ1Ш3JЪЭЬ1Ш3JЪЭЬ1Ш3JЪЭЬ1Ш3JЪЭЬ1Ш3JЪЭЬ2Ш4JЪЭЬШJШ,JШJЪЭЬШKЩЧЕЧ╨Г