<> <> DIRECTORY AbSets, Atom, Basics, BiRelBasics, IntStuff, SetBasics; BiRels: CEDAR DEFINITIONS IMPORTS AbSets, BiRelBasics, IntStuff, SetBasics = {OPEN IntStuff, SetBasics, Sets:AbSets, Sets, BiRelBasics; <> EINT: TYPE ~ IntStuff.EINT; Value: TYPE ~ SetBasics.Value; Interval: TYPE ~ SetBasics.Interval; IntInterval: TYPE ~ SetBasics.IntInterval; Set: TYPE ~ Sets.Set; Direction: TYPE ~ Sets.Direction; Side: TYPE ~ Sets.Side; Pair: TYPE ~ BiRelBasics.Pair; noPair: READONLY Pair; LOP: TYPE ~ LIST OF Pair; MaybePair: TYPE ~ BiRelBasics.MaybePair; noMaybePair: READONLY MaybePair; TripleMaybePair: TYPE ~ BiRelBasics.TripleMaybePair; MaybePairInterval: TYPE ~ BiRelBasics.MaybePairInterval; MaybePairSpace: TYPE ~ BiRelBasics.MaybePairSpace; Had: TYPE ~ BiRelBasics.Had; HadPair: TYPE ~ BiRelBasics.HadPair; HadSetPair: TYPE ~ BiRelBasics.HadSetPair; IfHad: TYPE ~ BiRelBasics.IfHad; IfHadPair: TYPE ~ BiRelBasics.IfHadPair; alwaysAdd: IfHadPair ~ BiRelBasics.alwaysAdd; addIfNew: IfHadPair ~ BiRelBasics.addIfNew; addIfOld: IfHadPair ~ BiRelBasics.addIfOld; BoolPair: TYPE ~ BiRelBasics.BoolPair; SpacePair: TYPE ~ BiRelBasics.SpacePair; SetPair: TYPE ~ BiRelBasics.SetPair; PairInterval: TYPE ~ BiRelBasics.PairInterval; RelOrder: TYPE ~ BiRelBasics.RelOrder; TotalRelOrder: TYPE ~ BiRelBasics.TotalRelOrder; leftFwd: RelOrder ~ BiRelBasics.leftFwd; leftBwd: RelOrder ~ BiRelBasics.leftBwd; rightFwd: RelOrder ~ BiRelBasics.rightFwd; rightBwd: RelOrder ~ BiRelBasics.rightBwd; PairSpace: TYPE ~ BiRelBasics.PairSpace; <> BiRel: TYPE ~ RECORD [class: BiRelClass, data: REF ANY]; <> ConsBiRel: PROC [class: BiRelClass, data: REF ANY] RETURNS [BiRel]; <> nilBiRel: BiRel ~ [NIL, NIL]; badBiRel: READONLY BiRel; DeRef: PROC [ra: REF ANY] RETURNS [BiRel] ~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, RefBiRel]^ ELSE nilBiRel]}; Refify: PROC [br: BiRel] RETURNS [RefBiRel] ~ INLINE {RETURN [NEW [BiRel _ br]]}; <> Cant: ERROR [br: BiRel]; <> AsSet: PROC [br: BiRel, ro: RelOrder] RETURNS [Set--of REF Pair--] <> ~ INLINE {RETURN br.class.AsSet[br, ro]}; HasPair: PROC [br: BiRel, pair: Pair] RETURNS [BOOL] ~ INLINE {RETURN br.class.HasPair[br, pair]}; HasAA: PROC [br: BiRel, left, right: REF ANY] RETURNS [BOOL] ~ INLINE {RETURN br.class.HasPair[br, [AV[left], AV[right]]]}; HasIA: PROC [br: BiRel, left: INT, right: REF ANY] RETURNS [BOOL] ~ INLINE {RETURN br.class.HasPair[br, [IV[left], AV[right]]]}; HasII: PROC [br: BiRel, left, right: INT] RETURNS [BOOL] ~ INLINE {RETURN br.class.HasPair[br, [IV[left], IV[right]]]}; Image: PROC [br: BiRel, set: Set, dir: Direction _ leftToRight] RETURNS [Set] <> ~ INLINE {RETURN br.class.Image[br, set, dir]}; Mapping: PROC [br: BiRel, v: Value, dir: Direction _ leftToRight] RETURNS [Set] <> ~ INLINE {RETURN br.class.Image[br, Sets.CreateSingleton[v, br.Spaces[][Source[dir]]], dir]}; MappingA: PROC [br: BiRel, v: REF ANY, dir: Direction _ leftToRight] RETURNS [Set] ~ INLINE {RETURN br.class.Image[br, Sets.CreateSingleton[AV[v], br.Spaces[][Source[dir]]], dir]}; MappingI: PROC [br: BiRel, v: INT, dir: Direction _ leftToRight] RETURNS [Set] ~ INLINE {RETURN br.class.Image[br, Sets.CreateSingleton[IV[v], br.Spaces[][Source[dir]]], dir]}; Enumerate: PROC [br: BiRel, Consume: PROC [Pair], ro: RelOrder _ []]; <> EnumAA: PROC [br: BiRel, Consume: PROC [REF ANY, REF ANY], ro: RelOrder _ []]; EnumIA: PROC [br: BiRel, Consume: PROC [INT, REF ANY], ro: RelOrder _ []]; EnumII: PROC [br: BiRel, Consume: PROC [INT, INT], ro: RelOrder _ []]; Tester: TYPE ~ PROC [Pair] RETURNS [BOOL]; AcceptAny: Tester--={RETURN[TRUE]}--; Scan: PROC [br: BiRel, Test: Tester, ro: RelOrder _ []] RETURNS [MaybePair] ~ INLINE {RETURN br.class.ScanRestriction[br, [], Test, ro]}; EnumerateImage: PROC [br: BiRel, set: Set, Consume: PROC [Value], dir: Direction _ leftToRight, ro: Sets.RelOrder _ no]; EnumerateMapping: PROC [br: BiRel, v: Value, Consume: PROC [Value], dir: Direction _ leftToRight, ro: Sets.RelOrder _ no] ~ INLINE {EnumerateImage[br, Sets.CreateSingleton[v, br.Spaces[][Source[dir]]], Consume, dir, ro]}; EnumerateHalfRestriction: PROC [br: BiRel, set: Set, Consume: PROC [Pair], side: Side _ left, ro: RelOrder _ []]; <> ScanImage: PROC [br: BiRel, set: Set, Test: Sets.Tester, dir: Direction _ leftToRight, ro: Sets.RelOrder _ no] RETURNS [MaybePair]; ScanMapping: PROC [br: BiRel, v: Value, Test: Sets.Tester, dir: Direction _ leftToRight, ro: Sets.RelOrder _ no] RETURNS [MaybePair] ~ INLINE {RETURN ScanImage[br, Sets.CreateSingleton[v, br.Spaces[][Source[dir]]], Test, dir, ro]}; ScanRestriction: PROC [br: BiRel, sets: SetPair _ [], Test: Tester, ro: RelOrder _ []] RETURNS [MaybePair] <> ~ INLINE {RETURN br.class.ScanRestriction[br, sets, Test, ro]}; ScanHalfRestriction: PROC [br: BiRel, set: Set, Test: Tester, side: Side _ left, ro: RelOrder _ []] RETURNS [MaybePair] ~ INLINE {RETURN br.class.ScanRestriction[br, ConsSets[side, set], Test, ro]}; ParallelScan: PROC [a, b: BiRel, Test: ParallelTester, roA, roB: RelOrder _ []] RETURNS [ParallelFind] ~ INLINE {RETURN ParallelScanRestriction[a, b, Test, [], [], roA, roB]}; ParallelScanRestriction: PROC [a, b: BiRel, Test: ParallelTester, setsA, setsB: SetPair _ [], roA, roB: RelOrder _ []] RETURNS [ParallelFind]; ParallelTester: TYPE ~ PROC [a, b: MaybePair] RETURNS [pass: BOOL _ FALSE]; ParallelFind: TYPE ~ RECORD [found: BOOL, a, b: MaybePair]; InterleavedProduceRestriction: PROC [a, b: BiRel, Consume: InterleavedConsumer, setsA, setsB: SetPair _ [], roA, roB: RelOrder _ []] RETURNS [MaybePair]; InterleavedConsumer: TYPE ~ PROC [PROC [Which] RETURNS [MaybePair]] RETURNS [MaybePair]; GetOne: PROC [br: BiRel, remove: BOOL, ro: RelOrder] RETURNS [MaybePair] ~ INLINE {RETURN br.class.GetOne[br, remove, ro]}; APair: PROC [br: BiRel, ro: RelOrder _ []] RETURNS [MaybePair] ~ INLINE {RETURN br.class.GetOne[br, FALSE, ro]}; Pop: PROC [br: BiRel, ro: RelOrder _ []] RETURNS [MaybePair] ~ INLINE {RETURN br.class.GetOne[br, TRUE, ro]}; First: PROC [br: BiRel] RETURNS [MaybePair] ~ INLINE {RETURN br.class.GetOne[br, FALSE, [ALL[fwd]]]}; Last: PROC [br: BiRel] RETURNS [MaybePair] ~ INLINE {RETURN br.class.GetOne[br, FALSE, [ALL[bwd]]]}; Next: PROC [br: BiRel, pair: Pair, ro: RelOrder _ [[fwd, no]]] RETURNS [MaybePair] ~ INLINE {RETURN [br.class.Get3[br, pair, ro, [FALSE, FALSE, TRUE]].next]}; Prev: PROC [br: BiRel, pair: Pair, ro: RelOrder _ [[fwd, no]]] RETURNS [MaybePair] ~ INLINE {RETURN [br.class.Get3[br, pair, ro, [TRUE, FALSE, FALSE]].prev]}; Get3: PROC [br: BiRel, pair: Pair, ro: RelOrder _ [[fwd, no]], want: TripleBool _ []] RETURNS [TripleMaybePair] ~ INLINE {RETURN br.class.Get3[br, pair, ro, want]}; SkipTo: PROC [br: BiRel, goal: Set, bounds: Interval _ fullInterval, side: Side _ left, bwd: BOOL _ FALSE] RETURNS [MaybePair] <> ~ INLINE {RETURN br.ScanRestriction[ConsSets[side, IntervalAsSet[br.Spaces[][side], bounds], goal], AcceptAny, ConsRelOrder[side, IF bwd THEN bwd ELSE fwd]]}; Lookup: PROC [br: BiRel, goal: Value, bounds: Interval _ fullInterval, side: Side _ left, bwd: BOOL _ FALSE] RETURNS [MaybeValue] ~ INLINE {RETURN br.SkipTo[Sets.CreateSingleton[goal, br.Spaces[][side]], bounds, side, bwd].KeepHalf[OtherSide[side]]}; Size: PROC [br: BiRel, limit: EINT _ lastEINT] RETURNS [EINT] ~ INLINE {RETURN [br.class.RestrictionSize[br, [], limit]]}; Empty: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.Size[one]=zero]}; RestrictionSize: PROC [br: BiRel, sets: SetPair _ [], limit: EINT _ lastEINT] RETURNS [EINT] ~ INLINE {RETURN br.class.RestrictionSize[br, sets, limit]}; ImageSize: PROC [br: BiRel, set: Set, dir: Direction _ leftToRight, limit: EINT _ lastEINT] RETURNS [EINT]; MappingSize: PROC [br: BiRel, v: Value, dir: Direction _ leftToRight, limit: EINT _ lastEINT] RETURNS [EINT] ~ INLINE {RETURN ImageSize[br, Sets.CreateSingleton[v, br.Spaces[][Source[dir]]], dir, limit]}; MappingEmpty: PROC [br: BiRel, v: Value, dir: Direction _ leftToRight] RETURNS [BOOL] ~ INLINE {RETURN [MappingSize[br, v, dir, one]=zero]}; IsDense: PROC [br: BiRel, when: When _ always, side: Side _ left] RETURNS [BOOL] <> ~ INLINE {RETURN br.class.IsDense[br, when, side]}; denseSide: READONLY ROPE; --complaint raised when a caller tries an operation that would put a hole in a necessarily dense side of a BiRel. SideFixed: PROC [br: BiRel, side: Side _ left] RETURNS [BOOL] < br.SetOn[side] won't change.>> ~ INLINE {RETURN br.class.SideFixed[br, side]}; fixedSide: READONLY ROPE; --complaint raised when a caller tries an operation that would change a fixed side of a BiRel. GetBounds: PROC [br: BiRel, want: EndBools _ [], ro: RelOrder _ [[fwd, no]]] RETURNS [MaybePairInterval] ~ INLINE {RETURN br.class.GetBounds[br, want, ro]}; MutabilityOf: PROC [br: BiRel] RETURNS [Mutability] ~ INLINE {RETURN [br.class.mutability]}; Copy: PROC [br: BiRel] RETURNS [VarBiRel] ~ INLINE {RETURN br.class.Copy[br]}; Insulate: PROC [br: BiRel] RETURNS [UWBiRel] ~ INLINE {RETURN br.class.Insulate[br]}; ValueOf: PROC [br: BiRel] RETURNS [ConstBiRel] ~ INLINE {RETURN br.class.ValueOf[br]}; Freeze: PROC [br: BiRel] RETURNS [ConstBiRel] ~ INLINE {RETURN br.class.Freeze[br]}; Thaw: PROC [br: BiRel] ~ INLINE {br.class.Thaw[br]}; Has: PROC [br, other: BiRel, want: BoolPair] RETURNS [HadSetPair]; AddPair: PROC [br: BiRel, pair: Pair, if: IfHadPair _ alwaysAdd] RETURNS [had: HadPair] <> ~ INLINE {RETURN br.class.AddPair[br, pair, if]}; AddAA: PROC [br: BiRel, left, right: REF ANY, if: IfHadPair _ alwaysAdd] RETURNS [had: HadPair]; AddIA: PROC [br: BiRel, left: INT, right: REF ANY, if: IfHadPair _ alwaysAdd] RETURNS [had: HadPair]; AddII: PROC [br: BiRel, left, right: INT, if: IfHadPair _ alwaysAdd] RETURNS [had: HadPair]; AddNewPair: PROC [br: BiRel, pair: Pair]; <> AddNewAA: PROC [br: BiRel, left, right: REF ANY]; AddNewIA: PROC [br: BiRel, left: INT, right: REF ANY]; AddNewII: PROC [br: BiRel, left, right: INT]; AddSet: PROC [br, other: BiRel, if: IfHadPair _ alwaysAdd] RETURNS [some: HadSetPair] <> ~ INLINE {RETURN br.class.AddSet[br, other, if]}; AddNewSet: PROC [br, other: BiRel]; <> Swap: PROC [br: BiRel, a, b: Value, side: Side _ left] < br after HasPair[[a, v]] iff br before HasPair[[b, v]], and so on.>> ~ INLINE {br.class.Swap[br, a, b, side]}; RemPair: PROC [br: BiRel, pair: Pair] RETURNS [had: HadPair] ~ INLINE {RETURN br.class.RemPair[br, pair]}; RemAA: PROC [br: BiRel, left, right: REF ANY] RETURNS [had: HadPair]; RemIA: PROC [br: BiRel, left: INT, right: REF ANY] RETURNS [had: HadPair]; RemII: PROC [br: BiRel, left, right: INT] RETURNS [had: HadPair]; RemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair] <> ~ INLINE {RETURN br.class.RemSet[br, other]}; Erase: PROC [br: BiRel] ~ INLINE {[] _ br.RemSet[br]}; Delete: PROC [br: BiRel, val: Value, side: Side _ left] RETURNS [hadSome: BOOL] <> ~ INLINE {RETURN br.class.Delete[br, val, side]}; DeleteA: PROC [br: BiRel, val: REF ANY, side: Side _ left] RETURNS [hadSome: BOOL] ~ INLINE {RETURN br.class.Delete[br, AV[val], side]}; DeleteI: PROC [br: BiRel, val: INT, side: Side _ left] RETURNS [hadSome: BOOL] ~ INLINE {RETURN br.class.Delete[br, IV[val], side]}; DeleteSet: PROC [br: BiRel, set: Set, side: Side _ left] RETURNS [had: SomeAll] ~ INLINE {RETURN br.class.DeleteSet[br, set, side]}; Spaces: PROC [br: BiRel] RETURNS [SpacePair] <> ~ INLINE {RETURN br.class.Spaces[br]}; SetOn: PROC [br: BiRel, side: Side] RETURNS [UWSet] <> ~ INLINE {RETURN [br.class.SetOn[br, side]]}; CurSetOn: PROC [br: BiRel, side: Side] RETURNS [ConstSet] <> ~ INLINE {RETURN br.class.CurSetOn[br, side]}; Functional: PROC [br: BiRel] RETURNS [BoolPair] < br can't have two pairs with equivalent left Values and non-equivalent right Values.>> ~ INLINE {RETURN [br.class.functional]}; Equal: PROC [a, b: BiRel, bounds: SetPair _ []] RETURNS [BOOL]; <<>> Hash: PROC [br: BiRel, bounds: SetPair _ []] RETURNS [CARDINAL]; Compare: PROC [a, b: BiRel, bounds: SetPair _ [], tro: TotalRelOrder _ [ALL[fwd]]] RETURNS [Comparison]; CreateBiRelSpace: PROC [eltSpaces: SpacePair] RETURNS [Space]; QuaBiRelSpace: PROC [Space] RETURNS [found: BOOL, eltSpaces: SpacePair]; <> SetIsBiRel: PROC [set: Set] RETURNS [BOOL] ~ INLINE {RETURN [set.class.QuaBiRel[set].found]}; SetAsBiRel: PROC [set: Set] RETURNS [BiRel] ~ INLINE {RETURN [SetQuaBiRel[set].it]}; SetQuaBiRel: PROC [set: Set] RETURNS [MaybeBiRel] ~ INLINE { found: BOOL; class, data: REF ANY; [found, class, data] _ set.class.QuaBiRel[set]; RETURN [IF found THEN [TRUE, [NARROW[class], data]] ELSE [FALSE, badBiRel]]}; <> VarBiRel: TYPE ~ RECORD [BiRel] --a variable BiRel--; IsVar: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.mutability=variable]}; AsVar: PROC [br: BiRel] RETURNS [VarBiRel] ~ INLINE {IF br#nilBiRel AND br.class.mutability#variable THEN Complain[br, notVariable]; RETURN [[br]]}; UWBiRel: TYPE ~ RECORD [BiRel] --an unwritable BiRel--; IsUW: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.mutability#variable]}; AsUW: PROC [br: BiRel] RETURNS [UWBiRel] ~ INLINE {IF br#nilBiRel AND br.class.mutability=variable THEN Complain[br, writeable]; RETURN [[br]]}; ConstBiRel: TYPE ~ RECORD [UWBiRel] --a constant BiRel--; IsConst: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.mutability=constant]}; AsConst: PROC [br: BiRel] RETURNS [ConstBiRel] ~ INLINE {IF br#nilBiRel AND br.class.mutability#constant THEN Complain[br, notConstant]; RETURN [[[br]]]}; Function: TYPE ~ BiRel --a BiRel that doesn't have two pairs with equal left sides--; VarFunction: TYPE ~ VarBiRel; UWFunction: TYPE ~ UWBiRel; ConstFunction: TYPE ~ ConstBiRel; IsFunction: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.functional[leftToRight]]}; AsFunction: PROC [br: BiRel] RETURNS [Function] ~ INLINE {IF NOT br.class.functional[leftToRight] THEN br.Complain[narrowFault]; RETURN [br]}; InvFunction: TYPE ~ BiRel --a BiRel that doesn't have two pairs with equal right sides--; IsInvFunction: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.functional[rightToLeft]]}; AsInvFunction: PROC [br: BiRel] RETURNS [InvFunction] ~ INLINE {IF NOT br.class.functional[rightToLeft] THEN br.Complain[narrowFault]; RETURN [br]}; OneToOne: TYPE ~ BiRel --a one-to-one BiRel--; VarOneToOne: TYPE ~ VarBiRel; ConstOneToOne: TYPE ~ ConstBiRel; IsOneToOne: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.class.functional=ALL[TRUE]]}; AsOneToOne: PROC [br: BiRel] RETURNS [OneToOne] ~ INLINE {IF NOT br.class.functional=ALL[TRUE] THEN br.Complain[narrowFault]; RETURN [br]}; Apply: PROC [br: BiRel, v: Value, dir: Direction _ leftToRight] RETURNS [MaybeValue] <> ~ INLINE {RETURN br.class.Apply[br, v, dir]}; mappingNotSingleton: READONLY ROPE; ApplyA: PROC [br: BiRel, v: REF ANY, dir: Direction _ leftToRight] RETURNS [MaybeValue] ~ INLINE {RETURN br.class.Apply[br, AV[v], dir]}; ApplyI: PROC [br: BiRel, v: INT, dir: Direction _ leftToRight] RETURNS [MaybeValue] ~ INLINE {RETURN br.class.Apply[br, IV[v], dir]}; IntRel: TYPE ~ BiRel --where left side may only contain integers--; IsIntRel: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [QuaIntRel[br].found]}; AsIntRel: PROC [br: BiRel] RETURNS [IntRel] ~ INLINE {RETURN [QuaIntRel[br].it]}; QuaIntRel: PROC [br: BiRel] RETURNS [MaybeBiRel]; GetIntDom: PROC [br: BiRel, want: EndBools _ []] RETURNS [IntInterval]; ShiftAndClipMe: PROC [br: IntRel, shift: EINT _ zero, clip: IntInterval _ []] <> ~ INLINE {br.class.ShiftAndClipMe[br, shift, clip]}; Index: PROC [br, goal: IntRel, bounds: IntInterval _ [], bwd: BOOL _ FALSE] RETURNS [MaybeValue] <> ~ INLINE {RETURN br.class.Index[br, goal, bounds, bwd]}; ReplaceMe: PROC [br, with: IntRel, where: IntInterval] <> <> <> <> <> <> ~ INLINE {br.class.ReplaceMe[br, with, where]}; Insert: PROC [br: IntRel, val: Value, before: INT] ~ INLINE {[] _ ReplaceMe[br, CreateSingleton[[[i: 0], val], br.Spaces], [before, before-1]]}; Append: PROC [br: IntRel, val: Value] ~ INLINE {Insert[br, val, br.GetIntDom.max+1]}; AppendA: PROC [br: IntRel, val: REF ANY] ~ INLINE {Insert[br, AV[val], br.GetIntDom.max+1]}; AppendI: PROC [br: IntRel, val: INT] ~ INLINE {Insert[br, IV[val], br.GetIntDom.max+1]}; IntFn: TYPE ~ IntRel --that is Functional[leftToRight]--; ConstIntFn: TYPE ~ ConstBiRel; IsIntFn: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [QuaIntFn[br].found]}; AsIntFn: PROC [br: BiRel] RETURNS [IntFn] ~ INLINE {RETURN [QuaIntFn[br].it]}; QuaIntFn: PROC [br: BiRel] RETURNS [MaybeBiRel]; Array: TYPE ~ IntFn --whose domain is an interval--; IsArray: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [IsIntFn[br] AND br.IsDense[now, left]]}; AsArray: PROC [br: BiRel] RETURNS [Array] ~ INLINE {IF NOT (IsIntFn[br] AND br.IsDense[now, left]) THEN br.Complain[narrowFault]; RETURN [br]}; FixedArray: TYPE ~ Array --whose domain will never change--; IsFixedArray: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [IsIntFn[br] AND br.IsDense[always, left] AND br.SideFixed[left]]}; AsFixdArray: PROC [br: BiRel] RETURNS [FixedArray] ~ INLINE {IF NOT IsFixedArray[br] THEN br.Complain[narrowFault]; RETURN [br]}; Sequence: TYPE ~ Array --whose lower bound is 0--; IsSequence: PROC [br: BiRel] RETURNS [BOOL] ~ INLINE {RETURN [br.IsArray AND br.GetIntDom[].min=0]}; Automorphism: TYPE ~ BiRel--that's one-to-one, and domain = range--; Permutation: TYPE ~ Sequence--that's an Automorphism--; GradeUp: PROC [a: IntFn, o: SetBasics.Order] RETURNS [p: Permutation]; <> TransPermute: PROC [from: IntFn, to: Sequence, p: Permutation]; <> PermuteInPlace: PROC [a: Sequence, p: Permutation]; <> CreateEmptyBiRel: PROC [SpacePair] RETURNS [ConstBiRel]; CreateIDSubset: PROC [Set] RETURNS [BiRel]; IsIDSubset: PROC [BiRel] RETURNS [BOOL]; CreateFullIDSubset: PROC [s: Space] RETURNS [ConstOneToOne] ~ INLINE {RETURN [CreateIDSubset[CreateFullSet[s]].AsConst]}; CreateAllPairs: PROC [SpacePair] RETURNS [ConstOneToOne]; CreateSingleton: PROC [elt: Pair, spaces: SpacePair] RETURNS [ConstBiRel] ~ INLINE {RETURN [[[[GetSingletonClass[spaces], NEW [Pair _ elt]]]]]}; GetSingletonClass: PROC [spaces: SpacePair] RETURNS [BiRelClass]; NCreateSingleton: PROC [elt: Pair, spaces: SpacePair] RETURNS [ConstBiRel]; CreateConstant: PROC [bounds: Interval, val: Value, spaces: SpacePair _ [ints, refs]] RETURNS [ConstIntFn] ~ INLINE {RETURN CreateProduct[[IntervalAsSet[spaces[left], bounds], Sets.CreateSingleton[val, spaces[right]]]].AsConst}; CreateProduct: PROC [SetPair] RETURNS [BiRel]; FnFromProc: PROC [ Apply: PROC [data: REF ANY, v: Value] RETURNS [mv: MaybeValue], spaces: SpacePair _ [refs, refs], data: REF ANY _ NIL, constant, oneToOne: BOOL _ FALSE, ScanInverse: PROC [data: REF ANY, v: Value, Test: Tester] RETURNS [MaybePair] _ NIL ] RETURNS [Function]; CreateSimple: PROC [bounds: IntInterval _ [0, -1], val: Value _ noValue, oneToOne, dense, domainFixed: BOOL _ FALSE, rightSpace: Space _ refs] RETURNS [IntFn]; CreateSimpleCopy: PROC [of: IntFn, bounds: IntInterval _ [], oneToOne, dense, domainFixed: RelBool _ SAME, rightSpace: Space _ NIL] RETURNS [IntFn]; <> CreateList: PROC [vals: LOP, functional: BoolPair _ [FALSE, FALSE], spaces: SpacePair _ [refs, refs], mutability: Mutability _ variable, order: RelOrder _ [], assumeSorted: BOOL _ FALSE] RETURNS [VarBiRel]; HashFn: TYPE ~ VarFunction; CreateHashReln: PROC [spaces: SpacePair _ [refs, refs], functional: BoolPair _ [FALSE, FALSE], mappable: BoolPair _ [TRUE, TRUE]] RETURNS [VarBiRel]; <<(functional[dir] OR mappable[dir]) tells whether the result can Image in direction dir.>> CreateHashOTO: PROC [spaces: SpacePair _ [refs, refs]] RETURNS [VarOneToOne] ~ INLINE {RETURN CreateHashReln[spaces, ALL[TRUE]]}; CreateHashFn: PROC [spaces: SpacePair _ [refs, refs], invable: BOOL _ TRUE] RETURNS [HashFn] ~ INLINE {RETURN CreateHashReln[spaces, [TRUE, FALSE], [TRUE, invable]]}; CreateHashTable: PROC [right: Space _ refs, invable: BOOL _ TRUE] RETURNS [HashFn] ~ INLINE {RETURN CreateHashReln[[refs, right], [TRUE, FALSE], [TRUE, invable]]}; CreateHashDictionary: PROC [case: BOOL _ TRUE, right: Space _ refs, invable: BOOL _ TRUE] RETURNS [HashFn] ~ INLINE {RETURN CreateHashReln[[ropes[case], right], [TRUE, FALSE], [TRUE, invable]]}; CreateHashCopy: PROC [br: BiRel, spaces: SpacePair _ [NIL, NIL], mappable: BoolPair _ [FALSE, FALSE]] RETURNS [HashFn]; <> <> Union: PROC [a, b: BiRel, disjoint: BOOL _ FALSE, ro: RelOrder _ []] RETURNS [UWBiRel]; Intersection: PROC [BiRel, BiRel] RETURNS [UWBiRel]; Difference: PROC [BiRel, BiRel] RETURNS [UWBiRel]; SymmetricDifference: PROC [a, b: BiRel] RETURNS [c: UWBiRel]; Negate: PROC [BiRel] RETURNS [BiRel]; Compose: PROC [left, right: BiRel, restricts: ARRAY Side OF BOOL _ [TRUE, TRUE]] RETURNS [BiRel]; <> Invert: PROC [BiRel] RETURNS [BiRel]; Collect: PROC [u: BiRel, side: Side _ right] RETURNS [c: Function]; <> UnCollect: PROC [c: Function, side: Side _ right] RETURNS [u: BiRel]; <> Replace: PROC [br, with: IntRel, where: IntInterval] RETURNS [IntRel]; ShiftAndClip: PROC [br: IntRel, shift: EINT _ zero, clip: IntInterval _ []] RETURNS [IntRel]; <> CreateShiftAndClipper: PROC [shift: EINT _ zero, clip: IntInterval _ []] RETURNS [ConstOneToOne]; <> Shift: PROC [br: IntRel, shift: EINT] RETURNS [IntRel] <> ~ INLINE {RETURN ShiftAndClip[br, shift]}; Subseq: PROC [br: IntRel, bounds: IntInterval] RETURNS [IntRel] ~ INLINE {RETURN ShiftAndClip[br, IE[bounds.min].Neg, bounds]}; ImplementSetBySequence: PROC [seq: Sequence, addat: SeqAddPlace, closeGaps: BOOL] RETURNS [Set]; SeqAddPlace: TYPE ~ {front, back}; ImplementSetByIDSubset: PROC [ids: OneToOne] RETURNS [Set]; EnumSeqOfSet: PROC [set: Set, ro: Sets.RelOrder _ no] RETURNS [Sequence]; <> <> BiRelClass: TYPE ~ REF BiRelClassPrivate; BiRelClassPrivate: TYPE ~ MONITORED RECORD [ Primitive: PROC [br: BiRel, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [PrimitiveAnswer] _ NIL, AsSet: PROC [br: BiRel, ro: RelOrder] RETURNS [Set--of REF Pair--] _ NIL, HasPair: PROC [br: BiRel, pair: Pair] RETURNS [BOOL] _ NIL, Image: PROC [br: BiRel, set: Set, dir: Direction] RETURNS [Set] _ NIL, Apply: PROC [br: BiRel, v: Value, dir: Direction] RETURNS [MaybeValue] _ NIL, ScanRestriction: PROC [br: BiRel, sets: SetPair, Test: Tester, ro: RelOrder] RETURNS [MaybePair] _ NIL, GetOne: PROC [br: BiRel, remove: BOOL, ro: RelOrder] RETURNS [MaybePair] _ NIL, Get3: PROC [br: BiRel, pair: Pair, ro: RelOrder, want: TripleBool] RETURNS [TripleMaybePair] _ NIL, Index: PROC [br, goal: IntRel, bounds: IntInterval, bwd: BOOL] RETURNS [MaybeValue] _ NIL, RestrictionSize: PROC [br: BiRel, sets: SetPair, limit: EINT] RETURNS [EINT] _ NIL, GetBounds: PROC [br: BiRel, want: EndBools, ro: RelOrder] RETURNS [MaybePairInterval] _ NIL, Copy: PROC [br: BiRel] RETURNS [VarBiRel] _ NIL, Insulate: PROC [br: BiRel] RETURNS [UWBiRel] _ NIL, ValueOf: PROC [br: BiRel] RETURNS [ConstBiRel] _ NIL, Freeze: PROC [br: BiRel] RETURNS [ConstBiRel] _ NIL, Thaw: PROC [br: BiRel] _ NIL, SetOn: PROC [br: BiRel, side: Side] RETURNS [UWSet] _ NIL, CurSetOn: PROC [br: BiRel, side: Side] RETURNS [ConstSet] _ NIL, AddPair: PROC [br: BiRel, pair: Pair, if: IfHadPair] RETURNS [had: HadPair] _ NIL, AddSet: PROC [br, other: BiRel, if: IfHadPair] RETURNS [some: HadSetPair] _ NIL, Swap: PROC [br: BiRel, a, b: Value, side: Side] _ NIL, RemPair: PROC [br: BiRel, pair: Pair] RETURNS [had: HadPair] _ NIL, RemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair] _ NIL, Delete: PROC [br: BiRel, val: Value, side: Side] RETURNS [hadSome: BOOL] _ NIL, DeleteSet: PROC [br: BiRel, set: Set, side: Side] RETURNS [had: SomeAll] _ NIL, ReplaceMe: PROC [br, with: IntRel, where: IntInterval] _ NIL, ShiftAndClipMe: PROC [br: BiRel, shift: EINT, clip: IntInterval] _ NIL, Spaces: PROC [br: BiRel] RETURNS [SpacePair] _, IsDense: PROC [br: BiRel, when: When, side: Side] RETURNS [BOOL] _ NIL, SideFixed: PROC [br: BiRel, side: Side] RETURNS [BOOL] _ NIL, functional: BoolPair _ [FALSE, FALSE], mutability: Mutability _ variable, other: Atom.PropList _ NIL, --the canonical expansion slot data: REF ANY _ NIL ]; <> CreateClass: PROC [cp: BiRelClassPrivate, dirable: BoolPair _ [TRUE, FALSE]] RETURNS [BiRelClass]; <> DefaultAsSet: PROC [br: BiRel, ro: RelOrder] RETURNS [Set--of REF Pair--]; DefaultHasPair: PROC [br: BiRel, pair: Pair] RETURNS [BOOL]; DefaultImage: PROC [br: BiRel, set: Set, dir: Direction] RETURNS [Set]; DefaultApply: PROC [br: BiRel, v: Value, dir: Direction] RETURNS [MaybeValue]; DefaultScanRestriction: PROC [br: BiRel, sets: SetPair, Test: Tester, ro: RelOrder] RETURNS [MaybePair]; DefaultGetOne: PROC [br: BiRel, remove: BOOL, ro: RelOrder] RETURNS [MaybePair]; DefaultGet3: PROC [br: BiRel, pair: Pair, ro: RelOrder, want: TripleBool] RETURNS [TripleMaybePair]; DefaultIndex: PROC [br, goal: IntRel, bounds: IntInterval, bwd: BOOL] RETURNS [MaybeValue]; DefaultRestrictionSize: PROC [br: BiRel, sets: SetPair, limit: EINT] RETURNS [EINT]; DefaultGetBounds: PROC [br: BiRel, want: EndBools, ro: RelOrder] RETURNS [MaybePairInterval]; DefaultCopy: PROC [br: BiRel] RETURNS [VarBiRel]; DefaultInsulate: PROC [br: BiRel] RETURNS [UWBiRel]; DefaultValueOf: PROC [br: BiRel] RETURNS [ConstBiRel]; DefaultFreeze: PROC [br: BiRel] RETURNS [ConstBiRel]; DefaultThaw: PROC [br: BiRel]; DefaultSetOn: PROC [br: BiRel, side: Side] RETURNS [UWSet]; DefaultCurSetOn: PROC [br: BiRel, side: Side] RETURNS [ConstSet]; DefaultAddPair: PROC [br: BiRel, pair: Pair, if: IfHadPair] RETURNS [had: HadPair]; DefaultAddSet: PROC [br, other: BiRel, if: IfHadPair] RETURNS [some: HadSetPair]; DefaultSwap: PROC [br: BiRel, a, b: Value, side: Side]; DefaultRemPair: PROC [br: BiRel, pair: Pair] RETURNS [had: HadPair]; DefaultRemSet: PROC [br, other: BiRel] RETURNS [some: HadSetPair]; DefaultDelete: PROC [br: BiRel, val: Value, side: Side] RETURNS [hadSome: BOOL]; DefaultDeleteSet: PROC [br: BiRel, set: Set, side: Side] RETURNS [had: SomeAll]; DefaultReplaceMe: PROC [br, with: IntRel, where: IntInterval]; DefaultShiftAndClipMe: PROC [br: BiRel, shift: EINT, clip: IntInterval]; DefaultIsDense: PROC [br: BiRel, when: When, side: Side] RETURNS [BOOL]; DefaultSideFixed: PROC [br: BiRel, side: Side] RETURNS [BOOL]; UpdateBiRelClassOther: PROC [class: BiRelClass, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]]; <> QualityOf: PROC [br: BiRel, op: ATOM, arg1, arg2, arg3, arg4: REF ANY _ NIL] RETURNS [ImplQuality]; <> <> <> RefBiRel: TYPE ~ REF BiRel; RefSetPair: TYPE ~ REF SetPair; refNilSets: READONLY RefSetPair; ToSide: PROC [arg: REF ANY, default: Side _ left] RETURNS [Side]; ToDir: PROC [arg: REF ANY, default: Direction _ leftToRight] RETURNS [Direction]; ToBiRel: PROC [arg: REF ANY] RETURNS [RefBiRel]; ToSets: PROC [arg: REF ANY, default: RefSetPair _ refNilSets] RETURNS [RefSetPair]; ToRO: PROC [arg: REF ANY, default: RelOrder _ []] RETURNS [RelOrder]; FromSide: PROC [side: Side] RETURNS [ATOM] ~ INLINE {RETURN [IF side=left THEN $left ELSE $right]}; FromDir: PROC [dir: Direction] RETURNS [ATOM] ~ INLINE {RETURN [IF dir=leftToRight THEN $leftToRight ELSE $rightToLeft]}; FakeSingleton: PROC [sp: SpacePair] RETURNS [ConstBiRel] ~ INLINE {RETURN CreateSingleton[noPair, sp]}; FakeRefSingleton: PROC [sp: SpacePair] RETURNS [RefBiRel] ~ INLINE {RETURN CreateSingleton[noPair, sp].Refify}; FromSets: PROC [sp: SetPair] RETURNS [RefSetPair]; FromRO: PROC [ro: RelOrder] RETURNS [ATOM]; <> Can: PROC [br: BiRel, op: ATOM, arg1, arg2, arg3, arg4: REF ANY _ NIL] RETURNS [BOOL] ~ INLINE {RETURN [QualityOf[br, op, arg1, arg2, arg3, arg4]#cant]}; GoodImpl: PROC [br: BiRel, op: ATOM, arg1, arg2, arg3, arg4: REF ANY _ NIL] RETURNS [BOOL] ~ INLINE {RETURN [QualityOf[br, op, arg1, arg2, arg3, arg4]>=goodDefault]}; Primitive: PROC [br: BiRel, op: ATOM, arg1, arg2: REF ANY _ NIL] RETURNS [BOOL]; <> Complain: PROC [br: BiRel, msg: ROPE, args: LOV _ NIL] ~ INLINE {Error[msg, CONS[AV[br.Refify], args]]}; MaybeBiRel: TYPE ~ RECORD [found: BOOL, it: BiRel]; }.