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:
INT ←
INT.
FIRST, max:
INT ←
INT.
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.