
    <<LichenDataImpl1A.Mesa>>
        <<Last tweaked by Mike Spreitzer on May 4, 1988 6:36:28 pm PDT>>

    DIRECTORY AbSets, AMBridge, BasicTime, BiRels, Convert, FS, Interpreter, InterpreterOps, IntStuff, IO, LichenDataOps, 
    LichenDataStructure, LichenIntBasics, List, ProcessProps, Rope, RopeHash, SetBasics, SymTab;

    LichenDataImpl1A: CEDAR PROGRAM
        IMPORTS AbSets, AMBridge, BiRels, Convert, FS, InterpreterOps, IntStuff, IO, LichenDataOps, LichenDataStructure, List, 
        ProcessProps, Rope, RopeHash, SetBasics, SymTab
        EXPORTS LichenIntBasics, LichenDataStructure
        =

    BEGIN OPEN IB:LichenIntBasics, IB, LichenDataStructure, LichenDataOps, Sets:AbSets;

    nyet: PUBLIC ERROR ~ CODE;

    Warning: PUBLIC SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] ~ CODE;

    Error: PUBLIC ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL] ~ CODE;

    PartClassName: PUBLIC ARRAY PartClass OF ROPE _ [
        p: "port",
        w: "wire",
        i: "cell instance"];

    Range2Div: PUBLIC PROC [r: Range2, 
        rr _ [
            X: [
                min: CeilDiv[r[X].min-
                maxPlusOne: FloorDiv[r[X].maxPlusOne-1-
            Y: [
                min: CeilDiv[r[Y].min-
                maxPlusOne: FloorDiv[r[Y].maxPlusOne-1-
        };

    Range1Div: PUBLIC PROC [r: Range, 
        rr _ [
            min: CeilDiv[r.min-
            maxPlusOne: FloorDiv[r.maxPlusOne-1-
        };

    Range2MulA: PUBLIC PROC [r: Range2, 
        rr _ [
            X: [
                min: r[X].min*
                maxPlusOne: (r[X].maxPlusOne-1)*
            Y: [
                min: r[Y].min*
                maxPlusOne: (r[Y].maxPlusOne-1)*
        };

    Range2MulB: PUBLIC PROC [r: Range2, 
        rr _ [
            X: [
                min: r[X].min*
                maxPlusOne: r[X].maxPlusOne*
            Y: [
                min: r[Y].min*
                maxPlusOne: r[Y].maxPlusOne*
        };

    Range1MulB: PUBLIC PROC [r: Range, 
        rr _ [
            min: r.min*
            maxPlusOne: r.maxPlusOne*
        };

    ACtName: PUBLIC PROC [ct: CellType] RETURNS [ROPE] ~ {
        RETURN [NARROW[ct.d.ctName.Lookup[goal: AV[ct], side: left, order: Sets.alleq].MDA]]};

    BestPName: PUBLIC PROC [ct: CellType, p: Port] RETURNS [SteppyName] ~ {
        RETURN [VSn[ct.fullName[p].Lookup[goal: AV[p], side: left].Val]]};

    BestWName: PUBLIC PROC [ct: CellType, w: Wire] RETURNS [SteppyName] ~ {
        RETURN [VSn[ct.fullName[w].Lookup[goal: AV[w], side: left].Val]]};

    BestIName: PUBLIC PROC [ct: CellType, ci: CellInstance] RETURNS [SteppyName] ~ {
        RETURN [VSn[ct.fullName[i].Lookup[goal: AV[ci], side: left].Val]]};

    DimName: ARRAY Dim2 OF ROPE = [X: "X", Y: "Y"];

    Describe: PUBLIC PROC [d: Design, subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [name: ROPE] = 
    {
        name _ UnparseSteppyName[SteppyDescribe[d, subject, relativeTo, nameGen]];
        RETURN};

    SteppyDescribe: PUBLIC PROC [d: Design, subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [name: 
    SteppyName] = {
        IF nameGen = NIL THEN nameGen _ defaultNameGen;
        IF subject = relativeTo THEN name _ noName ELSE WITH subject SELECT FROM
            sd: Design => {
                short: ROPE _ NARROW[sd.names.AnElt[].MDA];
                IF short=NIL THEN {
                    short _ nameGen.GenerateName[nameGen.data, subject];
                    IF NOT sd.names.AddA[short] THEN ERROR};
                name _ OSn[short];
                RETURN};
            ct: CellType => {
                short: ROPE _ ACtName[ct];
                IF short=NIL THEN {
                    short _ nameGen.GenerateName[nameGen.data, subject];
                    d.ctName.AddNewAA[ct, short]};
                name _ OSn[short];
                IF NOT d.cellTypes.HasMemA[ct] THEN ERROR;
                name _ SNCat[SteppyDescribe[d, d, relativeTo, nameGen], name];
                RETURN};
            v: Vertex => {
                cct: CellType ~ d.VCct[v];
                WITH relativeTo SELECT FROM
                    aw: Wire => {w: Wire ~ NARROW[v];
                        IF NOT PWIsAncestor[d, aw, w] THEN ERROR;
                        {msn: MaybeSteppyName ~ ScanRelativeNames[cct, w, aw, w, AcceptAnySteppyName];
                        IF NOT msn.found THEN ERROR;
                        name _ msn.it;
                        RETURN}};
                    ENDCASE => NULL;
                {mv: Sets.MaybeValue ~ cct.fullName[v.class].Lookup[goal: AV[v], side: left];
                IF mv.found THEN name _ VSn[mv.it] ELSE KnowVertexName[d, v, name _ OSn[nameGen.GenerateName[nameGen.data, subject]]];
                IF relativeTo#cct THEN name _ SNCat[SteppyDescribe[d, cct, relativeTo, nameGen], name];
                RETURN}};
            port: Port => {
                cct: CellType ~ d.PCct[port];
                WITH relativeTo SELECT FROM
                    ap: Port => {
                        IF NOT PWIsAncestor[d, ap, port] THEN ERROR;
                        {msn: MaybeSteppyName ~ ScanRelativeNames[cct, p, ap, port, AcceptAnySteppyName];
                        IF NOT msn.found THEN ERROR;
                        name _ msn.it;
                        RETURN}};
                    ENDCASE => NULL;
                {mv: Sets.MaybeValue ~ cct.fullName[p].Lookup[goal: AV[port], side: left];
                IF mv.found THEN name _ VSn[mv.it] ELSE KnowPortName[d, port, name _ OSn[nameGen.GenerateName[nameGen.data, subject]]];
                IF relativeTo#cct THEN name _ SNCat[SteppyDescribe[d, cct, relativeTo, nameGen], name];
                RETURN}};
            ENDCASE => ERROR;
        };

    genBland: NameGenerator = NEW [NameGeneratorPrivate _ [
        GenerateBlandName,
        NEW [NameCountsPrivate _ []]
        ]];

    NameCounts: TYPE = REF NameCountsPrivate;
    NameCountsPrivate: TYPE = RECORD [
        d, cellType, port, vertex: INT _ 0
        ];

    GenerateBlandName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
        nc: NameCounts = NARROW[data];
        name _ GenByCount[nc, "#", subject];
        };

    GenByCount: PROC [nc: NameCounts, sep: ROPE, subject: REF ANY] RETURNS [name: ROPE] = {
        n: INT _ 0;
        WITH subject SELECT FROM
            d: Design => {n _ nc.d _ nc.d + 1; name _ "D"};
            ct: CellType => {n _ nc.cellType _ nc.cellType + 1; name _ "CT"};
            p: Port => {n _ nc.port _ nc.port + 1; name _ "P"};
            v: Vertex => {n _ nc.vertex _ nc.vertex + 1; name _ "V"};
            ENDCASE => ERROR;
        name _ name.Cat[sep, Convert.RopeFromInt[n]];
        };

    genSymbol: NameGenerator = NEW [NameGeneratorPrivate _ [
        GenerateSymbolName,
        NEW [TVNameGeneratorPrivate _ [
            nc: NEW [NameCountsPrivate _ []],
            symbols: LIST[SymTab.Create[]]
            ]]
        ]];

    TVNameGenerator: TYPE = REF TVNameGeneratorPrivate;
    TVNameGeneratorPrivate: TYPE = RECORD [
        nc: NameCounts,
        symbols: Interpreter.SymbolsList
        ];

    GenerateSymbolName: PROC [data, subject: REF ANY] RETURNS [name: ROPE] = {
        tvng: TVNameGenerator ~ NARROW[data];
        evalHead: InterpreterOps.EvalHead ~ NARROW[List.Assoc[$EvalHead, ProcessProps.GetPropList[]]];
        syms: Interpreter.SymbolsList ~ IF evalHead#NIL AND evalHead.specials#NIL THEN evalHead.specials ELSE tvng.symbols;
        name _ Rope.Concat[IF syms=tvng.symbols THEN "&&" ELSE "&", GenByCount[tvng.nc, "", subject]];
        TRUSTED {InterpreterOps.RegisterTV[
            name: name,
            tv: AMBridge.TVForReferent[WITH subject SELECT FROM
                d: Design => NEW [Design _ d],
                ct: CellType => NEW [CellType _ ct],
                p: Port => NEW [Port _ p],
                v: Vertex => NEW [Vertex _ v],
                ENDCASE => ERROR],
            symbolsList: syms]};
        RETURN};

    defaultNameGen: NameGenerator ~ genSymbol;

    RelativeNames: PUBLIC PROC [ct: CellType, class: PWClass, anc, des: PW] RETURNS [names: Set--of SteppyName--] ~ {
        InsertName: PROC [sn: SteppyName] RETURNS [BOOL]
            ~ {[] _ names.AddElt[SnV[sn]]; RETURN [FALSE]};
        names _ Sets.CreateList[vals: NIL, space: steppyNameSpace, order: SetBasics.fwd];
        [] _ ScanRelativeNames[ct, class, anc, des, InsertName];
        RETURN};

    ScanRelativeNames: PUBLIC PROC [ct: CellType, class: PWClass, anc, des: PW, Test: PROC [SteppyName] RETURNS [BOOL]] RETURNS [msn: 
    MaybeSteppyName _ [FALSE, noName]] ~ {
        countA: LNAT ~ ct.fullName[class].MappingSize[AV[anc]].EN;
        countD: LNAT ~ ct.fullName[class].MappingSize[AV[des]].EN;
        OuterA: PROC [va: Sets.Value] RETURNS [BOOL] ~ {
            na: SteppyName ~ VSn[va];
            InnerD: PROC [vd: Sets.Value] RETURNS [BOOL] ~ {
                nd: SteppyName ~ VSn[vd];
                RETURN [(msn _ SteppyIsSub[na, nd]).found]};
            RETURN [ct.fullName[class].ScanMapping[AV[des], InnerD].found]};
        OuterD: PROC [vd: Sets.Value] RETURNS [BOOL] ~ {
            nd: SteppyName ~ VSn[vd];
            InnerA: PROC [va: Sets.Value] RETURNS [BOOL] ~ {
                na: SteppyName ~ VSn[va];
                RETURN [(msn _ SteppyIsSub[na, nd]).found]};
            RETURN [ct.fullName[class].ScanMapping[AV[anc], InnerA].found]};
        IF countA < countD
            THEN [] _ ct.fullName[class].ScanMapping[AV[anc], OuterA]
            ELSE [] _ ct.fullName[class].ScanMapping[AV[des], OuterD];
        RETURN};

    AcceptAnySteppyName: PUBLIC PROC [SteppyName] RETURNS [BOOL] ~ {RETURN [TRUE]};

    LSn: PUBLIC PROC [l: NameStepList] RETURNS [SteppyName]
        ~ {RETURN [[l, Grade[l]]]};

    Grade: PROC [steps: NameStepList] RETURNS [grade: SteppyNameGrade _ [FALSE, 0, FALSE, 0]] ~ {
        last: ROPE _ NIL;
        FOR steps _ steps, steps.rest WHILE steps#NIL DO
            WITH steps.first SELECT FROM
                x: ROPE => {grade.nonsubs _ grade.nonsubs+1; last _ x};
                x: REF INT => grade.subs _ grade.subs+1;
                ENDCASE => ERROR;
            ENDLOOP;
        IF last#NIL THEN [grade.global, grade.gend] _ Analast[last];
        RETURN};

    Analast: PROC [last: ROPE] RETURNS [global, gend: BOOL _ FALSE] ~ {
        xLen: INT ~ last.Length;
        IF NOT (global _ last.InlineFetch[xLen-1]='!) THEN {
            FOR i: INT DECREASING IN [0 .. xLen) DO
                SELECT last.InlineFetch[i] FROM
                    '#, '& => {gend _ TRUE; EXIT};
                    ENDCASE => NULL;
                ENDLOOP;
            };
        RETURN};

    ParseSteppyName: PUBLIC PROC [raw: ROPE] RETURNS [SteppyName] ~ {
        len: INT ~ raw.Length;
        steps: TList _ [];
        i: INT _ 0;
        DO
            start: INT ~ i;
            type: {unk, num, name} _ unk;
            WHILE i<len DO
                SELECT raw.InlineFetch[i] FROM
                    '/ => EXIT;
                    IN ['0 .. '9] => IF type=unk THEN type _ num;
                    ENDCASE => type _ name;
                i _ i + 1;
                ENDLOOP;
            {part: ROPE ~ raw.Substr[start: start, len: i-start];
            SELECT type FROM
                unk, name => steps _ steps.Append[part];
                num => steps _ steps.Append[NewInt[Convert.IntFromRope[part]]];
                ENDCASE => ERROR;
            IF i=len THEN EXIT ELSE i _ i + 1;
            }ENDLOOP;
        RETURN LSn[steps.head]};

    UnparseSteppyName: PUBLIC PROC [s: SteppyName] RETURNS [u: ROPE] ~ {
        u _ NIL;
        FOR steps: NameStepList _ s.steps, steps.rest WHILE steps#NIL DO
            r: ROPE ~ WITH steps.first SELECT FROM
                x: ROPE => x,
                x: REF INT => Convert.RopeFromInt[x^],
                ENDCASE => ERROR;
            IF u#NIL THEN u _ u.Cat["/", r] ELSE u _ u.Concat[r];
            ENDLOOP;
        RETURN};

    ActualName: PROC [instanceName, portName: SteppyName] RETURNS [actualName: SteppyName] ~ {
        IF portName.grade.global THEN RETURN [portName];
        actualName _ SNCat[instanceName, portName];
        RETURN};

    ActualNames: PUBLIC PROC [cins, pns: Set--of SteppyName--] RETURNS [acts: Set] ~ {
        Outer: PROC [pnv: Sets.Value] ~ {
            pn: SteppyName ~ VSn[pnv];
            Inner: PROC [cinv: Sets.Value] ~ {
                cin: SteppyName ~ VSn[cinv];
                act: SteppyName ~ ActualName[cin, pn];
                [] _ acts.AddElt[SnV[act]];
                RETURN};
            IF pn.grade.global THEN [] _ acts.AddElt[pnv] ELSE cins.Enumerate[Inner];
            RETURN};
        acts _ Sets.CreateHashSet[steppyNameSpace];
        pns.Enumerate[Outer];
        RETURN};

    SNsCat: PUBLIC PROC [as, bs: Set--of SteppyName--] RETURNS [cs: Set--of SteppyName--] ~ {
        Outer: PROC [av: Sets.Value] ~ {
            an: SteppyName ~ VSn[av];
            Inner: PROC [bv: Sets.Value] ~ {
                bn: SteppyName ~ VSn[bv];
                cn: SteppyName ~ SNCat[an, bn];
                [] _ cs.AddElt[SnV[cn]];
                RETURN};
            bs.Enumerate[Inner];
            RETURN};
        cs _ Sets.CreateHashSet[steppyNameSpace];
        as.Enumerate[Outer];
        RETURN};

    SNCat: PUBLIC PROC [a, b: SteppyName] RETURNS [SteppyName] ~ {
        IF b=noName THEN RETURN [a];
        IF a=noName THEN RETURN [b];
        IF b.grade.nonsubs>0 THEN RETURN [[
            steps: List.Append[a.steps, b.steps],
            grade: [
                global: b.grade.global,
                nonsubs: a.grade.nonsubs + b.grade.nonsubs,
                gend: b.grade.gend,
                subs: a.grade.subs + b.grade.subs]
            ]];
        RETURN [[
            steps: List.Append[a.steps, b.steps],
            grade: [
                global: a.grade.global,
                nonsubs: a.grade.nonsubs,
                gend: a.grade.gend,
                subs: a.grade.subs + b.grade.subs]
            ]]};

    SNPrepend: PUBLIC PROC [ns: NameStep, sn: SteppyName] RETURNS [SteppyName] ~ {
        ans: SteppyName _ [steps: CONS[ns, sn.steps], grade: sn.grade];
        WITH ns SELECT FROM
            x: ROPE => IF (ans.grade.nonsubs _ ans.grade.nonsubs+1) = 1 THEN [ans.grade.global, ans.grade.gend] _ Analast[x];
            x: REF INT => ans.grade.subs _ ans.grade.subs+1;
            ENDCASE => ERROR;
        RETURN [ans]};

    SNAppend: PUBLIC PROC [sn: SteppyName, ns: NameStep] RETURNS [SteppyName] ~ {
        ans: SteppyName _ [steps: List.Append[sn.steps, LIST[ns]], grade: sn.grade];
        WITH ns SELECT FROM
            x: ROPE => {
                ans.grade.nonsubs _ ans.grade.nonsubs+1;
                [ans.grade.global, ans.grade.gend] _ Analast[x]};
            x: REF INT => ans.grade.subs _ ans.grade.subs+1;
            ENDCASE => ERROR;
        RETURN [ans]};

    SteppyIsSub: PROC [sub, full: SteppyName] RETURNS [MaybeSteppyName] ~ {
        IF sub.grade.nonsubs>full.grade.nonsubs OR sub.grade.subs>full.grade.subs THEN RETURN [[FALSE, noName]];
        {ls: NameStepList _ sub.steps;
        lf: NameStepList _ full.steps;
        head, tail: NameStepList _ NIL;
        WHILE ls#NIL AND lf#NIL DO
            IF StepEqual[NIL, AV[ls.first], AV[lf.first]] THEN {
                ls _ ls.rest;
                }
            ELSE {
                this: NameStepList ~ LIST[lf.first];
                IF tail=NIL THEN head _ this ELSE tail.rest _ this;
                tail _ this;
                };
            lf _ lf.rest;
            ENDLOOP;
        IF ls#NIL THEN RETURN [[FALSE, noName]];
        IF tail=NIL THEN head _ lf ELSE tail.rest _ lf;
        RETURN [[TRUE, LSn[head]]]}};

    SteppyIsPrefix: PUBLIC PROC [prefix, full: SteppyName] RETURNS [MaybeSteppyName] ~ {
        IF prefix.grade.nonsubs>full.grade.nonsubs OR prefix.grade.subs>full.grade.subs THEN RETURN [[FALSE, noName]];
        {tail: NameStepList ~ List.NthTail[full.steps, prefix.grade.nonsubs+prefix.grade.subs];
        IF NameStepListEqual[prefix.steps, full.steps, NIL, tail] THEN RETURN [[FALSE, noName]];
        {suffix: SteppyName ~ LSn[tail];
        ok: BOOL ~ IF suffix.grade.nonsubs>0
            THEN full.grade.global=suffix.grade.global AND full.grade.nonsubs=prefix.grade.nonsubs+suffix.grade.nonsubs AND 
            full.grade.gend=suffix.grade.gend AND full.grade.subs=prefix.grade.subs+suffix.grade.subs
            ELSE full.grade.global=prefix.grade.global AND full.grade.nonsubs=prefix.grade.nonsubs AND full.grade.gend=prefix.grade.gend AND 
            full.grade.subs=prefix.grade.subs+suffix.grade.subs;
        IF ok THEN RETURN [[TRUE, suffix]] ELSE RETURN [[FALSE, noName]]}}};

    SteppyNameGradeCompare: PUBLIC PROC [g1, g2: SteppyNameGrade] RETURNS [SetBasics.TotalComparison] ~ {
        IF g1 = g2 THEN RETURN [equal];
        RETURN [SELECT TRUE FROM
            g1.global<g2.global => greater,
            g1.global>g2.global => less,
            g1.gend<g2.gend => less,
            g1.gend>g2.gend => greater,
            g1.nonsubs<g2.nonsubs => less,
            g1.nonsubs>g2.nonsubs => greater,
            g1.subs<g2.subs => less,
            g1.subs>g2.subs => greater,
            ENDCASE => ERROR--they were equal!--];
        };

    NameStepListCompare: PUBLIC PROC [l1, l2: NameStepList] RETURNS [c: SetBasics.TotalComparison] ~ {
        WHILE l1#l2 DO
            WITH l1.first SELECT FROM
                x1: REF INT => WITH l2.first SELECT FROM
                    x2: REF INT => IF (c _ SetBasics.CompareIntI[x1^, x2^]) # equal THEN RETURN;
                    x2: ROPE => RETURN [greater];
                    ENDCASE => ERROR;
                x1: ROPE => WITH l2.first SELECT FROM
                    x2: ROPE => IF (c _ SetBasics.Unbasicify[x1.Compare[x2]]) # equal THEN RETURN;
                    x2: REF INT => RETURN [less];
                    ENDCASE => ERROR;
                ENDCASE => ERROR;
            l1 _ l1.rest;
            l2 _ l2.rest;
            ENDLOOP;
        RETURN [equal]};

    NameStepListEqual: PUBLIC PROC [l1, l2: NameStepList, clip1, clip2: NameStepList _ NIL] RETURNS [BOOL] ~ {
        WHILE l1#clip1 AND l2#clip2 DO
            WITH l1.first SELECT FROM
                x: ROPE => WITH l2.first SELECT FROM
                    y: ROPE => IF NOT x.Equal[y] THEN RETURN [FALSE];
                    y: REF INT => RETURN [FALSE];
                    ENDCASE => ERROR;
                x: REF INT => WITH l2.first SELECT FROM
                    y: ROPE => RETURN [FALSE];
                    y: REF INT => IF x^#y^ THEN RETURN [FALSE];
                    ENDCASE => ERROR;
                ENDCASE => ERROR;
            l1 _ l1.rest;
            l2 _ l2.rest;
            ENDLOOP;
        RETURN [(l1=clip1) = (l2=clip2)]};

    nameStepSpace: PUBLIC SetBasics.Space ~ NEW [SetBasics.SpacePrivate _ [
        Contains: StepContains,
        Equal: StepEqual,
        AHash: StepHash,
        ACompare: StepCompare,
        Print: StepPrint,
        name: "name steps"
        ]];

    StepContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [WITH v.ra SELECT FROM
            y: ROPE => TRUE,
            y: REF INT => TRUE,
            ENDCASE => FALSE]};

    StepEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
        WITH v1.VA SELECT FROM
            x: REF INT => WITH v2.VA SELECT FROM
                y: REF INT => RETURN [x^ = y^];
                y: ROPE => RETURN [FALSE];
                ENDCASE => ERROR;
            x: ROPE => WITH v2.VA SELECT FROM
                y: REF INT => RETURN [FALSE];
                y: ROPE => RETURN [x.Equal[y]];
                ENDCASE => ERROR;
            ENDCASE => ERROR;
        };

    StepHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [CARDINAL] ~ {
        WITH v.VA SELECT FROM
            x: REF INT => RETURN SetBasics.HashIntI[x^];
            x: ROPE => RETURN [RopeHash.FromRope[rope: x]];
            ENDCASE => ERROR;
        };

    StepCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [SetBasics.TotalComparison] ~ {
        WITH v1.VA SELECT FROM
            x: REF INT => WITH v2.VA SELECT FROM
                y: REF INT => RETURN [SetBasics.CompareIntI[x^, y^]];
                y: ROPE => RETURN [less];
                ENDCASE => ERROR;
            x: ROPE => WITH v2.VA SELECT FROM
                y: REF INT => RETURN [greater];
                y: ROPE => RETURN [SetBasics.Unbasicify[x.Compare[y]]];
                ENDCASE => ERROR;
            ENDCASE => ERROR;
        };

    StepPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
        WITH v.VA SELECT FROM
            x: ROPE => to.PutRope[x];
            x: REF INT => to.Put[[integer[x^]]];
            ENDCASE => ERROR;
        RETURN};

    steppyNameSpace: PUBLIC SetBasics.Space ~ NEW [SetBasics.SpacePrivate _ [
        Contains: SteppyNamesContains,
        Equal: SteppyNamesEqual,
        AHash: SteppyNamesHash,
        ACompare: SteppyNamesCompare,
        Print: SteppyNamesPrint,
        name: "steppy names"
        ]];

    SteppyNamesContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [WITH v.ra SELECT FROM
            x: NameStepList => TRUE,
            ENDCASE => FALSE]};

    SteppyNamesEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [SteppyNamesCompare[data, v1, v2]=equal]};

    SteppyNamesHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [hash: CARDINAL _ 0] ~ {
        n: SteppyName _ VSn[v];
        FOR steps: NameStepList _ n.steps, steps.rest WHILE steps#NIL DO
            hash _ hash + (WITH steps.first SELECT FROM
                x: ROPE => RopeHash.FromRope[x],
                x: REF INT => SetBasics.HashIntI[x^],
                ENDCASE => ERROR);
            ENDLOOP;
        RETURN};

    SteppyNamesCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
        n1: SteppyName ~ VSn[v1];
        n2: SteppyName ~ VSn[v2];
        IF (c _ SteppyNameGradeCompare[n1.grade, n2.grade])#equal THEN RETURN;
        c _ NameStepListCompare[n1.steps, n2.steps];
        RETURN};

    SteppyNamesPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
    name: SteppyName ~ VSn[v];
    to.PutRope[UnparseSteppyName[name]];
        RETURN};

    emptyRopeSet: PUBLIC Set ~ Sets.CreateEmptySet[SetBasics.ropes[TRUE]];
    emptySteppySet: PUBLIC Set ~ Sets.CreateEmptySet[steppyNameSpace];

    endOfQ: PUBLIC Vertex ~ NEW [VertexPrivate[i]];

    CopyTil: PUBLIC PROC [old: TList] RETURNS [new: TList _ []] ~ {
        FOR cur: LORA _ old.head, cur.rest WHILE cur#old.tail DO
            this: LORA ~ LIST[cur.first];
            IF new.tail=NIL THEN new.head _ this ELSE new.tail.rest _ this;
            new.tail _ this;
            ENDLOOP;
        RETURN};

    NewInt: PUBLIC PROC [i: INT] RETURNS [REF INT] ~ {
        IF i IN [0 .. 64] THEN RETURN [intRefs[i]];
        RETURN [NEW [INT _ i]]};

    IntRefArray: TYPE ~ ARRAY [0 .. 64] OF REF INT;
    intRefs: REF IntRefArray ~ NEW [IntRefArray _ ALL[NIL]];

    AIName: PUBLIC PROC [act: CellType, ai: Int2] RETURNS [SteppyName] ~ {
        IF act.asArray.size2[X]=1
            THEN IF act.asArray.size2[Y]=1
                THEN RETURN [noName]
                ELSE RETURN OSn[NewInt[ai[Y]]]
            ELSE IF act.asArray.size2[Y]=1
                THEN RETURN OSn[NewInt[ai[X]]]
                ELSE RETURN LSn[LIST[NewInt[ai[X]], NewInt[ai[Y]]]]};

    ExtendName: PUBLIC PROC [fileName, defaultExtension: ROPE] RETURNS [fullFName: ROPE, cp: FS.ComponentPositions] ~ {
        [fullFName, cp, ] _ FS.ExpandName[fileName];
        IF defaultExtension.Length[]>0 AND cp.ext.start = cp.base.start+cp.base.length THEN {
            fileName _ FS.ConstructFName[[
                server: fullFName.Substr[cp.server.start, cp.server.length],
                dir: fullFName.Substr[cp.dir.start, cp.dir.length],
                subDirs: fullFName.Substr[cp.subDirs.start, cp.subDirs.length],
                base: fullFName.Substr[cp.base.start, cp.base.length],
                ext: defaultExtension,
                ver: fullFName.Substr[cp.ver.start, cp.ver.length]
                ]];
            [fullFName, cp, ] _ FS.ExpandName[fileName];
            RETURN};
        RETURN};

    Start: PROC ~ {
        FOR i: INT IN [0 .. 64] DO intRefs[i] _ NEW [INT _ i] ENDLOOP;
        RETURN};

    Start[];

    END.