
    <<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>>
        <<>>
    DIRECTORY
        CasabaPlatform USING [ CommandProc, Register ],
        UnionFind USING [ EnumerateSet, Find, GetData, InSameSet, MakeSet, SetElement, Union ],
        UnionFindImpl USING [ SetElement ],
        IO USING [ int, PutF, STREAM ];

    <<Tests Union/Find Algorithms>>
    <<>>
    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"];
            <<>>
            <<UnionFind.DismemberSet[set5];>>

            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];
        }.