DIRECTORY CasabaPlatform USING [ CommandProc, Register ], UnionFind USING [ EnumerateSet, Find, GetData, InSameSet, MakeSet, SetElement, Union ], UnionFindImpl USING [ SetElement ], IO USING [ int, PutF, STREAM ]; TestUnionFindImpl: CEDAR PROGRAM IMPORTS IO, UnionFind, CasabaPlatform SHARES UnionFindImpl ~ { DoTest: CasabaPlatform.CommandProc ~ { PrintPath: PROC [ on: IO.STREAM, properSetElement: UnionFind.SetElement ] ~ TRUSTED { currentElement: UnionFindImpl.SetElement; setElement: UnionFindImpl.SetElement _ LOOPHOLE[properSetElement]; on.PutF["Path: "]; FOR currentElement _ setElement, setElement.parent UNTIL ( currentElement = currentElement.parent ) DO on.PutF["%g ", IO.int[(NARROW[UnionFind.GetData[LOOPHOLE[currentElement, UnionFind.SetElement]], REF INT])^]] ENDLOOP; on.PutF["%g\n", IO.int[(NARROW[UnionFind.GetData[ LOOPHOLE[currentElement, UnionFind.SetElement]], REF INT])^]]; }; PrintSet: PROC [on: IO.STREAM, setElement: UnionFind.SetElement] ~ { canonicalElement: UnionFind.SetElement _ UnionFind.Find[setElement]; on.PutF["Contents of set, root first:"]; on.PutF["%g, ", IO.int[(NARROW[UnionFind.GetData[canonicalElement], REF INT])^]]; FOR currentElement: UnionFind.SetElement _ UnionFind.EnumerateSet[canonicalElement], UnionFind.EnumerateSet[currentElement] UNTIL ( currentElement = canonicalElement ) DO on.PutF["%g, ", IO.int[(NARROW[UnionFind.GetData[currentElement], REF INT])^]] ENDLOOP; on.PutF["\n"]; }; int1: REF INT ~ NEW[INT _ 1]; int2: REF INT ~ NEW[INT _ 2]; int3: REF INT ~ NEW[INT _ 3]; int4: REF INT ~ NEW[INT _ 4]; set1: UnionFind.SetElement ~ UnionFind.MakeSet[int1]; set2: UnionFind.SetElement ~ UnionFind.MakeSet[int2]; set3: UnionFind.SetElement ~ UnionFind.MakeSet[int3]; set4: UnionFind.SetElement ~ UnionFind.MakeSet[int4]; set5: UnionFind.SetElement ~ UnionFind.Union[set1, set2]; set6: UnionFind.SetElement ~ UnionFind.Union[set3, set4]; set7: UnionFind.SetElement ~ UnionFind.Union[set5, set6]; stdout: IO.STREAM ~ cmd.out; stdout.PutF["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])^] ]; stdout.PutF["Union of 1 and 2, "]; PrintSet[stdout, set5]; stdout.PutF["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 stdout.PutF["set1 and set5 are the same\n"]; IF ( UnionFind.InSameSet[set2, set5] ) THEN stdout.PutF["set2 and set5 are the same\n"]; IF ( UnionFind.InSameSet[set1, set2] ) THEN stdout.PutF["set1 and set2 are the same\n"]; stdout.PutF["Union of 3 and 4, "]; PrintSet[stdout, set6]; stdout.PutF["Union of 1, 2, 3 and 4, "]; PrintSet[stdout, set7]; stdout.PutF["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])^] ]; stdout.PutF["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])^] ]; stdout.PutF["set1: "]; PrintPath[stdout, set1]; stdout.PutF["set2: "]; PrintPath[stdout, set2]; stdout.PutF["set3: "]; PrintPath[stdout, set3]; stdout.PutF["set4: "]; PrintPath[stdout, set4]; stdout.PutF["set5: "]; PrintPath[stdout, set5]; stdout.PutF["set6: "]; PrintPath[stdout, set6]; stdout.PutF["set7: "]; PrintPath[stdout, set7]; stdout.PutF["\n"]; stdout.PutF["set1: "]; PrintSet[stdout, set1]; stdout.PutF["set2: "]; PrintSet[stdout, set2]; stdout.PutF["set3: "]; PrintSet[stdout, set3]; stdout.PutF["set4: "]; PrintSet[stdout, set4]; stdout.PutF["set5: "]; PrintSet[stdout, set5]; stdout.PutF["set6: "]; PrintSet[stdout, set6]; stdout.PutF["set7: "]; PrintSet[stdout, set7]; }; CasabaPlatform.Register["TestUnionFind", DoTest]; }. TestUnionFindImpl.Mesa Copyright Ó 1988 by Xerox Corporation. All rights reserved. Sturgis, May 19, 1986 3:09:09 pm PDT Field June 27, 1985 12:05:01 pm PDT Bill Jackson (bj) June 2, 1988 3:25:42 am PDT Tests Union/Find Algorithms UnionFind.DismemberSet[set5]; Ê?˜codešœ™Kšœ<™Kšœ˜K˜—šžœœœœ'˜DK˜DKšœ(˜(Kš œœœ&œœ˜Qšœyœ'˜ªKš œœœ$œœ˜NKšœ˜—Kšœ˜Kšœ˜K˜—Kš œœœœœ˜Kš œœœœœ˜Kš œœœœœ˜Kš œœœœœ˜K˜K˜5K˜5K˜5K˜5K˜9K˜9K˜9K˜Kšœœœ ˜K˜Kš!œ8œœœœœœœœœœœœœœœœ˜ŽK˜Kšœ:˜:K˜KšœMœœ*œœœœ*œœœœ*œœ˜žK˜Kšœ%œ-˜XKšœ%œ-˜XKšœ%œ-˜XK™Kšœ™K˜Kšœ:˜:Kšœ@˜@K˜š!œ8œœ*œœœœ*œœœœ*œœœœ*œœ˜ÎK˜—Kšœ.œœ*œœœœ*œœœœ*œœ˜ÿK˜Kšœ0˜0Kšœ0˜0Kšœ0˜0Kšœ0˜0Kšœ0˜0Kšœ0˜0Kšœ0˜0Kšœ˜Kšœ/˜/Kšœ/˜/Kšœ/˜/Kšœ/˜/Kšœ/˜/Kšœ/˜/Kšœ/˜/Kšœ˜K˜—Kšœ1˜1Kšœ˜K˜——…—üI