------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1994 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- int.sa: Built-in integers.
-------------------------------------------------------------------
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->;

   
   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_eq(arg: $OB): BOOL is
      -- Overloaded version of the is_eq routine that works with an argument
      -- of any type. If the type of the 'arg' is not the same as they
      -- type of 'self' then return false. Otherwise, deletegate to
      -- the 'real' is_eq(SAME):BOOL routine
      typecase arg  when SAME then return is_eq(arg)  else return false end;
   end;
   
   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 or equal to 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
-------------------------------------------------------------------
