<<>>
    <<VersionMap2Combs.Mesa>>
        <<Copyright Ó 1990 by Xerox Corporation.  All rights reserved.>>
        <<Last tweaked by Mike Spreitzer on December 1, 1990 5:33 pm PST>>

    DIRECTORY MorePfsNames, PFSNames, Rope, RopeParts, VersionMap2, VersionMap2Implr;

    VersionMap2Combs: CEDAR PROGRAM
        IMPORTS MorePfsNames, PFSNames, RopeParts, VersionMap2, VersionMap2Implr
        EXPORTS VersionMap2, VersionMap2Implr
        =

    BEGIN OPEN MPfsN:MorePfsNames, VersionMap2, VersionMap2Implr;

    notClass: MapClass ~ FillinDefaults[FALSE, readonly, [
        MMutability: NotMMutability,
        Has: NotHas,
        AddTuple: NotAddTuple,
        AddMap: NotAddMap,
        RemTuple: NotRemTuple,
        RemMap: NotRemMap,
        Negate: NotNegate,
        IsNegation: NotIsNegation,
        data: NIL]];

    DefaultNegate: PUBLIC PROC [map: Map] RETURNS [Map]
        ~ {RETURN [[notClass, map.Refify[]]]};

    DefaultIsNegation: PUBLIC PROC [map: Map] RETURNS [MaybeMap]
        ~ {RETURN [[FALSE, nullMap]]};

    NotFunctional: PROC [map: Map] RETURNS [BOOL] ~ {RETURN [FALSE]};

    NotMMutability: PROC [map: Map] RETURNS [Mutability] ~ {
        sub: REF Map ~ NARROW[map.data];
        RETURN sub^.MMutability[]};

    NotHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        sub: REF Map ~ NARROW[map.data];
        RETURN [NOT sub^.Has[elt]]};

    NotAddTuple: PROC [map: Map, t: VersionTuple, if: IfHads] RETURNS [had: Hads] ~ {
        sub: REF Map ~ NARROW[map.data];
        [] _ sub^.RemTuple[t];
        RETURN [ALL[none]]};

    NotAddMap: PROC [map, other: Map, if: IfHads] RETURNS [some: HadSets] ~ {
        sub: REF Map ~ NARROW[map.data];
        [] _ sub^.RemMap[other];
        RETURN [ALL[ALL[FALSE]]]};

    NotRemTuple: PROC [map: Map, t: VersionTuple] RETURNS [had: Hads] ~ {
        sub: REF Map ~ NARROW[map.data];
        [] _ sub^.AddTuple[t];
        RETURN [ALL[none]]};

    NotRemMap: PROC [map, other: Map] RETURNS [some: HadSets] ~ {
        sub: REF Map ~ NARROW[map.data];
        [] _ sub^.AddMap[other];
        RETURN [ALL[ALL[FALSE]]]};

    NotNegate: PROC [map: Map] RETURNS [Map] ~ {
        sub: REF Map ~ NARROW[map.data];
        RETURN [sub^]};

    NotIsNegation: PROC [map: Map] RETURNS [MaybeMap] ~ {
        sub: REF Map ~ NARROW[map.data];
        RETURN [[TRUE, sub^]]};

    Binary: TYPE ~ REF BinaryPrivate;
    BinaryPrivate: TYPE ~ RECORD [a, b: Map, op: {and, or}, test: UnionTest, ordered: BOOL];

    andClass: MapClass ~ FillinDefaults[FALSE, readonly, [
        Functional: AndFunctional,
        MMutability: BinMMutability,
        Has: AndHas,
        Scan: AndScan,
        CreateGenerator: AndCreateGenerator,
        Size: SizeByScan,
        Negate: AndNegate,
        IsIntersection: AndIsIntersection,
        data: NIL]];

    orClass: MapClass ~ FillinDefaults[FALSE, readonly, [
        MMutability: BinMMutability,
        Has: OrHas,
        Scan: OrScan,
        CreateGenerator: OrCreateGenerator,
        Size: SizeByScan,
        Negate: OrNegate,
        IsUnion: OrIsUnion,
        data: NIL]];

    DefaultIntersect: PUBLIC PROC [map, other: Map] RETURNS [Map] ~ {
        IF map=aFull THEN RETURN [other];
        IF other=aFull THEN RETURN [map];
        IF map=anEmpty OR other=anEmpty THEN RETURN [anEmpty];
        {b: Binary ~ NEW [BinaryPrivate _ [map, other, and, other, FALSE]];
        RETURN [[andClass, b]]}};

    DefaultIsIntersection: PUBLIC PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        RETURN [[FALSE, nullMap, nullMap]]};

    DefaultUnion: PUBLIC PROC [map, other: Map, test: UnionTest, ordered: BOOL] RETURNS [Map] ~ {
        IF map=anEmpty THEN RETURN [other];
        IF other=anEmpty THEN RETURN [map];
        IF map=aFull OR other=aFull THEN RETURN [anEmpty];
        {b: Binary ~ NEW [BinaryPrivate _ [map, other, or, test, ordered]];
        RETURN [[orClass, b]]}};

    DefaultIsUnion: PUBLIC PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        RETURN [[FALSE, nullMap, nullMap]]};

    DefaultDifference: PUBLIC PROC [map, other: Map] RETURNS [Map] ~ {
        RETURN map.Intersect[other.Negate[]]};

    DefaultIsDifference: PUBLIC PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        m1: Maybe2Maps ~ map.IsIntersection[];
        m2: MaybeMap;
        IF NOT m1.found THEN RETURN [m1];
        IF (m2 _ m1.other.IsNegation).found THEN RETURN [[TRUE, m1.map, m2.it]];
        IF (m2 _ m1.map.IsNegation).found THEN RETURN [[TRUE, m1.other, m2.it]];
        RETURN [[FALSE, nullMap, nullMap]]};

    DefaultSymmetricDifference: PUBLIC PROC [map, other: Map] RETURNS [Map] ~ {
        d1: Map ~ map.Difference[other];
        d2: Map ~ other.Difference[map];
        RETURN d1.Union[d2]};

    DefaultIsSymmetricDifference: PUBLIC PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        m1: Maybe2Maps ~ map.IsUnion[];
        IF NOT m1.found THEN RETURN [m1];
        {m12: Maybe2Maps ~ m1.map.IsDifference[];
        m21: Maybe2Maps ~ m1.other.IsDifference[];
        IF m12.found AND m21.found AND m12.map=m21.other AND m12.other=m21.map THEN RETURN [m12];
        RETURN [[FALSE, nullMap, nullMap]]}};

    AndFunctional: PROC [map: Map] RETURNS [BOOL] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [b.a.Functional[] OR b.b.Functional[]]};

    BinMMutability: PROC [map: Map] RETURNS [Mutability] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [MIN[readonly, MIN[b.a.MMutability[], b.b.MMutability[]]]]};

    AndHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [b.a.Has[elt] AND b.b.Has[elt]]};

    OrHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [b.a.Has[elt] OR b.b.Has[elt]]};

    AndScan: PROC [map: Map, Consume: TupleConsumer, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [MaybeTuple] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN b.a.FactoredScan[Consume, inOrder, PfmlAddMap[pfml, b.b]]};

    OrScan: PROC [map: Map, Consume: TupleConsumer, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [MaybeTuple] ~ {
        b: Binary ~ NARROW[map.data];
        IF inOrder AND NOT b.ordered THEN RETURN SortScan[map, map.class.Scan, Consume, pfml];
        {mt1: MaybeTuple ~ b.a.FactoredScan[Consume, inOrder, IF b.test=other THEN PfmlAddMap[pfml, b.b.Negate[]] ELSE pfml];
        IF mt1.found THEN RETURN [mt1];
        RETURN b.b.FactoredScan[Consume, inOrder, IF b.test=map THEN PfmlAddMap[pfml, b.a.Negate[]] ELSE pfml]}};

    AndCreateGenerator: PROC [map: Map, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [Generator] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN b.a.FactoredCreateGenerator[inOrder, PfmlAddMap[pfml, b.b]]};

    OrCreateGenerator: PROC [map: Map, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [Generator] ~ {
        b: Binary ~ NARROW[map.data];
        g1: Generator ~ b.a.FactoredCreateGenerator[inOrder, IF b.test=other THEN PfmlAddMap[pfml, b.b.Negate[]] ELSE pfml];
        g2: Generator ~ b.b.FactoredCreateGenerator[inOrder, IF b.test=map THEN PfmlAddMap[pfml, b.a.Negate[]] ELSE pfml];
        RETURN g1.GeneratorUnion[g2, inOrder]};

    AndNegate: PROC [map: Map] RETURNS [Map] ~ {
        b: Binary ~ NARROW[map.data];
        notA: Map ~ b.a.Negate[];
        notB: Map ~ b.b.Negate[];
        RETURN Union[notA, notB, other]};

    OrNegate: PROC [map: Map] RETURNS [Map] ~ {
        b: Binary ~ NARROW[map.data];
        notA: Map ~ b.a.Negate[];
        notB: Map ~ b.b.Negate[];
        IF b.test=map THEN RETURN Intersect[notB, notA];
        RETURN Intersect[notA, notB]};

    AndIsIntersection: PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [[TRUE, b.a, b.b]]};

    OrIsUnion: PROC [map: Map] RETURNS [Maybe2Maps] ~ {
        b: Binary ~ NARROW[map.data];
        RETURN [[TRUE, b.a, b.b]]};

    CreateSingleton: PUBLIC PROC [elt: VersionTuple] RETURNS [Map] ~ {
        RETURN [[singletonClass, NEW [VersionTuple _ elt]]]};

    singletonClass: MapClass ~ FillinDefaults[TRUE, constant, [
        Has: SingletonHas,
        Scan: SingletonScan,
        Size: SizeIsOne,
        PatternFactorMap: SingletonPatternFactorMap,
        data: NIL]];

    SingletonHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        re: REF VersionTuple ~ NARROW[map.data];
        RETURN TEqual[elt, re^]};

    SingletonScan: PROC [map: Map, Consume: TupleConsumer, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [MaybeTuple] ~ {
        re: REF VersionTuple ~ NARROW[map.data];
        IF pfml#[] AND NOT PfmlHas[pfml, re^] THEN RETURN [noMaybe];
        IF Consume[re^] THEN RETURN [[TRUE, re^]] ELSE RETURN [noMaybe]};

    SizeIsOne: PROC [map: Map, limit: INT] RETURNS [INT] ~ {RETURN [1]};

    SingletonPatternFactorMap: PROC [map: Map] RETURNS [PatternFactoredMap] ~ {
        re: REF VersionTuple ~ NARROW[map.data];
        RETURN [[re^, aFull, aFull]]};

    CreateMatcher: PUBLIC PROC [pattern: VersionTuple] RETURNS [Map] ~ {
        IF PatternIsConstant[pattern] THEN RETURN CreateSingleton[pattern];
        RETURN [[matcherClass, NEW [VersionTuple _ pattern]]]};

    matcherClass: MapClass ~ FillinDefaults[FALSE, constant, [
        Has: MatcherHas,
        Size: FullSize,
        PatternFactorMap: MatcherPatternFactorMap,
        data: NIL]];

    MatcherHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        rp: REF VersionTuple ~ NARROW[map.data];
        RETURN TMatches[elt, rp^]};

    MatcherPatternFactorMap: PROC [map: Map] RETURNS [PatternFactoredMap] ~ {
        rp: REF VersionTuple ~ NARROW[map.data];
        RETURN [[rp^, aFull, aFull]]};

    CreateSetMatcher: PUBLIC PROC [prefix: VersionTuple, suffixes: LOR] RETURNS [Map] ~ {
        lc: MPfsN.Component ~ prefix.name.ShortName[];
        lcr: ROPE ~ lc.ComponentRope[--must, and does, exclude version part--];
        sm: SetMatcher ~ NEW [SetMatcherPrivate _ [
            prefix,
            suffixes,
            prefix.name.ReplaceShortName[MPfsN.ConstructComponent[name: [lcr.Concat["*"]], version: lc.version]],
            lcr.Length[]
            ]];
        IF suffixes=NIL THEN RETURN [anEmpty];
        RETURN [[setMatcherClass, sm]]};

    SetMatcher: TYPE ~ REF SetMatcherPrivate;
    SetMatcherPrivate: TYPE ~ RECORD [
        prefix: VersionTuple,
        suffixes: LOR,
        prefixPattern: Name,
        variableStart: NAT
        ];

    setMatcherClass: MapClass ~ FillinDefaults[FALSE, constant, [
        Has: SetMatcherHas,
        Size: FullSize,
        PatternFactorMap: SetMatcherPatternFactorMap,
        data: NIL]];

    SetMatcherHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        sm: SetMatcher ~ NARROW[map.data];
        IF NOT TMatches[elt, [sm.prefixPattern, sm.prefix.created, sm.prefix.stamp]] THEN RETURN [FALSE];
        {lc: MPfsN.Component ~ elt.name.ShortName[];
        suff: RopeParts.RopePart ~ MPfsN.ComponentName[lc].Substr[start: sm.variableStart];
        FOR ss: LOR _ sm.suffixes, ss.rest WHILE ss#NIL DO
            IF RopeParts.Match[RopeParts.Make[ss.first], suff, FALSE] THEN RETURN [TRUE];
            ENDLOOP;
        RETURN [FALSE]}};

    SetMatcherPatternFactorMap: PROC [map: Map] RETURNS [PatternFactoredMap] ~ {
        sm: SetMatcher ~ NARROW[map.data];
        RETURN [[[sm.prefixPattern, sm.prefix.created, sm.prefix.stamp], map, aFull]]};


    END.