<> <> DIRECTORY Atom, Basics, Collections, IntStuff, PairCollections; IntFunctions: CEDAR DEFINITIONS IMPORTS Collections, IntStuff, PairCollections = {OPEN Colls:Collections, Collections, PairColls:PairCollections, PairCollections, Ints:IntStuff, IntStuff; <> EINT: TYPE ~ Ints.EINT; Interval: TYPE ~ Ints.Interval; XForm: TYPE ~ Ints.XForm; IVPair: TYPE ~ RECORD [left: INT, right: Value]; noPair: READONLY IVPair -- = ["this interface makes no attempt to define an exceptional INT, so there's nothing good to put here, and I'm not telling you what's actually used", noValue] --; IntFn: TYPE ~ RECORD [class: IntFnClass, data: Value]; <> nilIntFn: IntFn ~ [NIL, NIL]; DeRef: PROC [ra: REF ANY] RETURNS [IntFn] ~ INLINE {RETURN [IF ra#NIL THEN NARROW[ra, REF IntFn]^ ELSE nilIntFn]}; Refify: PROC [fn: IntFn] RETURNS [ref: REF ANY] ~ INLINE {ref _ NEW [IntFn _ fn]}; MaybeInt: TYPE ~ RECORD [found: BOOL, i: INT]; noInt: READONLY MaybeInt; I: PROC [m: MaybeInt] RETURNS [INT] ~ INLINE {RETURN [IF m.found THEN m.i ELSE Error[notFound, NIL]]}; MaybePair: TYPE ~ RECORD [found: BOOL, pair: IVPair]; noMaybePair: READONLY MaybePair -- = [FALSE, noPair]--; DropVal: PROC [mp: MaybePair] RETURNS [MaybeInt] ~ INLINE {RETURN [[mp.found, mp.pair.left]]}; DropKey: PROC [mp: MaybePair] RETURNS [MaybeValue] ~ INLINE {RETURN [[mp.found, mp.pair.right]]}; P: PROC [mp: MaybePair] RETURNS [IVPair] ~ INLINE {RETURN [IF mp.found THEN mp.pair ELSE Error[notFound, NIL]]}; DP: PROC [mp: MaybePair, ifNotFound: IVPair _ [INT.FIRST, NIL]] RETURNS [IVPair] ~ INLINE {RETURN [IF mp.found THEN mp.pair ELSE ifNotFound]}; <> Cant: ERROR [fn: IntFn]; <> QualityOf: PROC [fn: IntFn, op: ATOM, args: ArgList _ NIL] RETURNS [ImplQuality]; <> Restriction: TYPE ~ {unrestricted, filtered, restricted, tiny}; <> FromRestriction: PROC [Restriction] RETURNS [ATOM]; GetRestriction: PROC [args: ArgList, i: NAT, default: Restriction _ unrestricted] RETURNS [Restriction]; Can: PROC [fn: IntFn, op: ATOM, args: ArgList _ NIL] RETURNS [BOOL] ~ INLINE {RETURN [QualityOf[fn, op, args]#cant]}; Widen: PROC [fn: IntFn] RETURNS [Function--[left]: REF INT--] ~ INLINE {RETURN fn.class.Widen[fn]}; HasPair: PROC [fn: IntFn, pair: IVPair] RETURNS [BOOL] ~ INLINE {RETURN fn.class.HasPair[fn, pair]}; Apply: PROC [fn: IntFn, i: INT] RETURNS [MaybeValue] ~ INLINE {RETURN fn.class.Apply[fn, i]}; InvApply: PROC [fn: IntFn, v: Value] RETURNS [MaybeInt] <> ~ INLINE {RETURN fn.class.InvApply[fn, v]}; Ordered: PROC [fn: IntFn] RETURNS [BOOL] <> ~ INLINE {RETURN [fn.class.ordered]}; Enumerate: PROC [fn: IntFn, Consume: PROC [IVPair], left: Interval _ [], right: Collection _ passAll, bkwd: BOOL _ FALSE]; <> Tester: TYPE ~ PROC [pair: IVPair] RETURNS [pass: BOOL _ FALSE]; Scan: PROC [fn: IntFn, Test: Tester, left: Interval _ [], right: Collection _ passAll, bkwd: BOOL _ FALSE] RETURNS [MaybePair] ~ INLINE {RETURN fn.class.Scan[fn, Test, left, right, bkwd]}; First: PROC [fn: IntFn] RETURNS [MaybePair] ~ INLINE {RETURN fn.class.Extremum[fn, FALSE, FALSE]}; Last: PROC [fn: IntFn] RETURNS [MaybePair] ~ INLINE {RETURN fn.class.Extremum[fn, TRUE, FALSE]}; Pop: PROC [fn: IntFn, bkwd: BOOL _ FALSE] RETURNS [MaybePair] ~ INLINE {RETURN fn.class.Extremum[fn, bkwd, TRUE]}; Extremum: PROC [fn: IntFn, bkwd, remove: BOOL] RETURNS [MaybePair] ~ INLINE {RETURN fn.class.Extremum[fn, bkwd, remove]}; Next: PROC [fn: IntFn, pair: IVPair] RETURNS [MaybePair] ~ INLINE {RETURN [fn.class.Get3[fn, pair].next]}; Prev: PROC [fn: IntFn, pair: IVPair] RETURNS [MaybePair] ~ INLINE {RETURN [fn.class.Get3[fn, pair].prev]}; Get3: PROC [fn: IntFn, pair: IVPair] RETURNS [prev, same, next: MaybePair] ~ INLINE {RETURN fn.class.Get3[fn, pair]}; Index: PROC [fn, goal: IntFn, bounds: Interval _ [], bkwd: BOOL _ FALSE] RETURNS [MaybeInt] <> ~ INLINE {RETURN fn.class.Index[fn, goal, bounds, bkwd]}; SkipTo: PROC [fn: IntFn, goal: Collection, bounds: Interval _ [], bkwd: BOOL _ FALSE] RETURNS [MaybePair] <> ~ INLINE {RETURN fn.class.Scan[fn, AcceptAny, bounds, goal, bkwd]}; AcceptAny: Tester--={RETURN[TRUE]}--; Lookup: PROC [fn: IntFn, val: Value, bounds: Interval _ [], bkwd: BOOL _ FALSE] RETURNS [MaybeInt] <> ~ INLINE {RETURN SkipTo[fn, Colls.CreateSingleton[val, fn.RightSpace], bounds, bkwd].DropVal[]}; <<~ INLINE {RETURN fn.class.Index[fn, CreateZeroid[val, fn.RightSpace], bounds, bkwd]};>> Size: PROC [fn: IntFn, left: Interval _ [], right: Collection _ passAll, limit: LNAT _ LNAT.LAST] RETURNS [LNAT] ~ INLINE {RETURN [fn.class.Size[fn, left, right, limit]]}; Empty: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [Size[fn: fn, limit: 1]=0]}; GetBounds: PROC [fn: IntFn] RETURNS [Interval] ~ INLINE {RETURN fn.class.GetBounds[fn]}; ImproveBounds: PROC [fn: IntFn, bounds: Interval] RETURNS [Interval] <= bounds.min. for all i in result.min > i >= bounds.min: i not in domain of fn. result.max has the complementary condition. Thus, if the actual domain is difficult to determine, the given bounds may be returned.>> ~ INLINE {RETURN fn.class.ImproveBounds[fn, bounds]}; MutabilityOf: PROC [fn: IntFn] RETURNS [Mutability] ~ INLINE {RETURN [fn.class.mutability]}; Copy: PROC [fn: IntFn] RETURNS [VarIntFn] ~ INLINE {RETURN fn.class.Copy[fn]}; Insulate: PROC [fn: IntFn] RETURNS [UWIntFn] ~ INLINE {RETURN fn.class.Insulate[fn]}; ValueOf: PROC [fn: IntFn] RETURNS [ConstIntFn] ~ INLINE {RETURN fn.class.ValueOf[fn]}; Freeze: PROC [fn: IntFn] RETURNS [const: ConstIntFn] ~ INLINE {RETURN fn.class.Freeze[fn]}; Thaw: PROC [fn: IntFn] ~ INLINE {fn.class.Thaw[fn]}; AddPair: PROC [fn: IntFn, pair: IVPair, if: IfNewsPair _ alwaysAdd] RETURNS [news: NewsPair]; Store: PROC [fn: IntFn, pair: IVPair] RETURNS [new: BOOL] ~ INLINE {RETURN [AddPair[fn, pair][leftToRight]=new]}; AddColl: PROC [self, other: IntFn, if: IfNewsPair _ alwaysAdd] RETURNS [some: NewsSetPair] ~ INLINE {RETURN self.class.AddColl[self, other, if]}; RemPair: PROC [fn: IntFn, pair: IVPair] RETURNS [hadMapping: BoolPair] ~ INLINE {RETURN [fn.class.RemColl[fn, CreateSingleton[pair, fn.RightSpace]].hadAll]}; RemColl: PROC [self, other: IntFn] RETURNS [hadSome, hadAll: BoolPair] ~ INLINE {RETURN self.class.RemColl[self, other]}; LeftDelete: PROC [fn: IntFn, int: INT] RETURNS [had: BOOL] ~ INLINE {had _ fn.class.ReplaceMe[fn, empty, [int, int], [int, int]].losses.Positive}; LeftDeleteInterval: PROC [fn: IntFn, interval: Interval] RETURNS [hadSome, hadAll: BOOL] ~ INLINE { ilen: EINT ~ interval.Length; losses: EINT ~ fn.class.ReplaceMe[fn, empty, interval, interval].losses; RETURN [losses.Positive, ilen=losses]}; RightDelete: PROC [fn: IntFn, val: Value, style: RemoveStyle _ all] RETURNS [hadSome: BOOL] ~ INLINE {RETURN [RightDeleteColl[fn, Colls.CreateSingleton[val, fn.RightSpace], style].hadSome]}; RightDeleteColl: PROC [fn: IntFn, coll: Collection, style: RemoveStyle _ all] RETURNS [hadSome, hadAll: BOOL] ~ INLINE {RETURN fn.class.RightDeleteColl[fn, coll, style]}; ReplaceMe: PROC [fn, with: IntFn, where: Interval, clip: Interval] RETURNS [losses, gains: EINT] <> <> <> <> <> <> ~ INLINE {RETURN fn.class.ReplaceMe[fn, with, where, clip]}; Insert: PROC [fn: IntFn, val: Value, before: INT] ~ INLINE {[] _ ReplaceMe[fn, CreateZeroid[val, fn.RightSpace], [before, before-1], [0, 0]]}; Append: PROC [fn: IntFn, val: Value] ~ INLINE {Insert[fn, val, fn.GetBounds[].max+1]}; Remove: PROC [fn: IntFn, dom: Interval] ~ INLINE {[] _ ReplaceMe[fn, fn, dom, anEmptyInterval]}; ReshapeMe: PROC [fn: IntFn, lt: XForm _ [], lb: Interval _ [], rt: OneToOne _ PairColls.id, rb: Collection _ passAll] <> ~ INLINE {fn.class.ReshapeMe[fn, lt, lb, rt, rb]}; Swap: PROC [fn: IntFn, i, j: INT] <> <> ~ INLINE {fn.class.Swap[fn, i, j]}; RightSpace: PROC [fn: IntFn] RETURNS [Space] ~ INLINE {RETURN fn.class.RightSpace[fn]}; RightCollection: PROC [fn: IntFn] RETURNS [UWColl] <> ~ INLINE {RETURN fn.class.RightCollection[fn]}; CurRange: PROC [fn: IntFn] RETURNS [ConstSet] <> ~ INLINE {RETURN fn.class.CurRange[fn]}; IsOneToOne: PROC [fn: IntFn] RETURNS [BOOL] <<= Functional[fn.Widen, rightToLeft]>> ~ INLINE {RETURN [fn.class.isOneToOne]}; DomainIsFixed: PROC [fn: IntFn] RETURNS [BOOL] <> ~ INLINE {RETURN [fn.class.domainFixed OR fn.class.mutability=constant]}; fixedDomain: READONLY ROPE; DomainIsDense: PROC [fn: IntFn] RETURNS [BOOL] <> ~ INLINE {RETURN [fn.class.isDense]}; refIntFns: READONLY Space; Equal: PROC [a, b: IntFn, bounds: Interval _ []] RETURNS [BOOL]; <> Hash: PROC [fn: IntFn, bounds: Interval _ []] RETURNS [CARDINAL]; Compare: PROC [a, b: IntFn, bounds: Interval _ []] RETURNS [Basics.Comparison]; <> <> VarIntFn: TYPE ~ RECORD [IntFn] --a variable IntFn--; IsVar: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.mutability=variable]}; AsVar: PROC [fn: IntFn] RETURNS [VarIntFn] ~ INLINE {RETURN [IF fn.class.mutability=variable THEN [fn] ELSE Cant[fn]]}; UWIntFn: TYPE ~ RECORD [IntFn] --an unwritable IntFn--; IsUW: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.mutability#variable]}; AsUW: PROC [fn: IntFn] RETURNS [UWIntFn] ~ INLINE {RETURN [IF fn.class.mutability#variable THEN [fn] ELSE Cant[fn]]}; ConstIntFn: TYPE ~ RECORD [UWIntFn] --a constant IntFn--; IsConst: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.mutability=constant]}; AsConst: PROC [fn: IntFn] RETURNS [ConstIntFn] ~ INLINE {RETURN [IF fn.class.mutability=constant THEN [[fn]] ELSE Cant[fn]]}; Array: TYPE ~ IntFn --whose domain is an interval--; IsArray: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.isDense]}; FixedArray: TYPE ~ IntFn --whose domain in an unchanging interval--; IsFixedArray: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.isDense AND (fn.class.mutability=constant OR fn.class.domainFixed)]}; Sequence: TYPE ~ Array --whose lower bound is 0--; IsSequence: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.isDense AND GetBounds[fn].min=0]}; FixedSequence: TYPE ~ IntFn --a FixedArray whose lower bound is 0--; IsFixedSequence: PROC [fn: IntFn] RETURNS [BOOL] ~ INLINE {RETURN [fn.class.isDense AND GetBounds[fn].min=0 AND (fn.class.mutability=constant OR fn.class.domainFixed)]}; IsIdentitySubset: PROC [fn: IntFn] RETURNS [BOOL]; <> Permutation: TYPE ~ Sequence--new index GradeUp: PROC [a: IntFn, o: Colls.Ordering] RETURNS [p: Permutation]; <> TransPermute: PROC [from: IntFn, to: Sequence, p: Permutation]; <> PermuteInPlace: PROC [a: Sequence, p: Permutation]; <> empty, id: READONLY ConstIntFn; <> DisjointUnion: PROC [IntFn, IntFn] RETURNS [IntFn]; <> Intersection: PROC [IntFn, IntFn] RETURNS [IntFn]; Difference: PROC [IntFn, IntFn] RETURNS [IntFn]; Negate: PROC [IntFn] RETURNS [PairColl]; CreateZeroid: PROC [val: Value, space: Space] RETURNS [ConstIntFn] <> ~ INLINE {RETURN CreateSingleton[[0, val], space]}; CreateSingleton: PROC [pair: IVPair, right: Space] RETURNS [ConstIntFn]; CreateFromList: PROC [vals: LOP, oneToOne: BOOL _ FALSE, right: Space _ refs, invable: BOOL _ FALSE] RETURNS [ConstIntFn]; CreateConstant: PROC [bounds: Interval, val: Value, space: Space] RETURNS [ConstIntFn]; <> CreateSimple: PROC [bounds: Interval _ [0, -1], val: Value _ noValue, oneToOne, dense, domainFixed, invable: BOOL _ FALSE, rightSpace: Space _ refs] RETURNS [Array]; <> CreateSimpleCopy: PROC [array: Array, bounds: Interval _ [], oneToOne, dense, domainFixed: NewBOOL _ SAME, invable: BOOL _ FALSE, rightSpace: Space _ NIL] RETURNS [Array]; <> NewBOOL: TYPE ~ {SAME, OPPOSITE, FALSE, TRUE}; UpdateBool: PROC [nb: NewBOOL, b: BOOL] RETURNS [BOOL] ~ INLINE {RETURN [SELECT nb FROM SAME => b, OPPOSITE => NOT b, FALSE => FALSE, TRUE => TRUE, ENDCASE => ERROR]}; ConstNew: ARRAY BOOL OF NewBOOL ~ [FALSE: FALSE, TRUE: TRUE]; CreateFromCollection: PROC [coll: Collection, bkwd: BOOL _ FALSE] RETURNS [Sequence]; <<[i, v] if v is the i'th element of coll.Enumerate[bkwd]>> CreateFromProc: PROC [Produce: PROC [Consume: PROC [val: Value _ noValue, len: LNAT _ 1]], min: INT _ 0] RETURNS [ConstIntFn]; <> CollectInterval: PROC [Interval] RETURNS [ConstSet]; CreatePartnership: PROC [a, b: IntFn] RETURNS [IntFn]; <> CreateRedBlackArray: PROC [oneToOne, dense, invable: BOOL _ FALSE, rightSpace: Space _ refs] RETURNS [Array]; CreateRedBlackCopy: PROC [array: Array, bounds: Interval _ [], oneToOne, dense: NewBOOL _ SAME, invable: BOOL _ FALSE, rightSpace: Space _ NIL] RETURNS [Array]; Compose: PROC [left: IntFn, right: Function, leftRestricts, rightRestricts: BOOL _ TRUE] RETURNS [IntFn]; Invert: PROC [IntFn] RETURNS [Relation]; Replace: PROC [fn, with: IntFn, where: Interval, clip: Interval] RETURNS [IntFn]; Reshape: PROC [fn: IntFn, lt: XForm _ [], lb: Interval _ [], rt: OneToOne _ PairColls.id, rb: Collection _ passAll] RETURNS [IntFn]; Shift: PROC [fn: IntFn, ~ INLINE {RETURN Reshape[fn, [ Concat: PROC [fn, rest: IntFn] RETURNS [IntFn]; Clip: PROC [fn: IntFn, bounds: Interval _ []] RETURNS [IntFn] ~ INLINE {RETURN Reshape[fn, [], bounds]}; Subseq: PROC [fn: IntFn, bounds: Interval _ []] RETURNS [IntFn] ~ INLINE {RETURN Reshape[fn, [IE[bounds.min].Neg], bounds]}; <> IntFnClass: TYPE ~ REF IntFnClassPrivate; IntFnClassPrivate: TYPE ~ MONITORED RECORD [ Primitive: PROC [fn: IntFn, op: ATOM, args: ArgList _ NIL] RETURNS [PrimitiveAnswer] _ NIL, Widen: PROC [fn: IntFn] RETURNS [Function--[left]: REF INT--] _ NIL, HasPair: PROC [fn: IntFn, pair: IVPair] RETURNS [BOOL] _ NIL, Apply: PROC [fn: IntFn, i: INT] RETURNS [MaybeValue] _ NIL, InvApply: PROC [fn: IntFn, v: Value] RETURNS [MaybeInt] _ NIL, Scan: PROC [fn: IntFn, Test: Tester, left: Interval, right: Collection, bkwd: BOOL] RETURNS [MaybePair] _ NIL, Extremum: PROC [fn: IntFn, bkwd, remove: BOOL] RETURNS [MaybePair] _ NIL, Get3: PROC [fn: IntFn, pair: IVPair] RETURNS [prev, same, next: MaybePair] _ NIL, Index: PROC [fn, goal: IntFn, bounds: Interval, bkwd: BOOL] RETURNS [MaybeInt] _ NIL, Size: PROC [fn: IntFn, left: Interval, right: Collection, limit: LNAT] RETURNS [LNAT] _ NIL, GetBounds: PROC [fn: IntFn] RETURNS [Interval] _ NIL, ImproveBounds: PROC [fn: IntFn, bounds: Interval] RETURNS [Interval] _ NIL, Copy: PROC [fn: IntFn] RETURNS [VarIntFn] _ NIL, Insulate: PROC [fn: IntFn] RETURNS [UWIntFn] _ NIL, ValueOf: PROC [fn: IntFn] RETURNS [ConstIntFn] _ NIL, Freeze: PROC [fn: IntFn] RETURNS [const: ConstIntFn] _ NIL, Thaw: PROC [fn: IntFn] _ NIL, AddColl: PROC [fn, other: IntFn, if: IfNewsPair] RETURNS [some: NewsSetPair] _ NIL, RemColl: PROC [fn, other: IntFn] RETURNS [hadSome, hadAll: BoolPair] _ NIL, RightDeleteColl: PROC [fn: IntFn, coll: Collection, style: RemoveStyle] RETURNS [hadSome, hadAll: BOOL] _ NIL, ReplaceMe: PROC [fn, with: IntFn, where, clip: Interval] RETURNS [losses, gains: EINT] _ NIL, ReshapeMe: PROC [fn: IntFn, lt: XForm, lb: Interval, rt: OneToOne, rb: Collection] _ NIL, Swap: PROC [fn: IntFn, i, j: INT] _ NIL, RightCollection: PROC [fn: IntFn] RETURNS [UWColl] _ NIL, CurRange: PROC [fn: IntFn] RETURNS [ConstSet] _ NIL, RightSpace: PROC [fn: IntFn] RETURNS [Space] _ NIL, isOneToOne, isDense, ordered: BOOL _ FALSE, mutability: Mutability _ variable, domainFixed: BOOL _ FALSE, other: Atom.PropList _ NIL, --the canonical expansion slot data: Value _ NIL ]; <> CreateClass: PROC [ cp: IntFnClassPrivate, bkwdable: BB _ [TRUE, FALSE] ] RETURNS [IntFnClass]; <> DefaultWiden: PROC [fn: IntFn] RETURNS [Function--[left]: REF INT--]; DefaultScan: PROC [fn: IntFn, Test: Tester, left: Interval, right: Collection, bkwd: BOOL] RETURNS [MaybePair]; DefaultExtremum: PROC [fn: IntFn, bkwd, remove: BOOL] RETURNS [MaybePair]; DefaultIndex: PROC [fn, goal: IntFn, bounds: Interval, bkwd: BOOL] RETURNS [MaybeInt]; DefaultSize: PROC [fn: IntFn, left: Interval, right: Collection, limit: LNAT] RETURNS [LNAT]; DefaultInsulate: PROC [fn: IntFn] RETURNS [UWIntFn]; DefaultReshapeMe: PROC [fn: IntFn, lt: XForm, lb: Interval, rt: OneToOne, rb: Collection]; UpdateIntFnClassOther: PROC [class: IntFnClass, Update: PROC [Atom.PropList] RETURNS [Atom.PropList]]; <> LOP: TYPE ~ LIST OF IVPair; Complain: PROC [fn: IntFn, msg: ROPE, args: LOV _ NIL] ~ INLINE {Error[msg, CONS[NEW [IntFn _ fn], args]]}; }.