int.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- Copyright (C) International Computer Science Institute, 1994. COPYRIGHT --
-- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
-- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in --
-- the file "Doc/License" of the Sather distribution. The license is also --
-- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA. --
--------> Please email comments to sather-bugs@icsi.berkeley.edu. <----------
-- int.sa: Built-in integers.
immutable class INT < $NUMBER{INT}, $HASH, $FMT
immutable class INT < $NUMBER{INT}, $HASH, $FMT is
-- The most fundamental integer class. Signed, unsigned, and modular
-- versions of arithmetic operations are provided. The names of
-- unsigned operations begin with the letter "u". The names of
-- modular operations begin with the letter "m". Negative numbers
-- are represented using 2's complement. INT objects inherit from
-- AVAL{BOOL}. The number of bits in the representation is `asize'
-- and is implementation dependent. It must be at least 32, however
-- (to ensure portability of INT literals up to this size). Many of
-- the operations are specified to raise exceptions on overflow. They
-- are guaranteed to do this if checking is enabled, but this may
-- affect performance. Certain machines (with appropriate hardware)
-- may perform these checks even when checking is not enabled. The
-- modular operations are performed modulo 2^asize.
--
-- References:
-- Keith O. Geddes, Stephen R. Czapor, and George Labahn, "Algorithms
-- for Computer Algebra", Kluwer Academic Publishers, Boston, 1992.
-- AVAL does not work yet. For the moment leave out.
-- include AVAL{BOOL} asize->;
include COMPARABLE;
const asize:INT:=32;
-- Size in bits.
-- Signed operations:
plus(i:SAME):SAME is builtin INT_PLUS; end;
-- The signed sum of self and `i'. Raises an exception on
-- overflow, when enabled. Built-in.
minus(i:SAME):SAME is builtin INT_MINUS; end;
-- The signed difference between self and `i'. Raises an exception
-- on overflow, when enabled. Built-in.
negate:SAME is builtin INT_NEGATE; end;
-- The signed negation of self. Same as zero minus self.
-- Only raises an exception on the most negative value (which
-- doesn't have a corresponding positive value in 2's complement.)
-- Built-in.
times(i:SAME):SAME is builtin INT_TIMES; end;
-- The signed product of self and `i'. Raises an exception if the
-- product can't be held in the result, when enabled. Built-in.
div(i:SAME):SAME is builtin INT_DIV; end;
-- The signed quotient of self and `i'. This and `mod' have the
-- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. Raises
-- an exception when `i' is 0, when enabled. Built-in.
mod(i:SAME):SAME is builtin INT_MOD; end;
-- Signed remainder of self divided by `i'. This and `mod' have the
-- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. It's
-- also true that `0 <= x.mod(y) < y.abs'. Raises an exception when
-- `i' is 0, when enabled. Built-in.
is_eq(i:SAME):BOOL is builtin INT_IS_EQ; end;
-- True if self and `i' represent the same value.
-- return self=i
is_lt(i:SAME):BOOL is builtin INT_IS_LT; end;
-- True if self is less than `i' as signed integers. Built-in.
max(i:SAME):SAME is builtin INT_MAX; end;
-- The larger of self and `i' as signed integers. Built-in.
min(i:SAME):SAME is builtin INT_MIN; end;
-- The smaller of self and `i' as signed integers. Built-in.
at_least(x:SAME):SAME is
-- Same as `max(x)'.
return max(x)
end;
at_most(x:SAME):SAME is
-- Same as `min(x)'.
return min(x)
end;
within(x,y:SAME):SAME is
-- Same as `max(x).min(y)'.
return max(x).min(y)
end;
-- Conversion from other types:
create(x:INT):SAME is return x end;
create(x:INTI):SAME is return x.int end;
create(f:FLT):SAME is return f.int end;
create(f:FLTD):SAME is return f.int end;
create(s:STR): SAME is builtin INT_CREATE_STR; end;
int:INT is builtin INT_INT; end;
-- An integer version of self.
from_int(i:INT):SAME is
-- Returns `i'.
return i
end;
inti:INTI is
-- An infinite precision version of self.
return #INTI(self)
end;
flt:FLT is builtin INT_FLT; end;
-- A floating point version of self. It is an error if the
-- value cannot be held in a FLT. Built-in.
fltd:FLTD is builtin INT_FLTD; end;
-- A double floating point version of self. It is an error
-- if the value cannot be held in a FLTD. Built-in.
bool:BOOL is builtin INT_BOOL; end;
-- A boolean from self. Built-in.
char:CHAR is builtin INT_CHAR; end;
-- A character corresponding to the value of self. Built-in.
c_unsigned_int:C_UNSIGNED_INT is builtin INT_C_UNSIGNED_INT; end;
-- Convert to external C unsigned integer. Built-in.
-- Other computation:
abs:SAME is builtin INT_ABS; end;
-- The absolute value of self. Built-in.
square:SAME is builtin INT_SQUARE; end;
-- The square of self. Built-in.
cube:SAME is
-- The cube of self.
return self*self*self
end;
pow(i:INT):SAME
-- Self raised to the power `i'.
pre i>=0 is
r:SAME;
case i
when 0 then return 1
when 1 then return self
when 2 then return self*self
when 3 then return self*self*self
when 4 then r:=self*self; return r*r
when 5 then r:=self*self; return self*r*r
when 6 then r:=self*self; return r*r*r
when 7 then r:=self*self; return self*r*r*r
when 8 then r:=self*self; r:=r*r; return r*r
when 9 then r:=self*self; r:=r*r; return self*r*r
when 10 then r:=self*self; r:=self*r*r; return r*r
else
x ::= self; r := 1;
loop
-- r * x^i = self ^ i0
if i.is_odd then r := r*x end;
i := i.rshift(1);
while!(i>0);
x := x.square;
end;
return r;
end;
end;
sqrt:SAME
-- The largest integer whose square is smaller than self.
pre self>=0
is
x::=fltd;
r:SAME;
if self=x.floor.int then return x.sqrt.floor.int
else q::=1; r:=self;
loop while!(q<=r); q:=4*q end;
loop while!(q/=1); q:=q/4; h::=r+q; r:=r/2;
if h<=r then r:=r-h; r:=r+q end end end;
return r
end;
exp2:SAME pre self>=0 is return 0.set_bit(self) end;
ten_pow:SAME pre self>=0 is return exp10 end;
exp10:SAME
-- Ten to the self power. Small values use lookup table for speed.
pre self>=0
is
case self
when 0 then return 1
when 1 then return 10
when 2 then return 100
when 3 then return 1000
when 4 then return 10000
when 5 then return 100000
when 6 then return 1000000
when 7 then return 10000000
when 8 then return 100000000
when 9 then return 1000000000
else return 10.pow(self) end
end;
num_digits:INT
-- The number of decimal digits in non-negative self.
-- Use binary search so that small values take only 3 compares.
pre self>=0 is
if self<10000 then
if self<100 then
if self<10 then return 1 else return 2 end
else if self<1000 then return 3 else return 4 end end;
else
if self<1000000 then
if self<100000 then return 5 else return 6 end
else
return (self/10000).num_digits+4;
--r::=7; tst::=10000000;
--loop
-- if self<tst then return r end;
-- r:=r+1; tst:=tst*10 end;
--raise "INT::num_digits error."
end
end
end;
hash:INT is
r::=self;
-- We should try to get numbers away from each other, even if
-- they don't collide. For example, if SYS::id returns
-- objects in consecutive aligned positions, we don't want to
-- end up returning successive integers. Unfortunately, it's
-- not good enough to just multiply/add by some magic numbers,
-- because that doesn't affect the randomness once passed
-- through a mod function (for instance FSET etc. just use the
-- rightmost bits, equivalent to mod by a power of two.) Here
-- a few steps of a shift generator are done.
r:=r.bxor(r.lshift(17));
r:=r.bxor(r.urshift(15));
r:=r.bxor(r.lshift(17));
r:=r.bxor(r.urshift(15));
r:=r.bxor(r.lshift(17));
r:=r.bxor(r.urshift(15));
return r;
end;
-- Conversion into printable forms:
str_in (s: FSTR, n, b: INT, f: CHAR): FSTR pre b.is_bet(2, 16) is
-- Append a string representation of self to s using at least n digits
-- to the base b and return s. If less then n digits are used for the
-- representation of self (including its sign), the remaining left_most
-- positions are filled with character f.
--
if is_nil then
-- The nil value (most negative number) cannot be negated -
-- due to the inherent assymetry of the representation.
-- There is no corresponding positive number
x ::= self;
divid: INT := x/b;
rem1: INT := (x - divid*(b-1));
rem: INT := rem1-divid;
if rem > 0 then rem := rem-b; divid := divid + 1; end;
-- If divid was rounded up instead of down,manually divid to divid-1
first_char: CHAR := rem.abs.digit_char;
x := divid.abs;
i ::= s.length;
s := s+first_char;
n := n - 1;
loop s := s + (x%b).digit_char; x := x/b; n := n-1; until!(x = 0) end;
s := s + '-'; n := n-1;
loop while!(n > 0); s := s + f; n := n-1 end;
j ::= s.length-1;
loop while!(i < j);
ch ::= s[i]; s[i] := s[j]; s[j] := ch; i := i+1; j := j-1
end;
return s;
-- return #INTI(nil).str_in(s, n, b, f)
--#FSTR("nil");
else
x ::= self.abs; i ::= s.length;
loop s := s + (x%b).digit_char; x := x/b; n := n-1; until!(x = 0) end;
if self < 0 then s := s + '-'; n := n-1 end;
loop while!(n > 0); s := s + f; n := n-1 end;
j ::= s.length-1;
loop while!(i < j);
ch ::= s[i]; s[i] := s[j]; s[j] := ch; i := i+1; j := j-1
end;
return s
end
end;
str_in(s:FSTR):FSTR is
-- Append a decimal string version of self to `s' and return it.
return str_in(s, 0, 10, ' ')
end;
-- the shared buffer is actually faster, but not thread safe.
-- private shared buf:FSTR; -- Buffer for string output.
str:STR is
buf:FSTR;
-- A decimal string version of self.
buf.clear; buf:=str_in(buf); return buf.str
end;
fmt( f: STR ): STR
is
return BASE_FORMAT::fmt_int(self,f)
end;
digit_char:CHAR
-- A character representing self. If self is between 0 and 9, it
-- returns a digit. If between 10 and 15, returns 'A' thru 'F'.
pre self.is_bet(0,15) is
return "0123456789ABCDEF"[self]
end;
-- Integer properties:
is_even:BOOL is builtin INT_IS_EVEN; end;
is_odd:BOOL is builtin INT_IS_ODD; end;
is_pos:BOOL is
-- True if self is greater than zero.
return self>0
end;
is_neg:BOOL is
-- True if self is less than zero.
return self<0
end;
is_zero:BOOL is
-- True if self is zero.
return self=0
end;
is_non_zero:BOOL is
-- True if self is non-zero.
return self/=0
end;
is_non_neg:BOOL is
-- True if self is non-negative.
return self>=0
end;
is_non_pos:BOOL is
-- True if self is non-positive.
return self<=0
end;
sign:SAME is
-- -1,0,1 depending on the sign of self.
-- Steele, 304
if self<0 then return -1
elsif self>0 then return 1
else return 0 end
end;
is_bet(l,u:SAME):BOOL is builtin INT_IS_BETWEEN; end;
-- True if self between l and u. Built-in.
is_between(l,u:SAME):BOOL is builtin INT_IS_BETWEEN; end;
-- True if self between l and u. Built-in.
is_within(tolerance,val:SAME):BOOL is
return (self-val).abs<=tolerance;
end;
is_eq(i1,i2:SAME):BOOL is
-- True if self equals `i1' and `i2'.
return self=i1 and self=i2 end;
is_eq(i1,i2,i3:SAME):BOOL is
-- True if self equals `i1', `i2', and `i3'.
return self=i1 and self=i2 and self=i3 end;
nil:SAME is
-- The value to be used to represent no element in sets.
-- The most negative value.
return 1.lshift(asize-1)
end;
is_nil:BOOL is return self=1.lshift(asize-1); end;
-- Unsigned operations:
uplus(i:SAME):SAME is builtin INT_UPLUS; end;
-- The unsigned sum of self and `i'. Raises an exception on
-- overflow, when enabled. Built-in.
uminus(i:SAME):SAME is builtin INT_UMINUS; end;
-- The unsigned difference between self and `i'. Raises an
-- exception on overflow or if the result would be negative,
-- when enabled. Built-in.
utimes(i:SAME):SAME is builtin INT_UTIMES; end;
-- The unsigned product of self and `i'. Raises an exception if the
-- product can't be held in the result, when enabled. Built-in.
udiv(i:SAME):SAME is builtin INT_UDIV; end;
-- The unsigned quotient of self and `i'. Raises an exception when
-- `i' is 0, when enabled. Built-in.
umod(i:SAME):SAME is builtin INT_UMOD; end;
-- Unsigned remainder of self divided by `i'. Raises an exception
-- when `i' is 0, when enabled. Built-in.
is_ult(lhs:SAME):BOOL is
if self>=0 and lhs<0 then return true end;
if self<0 and lhs>=0 then return false end;
-- both (self and lhs) have the same sign
return self<lhs;
end;
is_uleq(i:SAME):BOOL is
-- True if self is less than or equal to `i' as unsigned integers.
return is_ult(i) or self=i
end;
is_ugt(i:SAME):BOOL is
-- True if self is greater than `i' as unsigned integers.
return i.is_ult(self)
end;
is_ugeq(i:SAME):BOOL is
-- True if self is greater than or equal to `i' as unsigned
-- integers.
return i.is_ult(self) or self=i
end;
umax(i:SAME):SAME is
-- The larger of self and `i' as unsigned integers.
if self.is_ugt(i) then return self else return i end
end;
umin(i:SAME):SAME is
-- The smaller of self and `i' as unsigned integers.
if self.is_ult(i) then return self else return i end
end;
evenly_divides(i:SAME):BOOL is
-- True if self evenly divides `i'.
return i%self=0
end;
next_multiple_of(i:SAME):SAME
-- The smallest value greater than or equal to self which is a
-- multiple of `i'.
pre i>0 is
return ((self+i-1)/i)*i
end;
gcd(i:SAME):SAME is
-- The greatest common divisor of self and `i'.
-- The result is non-negative and `x.gcd(0)=x.abs'.
-- Uses Euclidean algorithm. Geddes, et. al. p. 34.
c::=abs; d::=i.abs;
loop until!(d=0); r::=c.mod(d); c:=d; d:=r end;
return c
end;
extended_gcd(i:SAME, out self_factor,out i_factor: SAME): SAME is
-- The three parts of the return value `g', `g1', and `g2' are such
-- that `g' is the greatest common divisor of self and `i' and
-- `g1*self+g2*i=g'.
-- Uses the extended Euclidean algorithm. Geddes, et. al. p. 36.
c::=abs; d::=i.abs; c1::=1; d1::=0; c2::=0; d2::=1;
loop until!(d=0);
q::=c/d; r::=c-q*d; r1::=c1-q*d1; r2::=c2-q*d2;
c:=d; c1:=d1; c2:=d2; d:=r; d1:=r1; d2:=r2
end;
self_factor := c1/(abs*c.abs);
i_factor := c2/(abs*c.abs);
return c.abs;
end;
lcm(i:SAME):SAME is
-- The least common multiple of self and `i'.
-- Geddes, et. al. p. 28.
return (self*i).abs/gcd(i)
end;
is_prime:BOOL is
-- True if self is a prime number.
-- Replace by a faster algorithm.
if 2.evenly_divides(self) then return false end;
loop
d::=3.step!((self.sqrt+2)/2, 2);
if d.evenly_divides(self) then return false end
end;
return true
end;
is_relatively_prime_to(i:SAME):BOOL is
-- True if self is relatively prime to `i'.
return gcd(i)=1
end;
factorial:SAME is
-- The factorial of self.
-- Replace by faster algorithm.
p::=1;
loop p:=p*2.upto!(self) end;
return p
end;
-- Operations modulo 2^asize:
mplus(i:SAME):SAME is builtin INT_MPLUS; end;
-- The sum of self and `i' modulo 2^asize. Never raises
-- an exception. Built-in.
mminus(i:SAME):SAME is builtin INT_MMINUS; end;
-- The difference between self and `i' modulo 2^asize. Never
-- raises an exception. Built-in.
mnegate:SAME is builtin INT_MNEGATE; end;
-- The additive inverse of self modulo 2^asize. Never raises an
-- exception.
mtimes(i:SAME):SAME is builtin INT_MTIMES; end;
-- The product of self and `i' modulo 2^asize. Never raises
-- an exception. Built-in.
mdiv(i:SAME):SAME is builtin INT_MDIV; end;
-- The unsigned quotient of self and `i'. Raises an exception when
-- `i' is 0, when enabled. Built-in.
mmod(i:SAME):SAME is builtin INT_MMOD; end;
-- Unsigned remainder of self divided by `i'. Raises an exception
-- when `i' is 0, when enabled.
-- Bitwise operations:
bnot:SAME is builtin INT_BNOT; end;
-- The bitwise complement of self.
band(i:SAME):SAME is builtin INT_BAND; end;
-- The bitwise and of self and `i'.
bor(i:SAME):SAME is builtin INT_BOR; end;
-- The bitwise inclusive or of self and `i'.
bxor(i:SAME):SAME is builtin INT_BXOR; end;
-- The bitwise exclusive or of self and `i'.
bnand(i:SAME):SAME is
-- The bitwise nand of self and `i'.
return band(i).bnot end;
bnor(i:SAME):SAME is
-- The bitwise nor of self and `i'.
return bor(i).bnot end;
beqv(i:SAME):SAME is
-- The bits of res are 1 in positions where self and `i' have the
-- same bit values.
return bxor(i).bnot end;
boole(i:SAME, rule:INT):SAME
-- The bits of res are combinations of the corresponding bits of
-- self and `i' combined according to a rule specified by `rule'.
-- This must be a value between 0 and 15. The low order bit says
-- what to map a 0 in self and a 0 in `i' to, the second bit of
-- `rule' says what to map 0,1 to, the third bit defines 1,0 and
-- the fourth 1,1.
pre rule.is_bet(0,15) is
case rule when 0 then return 0
when 1 then return bor(i).bnot
when 2 then return bnot.band(i)
when 3 then return bnot
when 4 then return band(i.bnot)
when 5 then return i.bnot
when 6 then return bxor(i)
when 7 then return band(i).bnot
when 8 then return band(i)
when 9 then return bxor(i).bnot
when 10 then return i
when 11 then return bnot.bor(i)
when 12 then return self
when 13 then return bor(i.bnot)
when 14 then return bor(i)
when 15 then return -1
else raise "INT::boole(SAME,INT):SAME err."
end
end;
bcount:INT is
-- The number of bits in self which are set to 1.
r:SAME;
if asize=32 then
-- 32 bit version:
r:=self.band(0b01010101010101010101010101010101)
.uplus(self.urshift(1)
.band(0b01010101010101010101010101010101));
r:=r.band(0b00110011001100110011001100110011)
.uplus(r.urshift(2).band(0b00110011001100110011001100110011));
r:=r.band(0b00001111000011110000111100001111)
.uplus(r.urshift(4).band(0b00001111000011110000111100001111));
r:=r+r.rshift(8);
r:=(r+r.rshift(16)).band(0b111111);
-- No need to mask the last two steps since the bits can't
-- interfere.
else
-- General size.
-- Semi-clever version (fast when sparse but slow for dense):
x::=self;
loop until!(x=0); x:=x.band(x.uminus(1)); r:=r+1 end;
end;
return r
end;
lshift(i:INT):SAME is builtin INT_LSHIFT; end;
-- The bits of self shifted left by `i' places with
-- zeroes shifted in on the right.
rshift(i:INT):SAME is builtin INT_RSHIFT; end;
-- The bits of self shifted right by `i' places with
-- bits equal to the first bit of self shifted in on the left.
urshift(i:INT):SAME is builtin INT_URSHIFT; end;
-- The bits of self shifted right by `i' places with
-- zeroes shifted in on the left.
lrotate(i:INT):SAME
-- Left rotate the bits of self by `i' places.
pre i.is_bet(0,asize)
is
return lshift(i).bor(urshift(asize-i))
end;
rrotate(i:INT):SAME
-- Right rotate the bits of self by `i' places.
pre i.is_bet(0,asize)
is
return urshift(i).bor(lshift(asize-i))
end;
bit(i:INT):BOOL is
-- True if bit `i' of self is 1.
return band(1.lshift(i))/=0
end;
set_bit(i:INT,b:BOOL):SAME is
-- Self with bit `i' set to b.
if b then return set_bit(i) else return unset_bit(i) end
end;
set_bit(i:INT):SAME is
-- Self with bit `i' set to 1.
return bor(1.lshift(i))
end;
unset_bit(i:INT):SAME is
-- Self with bit `i' set to 0.
return band((1.lshift(i)).bnot)
end;
octal_str:STR is
-- The octal representation of self of the form "0o15".
-- Self is interpreted as an unsigned integer.
buf:FSTR;
buf.clear; i::=self;
loop
buf:=buf + i.band(7).digit_char;
i:=i.urshift(3);
until!(i=0)
end;
buf:=buf + "o0";
buf.to_reverse;
return buf.str
end;
binary_str:STR is
-- The binary representation of self of the form "0b100100".
-- Self is interpreted as an unsigned integer.
buf:FSTR;
buf.clear; i::=self;
loop
buf := buf + i.band(1).digit_char;
i:=i.urshift(1);
until!(i=0)
end;
buf:=buf + "b0";
buf.to_reverse;
return buf.str
end;
hex_str:STR is
-- The hexadecimal representation of self of the form "0x5A".
-- Self is interpreted as an unsigned integer.
buf:FSTR;
buf.clear; i::=self;
loop
buf:=buf + i.band(15).digit_char;
i:=i.urshift(4);
until!(i=0)
end;
buf:=buf + "x0";
buf.to_reverse;
return buf.str
end;
lowest_bit:INT is
-- The position of the lowest non-zero bit of self. -1 if none.
if self=0 then return -1 end;
if asize=32 then
-- 32 bit version:
x::=self; r::=31;
z::=x.lshift(16); if z/=0 then x:=z; r:=r-16 end;
z:=x.lshift(8); if z/=0 then x:=z; r:=r-8 end;
z:=x.lshift(4); if z/=0 then x:=z; r:=r-4 end;
z:=x.lshift(2); if z/=0 then x:=z; r:=r-2 end;
z:=x.lshift(1); if z/=0 then x:=z; r:=r-1 end;
return r
--
-- This implementation assumes that asize is a power of 2.
-- if self=0 then return -1 end;
-- x::=self; y::=asize/2; r:=asize-1;
-- loop until(y=0); z::=x.lshift(y);
-- if z/=0 then x:=z; r:=r-y end; y:=y.rshift(1) end; return r end;
--
else
-- Straightforward way:
loop i::=(asize-1).downto!(0);
if lshift(i)/=0 then r::=asize-i-1; return r end
end;
return -1;
end;
end;
highest_bit:INT is
-- The position of the highest non-zero bit of self. -1 if none.
if self=0 then return -1 end;
if asize=32 then
-- 32 bit version:
x::=self; z::=x.urshift(16); r:INT;
if z/=0 then x:=z; r:=r+16 end;
z:=x.urshift(8); if z/=0 then x:=z; r:=r+8 end;
z:=x.urshift(4); if z/=0 then x:=z; r:=r+4 end;
z:=x.urshift(2); if z/=0 then x:=z; r:=r+2 end;
z:=x.urshift(1); if z/=0 then x:=z; r:=r+1 end;
return r;
else
--
-- This implementation assumes that asize is a power of 2.
-- if self=0 then return -1 end;
-- x::=self; y::=asize/2;
-- loop until(y=0); z::=x.urshift(y);
-- if z/=0 then x:=z; r:=r+y end; y:=y.rshift(1) end;
-- return r end;
--
-- Straightforward way:
loop i::=1.upto!(asize-1);
if rshift(i)=0 then return i-1 end
end;
return asize-1;
end;
end;
log2:INT pre self>0 is return self.highest_bit end;
is_pow_of_2:BOOL is return is_exp2 end;
is_exp2:BOOL is
-- returns true iff self is positive and a power of two
res:BOOL:=false;
if self > 0 then
res := self.lowest_bit = self.highest_bit
end;
return res;
end;
next_pow_of_2:INT is return next_exp2 end;
next_exp2:INT is
-- for self positive it returns the p so that the following holds:
-- p.is_pow_of_2 and p>=self>(p/2)
res:INT:=0;
bit:INT:=self.highest_bit;
if ~self.is_pow_of_2 then
bit := bit + 1;
end;
return res.set_bit(bit);
end;
low_bits(i:INT):INT
-- The low `i' bits of self with 0 in the higher positions.
pre i.is_bet(0,asize)
is
return band(1.lshift(i).uminus(1))
end;
high_bits(i:INT):INT is
-- The high `i' bits of self with 0 in the lower positions.
return band((1.lshift(asize-i).uminus(1)).bnot)
end;
aget(i:INT):BOOL is builtin INT_AGET; end;
aset(i:INT,j:BOOL):INT is builtin INT_ASET; end;
aelt!:BOOL is loop yield [asize.times!]; end; end;
maxint:INT is builtin INT_MAXINT; end;
minint:INT is builtin INT_MININT; end;
const zero:SAME := 0; -- See $NUMBER.
const one: SAME := 1;
maxval:SAME is return maxint; end; -- See $NUMBER.
minval:SAME is return minint; end; -- See $NUMBER.
-- Iters:
times! pre self>=0 is builtin INT_TIMESB; end;
-- Yields self times without returning anything.
times!:SAME pre self>=0 is builtin INT_TIMESB_INT; end;
-- Yield successive integers from 0 up to self-1.
for!(once i:SAME):SAME
-- Yields `i' successive integers starting with self.
pre i>=0 is builtin INT_FORB;
end;
up!:SAME is builtin INT_UPB; end;
-- Yield successive integers from self up.
upto!(once i:SAME):SAME is builtin INT_UPTOB; end;
-- Yield successive integers from self to `i' inclusive.
downto!(once i:SAME):SAME is builtin INT_DOWNTOB; end;
-- Yield successive integers from self down to `i' inclusive.
step!(once num,once step:SAME):SAME
-- Yield `num' integers starting with self and stepping by `step'.
pre num>=0
is
r::=self; last::=self+(num-1)*step;
if step>0 then
loop until!(r>last); yield r; r:=r+step end
elsif step<0 then
loop until!(r<last); yield r; r:=r+step end
else
loop num.times!; yield r end
end
end;
stepto!(once to,once by:SAME): SAME
-- Yield succeeding integers from self to `to' by step `by'.
-- Might quit immediately if self is aleady `beyond'.
pre by /= 0
is
r ::= self;
if by>0 then
loop until!(r>to); yield r; r := r + by end
else
loop until!(r<to); yield r; r := r + by end
end
end;
sum!(i:SAME):SAME is
-- Yields the sum of all previous values of `i'.
r:SAME;
loop r:=r+i; yield r end
end;
product!(i:SAME):SAME is
-- Yields the product of all previous values of `i'.
r::=1;
loop r:=r*i; yield r end
end;
end; -- class INT