<> <> DIRECTORY AbSets, BiRelBasics, BiRels, IntStuff, SetBasics; BiRelVectors: CEDAR PROGRAM IMPORTS AbSets, BiRelBasics, BiRels, IntStuff, SetBasics EXPORTS BiRels = BEGIN OPEN IntStuff, SetBasics, Sets:AbSets, Sets, BiRelBasics, BiRels; Simple: TYPE ~ REF SimplePrivate; SimplePrivate: TYPE ~ RECORD [ right: Space, bounds: IntInterval, leftDense, domFixed: BOOL, vals: SimpleElts, size, freezeCount: INT _ 0]; <> SimpleElts: TYPE ~ REF SimpleEltsPrivate; SimpleEltsPrivate: TYPE ~ RECORD [vals: SEQUENCE size: NATURAL OF Value]; CreateSimpleCopy: PUBLIC PROC [of: IntFn, bounds: IntInterval _ [], oneToOne, dense, domainFixed: RelBool _ SAME, rightSpace: Space _ NIL] RETURNS [IntFn] ~ { realBounds: IntInterval ~ of.GetIntDom.Intersect[bounds]; realOneToOne: BOOL ~ oneToOne.RelativizeBool[of.Functional[][rightToLeft]]; realDense: BOOL ~ dense.RelativizeBool[of.IsDense[always, left]]; realDomainFixed: BOOL ~ domainFixed.RelativizeBool[of.SideFixed[left]]; realSpace: Space ~ IF rightSpace#NIL THEN rightSpace ELSE of.Spaces[][right]; vals: SimpleElts ~ NEW [SimpleEltsPrivate[realBounds.Length.EN]]; simple: Simple ~ NEW [SimplePrivate _ [realSpace, realBounds, realDense, realDomainFixed, realBounds.min, vals, of.Size[].EN]]; FOR i: INT IN [realBounds.min .. realBounds.max] DO TRUSTED { mv: MaybeValue ~ of.ApplyI[i]; vals[i-simple. }ENDLOOP; RETURN [[simpleClasses[realOneToOne][realDense][realDomainFixed][variable], simple]]}; CreateSimple: PUBLIC PROC [bounds: IntInterval _ [0, -1], val: Value _ noValue, oneToOne, dense, domainFixed: BOOL _ FALSE, rightSpace: Space _ basic] RETURNS [IntFn] ~ { vals: SimpleElts ~ NEW [SimpleEltsPrivate[bounds.Length.EN]]; simple: Simple ~ NEW [SimplePrivate _ [rightSpace, bounds, dense, domainFixed, bounds.min, vals, bounds.Length.EN]]; FOR i: NATURAL IN [0 .. vals.size) DO TRUSTED {vals[i] _ val} ENDLOOP; IF val=noValue THEN { simple.bounds _ simple.bounds.ClipTop[simple.bounds.min]; simple.size _ 0}; RETURN [[simpleClasses[oneToOne][dense][domainFixed][variable], simple]]}; SimpleClasses: TYPE ~ ARRAY --oneToOne--BOOL OF ARRAY --leftDense--BOOL OF ARRAY --domainFixed--BOOL OF ARRAY Mutability OF BiRelClass; simpleClasses: REF SimpleClasses ~ NEW [SimpleClasses]; SimplePrimitive: PROC [br: BiRel, op: ATOM, arg1, arg2: REF ANY] RETURNS [PrimitiveAnswer] ~ { simple: Simple ~ NARROW[br.data]; SELECT op FROM $Apply => {dir: Direction ~ ToDir[arg1]; RETURN [IF dir=leftToRight THEN yes ELSE no]}; $ScanRestriction, $GetBounds => {ro: RelOrder ~ ToRO[arg2]; RETURN [IF ro.first#left AND ro.sub[ro.first]#no THEN no ELSE yes]}; $RestrictionSize => {sets: RefSetPair ~ ToSets[arg1]; RETURN [IF sets^=ALL[nilSet] THEN yes ELSE no]}; ENDCASE => RETURN [pass]}; SimpleApply: PROC [br: BiRel, v: Value, dir: Direction] RETURNS [MaybeValue] ~ { simple: Simple ~ NARROW[br.data]; IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen]; IF dir=rightToLeft THEN RETURN DefaultApply[br, v, dir]; {i: INT ~ v.VI; w: Value ~ IF simple.bounds.Contains[i] THEN simple.vals[i-simple. RETURN [[w#noValue, w]]}}; SimpleScanRestriction: PROC [br: BiRel, sets: SetPair, Test: Tester, ro: RelOrder] RETURNS [MaybePair] ~ { simple: Simple ~ NARROW[br.data]; IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen]; IF ro.first#left AND ro.sub[ro.first]#no THEN RETURN DefaultScanRestriction[br, sets, Test, ro]; {vals: SimpleElts ~ simple.vals; lb: MaybeIntInterval ~ IF sets[left]#nilSet THEN sets[left].QuaIntInterval ELSE [TRUE, []]; scanBounds: IntInterval ~ simple.bounds.Intersect[IF lb.found THEN lb.it ELSE []]; left: Set ~ sets[left]; right: Set ~ sets[right]; rn: BOOL ~ right=nilSet; ld: BOOL ~ lb.found; IF ro.sub[left]=bwd THEN FOR i: INT DECREASING IN [scanBounds.min .. scanBounds.max] DO pair: Pair ~ [[i[i]], simple.vals[i-simple. IF pair[right]#noValue AND (ld OR left.HasMember[[i[i]]]) AND (rn OR right.HasMember[pair[right]]) AND Test[pair] THEN RETURN [[TRUE, pair]]; ENDLOOP ELSE FOR i: INT IN [scanBounds.min .. scanBounds.max] DO pair: Pair ~ [[i[i]], simple.vals[i-simple. IF pair[right]#noValue AND (ld OR left.HasMember[[i[i]]]) AND (rn OR right.HasMember[pair[right]]) AND Test[pair] THEN RETURN [[TRUE, pair]]; ENDLOOP; RETURN [noMaybePair]}}; SimpleRestrictionSize: PROC [br: BiRel, sets: SetPair, limit: EINT] RETURNS [EINT] ~ { simple: Simple ~ NARROW[br.data]; IF sets # ALL[nilSet] THEN RETURN DefaultRestrictionSize[br, sets, limit]; RETURN [IE[simple.size]]}; SimpleGetBounds: PROC [br: BiRel, want: EndBools, ro: RelOrder] RETURNS [MaybePairInterval] ~ { simple: Simple ~ NARROW[br.data]; IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen]; IF ro.first#left AND ro.sub[left]#no THEN RETURN DefaultGetBounds[br, want, ro]; IF simple.bounds.Empty THEN RETURN [[FALSE, [ min: [[i[simple.bounds.min]], noValue], max: [[i[simple.bounds.max]], noValue]] ]]; {pi: PairInterval ~ [min: [[i[simple.bounds.min]], simple.vals[simple.bounds.min-simple. simple.vals[simple.bounds.max-simple. RETURN [[TRUE, IF ro.sub[left]#bwd THEN pi ELSE RevPI[pi] ]]}}; SimpleCopy: PROC [br: BiRel] RETURNS [VarBiRel] ~ { simple: Simple ~ NARROW[br.data]; v1: SimpleElts ~ simple.vals; IF br.MutabilityOf=constant AND simple.freezeCount=0 THEN Complain[br, unfrozen]; {v2: SimpleElts ~ NEW [SimpleEltsPrivate[v1.size]]; s2: Simple ~ NEW [SimplePrivate _ simple^]; s2.vals _ v2; s2.freezeCount _ 0; FOR i: NATURAL IN [0 .. v2.size) DO TRUSTED {v2[i] _ v1[i]} ENDLOOP; RETURN AsVar[[simpleClasses [br.Functional[][rightToLeft]] [simple.leftDense] [simple.domFixed] [variable], s2]]}}; SimpleFreeze: PROC [br: BiRel] RETURNS [ConstBiRel] ~ { simple: Simple ~ NARROW[br.data]; IF br.MutabilityOf#variable THEN Complain[br, notVariable]; simple.freezeCount _ simple.freezeCount + 1; RETURN AsConst[[ simpleClasses [br.IsOneToOne] [simple.leftDense] [br.SideFixed[left]] [constant], simple]]; }; SimpleThaw: PROC [br: BiRel] ~ { simple: Simple ~ NARROW[br.data]; IF br.MutabilityOf#variable THEN Complain[br, notVariable]; IF simple.freezeCount<=0 THEN Complain[br, "too many thaws"]; simple.freezeCount _ simple.freezeCount-1; RETURN}; SimpleAddSet: PROC [br, other: BiRel, if: IfHadPair] RETURNS [some: HadSetPair] ~ { simple: Simple ~ NARROW[br.data]; right: Space ~ simple.right; invSearch: BOOL ~ br.Functional[][rightToLeft]; urSize: INT ~ simple.size; bounds: IntInterval; vals: SimpleElts; expansionCount: NATURAL _ 0; Per: PROC [pair: Pair] RETURNS [BOOL] ~ { i: INT ~ pair[left].VI; news: Had _ different; IF invSearch THEN FOR j: INT IN [bounds.min-d .. bounds.max-d] DO IF vals[j]#noValue AND right.SEqual[vals[j], pair[right]] THEN {some[rightToLeft][IF i=j THEN same ELSE different] _ TRUE; EXIT}; REPEAT FINISHED => some[rightToLeft][none] _ TRUE; ENDLOOP; IF bounds.Contains[i] THEN { old: Value ~ vals[i- IF old=noValue THEN { news _ none; simple.size _ simple.size+1; } ELSE IF right.SEqual[pair[right], old] THEN news _ same } ELSE IF simple.domFixed THEN br.Complain[fixedSide, LIST[[a[$left]]]] ELSE { IF expansionCount _ expansionCount + simple.size _ simple.size+1; bounds _ simple.bounds; TRUSTED {vals[i- some[leftToRight][news] _ TRUE; RETURN [FALSE]}; IF br.MutabilityOf # variable THEN br.Complain[notVariable]; IF simple.freezeCount#0 THEN br.Complain[frozen]; some _ ALL[ALL[FALSE]]; IF other.QualityOf[$GetIntDom] >= goodDefault THEN expansionCount _ EnsureContains[simple, other.GetIntDom[]]; bounds _ simple.bounds; [] _ other.Scan[Per]; {newCount: NATURAL ~ simple.size - urSize; IF newCount>expansionCount THEN ERROR; IF simple.leftDense AND newCount= simple.bounds.min AND bounds.max <= simple.bounds.max THEN RETURN [0]; {oldVals: SimpleElts ~ simple.vals; oldSize: NATURAL ~ oldVals.size; oldBounds: IntInterval ~ simple.bounds; newBounds: IntInterval ~ simple.bounds.MBI[bounds]; newLen: NATURAL ~ newBounds.Length.EN; old expansionCount _ newLen - oldBounds.Length.EN; simple.bounds _ newBounds; IF newBounds.min >= old IF newLen <= oldSize THEN { newPad: INT ~ (oldSize - newLen)/2; new IF new FOR i: INT IN [oldBounds.min .. oldBounds.max] DO TRUSTED {oldVals[i-new ENDLOOP; IF NOT oldBounds.Empty THEN FOR i: INT IN (oldBounds.max-new TRUSTED {oldVals[i] _ noValue}; ENDLOOP; }; IF new FOR i: INT DECREASING IN [oldBounds.min .. oldBounds.max] DO TRUSTED {oldVals[i-new ENDLOOP; IF NOT oldBounds.Empty THEN FOR i: INT IN [oldBounds.min-old TRUSTED {oldVals[i] _ noValue}; ENDLOOP; }; simple. RETURN}; {newSize: NATURAL ~ MIN[INT[NATURAL.LAST], MAX[newLen, INT[oldSize]*2]]; newVals: SimpleElts ~ NEW [SimpleEltsPrivate[newSize]]; newPad: INT ~ (newSize - newLen)/2; new IF oldBounds.Empty THEN TRUSTED { FOR i: INT IN [0 .. newSize) DO newVals[i] _ noValue ENDLOOP; } ELSE TRUSTED { FOR i: INT IN [0 .. oldBounds.min-new FOR i: INT IN [oldBounds.min .. oldBounds.max] DO newVals[i-new FOR i: INT IN (oldBounds.max-new }; simple. simple.vals _ newVals; RETURN}}}; SimpleDenseRemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair _ []] ~ { simple: Simple ~ NARROW[br.data]; vals: SimpleElts ~ simple.vals; right: Space ~ simple.right; urSize: INT ~ simple.size; oldBounds: IntInterval ~ simple.bounds; otherBounds: IntInterval ~ other.GetIntDom[]; scanBounds: IntInterval ~ oldBounds.Intersect[otherBounds]; mustKeep: IntInterval _ anEmptyInterval; may: IntInterval _ oldBounds; Per: PROC [pair: Pair] RETURNS [BOOL] ~ { i: INT ~ pair[left].VI; w: Value ~ vals[i-simple. hadIt: BOOL ~ right.SEqual[pair[right], w]; IF hadIt THEN { IF simple.domFixed THEN br.Complain[fixedSide, LIST[[a[$left]]]] ELSE IF mustKeep.Contains[i] THEN br.Complain[denseSide, LIST[[a[$left]]]] ELSE IF may.Contains[i] THEN { SELECT i FROM < mustKeep.min => may.min _ i+1; > mustKeep.max => may.max _ i-1; ENDCASE => ERROR; }; TRUSTED {vals[i-simple. some[leftToRight][same] _ TRUE; simple.size _ simple.size - 1} ELSE { IF NOT may.Contains[i] THEN br.Complain[denseSide, LIST[[a[$left]]]] ELSE IF NOT mustKeep.Contains[i] THEN mustKeep _ [min: MIN[mustKeep.min, i], max: MAX[mustKeep.max, i]]; some[leftToRight][different] _ TRUE}; RETURN [FALSE]}; IF br.MutabilityOf # variable THEN br.Complain[notVariable]; IF simple.freezeCount#0 THEN br.Complain[frozen]; some[leftToRight][none] _ scanBounds#otherBounds; IF br.Functional[][rightToLeft] THEN some[rightToLeft] _ Has[br, other, [FALSE, TRUE]][rightToLeft]; [] _ other.ScanHalfRestriction[IIAsSet[scanBounds], Per]; simple.bounds _ may; simple. IF may.Length.AddI[urSize-simple.size] # oldBounds.Length THEN br.Complain[denseSide, LIST[[a[$left]]]]; RETURN}; SimpleSparseRemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair _ []] ~ { simple: Simple ~ NARROW[br.data]; vals: SimpleElts ~ simple.vals; right: Space ~ simple.right; oldBounds: IntInterval ~ simple.bounds; otherBounds: IntInterval ~ other.GetIntDom[]; scanBounds: IntInterval ~ otherBounds.Intersect[oldBounds]; rebound: BOOL _ FALSE; Per: PROC [pair: Pair] RETURNS [pass: BOOL _ FALSE] ~ { i: INT ~ pair[left].VI; w: Value ~ vals[i-simple. notno: BOOL ~ w#noValue; hadIt: BOOL ~ notno AND right.SEqual[pair[right], w]; IF hadIt THEN { IF simple.domFixed THEN br.Complain[fixedSide, LIST[[a[$left]]]]; IF i=oldBounds.min OR i=oldBounds.max THEN rebound _ TRUE; TRUSTED {vals[i-simple. simple.size _ simple.size - 1; some[leftToRight][same] _ TRUE} ELSE some[leftToRight][IF notno THEN different ELSE none] _ TRUE; }; IF br.MutabilityOf # variable THEN br.Complain[notVariable]; IF simple.freezeCount#0 THEN br.Complain[frozen]; some[leftToRight][none] _ scanBounds#otherBounds; IF br.Functional[][rightToLeft] THEN some[rightToLeft] _ Has[br, other, [FALSE, TRUE]][rightToLeft]; [] _ other.ScanHalfRestriction[IIAsSet[scanBounds], Per]; IF rebound THEN FixBounds[br, simple]; RETURN}; FixBounds: PROC [br: BiRel, simple: Simple] ~ { vals: SimpleElts ~ simple.vals; oldBounds: IntInterval ~ simple.bounds; newBounds: IntInterval _ oldBounds; WHILE newBounds.min<=newBounds.max AND vals[newBounds.min- WHILE newBounds.min<=newBounds.max AND vals[newBounds.max- simple.bounds _ newBounds; IF NOT (oldBounds.Empty OR newBounds.Empty) THEN simple. RETURN}; LeftDelete: PROC [simple: Simple, where: IntInterval] ~ { in: IntInterval ~ where.Intersect[simple.bounds]; IF in.Empty THEN RETURN; FOR i: INT IN [in.min-simple. IF simple.vals[i]#noValue THEN TRUSTED { simple.vals[i] _ noValue; simple.size _ simple.size-1}; ENDLOOP; IF where.min > simple.bounds.min THEN IF where.max < simple.bounds.max THEN NULL ELSE simple.bounds.max _ where.min-1 ELSE IF where.max < simple.bounds.max THEN simple.bounds.min _ where.max+1 ELSE simple.bounds _ anEmptyInterval; RETURN}; SimpleReplaceMe: PROC [br, with: BiRel, where: IntInterval] ~ { simple: Simple ~ NARROW[br.data]; clip: IntInterval ~ with.GetIntDom[]; clipLen: EINT ~ clip.Length; whereLen: EINT ~ where.Length; tailShift: EINT ~ clipLen.Sub[whereLen]; insertShift: EINT ~ ISub[where.min, clip.min]; oldBounds: IntInterval ~ simple.bounds; insertBoundsEst: IntInterval ~ clip.ClipShiftInterval[insertShift]; beforeTail: INT ~ IF where.Empty THEN where.min-1 ELSE where.max; bounds: IntInterval _ anEmptyInterval; newBoundsEst, headNeed, tailNeed: IntInterval; AddStuff: PROC [new: IntInterval] ~ {bounds _ bounds.MBI[new]}; AddPair: PROC [pair: Pair] RETURNS [BOOL] ~ { i: INT ~ insertShift.AddI[pair[left].VI].EI; [] _ EnsureContains[simple, [i, i]]; AddStuff[[i, i]]; simple.size _ simple.size + 1; TRUSTED {simple.vals[i-simple. RETURN [FALSE]}; IF br.MutabilityOf # variable THEN br.Complain[notVariable]; IF simple.freezeCount#0 THEN br.Complain[frozen]; SELECT TRUE FROM oldBounds.max < where.min => {headNeed _ newBoundsEst _ oldBounds; tailNeed _ anEmptyInterval}; oldBounds.min > beforeTail => {tailNeed _ newBoundsEst _ oldBounds.ShiftInterval[tailShift]; headNeed _ anEmptyInterval}; ENDCASE => { newBoundsEst _ [ min: MIN[oldBounds.min, where.min], max: tailShift.AddI[MAX[oldBounds.max, where.max]].ClipI]; headNeed _ newBoundsEst.ClipTop[where.min]; tailNeed _ newBoundsEst.ClipBot[tailShift.AddI[beforeTail].ClipI]}; [] _ EnsureContains[simple, tailNeed]; AddStuff[headNeed]; AddStuff[tailNeed]; IF NOT tailNeed.Empty THEN SELECT tailShift.Sgn[] FROM <0 => { FOR i: INT IN [tailNeed.min-simple. j: INT ~ tailShift.SubFromI[i].EI; IF simple.vals[i]=noValue THEN simple.size _ simple.size-1; TRUSTED {simple.vals[i] _ simple.vals[j]; simple.vals[j] _ noValue}; ENDLOOP; }; >0 => { olds: IntInterval ~ oldBounds.ClipBot[insertBoundsEst.max].ClipTop[tailNeed.min]; FOR i: INT DECREASING IN [tailNeed.min .. tailNeed.max] DO j: INT ~ tailShift.SubFromI[i].EI; TRUSTED {simple.vals[i-simple. ENDLOOP; FOR i: INT IN [olds.min .. olds.max] DO TRUSTED {simple.vals[i-simple. ENDLOOP; }; =0 => NULL; ENDCASE => ERROR; LeftDelete[simple, insertBoundsEst]; {midSize: INT ~ simple.size; [] _ with.Scan[AddPair]; IF simple.leftDense AND headNeed.Length.Add[tailNeed.Length].AddI[simple.size-midSize] # bounds.Length THEN br.Complain[denseSide, LIST[[a[$left]]]]; IF simple.domFixed AND bounds#oldBounds THEN br.Complain[fixedSide, LIST[[a[$left]]]]; simple.bounds _ bounds; IF NOT (bounds.Empty OR oldBounds.Empty) THEN simple. RETURN}}; SimpleShiftAndClipMe: PROC [br: BiRel, shift: EINT, clip: IntInterval] ~ { simple: Simple ~ NARROW[br.data]; unshifted: IntInterval ~ simple.bounds.Intersect[clip]; newBounds: IntInterval ~ unshifted.ClipShiftInterval[shift]; IF br.MutabilityOf#variable THEN br.Complain[notVariable]; IF simple.freezeCount#0 THEN br.Complain[frozen]; IF simple.domFixed AND newBounds#simple.bounds THEN br.Complain[fixedSide, LIST[[a[$left]]]]; TRUSTED { FOR i: INT IN [simple.bounds.min-simple. IF simple.vals[i]#noValue THEN {simple.vals[i] _ noValue; simple.size _ simple.size-1}; ENDLOOP; FOR i: INT IN (unshifted.max-simple. IF simple.vals[i]#noValue THEN {simple.vals[i] _ noValue; simple.size _ simple.size-1}; ENDLOOP; }; simple. simple.bounds _ newBounds; RETURN}; SimpleSpaces: PROC [br: BiRel] RETURNS [SpacePair] ~ { simple: Simple ~ NARROW[br.data]; RETURN [[ints, simple.right]]}; SimpleIsDense: PROC [br: BiRel, when: When, side: Side] RETURNS [BOOL] ~ { simple: Simple ~ NARROW[br.data]; RETURN [side=left AND simple.leftDense]}; SimpleSideFixed: PROC [br: BiRel, side: Side] RETURNS [BOOL] ~ { simple: Simple ~ NARROW[br.data]; RETURN [br.MutabilityOf=constant OR (side=left AND simple.domFixed)]}; Start: PROC ~ { FOR isOneToOne: BOOL IN BOOL DO FOR dense: BOOL IN BOOL DO FOR domainFixed: BOOL IN BOOL DO FOR mutability: Mutability IN Mutability DO simpleClasses[isOneToOne][dense][domainFixed][mutability] _ CreateClass[ cp: [ Primitive: SimplePrimitive, Apply: SimpleApply, ScanRestriction: SimpleScanRestriction, RestrictionSize: SimpleRestrictionSize, GetBounds: SimpleGetBounds, Copy: SimpleCopy, Freeze: SimpleFreeze, Thaw: SimpleThaw, AddSet: SimpleAddSet, RemSet: IF dense THEN SimpleDenseRemSet ELSE SimpleSparseRemSet, ReplaceMe: SimpleReplaceMe, ShiftAndClipMe: SimpleShiftAndClipMe, Spaces: SimpleSpaces, IsDense: SimpleIsDense, SideFixed: SimpleSideFixed, functional: [TRUE, isOneToOne], mutability: mutability ], dirable: [TRUE, TRUE] ]; ENDLOOP ENDLOOP ENDLOOP ENDLOOP; }; Start[]; END.