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[]};

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]
~ 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]
~ 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 f old 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];

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, d: EINT] RETURNS [IntFn]
~ INLINE {RETURN Reshape[fn, [d]]};
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]]};
}.
ήIntFunctions.Mesa
Last tweaked by Mike Spreitzer on October 16, 1987 10:11:28 am PDT
Basic Types
A function from INT to Value, or a variable function from INT to Value.
Operations on IntFns
Raised when an IntFn is asked to perform an operation it can't.
The only arguments that make a difference are bkwd: BOOL and restrictions.  A restriction is an interval or collection that is to limit the pairs under consideration.
unrestricted corresponds to the full interval ([]) or the universal set (passAll).  filtered corresponds to a collection that can test membership, but not enumerate.  restricted corresponds to a non-full interval or a collection that can enumerate.  tiny corresponds to an interval whose length is 0 or 1, or a collection that can enumerate with 0 or 1 elements.
fn must be one-to-one.
An ordered IntFn's forward enumeration order is increasing left side.  No guarantees about an unordered one.
Enumerates those [i, v] in fn such that i in left and v in right.
result is (if bkwd then greatest else least) solution in bounds to: Equal[Shift[fn, -result.i], goal, goal.bounds] (or, equivelently, Equal[fn, Shift[goal, result.i], ShiftInterval[goal.Bounds, resulti]]); if no such solution, result.found=FALSE and result.i is unrestricted.
result is (if bkwd then greatest else least) solution in bounds to: fn[i]=v AND goal.HasMember[v]; if no such solution, result.found=FALSE and result.i is unrestricted.
Returns (if bkwd then greatest else least) i in bounds such that fn[i]=val.
~ INLINE {RETURN fn.class.Index[fn, CreateZeroid[val, fn.RightSpace], bounds, bkwd]};
result.min >= 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.
new[i, v] iff
old[i, v] & i < where.min, or
with[i-where.min+clip.min, v] & where.min <= i < where.min+clip.Length, or
old[i-clip.Length+where.Length, v] & where.min+clip.Length <= i.
losses = size of intersection of domain of fn and where.
gains = size of intersection of domain of with and clip.
new.HasPair[[lt.XFormInt[i], rt.Apply[v].Val]] iff (old.HasPair[[i, v]] AND i in lb AND v in rb)
new.HasPair[[i, v]] iff old.HasPair[[j, v]].
new.HasPair[[j, v]] iff old.HasPair[[i, v]].
Result tracks changes to fn, if any.
Result does not track changes to fn.
= Functional[fn.Widen, rightToLeft]
A variable IntFn may guarantee that its domain never changes.
Is the domain an interval?
a's right Space is used.  Only pairs within the given bounds are compared.
Lexicographic ordering, using a's right space.  noValue is considered less than any value.  Only pairs within the given bounds are compared.
Special Cases of IntFns
TRUE iff for all i in domain of fn: fn[i]=i.
i < j g a[p[i]] < a[p[j]].
for each [new, old] in p: to[new] _ from[old].
Some Implementations of IntFns
The following use a standard implementation.  The result tracks changes to the arguments, if any.  Result may duplicate iff any argument may.
Assumes arguments have no elements in common.
Returns a constant IntFn whose domain is {0} and range is {val}.
Returns a constant IntFn whose domain is bounds and range is {val}.
The implementation of this keeps a Cedar SEQUENCE at least long enough to cover the current bounds.  Initially allocates a sequence long enough to keep the given bounds.  Initially has pairs iff val#noValue, in which case they all have [right]=val and [left] in bounds.  If oneToOne, client promises to never require the implicit removal of pairs.
Like CreateSimple, but the array is initialized from the given array, subject to the given bounds.  Giving rightSpace=NIL means to use the original's.
[i, v] if v is the i'th element of coll.Enumerate[bkwd]
Creates a constant IntFn from a producer of runs.
a and b cooperate to implement the same function.  a provides most of the functionality; b provides backward mapping.
Implementing IntFns
The only part that may vary is the other, and that must be accessed through the update procedure below.
NIL procs mean the implementor declines to implement the proc.  Where possible, NIL fields get filled in with default procedures that compute with provided fields; the other fields get filled in with CantXXX procedures, which raise Cant.
Other New Stuff
Κξ–

"cedar" style˜
code™Kš
œB™B—K˜KšΟk	œ6˜?K˜šΟnœœ
˜Kšœ'˜.Kš	œœ
žœž	œ#žœ˜l—
head™Kšœœœ
˜Kšœ
œ˜Kšœœ˜K˜Kšœœœœ˜0KšœœΟc€
œ
˜½
K˜šœœœ"˜6Kšœœ'œ
™G—K˜Kšœœœ˜š
žœœœ
œœ˜)Kšœœœœœ
œ
œœ	œ˜H—š
žœœ
œœ
œ
˜/Kšœœœ˜"—K˜Kš	œ
œœ	œœ˜.Kšœœ
˜K˜šž
œœœœ
˜#Kš
œœœœ	œœœ˜B—K˜Kšœœœ	œ˜5Kšœ
œŸœ
˜7K˜šžœœœ˜0Kšœœœ˜-—K˜šžœœœ
˜2Kšœœœ˜.—K˜šž
œœœ	˜(Kš
œœœœ
œ	œœ˜G—K˜šœœ'œ
œœœ	˜PKšœœœœ
œ	œ˜=——™šžœœ
˜K™?—K˜š
ž	œœœœœ˜QK™¦
—K˜šœ
œ.˜?Kš
œκ™κ—K˜Kšžœœœœ˜3Kšžœœœ'œ˜hK˜šžœœœœœœ
˜CKšœœœ!˜1—K˜šžœœ
œ
Ÿœ
˜=Kšœœœ˜%—K˜šžœœœœ
˜6Kšœœœ˜-—K˜šžœœœœ
˜4Kšœœœ˜(—K˜šžœœœ˜7K™Kšœœœ˜+—K˜šžœœ
œœ
˜(K™lKšœœœ˜%—K˜šž	œœ
žœœCœœ˜zK™A—K˜Kšœœœœœœ˜@K˜šžœœ
žœBœœœ˜~Kšœœœ-˜=—K˜šžœœ
œ˜+Kš	œœœœœ˜6—šžœœ
œ˜*Kš	œœœœœ˜5—š
žœœœœœ˜=Kšœœœœ˜4—šžœœœœ˜BKšœœœ&˜6—K˜šžœœœ˜8Kšœœœ!˜1—šžœœœ˜8Kšœœœ!˜1—šžœœœ˜JKšœœœ˜*—K˜š
žœœ0œœœ˜[Kšœπ
œ™“Kšœœœ)˜9—K˜š
žœœ<œœœ˜iKšœLœ6œ™¨
Kšœœœ3˜CKšž	œŸœ
˜%—K˜š
žœœ6œœœ˜bKš
œK™KKšœœœP˜`KšœœœE™U—K˜šžœœFœœ
œœœ
˜pKšœœœ*˜:—K˜šžœœ
œœ
˜&Kšœœœ˜-—K˜šž	œœ
œ˜.Kšœœœ˜)—K˜šž
œœœ˜DK™β
Kšœœœ%˜5—K˜šžœœ
œ
˜3Kšœœœ˜(—K˜šžœœ
œ˜)Kšœœœ˜$—K˜šžœœ
œ
˜,Kšœœœ˜(—K˜šžœœ
œ
˜.Kšœœœ˜'—K˜šžœœ
œ˜4Kšœœœ˜&—K˜šžœœ˜Kšœœ˜—K˜Kšžœœ7œ˜]K˜šžœœœœ
˜9Kšœœœ'˜7—K˜šžœœ2œ˜ZKšœœœ&˜6—K˜šžœœœ˜FKšœœœF˜V—K˜šžœœœ˜FKšœœœ"˜2—K˜š
ž
œœœœœ
˜:KšœœO˜W—K˜šžœœ!œœ
˜Xšœœ˜
Kšœœ˜Kšœœ<˜HKšœ!˜'——K˜šžœœ3œœ
˜[KšœœœR˜b—K˜šžœœ9œœ
˜mKšœœœ,˜<—K˜šž	œœ4œœ
˜`K™
K™K™JK™@KšΟeœ% œ œ
™8Kš œ% œ œ
™8Kšœœœ,˜<—K˜šžœœ!œ
˜1KšœœT˜\—K˜šžœœ˜$Kšœœ)˜1—K˜šžœœ˜'Kšœœ0˜8—K˜šž	œœf˜uKšœHœ	œ	™`Kšœœ*˜2—K˜šžœœœ
˜!K™,K™,Kšœœ˜#—K˜šž
œœ
œ˜,Kšœœœ˜*—K˜šžœœ
œ	˜2K™$Kšœœœ˜/—K˜šžœœ
œ˜-K™$Kšœœœ˜(—K˜šž
œœ
œœ
˜+K™#Kšœœœ˜(—K˜šž
œœ
œœ
˜.K™=Kšœœœœ ˜IKšœ
œ
œ
˜—K˜šž
œœ
œœ
˜.K™Kšœœœ˜%—K˜Kšœœ˜K˜šžœœ&œœ˜@Kš
œJ™J—K˜Kšžœœ$œœ˜AK˜šžœœ&œ˜OKš
œŒ
™Œ
——™Kšœ
œœ	Ÿœ
˜5šžœœ
œœ
˜&Kšœœœ!˜1—šžœœ
œ˜*Kšœœœœœœ˜L—K˜Kšœ	œœ	Ÿœ
˜7šžœœ
œœ
˜%Kšœœœ!˜1—šžœœ
œ
˜(Kšœœœœœœ˜L—K˜KšœœœŸœ
˜9šžœœ
œœ
˜(Kšœœœ!˜1—šžœœ
œ
˜.Kšœœœœœœ˜N—K˜Kšœœ	Ÿœ
˜4šžœœ
œœ
˜(Kšœœœ˜%—K˜Kšœœ	Ÿ*œ
˜Dšžœœ
œœ
˜-Kš	œœœœœ˜`—K˜Kšœ
œ	Ÿœ
˜2šž
œœ
œœ
˜+Kšœœœœ˜=—K˜Kšœœ	Ÿ'œ
˜Dšžœœ
œœ
˜0Kšœœœœœœ˜x—K˜šžœœ
œœ˜2K™,—K˜Kšœ
œŸΠcm
Ÿœ
˜6šžœœœ˜EKšœΟm
œ	’
œ	™—šžœœ-˜?K™.—Kšžœœ˜3—š
œ™Kšœœ˜K˜Kš
œ
™
šž
œœœ	˜3K™-—Kšžœœœ	˜2Kšž
œœœ	˜0Kšžœœ	œ˜(K˜šžœœœ
˜BK™@Kšœœœ#˜3—K˜Kšžœœœ˜HK˜Kšžœœœœœ œœœ˜zK˜šžœœ.œ˜WKš
œC™C—K˜š
žœœ[œœœ	˜₯
Kš	œΓ
 œ. œ œ œA™Ϋ—K˜šžœœOœœœœœ	˜«
Kš
œ–
™–
—K˜Kšœ	œœœœœ˜.š
ž
œœœœœ
˜6šœœœœ˜ Kšœ˜
Kšœœ˜Kšœœ
˜Kšœœ
˜
Kšœœ˜——šžœœ
œ
œ˜Kš	œœœœœ˜—K˜š
žœœœœœ˜UK™7—K˜šžœœžœœžœœœ
œœ˜~Kš
œ1™1—K˜Kšžœœœ˜4K˜šžœœœ	˜6K™u—K˜Kš
žœœœœœ	˜mKšžœœBœœœœœ	˜ 
K˜Kš
žœœ?œœœ	˜iKšžœœ	œ˜(K˜Kšžœœ4œ	˜QKšžœœgœ	˜„
K˜š
žœœ
Οg
œœœ˜0Kšœœœ£
œ˜#—Kšžœœœ	˜/šžœœ$œ˜=Kšœœœ˜*—šžœœ$œ˜?Kšœœœœ˜<——š
œ™Kšœœœ˜)šœœ	œ
œ˜,Kšž	œœœœœœ
˜[Kš
žœœ
œ
Ÿœœ
˜DKš
žœœœœœ
˜=Kš
žœœœœœ
˜;Kšžœœœœ
˜>Kšžœœ
žœ3œœœ
˜nKš
žœœœœœ
˜IKšžœœœ!œ
˜QKš
žœœ+œœœ
˜UKšžœœ7œœœœ
˜\Kšž	œœ
œœ
˜5Kšž
œœœœ
˜KKšžœœ
œœ
˜0Kšžœœ
œ
œ
˜3Kšžœœ
œœ
˜5Kšžœœ
œœ
˜;Kšžœœœ
˜Kšžœœ$œœ
˜SKšžœœœœ
˜KKš
žœœ3œœœ
˜nKš
ž	œœ*œœœ
˜]Kšž	œœFœ
˜YKšžœœœœ
˜(Kšžœœ
œœ
˜9Kšžœœ
œœ
˜4Kšž
œœ
œœ
˜3Kšœœœ
˜+K˜"Kšœ
œœ
˜KšœœŸ˜:Kšœ˜K˜Kšœ# œ?™g—K˜šžœ˜š
œ
˜
Kš
œ˜Kšœ
œœœ
˜Kš
œ
˜
—Kšœ˜KšœMœš
™ν
—K˜Kšžœœ
œ
Ÿœ˜EKš
žœœ
žœ3œœ
˜oKšžœœœœ
˜JKšžœœ+œœ˜VKš
žœœ7œœœ˜]Kšžœœ
œ˜4KšžœœD˜ZK˜Kš
žœœžœœœ˜f—™Kšœœœ
œ˜K˜š
žœœœœœ
˜6Kšœœ
œ
œ˜4——L˜—…—=cΜ