home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / LIBRARY / INT.SA < prev    next >
Text File  |  1995-02-06  |  31KB  |  849 lines
  1. -- Copyright (C) International Computer Science Institute, 1994.  COPYRIGHT  --
  2. -- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
  3. -- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in    --
  4. -- the file "Doc/License" of the Sather distribution.  The license is also   --
  5. -- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA.  --
  6. --------> Please email comments to "sather-bugs@icsi.berkeley.edu". <----------
  7.  
  8. -- int.sa: Built-in integers.
  9. -------------------------------------------------------------------
  10. value class INT < $IS_EQ{INT}, $IS_LT{INT}, $NIL{INT}, $HASH is
  11.    -- The most fundamental integer class. Signed, unsigned, and modular
  12.    -- versions of arithmetic operations are provided. The names of
  13.    -- unsigned operations begin with the letter "u". The names of 
  14.    -- modular operations begin with the letter "m". Negative numbers 
  15.    -- are represented using 2's complement. INT objects inherit from
  16.    -- AVAL{BOOL}. The number of bits in the representation is `asize'
  17.    -- and is implementation dependent. It must be at least 32, however 
  18.    -- (to ensure portability of INT literals up to this size). Many of 
  19.    -- the operations are specified to raise exceptions on overflow. They 
  20.    -- are guaranteed to do this if checking is enabled, but this may 
  21.    -- affect performance. Certain machines (with appropriate hardware) 
  22.    -- may perform these checks even when checking is not enabled. The 
  23.    -- modular operations are performed modulo 2^asize. 
  24.    -- 
  25.    -- References:
  26.    -- Keith O. Geddes, Stephen R. Czapor, and George Labahn, "Algorithms
  27.    -- for Computer Algebra", Kluwer Academic Publishers, Boston, 1992.
  28.    
  29.    -- AVAL does not work yet.  For the moment leave out.
  30.    include AVAL{BOOL} asize->;
  31.    const asize:INT:=32;
  32.        -- Size in bits.  This should be overridden in the compiler
  33.        -- file MACROS if not 32.
  34.  
  35. -- Signed operations:
  36.    
  37.    plus(i:SAME):SAME is 
  38.       -- The signed sum of self and `i'. Raises an exception on 
  39.       -- overflow, when enabled. Built-in.
  40.       raise "INT::plus(SAME):SAME undefined." end;
  41.    
  42.    minus(i:SAME):SAME is
  43.       -- The signed difference between self and `i'. Raises an exception
  44.       -- on overflow, when enabled. Built-in.     
  45.       raise "INT::minus(SAME):SAME undefined." end;   
  46.    
  47.    negate:SAME is
  48.       -- The signed negation of self. Same as zero minus self.
  49.       -- Only raises an exception on the most negative value (which
  50.       -- doesn't have a corresponding positive value in 2's complement.)
  51.       return 0-self end;
  52.  
  53.    times(i:SAME):SAME is
  54.       -- The signed product of self and `i'. Raises an exception if the
  55.       -- product can't be held in the result, when enabled. Built-in.
  56.       raise "INT::times(SAME):SAME undefined." end;   
  57.    
  58.    div(i:SAME):SAME is
  59.       -- The signed quotient of self and `i'. This and `mod' have the 
  60.       -- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. Raises
  61.       -- an exception when `i' is 0, when enabled. Built-in.            
  62.       raise "INT::div(SAME):SAME undefined." end;   
  63.    
  64.    mod(i:SAME):SAME is
  65.       -- Signed remainder of self divided by `i'. This and `mod' have the 
  66.       -- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. It's
  67.       -- also true that `0 <= x.mod(y) < y.abs'. Raises an exception when
  68.       -- `i' is 0, when enabled. Built-in.        
  69.       raise "INT::mod(SAME):SAME undefined." end;   
  70.    
  71.    is_eq(i:SAME):BOOL is
  72.       -- True if self and `i' represent the same value.
  73.       -- return self=i 
  74.       raise "INT::is_eq(SAME):BOOL undefined." end;
  75.  
  76.    is_neq(i:SAME):BOOL is
  77.       -- True if self and `i' represent different values.
  78.       raise "INT::is_neq(INT):BOOL undefined." end;
  79.    
  80.    is_lt(i:SAME):BOOL is
  81.       -- True if self is less than `i' as signed integers. Built-in.
  82.       raise "INT::is_lt(SAME):BOOL undefined." end;   
  83.  
  84.    is_leq(i:SAME):BOOL is
  85.       -- True if self is less than or equal to `i' as signed integers.
  86.       -- return is_lt(i) or is_eq(i) 
  87.       raise "INT::is_geq(SAME):BOOL undefined." end;
  88.    
  89.    is_gt(i:SAME):BOOL is
  90.       -- True if self is greater than `i' as signed integers.
  91.       -- return i.is_lt(self) 
  92.       raise "INT::is_gt(SAME):BOOL undefined." end;
  93.  
  94.    is_geq(i:SAME):BOOL is
  95.       -- True if self is greater than or equal to `i' as signed integers.
  96.       -- return is_gt(i) or is_eq(i) 
  97.       raise "INT::is_geq(SAME):BOOL undefined." end;
  98.  
  99.    flt:FLT is
  100.       -- A floating point version of self. It is an error if the
  101.       -- value cannot be held in a FLT.
  102.       -- Built-in.
  103.       raise "INT::flt:FLT undefined." end;   
  104.  
  105.    fltd:FLTD is
  106.       -- A double floating point version of self. It is an error
  107.       -- if the value cannot be held in a FLTD.
  108.       -- Built-in.      
  109.       raise "INT::fltd:FLTD undefined." end;
  110.  
  111.    fltx:FLTX is
  112.       -- An extended floating point version of self. It is an
  113.       -- error if the value cannot be held in a FLTX.
  114.       -- Built-in.      
  115.          raise "INT::fltx:FLTX undefined." end;
  116.    
  117.    fltdx:FLTDX is
  118.       -- An extended floating point version of self. It is an
  119.       -- error if the value cannot be held in a FLTDX.
  120.       -- Built-in.         
  121.          raise "INT::fltdx(SAME):SAME undefined." end;
  122.  
  123.    char:CHAR is
  124.       -- A character corresponding to the value of self.
  125.       -- Built-in.      
  126.          raise "INT::char:CHAR undefined." end;
  127.  
  128.    int:INT is
  129.       -- An integer version of self.
  130.       return self end;
  131.  
  132.    inti:INTI is
  133.       -- An infinite precision version of self.
  134.       return #INTI(self) end;
  135.    
  136.    from_int(i:INT):SAME is
  137.       -- Returns `i'.
  138.       return i end;
  139.    
  140.    abs:SAME is
  141.       -- The absolute value of self.
  142. --    if self<0 then return (-self) else return self end end;                   -- NLP
  143.       if self<0 then return (-self); end; return self; end;                     -- NLP
  144.    
  145.    square:SAME is
  146.       -- The square of self.
  147.       return self*self end;
  148.  
  149.    cube:SAME is
  150.       -- The cube of self.
  151.       return self*self*self end;
  152.  
  153.    max(i:SAME):SAME is
  154.       -- The larger of self and `i' as signed integers.
  155. --    if self>i then return self else return i end end;                         -- NLP
  156.       if self>i then return self; end; return i; end;                           -- NLP
  157.  
  158.    min(i:SAME):SAME is
  159.       -- The smaller of self and `i' as signed integers.
  160. --    if self<i then return self else return i end end;                         -- NLP
  161.       if self<i then return self; end; return i; end;                           -- NLP
  162.  
  163.    at_least(x:SAME):SAME is
  164.       -- Same as `max(x)'.
  165.       return max(x) end;
  166.  
  167.    at_most(x:SAME):SAME is
  168.       -- Same as `min(x)'.
  169.       return min(x) end;
  170.  
  171.    within(x,y:SAME):SAME is
  172.       -- Same as `max(x).min(y)'.
  173.       return max(x).min(y) end;
  174.  
  175.    pow(i:INT):SAME
  176.       -- Self raised to the power `i'.
  177.       pre i>=0 is
  178.       r:SAME;
  179.       case i 
  180.       when 0 then return 1       
  181.       when 1 then return self
  182.       when 2 then return self*self     
  183.       when 3 then return self*self*self
  184.       when 4 then r:=self*self; return r*r
  185.       when 5 then r:=self*self; return self*r*r
  186.       when 6 then r:=self*self; return r*r*r
  187.       when 7 then r:=self*self; return self*r*r*r
  188.       when 8 then r:=self*self; r:=r*r; return r*r
  189.       when 9 then r:=self*self; r:=r*r; return self*r*r
  190.       when 10 then r:=self*self; r:=self*r*r; return r*r
  191.       else
  192.           x ::= self; r := 1;
  193.           loop while!(i > 0);
  194.          -- r * x^i = self ^ i0
  195.          if i.is_odd then r := r*x end;
  196.          x := x.square; i := i.rshift(1);
  197.           end;
  198. --            return r;                                                         -- NLP
  199.           end; return r;                                                        -- NLP
  200. --    end;                                                                      -- NLP
  201.    end;
  202.  
  203.    sqrt:SAME 
  204.       -- The largest integer whose square is smaller than self.
  205.       pre self>=0 is
  206.       x::=fltd;
  207.       r:SAME;
  208.       if self=x.floor.int then return x.sqrt.floor.int
  209.       else q::=1; r:=self; 
  210.      loop while!(q<=r); q:=4*q end;
  211.      loop while!(q/=1); q:=q/4; h::=r+q; r:=r/2; 
  212.         if h<=r then r:=r-h; r:=r+q end end end;
  213.       return r end;
  214.    
  215.    hash:INT is
  216.       -- A very cheap, but not very good hash value. It just returns 
  217.       -- self.
  218.       return self end;
  219.    
  220.    str_in (s: FSTR, n, b: INT, f: CHAR): FSTR pre b.is_bet(2, 16) is
  221.    -- Append a string representation of self to s using at least n digits
  222.    -- to the base b and return s. If less then n digits are used for the
  223.    -- representation of self (including its sign), the remaining left_most
  224.    -- positions are filled with character f.
  225.    --
  226.       if self = nil then return #INTI(nil).str_in(s, n, b, f)
  227.       else
  228.          x ::= self.abs; i ::= s.length;
  229.          loop s := s + (x%b).digit_char; x := x/b; n := n-1; until!(x = 0) end;
  230.          if self < 0 then s := s + '-'; n := n-1 end;
  231.          loop while!(n > 0); s := s + f; n := n-1 end;
  232.          j ::= s.length-1;
  233.          loop while!(i < j); ch ::= s[i]; s[i] := s[j]; s[j] := ch; i := i+1; j := j-1 end;
  234. --       return s                                                               -- NLP
  235.       end; return s;                                                            -- NLP
  236. --    end                                                                       -- NLP
  237.    end;
  238.  
  239.    str_in(s:FSTR):FSTR is
  240.       -- Append a decimal string version of self to `s' and return it.
  241.       return str_in(s, 0, 10, ' ')
  242.    end;
  243.  
  244.    private shared buf:FSTR;    -- Buffer for string output.   
  245.    
  246.    str:STR is
  247.       -- A decimal string version of self.
  248.       buf.clear; buf:=str_in(buf); return buf.str end;
  249.  
  250.    digit_char:CHAR
  251.       -- A character representing self. If self is between 0 and 9, it
  252.       -- returns a digit. If between 10 and 15, returns 'A' thru 'F'.
  253.       pre self.is_bet(0,15) is
  254.       return "0123456789ABCDEF"[self] end;
  255.    
  256.    ten_pow:SAME 
  257.       -- Ten to the self power. Small values use lookup table for speed.
  258.       pre self>=0 is
  259.       case self when 0 then return 1 
  260.       when 1 then return 10 
  261.       when 2 then return 100
  262.       when 3 then return 1000 
  263.       when 4 then return 10000 
  264.       when 5 then return 100000
  265.       when 6 then return 1000000 
  266.       when 7 then return 10000000
  267.       when 8 then return 100000000 
  268.       when 9 then return 1000000000
  269. --    else return 10.pow(self) end end;                                         -- NLP
  270.       else; end; return 10.pow(self); end;                                      -- NLP
  271.    
  272.    num_digits:INT
  273.       -- The number of decimal digits in non-negative self.
  274.       -- Use binary search so that small values take only 3 compares.
  275.       pre self>=0 is
  276.       if self<10000 then
  277.      if self<100 then 
  278.         if self<10 then return 1 else return 2 end
  279.      else if self<1000 then return 3 else return 4 end end;
  280.       else
  281.      if self<1000000 then 
  282.         if self<100000 then return 5 else return 6 end
  283.      else
  284.         return (self/10000).num_digits+4;
  285.         --r::=7; tst::=10000000;
  286.         --loop 
  287.         --   if self<tst then return r end; 
  288.         --   r:=r+1; tst:=tst*10 end;
  289.         --raise "INT::num_digits error."
  290. --          end end end;                                                        -- NLP
  291.             end; end; return 0; end;                                            -- NLP
  292.    
  293.    create(s:STR):SAME is
  294.       -- The integer represented by `s'. It may be decimal, binary, octal
  295.       -- or hex. Raises an exception if `s' has incorrect form.
  296.  
  297.       -- This is not a good way to do this.  Should have own implementation.
  298.       return #INTI(s).int end;
  299.  
  300.    is_even:BOOL is
  301.       -- True if self is even.
  302.       return band(1)=0 end;
  303.  
  304.    is_odd:BOOL is
  305.       -- True if self is odd.
  306.       return band(1)/=0 end;   
  307.  
  308.    is_pos:BOOL is
  309.       -- True if self is greater than zero.
  310.       return self>0 end;
  311.  
  312.    is_neg:BOOL is
  313.       -- True if self is less than zero.
  314.       return self<0 end;
  315.  
  316.    is_zero:BOOL is
  317.       -- True if self is zero.
  318.       return self=0 end;
  319.  
  320.    is_non_neg:BOOL is
  321.       -- True if self is non-negative.
  322.       return self>=0 end;
  323.  
  324.    is_non_pos:BOOL is
  325.       -- True if self is non-positive.
  326.       return self<=0 end;   
  327.    
  328.    sign:SAME is
  329.       -- -1,0,1 depending on the sign of self.
  330.       -- Steele, 304
  331.       if self<0 then return -1 
  332.       elsif self>0 then return 1 
  333. --    else return 0 end end;                                                    -- NLP
  334.       end; return 0; end;                                                       -- NLP
  335.  
  336.    is_bet(l,u:SAME):BOOL is
  337.       -- True if self between l and u.
  338.       return (l<=self and self<=u) or (u<=self and self<=l) end;
  339.  
  340.    is_eq(i1,i2:SAME):BOOL is
  341.       -- True if self equals `i1' and `i2'.
  342.       return self=i1 and self=i2 end;
  343.  
  344.    is_eq(i1,i2,i3:SAME):BOOL is
  345.       -- True if self equals `i1', `i2', and `i3'.
  346.       return self=i1 and self=i2 and self=i3 end;   
  347.  
  348.    nil:SAME is
  349.       -- The value to be used to represent no element in sets.
  350.       -- The most negative value.
  351.       return 1.lshift(asize-1) end;
  352.    
  353. -- Unsigned operations:   
  354.    
  355.    uplus(i:SAME):SAME is 
  356.       -- The unsigned sum of self and `i'. Raises an exception on 
  357.       -- overflow, when enabled. Built-in.      
  358.          raise "INT::uplus(SAME):SAME undefined." end;
  359.  
  360.    uminus(i:SAME):SAME is
  361.       -- The unsigned difference between self and `i'. Raises an 
  362.       -- exception on overflow or if the result would be negative,
  363.       -- when enabled. Built-in.      
  364.          raise "INT::uminus(SAME):SAME undefined." end;
  365.  
  366.    utimes(i:SAME):SAME is
  367.       -- The unsigned product of self and `i'. Raises an exception if the
  368.       -- product can't be held in the result, when enabled. Built-in.
  369.          raise "INT::utimes(SAME):SAME undefined." end;
  370.  
  371.    udiv(i:SAME):SAME is
  372.       -- The unsigned quotient of self and `i'. Raises an exception when
  373.       -- `i' is 0, when enabled. Built-in.            
  374.          raise "INT::udiv(SAME):SAME undefined." end;
  375.  
  376.    umod(i:SAME):SAME is
  377.       -- Unsigned remainder of self divided by `i'. Raises an exception 
  378.       -- when `i' is 0, when enabled. Built-in.            
  379.          raise "INT::umod(SAME):SAME undefined." end;
  380.    
  381.    is_ult(i:SAME):BOOL is
  382.       -- True if self is less than `i' as unsigned integers. 
  383.       return mminus(i)<0 end;   
  384.  
  385.    is_uleq(i:SAME):BOOL is
  386.       -- True if self is less than or equal to `i' as unsigned integers.
  387.       return is_ult(i) or self=i end;   
  388.    
  389.    is_ugt(i:SAME):BOOL is
  390.       -- True if self is greater than `i' as unsigned integers.
  391.       return i.is_ult(self) end;   
  392.  
  393.    is_ugeq(i:SAME):BOOL is
  394.       -- True if self is greater than or equal to `i' as unsigned 
  395.       -- integers.
  396.       return i.is_ult(self) or self=i end;    
  397.    
  398.    umax(i:SAME):SAME is
  399.       -- The larger of self and `i' as unsigned integers.
  400. --    if self.is_ugt(i) then return self else return i end end;                 -- NLP
  401.       if self.is_ugt(i) then return self; end; return i; end;                   -- NLP
  402.    
  403.    umin(i:SAME):SAME is
  404.       -- The smaller of self and `i' as unsigned integers.
  405. --    if self.is_ult(i) then return self else return i end end;                 -- NLP
  406.       if self.is_ult(i) then return self; end; return i; end;                   -- NLP
  407.    
  408.    evenly_divides(i:SAME):BOOL is
  409.       -- True if self evenly divides `i'.
  410.       return i%self=0 end;
  411.  
  412.    next_multiple_of(i:SAME):SAME 
  413.       -- The smallest value greater than or equal to self which is a 
  414.       -- multiple of `i'. 
  415.       pre i>0 is
  416.       return ((self+i-1)/i)*i end;
  417.    
  418.    gcd(i:SAME):SAME is
  419.       -- The greatest common divisor of self and `i'.
  420.       -- The result is non-negative and `x.gcd(0)=x.abs'.
  421.       -- Uses Euclidean algorithm. Geddes, et. al. p. 34.
  422.       c::=abs; d::=i.abs;
  423.       loop until!(d=0); r::=c.mod(d); c:=d; d:=r end; 
  424.       return c end;
  425.  
  426.    extended_gcd(i:SAME):TUP{SAME,SAME,SAME} is
  427.       -- The three parts of the return value `g', `g1', and `g2' are such
  428.       -- that `g' is the greatest common divisor of self and `i' and
  429.       -- `g1*self+g2*i=g'.
  430.       -- Uses the extended Euclidean algorithm. Geddes, et. al. p. 36.
  431.       c::=abs; d::=i.abs; c1::=1; d1::=0; c2::=0; d2::=1;
  432.       loop until!(d=0);
  433.      q::=c/d; r::=c-q*d; r1::=c1-q*d1; r2::=c2-q*d2;
  434.      c:=d; c1:=d1; c2:=d2; d:=r; d1:=r1; d2:=r2 end;
  435.       return #(c.abs,c1/(abs*c.abs),c2/(abs*c.abs)) end;
  436.    
  437.    lcm(i:SAME):SAME is
  438.       -- The least common multiple of self and `i'.
  439.       -- Geddes, et. al. p. 28.      
  440.       return (self*i).abs/gcd(i) end;
  441.    
  442.    is_prime:BOOL is
  443.       -- True if self is a prime number.
  444.       -- Replace by a faster algorithm.
  445.       if 2.evenly_divides(self) then return false end;
  446.       loop d::=3.step!((self.sqrt+2)/2, 2);
  447.      if d.evenly_divides(self) then return false end end; 
  448.       return true end;
  449.       
  450.    is_relatively_prime_to(i:SAME):BOOL is
  451.       -- True if self is relatively prime to `i'.
  452.       return gcd(i)=1 end;
  453.    
  454.    factorial:SAME is
  455.       -- The factorial of self.
  456.       -- Replace by faster algorithm.
  457.       p::=1; loop p:=p*2.upto!(self) end; return p end;
  458.    
  459. -- Operations modulo 2^asize:
  460.    
  461.    mplus(i:SAME):SAME is
  462.       -- The sum of self and `i' modulo 2^asize. Never raises
  463.       -- an exception. Built-in.      
  464.          raise "INT::mplus(SAME):SAME undefined." end;
  465.    
  466.    mminus(i:SAME):SAME is
  467.       -- The difference between self and `i' modulo 2^asize. Never
  468.       -- raises an exception. Built-in.      
  469.             raise "INT::mminus(SAME):SAME undefined." end;
  470.  
  471.    mnegate:SAME is 
  472.       -- The additive inverse of self modulo 2^asize. Never raises an
  473.       -- exception. 
  474.       return 0.mminus(self) end;
  475.    
  476.    mtimes(i:SAME):SAME is 
  477.       -- The product of self and `i' modulo 2^asize. Never raises
  478.       -- an exception. Built-in.
  479.             raise "INT::mtimes(SAME):SAME undefined." end;
  480.    
  481.    mdiv(i:SAME):SAME is 
  482.       -- The unsigned quotient of self and `i'. Raises an exception when
  483.       -- `i' is 0, when enabled. Built-in.            
  484.       return udiv(i) end;   
  485.  
  486.    mmod(i:SAME):SAME is
  487.       -- Unsigned remainder of self divided by `i'. Raises an exception 
  488.       -- when `i' is 0, when enabled. 
  489.       return umod(i) end;
  490.  
  491. -- Bitwise operations:
  492.    
  493.    bnot:SAME is 
  494.       -- The bitwise complement of self.
  495.       -- Built-in.      
  496.       raise "INT::bnot(SAME):SAME undefined." end;
  497.  
  498.    band(i:SAME):SAME is
  499.       -- The bitwise and of self and `i'.
  500.       -- Built-in.      
  501.       raise "INT::band(SAME):SAME undefined." end;
  502.  
  503.    bor(i:SAME):SAME is
  504.       -- The bitwise inclusive or of self and `i'.
  505.       -- Built-in.      
  506.       raise "INT::bor(SAME):SAME undefined." end;
  507.    
  508.    bxor(i:SAME):SAME is
  509.       -- The bitwise exclusive or of self and `i'.
  510.       -- Built-in.      
  511.       raise "INT::bxor(SAME):SAME undefined." end;
  512.  
  513.    bnand(i:SAME):SAME is
  514.       -- The bitwise nand of self and `i'.
  515.       return band(i).bnot end;
  516.  
  517.    bnor(i:SAME):SAME is
  518.       -- The bitwise nor of self and `i'.
  519.       return bor(i).bnot end;
  520.  
  521.    beqv(i:SAME):SAME is
  522.       -- The bits of res are 1 in positions where self and `i' have the
  523.       -- same bit values.
  524.       return bxor(i).bnot end;      
  525.  
  526.    boole(i:SAME, rule:INT):SAME 
  527.       -- The bits of res are combinations of the corresponding bits of
  528.       -- self and `i' combined according to a rule specified by `rule'. 
  529.       -- This must be a value between 0 and 15. The low order bit says 
  530.       -- what to map a 0 in self and a 0 in `i' to, the second bit of
  531.       -- `rule' says what to map 0,1 to, the third bit defines 1,0 and 
  532.       -- the fourth 1,1.
  533.       pre rule.is_bet(0,15) is
  534.       case rule when 0 then return 0         
  535.       when 1 then return bor(i).bnot
  536.       when 2 then return bnot.band(i)   
  537.       when 3 then return bnot
  538.       when 4 then return band(i.bnot)   
  539.       when 5 then return i.bnot
  540.       when 6 then return bxor(i)         
  541.       when 7 then return band(i).bnot
  542.       when 8 then return band(i)        
  543.       when 9 then return bxor(i).bnot
  544.       when 10 then return i             
  545.       when 11 then return bnot.bor(i)
  546.       when 12 then return self            
  547.       when 13 then return bor(i.bnot)
  548.       when 14 then return bor(i)        
  549.       when 15 then return -1 
  550. --    else raise "INT::boole(SAME,INT):SAME err." end end;                      -- NLP
  551.       else raise "INT::boole(SAME,INT):SAME err." end; return 0; end;           -- NLP
  552.  
  553.    bcount:INT is
  554.       -- The number of bits in self which are set to 1.
  555.       r:SAME;
  556.       if asize=32 then
  557.       -- 32 bit version:
  558.       r:=self.band(0b01010101010101010101010101010101).uplus(
  559.          self.urshift(1).band(0b01010101010101010101010101010101));
  560.       r:=r.band(0b00110011001100110011001100110011).uplus(
  561.          r.urshift(2).band(0b00110011001100110011001100110011));
  562.       r:=r.band(0b00001111000011110000111100001111).uplus(
  563.          r.urshift(4).band(0b00001111000011110000111100001111));
  564.       r:=r+r.rshift(8); 
  565.       r:=(r+r.rshift(16)).band(0b111111);
  566.       -- No need to mask the last two steps since the bits can't 
  567.       -- interfere.
  568.       else
  569.       -- General size.
  570.       -- Semi-clever version (fast when sparse but slow for dense):
  571.       x::=self; 
  572.       loop until!(x=0); x:=x.band(x.uminus(1)); r:=r+1 end;
  573.       end;
  574.       return r
  575.    end;
  576.    
  577.    lshift(i:INT):SAME is
  578.       -- The bits of self shifted left by `i' places with
  579.       -- zeroes shifted in on the right.
  580.       -- Built-in.      
  581.       raise "INT::lshift(INT):SAME undefined." end;
  582.  
  583.    rshift(i:INT):SAME is 
  584.       -- The bits of self shifted right by `i' places with
  585.       -- bits equal to the first bit of self shifted in on the left.
  586.       -- Built-in.      
  587.       raise "INT::rshift(INT):SAME undefined." end;
  588.  
  589.    urshift(i:INT):SAME is 
  590.       -- The bits of self shifted right by `i' places with
  591.       -- zeroes shifted in on the left.
  592.       -- Built-in.      
  593.       raise "INT::urshift(INT):SAME undefined." end;
  594.  
  595.    lrotate(i:INT):SAME
  596.       -- Left rotate the bits of self by `i' places.
  597.       pre i.is_bet(0,asize) is
  598.       return lshift(i).bor(urshift(asize-i)) end;
  599.  
  600.    rrotate(i:INT):SAME
  601.       -- Right rotate the bits of self by `i' places.
  602.       pre i.is_bet(0,asize) is      
  603.       return urshift(i).bor(lshift(asize-i)) end;   
  604.  
  605.    bit(i:INT):BOOL is
  606.       -- True if bit `i' of self is 1.
  607.       return band(1.lshift(i))/=0 end;
  608.  
  609.    set_bit(i:INT):SAME is
  610.       -- Self with bit `i' set to 1.
  611.       return bor(1.lshift(i)) end;
  612.    
  613.    unset_bit(i:INT):SAME is
  614.       -- Self with bit `i' set to 0.
  615.       return band((1.lshift(i)).bnot) end;
  616.  
  617.    octal_str:STR is
  618.       -- The octal representation of self of the form "0o15".
  619.       -- Self is interpreted as an unsigned integer.
  620.       buf.clear; i::=self;
  621.       loop buf:=buf + i.band(7).digit_char; 
  622.      i:=i.urshift(3);
  623.      until!(i=0) end;
  624.       buf:=buf + "o0"; 
  625.       buf.to_reverse; return buf.str end;
  626.  
  627.    binary_str:STR is
  628.       -- The binary representation of self of the form "0b100100".
  629.       -- Self is interpreted as an unsigned integer.
  630.       buf.clear; i::=self;
  631.       loop buf := buf + i.band(1).digit_char; 
  632.      i:=i.urshift(1);
  633.      until!(i=0) end;
  634.       buf:=buf + "b0"; 
  635.       buf.to_reverse; return buf.str end;
  636.  
  637.    hex_str:STR is
  638.       -- The hexadecimal representation of self of the form "0x5A".
  639.       -- Self is interpreted as an unsigned integer.
  640.       buf.clear; i::=self;
  641.       loop buf:=buf + i.band(15).digit_char; 
  642.      i:=i.urshift(4); until!(i=0) end;
  643.       buf:=buf + "x0"; 
  644.       buf.to_reverse; return buf.str end;
  645.    
  646.    lowest_bit:INT is
  647.       -- The position of the lowest non-zero bit of self. -1 if none.
  648.       if self=0 then return -1 end;
  649.       if asize=32 then
  650.       -- 32 bit version:
  651.       x::=self; r::=31;
  652.       z::=x.lshift(16); if z/=0 then x:=z; r:=r-16 end;
  653.       z:=x.lshift(8); if z/=0 then x:=z; r:=r-8 end;
  654.       z:=x.lshift(4); if z/=0 then x:=z; r:=r-4 end;
  655.       z:=x.lshift(2); if z/=0 then x:=z; r:=r-2 end;
  656.       z:=x.lshift(1); if z/=0 then x:=z; r:=r-1 end;
  657.       return r
  658.       -- 
  659.       -- This implementation assumes that asize is a power of 2.      
  660.       -- if self=0 then return -1 end;
  661.       -- x::=self; y::=asize/2; r:=asize-1;
  662.       -- loop until(y=0); z::=x.lshift(y);
  663.       -- if z/=0 then x:=z; r:=r-y end; y:=y.rshift(1) end; return r end;
  664.       -- 
  665.       else
  666.       -- Straightforward way:
  667.       loop i::=(asize-1).downto!(0);
  668.           if lshift(i)/=0 then r::=asize-i-1; return r end
  669.       end;
  670. --        return -1;                                                            -- NLP
  671.       end;
  672.       return -1;                                                                -- NLP
  673.    end;
  674.  
  675.    highest_bit:INT is
  676.       -- The position of the highest non-zero bit of self. -1 if none.
  677.       if self=0 then return -1 end;
  678.       if asize=32 then
  679.       -- 32 bit version:
  680.       x::=self; z::=x.urshift(16); r:INT;
  681.       if z/=0 then x:=z; r:=r+16 end;
  682.       z:=x.urshift(8); if z/=0 then x:=z; r:=r+8 end;
  683.       z:=x.urshift(4); if z/=0 then x:=z; r:=r+4 end;
  684.       z:=x.urshift(2); if z/=0 then x:=z; r:=r+2 end;
  685.       z:=x.urshift(1); if z/=0 then x:=z; r:=r+1 end;
  686.       return r;
  687.       else
  688.       --
  689.       -- This implementation assumes that asize is a power of 2.
  690.       -- if self=0 then return -1 end;      
  691.       -- x::=self; y::=asize/2;
  692.       -- loop until(y=0); z::=x.urshift(y);
  693.       --    if z/=0 then x:=z; r:=r+y end; y:=y.rshift(1) end; 
  694.       -- return r end;
  695.       --
  696.       -- Straightforward way:
  697.       loop i::=(asize-1).downto!(0);
  698.           if rshift(i)=0 then return i-1 end
  699.       end;
  700. --        return asize-1;                                                       -- NLP
  701.       end; 
  702.       return asize-1;                                                           -- NLP
  703.    end;
  704.  
  705.   is_pow_of_2:BOOL is
  706.     -- returns true iff self is positive and a power of two
  707.  
  708.     res:BOOL:=false;
  709.     if self > 0 then
  710.       res := self.lowest_bit = self.highest_bit
  711.     end;
  712.     return res;
  713.   end;
  714.  
  715.   next_pow_of_2:INT is
  716.     -- for self positive it returns the p so that the following holds:
  717.     -- p.is_pow_of_2 and p>=self>(p/2)
  718.  
  719.     res:INT:=0;
  720.     bit:INT:=self.highest_bit;
  721.     if ~self.is_pow_of_2 then
  722.       bit := bit + 1;
  723.     end;
  724.     
  725.     return res.set_bit(bit); 
  726.   end;
  727.  
  728.    low_bits(i:INT):INT 
  729.       -- The low `i' bits of self with 0 in the higher positions.
  730.       pre i.is_bet(0,asize) is
  731.       return band(1.lshift(i).uminus(1)) end;
  732.  
  733.    high_bits(i:INT):INT is
  734.       -- The high `i' bits of self with 0 in the lower positions.
  735.       return band((1.lshift(asize-i).uminus(1)).bnot) end;   
  736.  
  737.    maxint:INT is raise "INT::maxint undefined"; end;
  738.    minint:INT is raise "INT::minint undeinfed"; end;
  739.    
  740. -- Iters:
  741.    
  742.    times!  
  743.       -- Yields self times without returning anything.
  744.       pre self>=0 is 
  745.       i::=self; 
  746.       loop until!(i<=0); yield; i:=i-1 end end;
  747.    
  748.    times!:SAME 
  749.       -- Yield successive integers from 0 up to self-1.
  750.       pre self>=0 is r:SAME;
  751.       loop until!(r>=self); yield r; r:=r+1 end end;
  752.  
  753.    for!(i:SAME):SAME 
  754.       -- Yields `i' successive integers starting with self.
  755.       pre i>=0 is 
  756.       r::=self; e::=self+i;
  757.       loop until!(r>=e); yield r; r:=r+1 end end;      
  758.  
  759.    up!:SAME is
  760.       -- Yield successive integers from self up.
  761.       r::=self;
  762.       loop yield r; r:=r+1 end end;
  763.       
  764.    upto!(i:SAME):SAME is
  765.       -- Yield successive integers from self to `i' inclusive.
  766.       r::=self; 
  767.       loop until!(r>i); yield r; r:=r+1 end end;
  768.       
  769.    downto!(i:SAME):SAME is
  770.       -- Yield successive integers from self down to `i' inclusive.
  771.       r::=self; 
  772.       loop until!(r<i); yield r; r:=r-1 end end;
  773.       
  774.    step!(num,step:SAME):SAME 
  775.       -- Yield `num' integers starting with self and stepping by `step'.
  776.       pre num>=0 is 
  777.       r::=self; last::=self+(num-1)*step;
  778.       if step>0 then 
  779.      loop until!(r>last); yield r; r:=r+step end
  780.       elsif step<0 then 
  781.      loop until!(r<last); yield r; r:=r+step end
  782.       else 
  783.      loop num.times!; yield r end end end;
  784.  
  785.    sum!(i:SAME!):SAME is
  786.       -- Yields the sum of all previous values of `i'.
  787.       r:SAME; loop r:=r+i; yield r end end;
  788.  
  789.    product!(i:SAME!):SAME is
  790.       -- Yields the product of all previous values of `i'.
  791.       r::=1; loop r:=r*i; yield r end end;   
  792.    
  793. end; -- class INT
  794.  
  795. -------------------------------------------------------------------
  796. class TEST_INT is
  797.    include TEST;
  798.    
  799.    main is
  800.       class_name("INT");
  801.       a ::= 5;
  802.       b ::= 7;
  803.       val ::= a.plus(b);
  804.       test("plus",val.str,"12");
  805.       test("plus",(a+b).str,"12");
  806.       test("minus",(a-b).str,"-2");
  807.       test("negate",(-a).str,"-5");
  808.       test("times",(a*b).str,"35");
  809.       test("div",(b/a).str,"1");
  810.       test("mod",(b.mod(a)).str,"2");
  811.       test("is_eq",(b=a).str,"false");
  812.       test("is_eq",(a=a).str,"true");
  813.       -- neq --- missing routines...
  814.       -- ...
  815.       -- Iter routines
  816.       i::=0; loop 9.times!; i:= i+1; end;
  817.       test("times!",i.str,"9");
  818.       res::="";  loop res := res+5.times!+" "; end;
  819.       test("times!:SAME",res,"0 1 2 3 4 ");
  820.       res:="";  loop res := res+5.for!(4)+" "; end;
  821.       test("for!",res,"5 6 7 8 ");
  822.       res:="";  loop res := res+5.upto!(10)+" "; end;
  823.       test("upto!",res,"5 6 7 8 9 10 ");
  824.       res:="";  loop res := res+5.downto!(1)+" "; end;
  825.       test("downto",res,"5 4 3 2 1 ");
  826.       res:="";  loop res := res+5.step!(3,4)+" "; end;
  827.       test("step",res,"5 9 13 ");
  828.       i:=0; loop i := 0.sum!(5.step!(3,4)); end;
  829.       test("sum!",i.str,"27");
  830.       i:=0; loop i := 0.product!(5.step!(3,4)); end;
  831.       test("product!",i.str,"585");
  832.       
  833.       test("pow 2^8",2.pow(8).str,256.str);
  834.       cur ::= 0;
  835.       cur_pow ::= 1;
  836.       loop
  837.      31.times!;
  838.      test("pow 2^"+cur,2.pow(cur).str,cur_pow.str);
  839.      cur := cur + 1;
  840.      cur_pow := cur_pow*2;
  841.      end;
  842.       
  843.       finish;
  844.       end;
  845.    
  846. end; -- class TEST_INT
  847.  
  848. -------------------------------------------------------------------
  849.