
(********************************************************************)
(*                                                                  *)
(*  bigrat.s7i    Big rational number support library               *)
(*  Copyright (C) 2006, 2007  Thomas Mertes                         *)
(*                                                                  *)
(*  This file is part of the Seed7 Runtime Library.                 *)
(*                                                                  *)
(*  The Seed7 Runtime Library is free software; you can             *)
(*  redistribute it and/or modify it under the terms of the GNU     *)
(*  Lesser General Public License as published by the Free Software *)
(*  Foundation; either version 2.1 of the License, or (at your      *)
(*  option) any later version.                                      *)
(*                                                                  *)
(*  The Seed7 Runtime 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 the GNU Lesser General Public License for more    *)
(*  details.                                                        *)
(*                                                                  *)
(*  You should have received a copy of the GNU Lesser General       *)
(*  Public License along with this program; if not, write to the    *)
(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
(*                                                                  *)
(********************************************************************)


include "bigint.s7i";


(**
 *  Rational numbers represented with 'bigInteger' numerator and denominator.
 *  The values of the type 'bigRational' are finite and periodical
 *  decimal numbers. BigRational literals do not exist. Although
 *  'bigRational' operations cannot overflow, it can happen that
 *  there is not enough memory to represent a 'bigRational' value.
 *  In this case the exception 'MEMORY_ERROR' is raised.
 *)
const type: bigRational is new object struct
    var bigInteger: numerator is 0_;
    var bigInteger: denominator is 1_;
  end struct;


const proc: normalize (inout bigRational: number) is func
  begin
    if number.denominator < 0_ then
      number.numerator := -number.numerator;
      number.denominator := -number.denominator;
    end if;
  end func;


const proc: reduce (inout bigRational: number) is func
  local
    var bigInteger: gcd is 0_;
  begin
    gcd := gcd(number.numerator, number.denominator);
    number.numerator := number.numerator div gcd;
    number.denominator := number.denominator div gcd;
  end func;


(**
 *  Create a bigRational number from its numerator and denominator.
 *  @return the created bigRational value.
 *)
const func bigRational: (in bigInteger: numerator) / (in bigInteger: denominator) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := numerator;
    result.denominator := denominator;
    normalize(result);
    reduce(result);
  end func;


(**
 *  Plus sign for bigRational numbers.
 *  @return its operand unchanged.
 *)
const func bigRational: + (in bigRational: number) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := number.numerator;
    result.denominator := number.denominator;
  end func;


(**
 *  Minus sign, negate a bigRational number.
 *  @return the negated value of the number.
 *)
const func bigRational: - (in bigRational: number) is func
  result
    var bigRational: negatedValue is bigRational.value;
  begin
    negatedValue.numerator := -number.numerator;
    negatedValue.denominator := number.denominator;
  end func;


(**
 *  Add two bigRational numbers.
 *  @return the sum of the two numbers.
 *)
const func bigRational: (in bigRational: summand1) + (in bigRational: summand2) is func
  result
    var bigRational: sum is bigRational.value;
  local
    var bigInteger: gcd_denominator is 0_;
  begin
    gcd_denominator := gcd(summand1.denominator, summand2.denominator);
    sum.numerator := (summand1.numerator * summand2.denominator +
        summand2.numerator * summand1.denominator) div gcd_denominator;
    sum.denominator := summand1.denominator div gcd_denominator * summand2.denominator;
  end func;


(**
 *  Compute the subtraction of two bigRational numbers.
 *  @return the difference of the two numbers.
 *)
const func bigRational: (in bigRational: minuend) - (in bigRational: subtrahend) is func
  result
    var bigRational: difference is bigRational.value;
  local
    var bigInteger: gcd_denominator is 0_;
  begin
    gcd_denominator := gcd(minuend.denominator, subtrahend.denominator);
    difference.numerator := (minuend.numerator * subtrahend.denominator -
        subtrahend.numerator * minuend.denominator) div gcd_denominator;
    difference.denominator := minuend.denominator div gcd_denominator * subtrahend.denominator;
  end func;


(**
 *  Multiply two bigRational numbers.
 *  @return the product of the two numbers.
 *)
const func bigRational: (in bigRational: factor1) * (in bigRational: factor2) is func
  result
    var bigRational: product is bigRational.value;
  local
    var bigInteger: gcd1 is 0_;
    var bigInteger: gcd2 is 0_;
  begin
    gcd1 := gcd(factor1.numerator, factor2.denominator);
    gcd2 := gcd(factor2.numerator, factor1.denominator);
    product.numerator := (factor1.numerator div gcd1) * (factor2.numerator div gcd2);
    product.denominator := (factor1.denominator div gcd2) * (factor2.denominator div gcd1);
  end func;


(**
 *  Compute the division of two bigRational numbers.
 *  @return the quotient of the division.
 *  @exception NUMERIC_ERROR When a division by zero occurs.
 *)
const func bigRational: (in bigRational: dividend) / (in bigRational: divisor) is func
  result
    var bigRational: quotient is bigRational.value;
  begin
    quotient.numerator := dividend.numerator * divisor.denominator;
    quotient.denominator := dividend.denominator * divisor.numerator;
    normalize(quotient);
    reduce(quotient);
  end func;


(**
 *  Increment a bigRational number by a delta.
 *)
const proc: (inout bigRational: number) +:= (in bigRational: delta) is func
  local
    var bigInteger: gcd_denominator is 0_;
  begin
    gcd_denominator := gcd(number.denominator, delta.denominator);
    number.numerator := (number.numerator * delta.denominator +
        delta.numerator * number.denominator) div gcd_denominator;
    number.denominator *:= delta.denominator div gcd_denominator;
  end func;


(**
 *  Decrement a bigRational number by a delta.
 *)
const proc: (inout bigRational: number) -:= (in bigRational: delta) is func
  local
    var bigInteger: gcd_denominator is 0_;
  begin
    gcd_denominator := gcd(number.denominator, delta.denominator);
    number.numerator := (number.numerator * delta.denominator -
        delta.numerator * number.denominator) div gcd_denominator;
    number.denominator *:= delta.denominator div gcd_denominator;
  end func;


(**
 *  Multiply a bigRational number by a factor and assign the result back to number.
 *)
const proc: (inout bigRational: number) *:= (in bigRational: factor) is func
  begin
    number.numerator *:= factor.numerator;
    number.denominator *:= factor.denominator;
    reduce(number);
  end func;


(**
 *  Divide a bigRational number by a divisor and assign the result back to number.
 *)
const proc: (inout bigRational: number) /:= (in bigRational: divisor) is func
  begin
    number.numerator *:= divisor.denominator;
    number.denominator *:= divisor.numerator;
    normalize(number);
    reduce(number);
  end func;


(**
 *  Compute the exponentiation of a bigRational base by an integer exponent.
 *  @return the result of the exponentation.
 *)
const func bigRational: (in bigRational: base) ** (in integer: exponent) is func
  result
    var bigRational: power is bigRational.value;
  begin
    if exponent >= 0 then
      power.numerator := base.numerator ** exponent;
      power.denominator := base.denominator ** exponent;
    else
      power.numerator := base.denominator ** (-exponent);
      power.denominator := base.numerator ** (-exponent);
      normalize(power);
    end if;
  end func;


(**
 *  Check if two bigRational numbers are equal.
 *  @return TRUE if both numbers are equal,
 *          FALSE otherwise.
 *)
const func boolean: (in bigRational: number1) = (in bigRational: number2) is
  return number1.numerator   = number2.numerator and
         number1.denominator = number2.denominator;


(**
 *  Check if two bigRational numbers are not equal.
 *  @return FALSE if both numbers are equal,
 *          TRUE otherwise.
 *)
const func boolean: (in bigRational: number1) <> (in bigRational: number2) is
  return number1.numerator   <> number2.numerator or
         number1.denominator <> number2.denominator;


(**
 *  Check if number1 is less than number2.
 *  @return TRUE if number1 is less than number2,
 *          FALSE otherwise.
 *)
const func boolean: (in bigRational: number1) < (in bigRational: number2) is
  return number1.numerator * number2.denominator <
         number2.numerator * number1.denominator;


(**
 *  Check if number1 is greater than number2.
 *  @return TRUE if number1 is greater than number2,
 *          FALSE otherwise.
 *)
const func boolean: (in bigRational: number1) > (in bigRational: number2) is
  return number1.numerator * number2.denominator >
         number2.numerator * number1.denominator;


(**
 *  Check if number1 is less than or equal to number2.
 *  @return TRUE if number1 is less than or equal to number2,
 *          FALSE otherwise.
 *)
const func boolean: (in bigRational: number1) <= (in bigRational: number2) is
  return number1.numerator * number2.denominator <=
         number2.numerator * number1.denominator;


(**
 *  Check if number1 is greater than or equal to number2.
 *  @return TRUE if number1 is greater than or equal to number2,
 *          FALSE otherwise.
 *)
const func boolean: (in bigRational: number1) >= (in bigRational: number2) is
  return number1.numerator * number2.denominator >=
         number2.numerator * number1.denominator;


(**
 *  Compare two bigRational numbers.
 *  @return -1, 0 or 1 if the first argument is considered to be
 *          respectively less than, equal to, or greater than the
 *          second.
 *)
const func integer: compare (in bigRational: number1, in bigRational: number2) is func
  result
    var integer: result is 0;
  begin
    if number1.numerator * number2.denominator <
        number2.numerator * number1.denominator then
      result := -1;
    elsif number1.numerator * number2.denominator >
        number2.numerator * number1.denominator then
      result := 1;
    end if;
  end func;


(**
 *  Compute the hash value of a bigRational number.
 *  @return the hash value.
 *)
const func integer: hashCode (in bigRational: number) is
  return hashCode(number.numerator) * hashCode(number.denominator);


(**
 *  Return the conversion of a bigInteger to a bigRational.
 *)
const func bigRational: rat (in bigInteger: number) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := number;
    result.denominator := 1_;
  end func;


(**
 *  Return the conversion of an integer to a bigRational.
 *)
const func bigRational: (attr bigRational) conv (in integer: number) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := bigInteger conv number;
    result.denominator := 1_;
  end func;


(**
 *  Return the conversion of a bigInteger to a bigRational.
 *)
const func bigRational: (attr bigRational) conv (in bigInteger: number) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := number;
    result.denominator := 1_;
  end func;


(**
 *  Compute the absolute value of a bigRational number.
 *  @return the absolute value.
 *)
const func bigRational: abs (in bigRational: number) is func
  result
    var bigRational: absoluteValue is bigRational.value;
  begin
    absoluteValue.numerator := abs(number.numerator);
    absoluteValue.denominator := number.denominator;
  end func;


(**
 *  Convert a bigRational number to a string.
 *  The number is converted to a string with a fraction (e.g.: "3/5"),
 *  were numerator and denominator are separated with a slash (/).
 *  @return the string result of the conversion.
 *)
const func string: str (in bigRational: number) is func
  result
    var string: result is "";
  begin
    result := str(number.numerator) & "/" & str(number.denominator);
  end func;


(**
 *  Convert a bigRational number to a string.
 *  The number is converted to a string with decimal representation.
 *  The precision parameter specifies the number of digits after
 *  the decimal point.
 *  @return the string result of the conversion.
 *)
const func string: (in bigRational: number) digits (in integer: precision) is func
  result
    var string: result is "";
  begin
    result := str((number.numerator * 10_ ** precision) div number.denominator);
    if precision + 1 - length(result) > 0 then
      result := "0" mult (precision + 1 - length(result)) & result;
    end if;
    result := result[ .. length(result) - precision] & "." &
        result[length(result) - precision + 1 .. ];
  end func;


(**
 *  Convert a string to a bigRational number.
 *  The string must contain a fraction (e.g.: "3/5"), were numerator
 *  and denominator are separated with a slash (/).
 *  @return the bigRational result of the conversion.
 *  @exception RANGE_ERROR When stri contains not a valid bigRational value.
 *)
const func bigRational: (attr bigRational) parse (in var string: stri) is func
  result
    var bigRational: result is bigRational.value;
  begin
    result.numerator := bigInteger parse getint(stri);
    if stri[1] <> '/' then
      raise RANGE_ERROR;
    end if;
    stri := stri[2 ..];
    result.denominator := bigInteger parse getint(stri);
  end func;


enable_io(bigRational);


(**
 *  Return a bigRational number truncated towards negative infinity.
 *)
const func bigInteger: floor (ref bigRational: number) is func
  result
    var bigInteger: int_val is 0_;
  begin
    int_val := number.numerator mdiv number.denominator;
  end func;


(**
 *  Return a bigRational number rounded up towards positive infinity.
 *)
const func bigInteger: ceil (ref bigRational: number) is func
  result
    var bigInteger: int_val is 0_;
  begin
    int_val := -(number.numerator mdiv -number.denominator);
  end func;


(**
 *  Return a bigRational number truncated towards zero.
 *)
const func bigInteger: trunc (ref bigRational: number) is func
  result
    var bigInteger: int_val is 0_;
  begin
    int_val := number.numerator div number.denominator;
  end func;


(**
 *  Return a bigRational number rounded towards zero.
 *)
const func bigInteger: round (ref bigRational: number) is func
  result
    var bigInteger: int_val is 0;
  begin
    if number.numerator >= 0_ then
      int_val := (2_ * number.numerator + number.denominator) div (2_ * number.denominator);
    else
      int_val := (2_ * number.numerator - number.denominator) div (2_ * number.denominator);
    end if;
  end func;
