IntStuff.Mesa
Last tweaked by Mike Spreitzer on November 17, 1987 7:36:52 pm PST
DIRECTORY Basics, Rope, RuntimeError;
IntStuff: CEDAR DEFINITIONS
IMPORTS Basics, RuntimeError
=
BEGIN
LNAT: TYPE ~ INT --should be the subrange [0 .. INT.LAST], but compiler can't hack it--;
ROPE: TYPE ~ Rope.ROPE;
EINT: TYPE ~ RECORD [variant: SELECT OVERLAID * FROM
loShort => [lo: CARDINAL, hi: INT],
hiShort => [lower: CARD, higher: INTEGER],
signed => [low: ARRAY [0 .. 1] OF CARDINAL, high: INTEGER],
unsigned => [cards: ARRAY [0 .. 2] OF CARDINAL],
ENDCASE];
An extended precision integer. lo + b1*hi = lower + b2*higher = the value represented.
zero: EINT ~ [loShort[0, 0]];
one: EINT ~ [loShort[lo: 1, hi: 0]];
two: EINT ~ [loShort[lo: 2, hi: 0]];
negOne: EINT ~ [loShort[lo: CARDINAL.LAST, hi: -1]];
firstEINT: EINT ~ [loShort[lo: 0, hi: INT.FIRST]];
lastEINT: EINT ~ [loShort[lo: CARDINAL.LAST, hi: INT.LAST]];
firstINT: EINT ~ [loShort[lo: 0, hi: INTEGER.FIRST]];
lastINT: EINT ~ [loShort[lo: CARDINAL.LAST, hi: INTEGER.LAST]];
maxIntervalLength: EINT ~ [hiShort[lower: 0, higher: 1]];
b1: CARD ~ CARD[CARDINAL.LAST].SUCC;
hb2: CARD ~ 2147483648;
hb2l1: CARD ~ 2147483647;
IE: PROC [i: INT] RETURNS [EINT]
~ INLINE {RETURN [[loShort[lo: Basics.LowHalf[i], hi: HighInt[i]]]]};
CE: PROC [c: CARD] RETURNS [EINT]
~ INLINE {RETURN [[hiShort[lower: c, higher: 0]]]};
EI: PROC [t: EINT] RETURNS [INT]
~ INLINE {test: INTEGER ~ t.hi; RETURN [LOOPHOLE[t.lower]]};
EC: PROC [t: EINT] RETURNS [CARD]
~ INLINE {RETURN [IF t.higher=0 THEN t.lower ELSE RuntimeError.BoundsFault[]]};
EN: PROC [t: EINT] RETURNS [n: LNAT]
~ INLINE {IF t.higher=0 THEN n ← t.lower ELSE RuntimeError.BoundsFault[]};
IsInt: PROC [t: EINT] RETURNS [BOOL]
~ INLINE {RETURN [Basics.HighHalf[LOOPHOLE[t.hi, CARD]+CARDINAL[INTEGER.LAST].SUCC]=0]};
IsCard: PROC [t: EINT] RETURNS [BOOL]
~ INLINE {RETURN [t.higher = 0]};
IsNat: PROC [t: EINT] RETURNS [BOOL]
~ INLINE {RETURN [t.hi <= INTEGER.LAST]};
FromRope: PROC [r: ROPE, base: [2..36] ← 10] RETURNS [EINT];
ToRope: PROC [t: EINT, base: [2..36] ← 10] RETURNS [ROPE];
Sgn: PROC [t: EINT] RETURNS [[-1 .. 1]]
~ INLINE {RETURN [IF t.higher=0 THEN IF t.lower>0 THEN 1 ELSE 0 ELSE IF t.higher>0 THEN 1 ELSE -1]};
Abs: PROC [t: EINT] RETURNS [EINT]
~ INLINE {RETURN [IF t.higher>=0 THEN t ELSE Neg[t]]};
Positive: PROC [t: EINT] RETURNS [BOOL]
~ INLINE {RETURN [t.higher>0 OR t.higher=0 AND t.lower#0]};
Negative: PROC [t: EINT] RETURNS [BOOL]
~ INLINE {RETURN [t.higher<0]};
ClipI: PROC [t: EINT] RETURNS [INT]
~ INLINE {RETURN [SELECT t.higher FROM
<-1 => INT.FIRST,
< 0 => LOOPHOLE[MAX[hb2, t.lower]],
= 0 => MIN[hb2l1, t.lower],
ENDCASE => INT.LAST]};
ClipC: PROC [t: EINT] RETURNS [CARD]
~ INLINE {RETURN [SELECT t.higher FROM
<0 => CARD.FIRST,
=0 => t.lower,
ENDCASE => CARD.LAST]};
ClipN: PROC [t: EINT] RETURNS [n: LNAT]
~ INLINE {n ← SELECT t.higher FROM
<0 => 0,
=0 => t.lower,
ENDCASE => LNAT.LAST};
Add: PROC [a, b: EINT] RETURNS [EINT]
~ INLINE {m: CARD ~ a.lo.LONG + b.lo.LONG; RETURN [[loShort[lo: Basics.LowHalf[m], hi: INT[Basics.HighHalf[m]] + a.hi + b.hi]]]};
Sub: PROC [a, b: EINT] RETURNS [EINT]
~ INLINE {m: INT ~ INT[a.lo] - INT[b.lo]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: HighInt[m] + a.hi - b.hi]]]};
Compare: PROC [a, b: EINT] RETURNS [c: Basics.Comparison]
~ INLINE {IF (c ← Basics.CompareInt[a.hi, b.hi])=equal THEN c ← Basics.CompareCard[a.lo, b.lo]};
CompareI: PROC [a: EINT, b: INT] RETURNS [c: Basics.Comparison]
~ INLINE {IF (c ← Basics.CompareInt[a.hi, HighInt[b]])=equal THEN c ← Basics.CompareCard[a.lo, Basics.LowHalf[b]]};
Min: PROC [a, b: EINT] RETURNS [EINT]
~ INLINE {RETURN [IF a.Compare[b]=greater THEN b ELSE a]};
Max: PROC [a, b: EINT] RETURNS [EINT]
~ INLINE {RETURN [IF a.Compare[b]=less THEN b ELSE a]};
Neg: PROC [x: EINT] RETURNS [EINT]
~ INLINE {RETURN [IF x.lo=0 THEN [loShort[lo: 0, hi: -x.hi]] ELSE [loShort[lo: b1-x.lo, hi: -1-x.hi]]]};
AddI: PROC [a: EINT, b: INT] RETURNS [EINT]
~ INLINE {m: CARD ~ a.lo.LONG + Basics.LowHalf[b]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: INT[Basics.HighHalf[m]] + a.hi + HighInt[b]]]]};
SubI: PROC [a: EINT, b: INT] RETURNS [EINT]
~ INLINE {m: INT ~ INT[a.lo] - INT[Basics.LowHalf[b]]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: HighInt[m] + a.hi - HighInt[b]]]]};
SubFromI: PROC [b: EINT, a: INT] RETURNS [EINT]
~ INLINE {m: INT ~ INT[Basics.LowHalf[a]] - INT[b.lo]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: HighInt[m] - b.hi + HighInt[a]]]]};
Mul: PROC [a, b: EINT] RETURNS [DEINT];
DEINT: TYPE ~ RECORD [lo, hi: EINT];
represents hi * (lastEINT-firstEINT+1) + lo
MulI: PROC [a: EINT, b: INT] RETURNS [EINT];
IAdd: PROC [a, b: INT] RETURNS [EINT]
~ INLINE {m: CARD ~ Basics.LowHalf[a].LONG + Basics.LowHalf[b]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: INT[Basics.HighHalf[m]] + HighInt[a] + HighInt[b]]]]};
ISub: PROC [a, b: INT] RETURNS [EINT]
~ INLINE {m: INT ~ INT[Basics.LowHalf[a]] - INT[Basics.LowHalf[b]]; RETURN [[loShort[lo: Basics.LowHalf[m], hi: HighInt[m] + INT[HighInt[a]] - HighInt[b]]]]};
Succ: PROC [t: EINT] RETURNS [EINT]
~ INLINE {m: CARD ~ t.lo.LONG.SUCC; RETURN [[loShort[lo: Basics.LowHalf[m], hi: Basics.HighHalf[m]+t.hi]]]};
Pred: PROC [t: EINT] RETURNS [EINT]
~ INLINE {m: INT ~ INT[t.lo].PRED; RETURN [[loShort[lo: Basics.LowHalf[m], hi: HighInt[m]+t.hi]]]};
HighInt: PROC [i: INT] RETURNS [INTEGER]
~ INLINE {RETURN [LOOPHOLE[Basics.HighHalf[i]]]};
Interval: TYPE ~ RECORD [min: INTINT.FIRST, max: INTINT.LAST];
max < min signifies an empty interval (located at min, if a location is required).
anEmptyInterval: Interval ~ [INT.LAST, INT.FIRST];
Empty: PROC [i: Interval] RETURNS [BOOL]
~ INLINE {RETURN [i.max < i.min]};
BoundsOfInts: PROC [i1, i2: INT] RETURNS [Interval]
~ INLINE {RETURN [[MIN[i1, i2], MAX[i1, i2]]]};
Length: PROC [i: Interval] RETURNS [EINT]
~ INLINE {RETURN [IF i.max >= i.min THEN ISub[i.max, i.min].Succ ELSE zero]};
Contains: PROC [i: Interval, int: INT] RETURNS [BOOL]
~ INLINE {RETURN [int >= i.min AND int <= i.max]};
Intersect: PROC [i1, i2: Interval] RETURNS [Interval]
~ INLINE {RETURN [[MAX[i1.min, i2.min], MIN[i1.max, i2.max]]]};
ClipTop: PROC [interval: Interval, i: INT] RETURNS [Interval]
~ INLINE {RETURN [IF i>INT.FIRST THEN [min: interval.min, max: MIN[interval.max, i-1]] ELSE anEmptyInterval]};
ClipBot: PROC [interval: Interval, i: INT] RETURNS [Interval]
~ INLINE {RETURN [IF i<INT.LAST THEN [min: MAX[interval.min, i+1], max: interval.max] ELSE anEmptyInterval]};
MBI: PROC [i1, i2: Interval] RETURNS [Interval]
~ INLINE {RETURN [IF i1.Empty THEN i2 ELSE IF i2.Empty THEN i1 ELSE [min: MIN[i1.min, i2.min], max: MAX[i1.max, i2.max]]]};
ShiftInterval: PROC [i: Interval, d: EINT] RETURNS [Interval];
Raises bounds fault if resultant interval would exceed the range of INTs.
ClipShiftInterval: PROC [i: Interval, d: EINT] RETURNS [Interval];
Doesn't raise bounds fault; instead, it just clips the resultant interval.
XForm: TYPE ~ RECORD [o: EINT ← zero, d: INT ← 1];
Transforms i into i*d+o; d can't be 0.
XFormInt: PROC [t: XForm, i: INT] RETURNS [INT]
~ INLINE {RETURN [t.o.AddI[t.d*i].EI]};
EXFormInt: PROC [t: XForm, i: INT] RETURNS [EINT]
~ INLINE {RETURN [t.o.AddI[t.d*i]]};
XFormInterval: PROC [t: XForm, i: Interval] RETURNS [Interval]
~ INLINE {RETURN [IF i.Empty THEN anEmptyInterval ELSE BoundsOfInts[t.XFormInt[i.min], t.XFormInt[i.max]]]};
InvertXForm: PROC [x: XForm] RETURNS [XForm]
~ INLINE {RETURN [SELECT x.d FROM
1 => [x.o.Neg, 1],
-1 => [x.o, -1],
ENDCASE => ERROR]};
InverseXFormInt: PROC [t: XForm, i: INT] RETURNS [INT]
~ INLINE {RETURN [SELECT t.d FROM
1 => t.o.SubFromI[i].EI,
-1 => t.o.SubI[i].EI,
ENDCASE => ERROR]};
EInverseXFormInt: PROC [t: XForm, i: INT] RETURNS [EINT]
~ INLINE {RETURN [SELECT t.d FROM
1 => t.o.SubFromI[i],
-1 => t.o.SubI[i],
ENDCASE => ERROR]};
InverseXFormInterval: PROC [t: XForm, i: Interval] RETURNS [Interval]
~ INLINE {RETURN [IF i.Empty THEN anEmptyInterval ELSE BoundsOfInts[t.InverseXFormInt[i.min], t.InverseXFormInt[i.max]]]};
ClipInverseXFormInterval: PROC [t: XForm, interval: Interval] RETURNS [Interval]
~ TRUSTED INLINE {
IF interval.Empty THEN RETURN [anEmptyInterval];
{min: EINT ← t.EInverseXFormInt[interval.min];
max: EINT ← t.EInverseXFormInt[interval.max];
IF min.Compare[max] = greater THEN {t: EINT ← min; min ← max; max ← t};
IF max.Compare[firstINT]=less THEN RETURN [anEmptyInterval];
IF min.Compare[lastINT]=greater THEN RETURN [anEmptyInterval];
RETURN [[min: min.ClipI, max: max.ClipI]]}};
Concat: PROC [t1, t2: XForm] RETURNS [XForm]
~ INLINE {RETURN [[
d: t1.d*t2.d,
o: t1.o.MulI[t2.d].Add[t2.o]
]]};
END.