------------------------------------------------------------------------------
--- A collection of common operations on integer numbers.
--- Most operations make no assumption on the precision of integers.
--- Operation <EM>bitNot</EM> is necessarily an exception.
---
--- @author Sergio Antoy
--- @version Sept 4, 2003
--  Thu Sep  4 12:42:05 PDT 2003
------------------------------------------------------------------------------

module Integer(pow, ilog, isqrt, factorial, binomial,
               abs, max, min, max3, min3, maxlist, minlist,
               bitTrunc, bitAnd, bitOr, bitNot, bitXor,
               even, odd) where

------------------------------------------------------------------
--                       Public Operations
------------------------------------------------------------------

--- The value of <EM>pow a b</EM> is <EM>a</EM>
--- raised to the power of <EM>b</EM>.
--- Fails if <EM>b < 0</EM>.
--- Executes in <EM>O(log b)</EM> steps.
---
--- @param a - The base.
--- @param b - The exponent.
--- @return <EM>a</EM> raised to the power of <EM>b</EM>.

pow a b | b>= 0 = powaux 1 a b
  where
    powaux n x y = if y == 0 then n
                   else powaux (n * if (y `mod` 2 == 1) then x else 1)
                               (x * x)
                               (y `div` 2)

--- The value of <EM>ilog n</EM> is the floor of the logarithm
--- in the base 10 of <EM>n</EM>.
--- Fails if <EM>n <= 0</EM>.
--- For positive integers, the returned value is
--- 1 less the number of digits in the decimal representation of <EM>n</EM>.
---
--- @param n - The argument.
--- @return the floor of the logarithm in the base 10 of <EM>n</EM>.

ilog n | n>0 = if n<10 then 0 else 1 + ilog (n `div` 10)

--- The value of <EM>isqrt n</EM> is the floor
--- of the square root of <EM>n</EM>.
--- Fails if <EM>n < 0</EM>.
--- Executes in <EM>O(log n)</EM> steps, but there must be a better way.
---
--- @param n - The argument.
--- @return the floor of the square root of <EM>n</EM>.

isqrt n | n >= 0 =
  if n == 0 then 0 else
  if n <  4 then 1 else
  aux 2 n
  where aux low past = -- invariant low <= result < past
          if past == low+1 then low
          else let cand = (past + low) `div` 2
                in if cand*cand > n then aux low cand else aux cand past

--- The value of <EM>factorial n</EM> is the factorial of <EM>n</EM>.
--- Fails if <EM>n < 0</EM>.
---
--- @param n - The argument.
--- @return the factorial of <EM>n</EM>.

factorial n | n >= 0 = if n == 0 then 1 else n * factorial (n-1)

--- The value of <EM>binomial n m</EM> is 
--- n*(n-1)*...*(n-m+1)/m*(m-1)*...1
--- Fails if <EM>m <= 0</EM> or <EM>n < m</EM>.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the binomial coefficient of <EM>n</EM> over <EM>m</EM>.

binomial n m | m > 0 && n >= m = aux m n `div` factorial m
  where aux x y = if x == 0 then 1 else y * aux (x-1) (y-1)

--- The value of <EM>abs n</EM> is the absolute value of <EM>n</EM>.
---
--- @param n - The argument.
--- @return the absolute value of <EM>n</EM>.

abs n = if n<0 then -n else n

--- Returns the maximum of the two arguments
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the maximum of <EM>n</EM> and <EM>m</EM>.

max n m = if n<m then m else n

--- Returns the minimum of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the minimum of <EM>n</EM> and <EM>m</EM>.

min n m = if n<m then n else m

--- Returns the maximum of the three arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @param p - Argument.
--- @return the maximum among <EM>n</EM>, <EM>m</EM> and <EM>p</EM>.

max3 n m p = max n (max m p)

--- Returns the minimum of the three arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @param p - Argument.
--- @return the minimum among <EM>n</EM>, <EM>m</EM> and <EM>p</EM>.

min3 n m p = min n (min m p)

--- Returns the maximum of a list of integer values.
--- Fails if the list is empty.
---
--- @param l - The list of values.
--- @return the maximum element of <EM>l</EM>.

maxlist [n] = n
maxlist (n:m:ns) = max n (maxlist (m:ns))

--- Returns the minimum of a list of integer values.
--- Fails if the list is empty.
---
--- @param l - The list of values.
--- @return the minimum element of <EM>l</EM>.

minlist [n] = n
minlist (n:m:ns) = min n  (minlist (m:ns))

--- The value of <EM>bitTrunc n m</EM> is the value of the <EM>n</EM>
--- least significant bits of <EM>m</EM>.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return <EM>m</EM> truncated to the <EM>n</EM> least significant bits.

bitTrunc n m = bitAnd (pow 2 n - 1) m

--- Returns the bitwise AND of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise and of <EM>n</EM> and <EM>m</EM>.

bitAnd n m = if m == 0 then 0
             else let p = 2 * bitAnd (n `div` 2) (m `div` 2)
                      q = if m `mod` 2 == 0 then 0 else n `mod` 2
                   in p + q

--- Returns the bitwise inclusive OR of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise inclusive or of <EM>n</EM> and <EM>m</EM>.

bitOr n m = if m == 0 then n
            else let p = 2 * bitOr (n `div` 2) (m `div` 2)
                     q = if m `mod` 2 == 1 then 1 else n `mod` 2
                  in p + q

--- Returns the bitwise NOT of the argument.
--- Since integers have unlimited precision,
--- only the 32 least significant bits are computed.
---
--- @param n - Argument.
--- @return the bitwise negation of <EM>n</EM> truncated to 32 bits.

bitNot n = aux 32 n
  where aux c m = if c==0 then 0
                  else let p = 2 * aux (c-1) (m `div` 2)
                           q = 1 - m `mod` 2
                        in p + q

--- Returns the bitwise exclusive OR of the two arguments.
---
--- @param n - Argument.
--- @param m - Argument.
--- @return the bitwise exclusive of <EM>n</EM> and <EM>m</EM>.

bitXor n m = if m == 0 then n
             else let p = 2 * bitXor (n `div` 2) (m `div` 2)
                      q = if m `mod` 2 == n `mod` 2 then 0 else 1
                   in p + q

--- Returns whether an integer is even
---
--- @param n - Argument.
--- @return whether <EM>n</EM> is even.

even n = n `mod` 2 == 0

--- Returns whether an integer is odd
---
--- @param n - Argument.
--- @return whether <EM>n</EM> is odd.

odd n = n `mod` 2 /= 0