(********************************************************************)
(*                                                                  *)
(*  rational.s7i  Rational number support library                   *)
(*  Copyright (C) 1991 - 1994, 2005, 2007 - 2009  Thomas Mertes     *)
(*                2011, 2013 - 2015, 2018, 2023  Thomas Mertes      *)
(*                2024  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.                       *)
(*                                                                  *)
(********************************************************************)


(**
 *  Rational numbers represented with 'integer' numerator and denominator.
 *  The values of the type ''rational'' are finite and periodical
 *  decimal numbers. Rational literals do not exist. The result of a
 *  ''rational'' operation is undefined if it overflows.
 *)
const type: rational is new object struct
    var integer: numerator is 0;
    var integer: denominator is 1;
  end struct;


const proc: normalize (inout rational: 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 rational: number) is func
  local
    var integer: a is 0;
    var integer: b is 0;
    var integer: help is 0;
  begin
    a := abs(number.numerator);
    b := number.denominator;
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
    if b >= 2 then
      number.numerator := number.numerator div b;
      number.denominator := number.denominator div b;
    end if;
  end func;


const func integer: gcd1 (in var integer: a, in var integer: b) is func
  result
    var integer: gcd is 0;
  local
    var integer: help is 0;
  begin
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
    gcd := b;
  end func;


const func integer: gcd2 (in integer: numerator, in integer: denominator) is func
  result
    var integer: b is 0;
  local
    var integer: a is 0;
    var integer: help is 0;
  begin
    if numerator >= 0 then
      a := numerator;
    else
      a := -numerator;
    end if;
    b := denominator;
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
  end func;


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


(**
 *  Plus sign for ''rational'' numbers.
 *  @return its operand unchanged.
 *)
const func rational: + (in rational: number) is
  return number;


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


(**
 *  Add two ''rational'' numbers.
 *  @return the sum of the two numbers.
 *)
const func rational: (in rational: summand1) + (in rational: summand2) is func
  result
    var rational: sum is rational.value;
  local
    var integer: gcd_denominator is 0;
  begin
    gcd_denominator := gcd1(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;
    reduce(sum);
  end func;


(**
 *  Compute the subtraction of two ''rational'' numbers.
 *  @return the difference of the two numbers.
 *)
const func rational: (in rational: minuend) - (in rational: subtrahend) is func
  result
    var rational: difference is rational.value;
  local
    var integer: gcd_denominator is 0;
  begin
    gcd_denominator := gcd1(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;
    reduce(difference);
  end func;


(**
 *  Multiply two ''rational'' numbers.
 *  @return the product of the two numbers.
 *)
const func rational: (in rational: factor1) * (in rational: factor2) is func
  result
    var rational: product is rational.value;
  local
    var integer: gcd1 is 0;
    var integer: gcd2 is 0;
  begin
    gcd1 := gcd2(factor1.numerator, factor2.denominator);
    gcd2 := gcd2(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 ''rational'' numbers.
 *  @return the quotient of the division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 *)
const func rational: (in rational: dividend) / (in rational: divisor) is func
  result
    var rational: quotient is rational.value;
  local
    var integer: gcd1 is 0;
    var integer: gcd2 is 0;
  begin
    gcd1 := gcd2(dividend.numerator, divisor.numerator);
    gcd2 := gcd2(divisor.denominator, dividend.denominator);
    quotient.numerator := (dividend.numerator div gcd1) * (divisor.denominator div gcd2);
    quotient.denominator := (dividend.denominator div gcd2) * (divisor.numerator div gcd1);
    normalize(quotient);
  end func;


(**
 *  Increment a ''rational'' number by a delta.
 *)
const proc: (inout rational: number) +:= (in rational: delta) is func
  local
    var integer: gcd_denominator is 0;
  begin
    gcd_denominator := gcd1(number.denominator, delta.denominator);
    number.numerator := (number.numerator * delta.denominator +
        delta.numerator * number.denominator) div gcd_denominator;
    number.denominator *:= delta.denominator div gcd_denominator;
    reduce(number);
  end func;


(**
 *  Decrement a ''rational'' number by a delta.
 *)
const proc: (inout rational: number) -:= (in rational: delta) is func
  local
    var integer: gcd_denominator is 0;
  begin
    gcd_denominator := gcd1(number.denominator, delta.denominator);
    number.numerator := (number.numerator * delta.denominator -
        delta.numerator * number.denominator) div gcd_denominator;
    number.denominator *:= delta.denominator div gcd_denominator;
    reduce(number);
  end func;


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


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


(**
 *  Compute the exponentiation of a ''rational'' base with an integer exponent.
 *  @return the result of the exponentiation.
 *)
const func rational: (in rational: base) ** (in integer: exponent) is func
  result
    var rational: power is rational.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 ''rational'' numbers are equal.
 *  @return TRUE if both numbers are equal,
 *          FALSE otherwise.
 *)
const func boolean: (in rational: number1) = (in rational: number2) is
  return number1.numerator   = number2.numerator and
         number1.denominator = number2.denominator;


(**
 *  Check if two ''rational'' numbers are not equal.
 *  @return FALSE if both numbers are equal,
 *          TRUE otherwise.
 *)
const func boolean: (in rational: number1) <> (in rational: 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 rational: number1) < (in rational: 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 rational: number1) > (in rational: 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 rational: number1) <= (in rational: 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 rational: number1) >= (in rational: number2) is
  return number1.numerator * number2.denominator >=
         number2.numerator * number1.denominator;


(**
 *  Compare two ''rational'' 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 rational: number1, in rational: number2) is
  return compare(number1.numerator * number2.denominator,
                 number2.numerator * number1.denominator);


(**
 *  Compute the hash value of a ''rational'' number.
 *  @return the hash value.
 *)
const func integer: hashCode (in rational: number) is
  return number.numerator mod 16#40000000 + number.denominator mod 16#40000000;


(**
 *  Return the conversion of an integer to a ''rational''.
 *)
const func rational: rat (in integer: number) is func
  result
    var rational: aRational is rational.value;
  begin
    aRational.numerator := number;
    aRational.denominator := 1;
  end func;


(**
 *  Return the conversion of an integer to a ''rational''.
 *)
const func rational: rational (in integer: number) is func
  result
    var rational: aRational is rational.value;
  begin
    aRational.numerator := number;
    aRational.denominator := 1;
  end func;


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


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


(**
 *  Return a rational number truncated towards negative infinity.
 *)
const func integer: floor (in rational: number) is
  return number.numerator mdiv number.denominator;


(**
 *  Return a rational number rounded up towards positive infinity.
 *)
const func integer: ceil (in rational: number) is
  return -(number.numerator mdiv -number.denominator);


(**
 *  Return a rational number truncated towards zero.
 *)
const func integer: trunc (in rational: number) is
  return number.numerator div number.denominator;


(**
 *  Round a ''rational'' number to the nearest [[integer]].
 *  Halfway cases are rounded away from zero.
 *  @return the rounded value.
 *)
const func integer: round (in rational: number) is func
  result
    var integer: 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;


(**
 *  Round a ''rational'' number with a decimal ''precision''.
 *  Halfway cases are rounded away from zero.
 *  @return the rounded value.
 *)
const func rational: round10 (in rational: number, in integer: precision) is func
  result
    var rational: rounded is rational.value;
  begin
    if precision < 0 then
      rounded.numerator := (abs(number.numerator) div 10 ** pred(-precision) +
                           number.denominator * 5) div (number.denominator * 10) *
                           10 ** (-precision);
      rounded.denominator := 1;
    else
      rounded.numerator := (abs(number.numerator) * 10 ** succ(precision) +
                           number.denominator * 5) div (number.denominator * 10);
      rounded.denominator := 10 ** precision;
    end if;
    if number.numerator < 0 then
      rounded.numerator := -rounded.numerator;
    end if;
  end func;


const type: INT_REMAINDER_HASH_TYPE is hash [integer] integer;


(**
 *  Convert a ''rational'' number to a [[string]].
 *  The number is converted to a string with a decimal representation
 *  (e.g.: "1.25"). The representation has a decimal point and at
 *  least one digit before and after the decimal point. Negative
 *  numbers are preceded by a minus sign (e.g.: "-1.25"). The
 *  decimal number can have repeating decimals, which are enclosed
 *  in parentheses ("e.g.: "0.(3)"). The repeating decimals will
 *  not start before the decimal point.
 *  @return the string result of the conversion.
 *)
const func string: str (in rational: number) is func
  result
    var string: stri is "";
  local
    var integer: remainder is 0;
    var INT_REMAINDER_HASH_TYPE: remainderHash is INT_REMAINDER_HASH_TYPE.value;
    var integer: pos is 0;
  begin
    if number.denominator = 0 then
      if number.numerator > 0 then
        stri := "Infinity";
      elsif number.numerator = 0 then
        stri := "NaN";
      else
        stri := "-Infinity";
      end if;
    else
      stri := str(abs(number.numerator) div number.denominator);
      stri &:= ".";
      remainder := abs(number.numerator) rem number.denominator;
      if remainder = 0 then
        stri &:= "0";
      else
        repeat
          remainderHash @:= [remainder] length(stri);
          remainder *:= 10;
          stri &:= str(remainder div number.denominator);
          remainder := remainder rem number.denominator;
        until remainder = 0 or remainder in remainderHash;
        if remainder <> 0 then
          pos := remainderHash[remainder];
          stri := stri[.. pos] & "(" & stri[succ(pos) ..] & ")";
        end if;
      end if;
      if number.numerator < 0 then
        stri := "-" & stri;
      end if;
    end if;
  end func;


(**
 *  Convert a ''rational'' to a [[string]] with a fraction.
 *   fraction(rational("0.(3)"))  returns  "1/3"
 *  @return the string with the corrresponding fraction.
 *)
const func string: fraction (in rational: number) is
    return str(number.numerator) & "/" & str(number.denominator);


(**
 *  Convert a ''rational'' number to a [[string]] in decimal fixed point notation.
 *  The number is rounded to the specified number of digits (''precision'').
 *  Halfway cases are rounded away from zero. Except for a ''precision'' of
 *  zero the representation has a decimal point and at least one digit
 *  before and after the decimal point. Negative numbers are preceded by
 *  a minus sign (e.g.: "-1.25"). If all digits in the result are 0 a
 *  possible negative sign is omitted.
 *   1/64 digits 7     returns "0.0156250"
 *   1/64 digits 4     returns "0.0156"
 *   1/64 digits 2     returns "0.02"
 *   355/113 digits 6  returns "3.141593"
 *   22/7 digits 0     returns "3"
 *   -1/2 digits 1     returns "-1"
 *   1/0 digits 5      returns "Infinity"
 *   -1/0 digits 6     returns "-Infinity"
 *   0/0 digits 7      returns "NaN"
 *   -1/2048 digits 3  returns "0.000"
 *  @param precision Number of digits after the decimal point.
 *         If the ''precision'' is zero the decimal point is omitted.
 *  @return the string result of the conversion.
 *  @exception RANGE_ERROR If the ''precision'' is negative.
 *)
const func string: (in rational: number) digits (in integer: precision) is func
  result
    var string: stri is "";
  local
    var integer: mantissa is 0;
  begin
    if precision < 0 then
      raise RANGE_ERROR;
    elsif number.denominator = 0 then
      if number.numerator > 0 then
        stri := "Infinity";
      elsif number.numerator = 0 then
        stri := "NaN";
      else
        stri := "-Infinity";
      end if;
    else
      mantissa := (abs(number.numerator) * 10 ** succ(precision) +
                  number.denominator * 5) div (number.denominator * 10);
      stri := str(mantissa);
      if precision >= length(stri) then
        stri := "0" mult (precision - length(stri) + 1) & stri;
      end if;
      if precision <> 0 then
        stri := stri[ .. length(stri) - precision] & "." &
            stri[length(stri) - precision + 1 .. ];
      end if;
      if number.numerator < 0 and mantissa <> 0 then
        stri := "-" & stri;
      end if;
    end if;
  end func;


const func integer: decimalExponent (in rational: number) is func
  result
    var integer: exponent is 0;
  begin
    if abs(number.numerator) >= number.denominator then
      exponent := log10(abs(number.numerator) div number.denominator);
    else
      exponent := -log10(number.denominator div abs(number.numerator)) - 1;
    end if;
  end func;


(**
 *  Convert a ''rational'' number to a [[string]] in scientific notation.
 *  Scientific notation uses a decimal significand and a decimal exponent.
 *  The significand has an optional sign and exactly one digit before the
 *  decimal point. The fractional part of the significand is rounded
 *  to the specified number of digits (''precision''). Halfway cases are
 *  rounded away from zero. The fractional part is followed by the
 *  letter e and an exponent, which is always signed. The value zero is
 *  never written with a negative sign.
 *   1/64 sci 4     returns "1.5625e-2"
 *   1/64 sci 3     returns "1.563e-2"
 *   1/64 sci 2     returns "1.56e-2"
 *   355/113 sci 6  returns "3.141593e+0"
 *   22/7 sci 0     returns "3e+0"
 *   -1/2 sci 1     returns "-5.0e-1"
 *   1/0 sci 5      returns "Infinity"
 *   -1/0 sci 6     returns "-Infinity"
 *   0/0 sci 7      returns "NaN"
 *   -1/2048 sci 3  returns "-4.883e-4"
 *   -0/1 sci 2     returns "0.00e+0"
 *  @param precision Number of digits after the decimal point.
 *         If the ''precision'' is zero the decimal point is omitted.
 *  @return the string result of the conversion.
 *  @exception RANGE_ERROR If the ''precision'' is negative.
 *)
const func string: (in rational: number) sci (in integer: precision) is func
  result
    var string: stri is "";
  local
    var integer: exponent is 0;
    var integer: mantissa is 0;
  begin
    if precision < 0 then
      raise RANGE_ERROR;
    elsif number.denominator = 0 then
      if number.numerator > 0 then
        stri := "Infinity";
      elsif number.numerator = 0 then
        stri := "NaN";
      else
        stri := "-Infinity";
      end if;
    elsif number.numerator = 0 then
      if precision = 0 then
        stri := "0e+0";
      else
        stri := "0." & "0" mult precision & "e+0";
      end if;
    else
      exponent := decimalExponent(number);
      if succ(precision) >= exponent then
        mantissa := (abs(number.numerator) * 10 ** succ(precision - exponent) +
                    number.denominator * 5) div (number.denominator * 10);
      else
        mantissa := (abs(number.numerator) div 10 ** pred(exponent - precision) +
                    number.denominator * 5) div (number.denominator * 10);
      end if;
      stri := str(mantissa);
      if length(stri) > succ(precision) then
        # Rounding up increased the number of digits.
        incr(exponent);
        stri := stri[.. succ(precision)];
      end if;
      if precision <> 0 then
        stri := stri[1 fixLen 1] & "." & stri[2 .. ];
      end if;
      if exponent >= 0 then
        stri &:= "e+" <& exponent;
      else
        stri &:= "e" <& exponent;
      end if;
      if number.numerator < 0 then
        stri := "-" & stri;
      end if;
    end if;
  end func;


(**
 *  Convert a [[string]] to a ''rational'' number.
 *  The [[string]] must contain a fraction (e.g.: "3/5") or a decimal number
 *  (e.g.: "1.25"). In a fraction numerator and denominator are separated
 *  with a slash (/). A decimal number can have repeating decimals,
 *  which are enclosed in parentheses ("e.g.: "0.(3)"). The repeating
 *  decimals are not allowed to start before the decimal point.
 *   rational("3/5")         returns   3 /   5
 *   rational("1.25")        returns   5 /   4
 *   rational("0.(3)")       returns   1 /   3
 *   rational("1.23(45)")    returns 679 / 550
 *   rational("3.(142857)")  returns  22 /   7
 *   rational("0.(846153)")  returns  11 /  13
 *  @return the ''rational'' result of the conversion.
 *  @exception RANGE_ERROR If stri contains not a valid ''rational'' value.
 *)
const func rational: rational (in var string: stri) is func
  result
    var rational: aRational is rational.value;
  local
    var boolean: negative is FALSE;
    var string: fraction is "";
    var string: period is "";
  begin
    if stri <> "" then
      if stri[1] = '-' then
        stri := stri[2 ..];
        negative := TRUE;
      elsif stri[1] = '+' then
        stri := stri[2 ..];
      end if;
      aRational.numerator := integer(getint(stri));
      if stri[1] = '/' then
        stri := stri[2 ..];
        aRational.denominator := integer(getint(stri));
        reduce(aRational);
      elsif stri[1] = '.' then
        stri := stri[2 ..];
        if startsWith(stri, "(") then
          stri := stri[2 ..];
          period := getint(stri);
          aRational.denominator := 1;
          aRational +:= integer(period) / pred(10 ** length(period));
          if stri[1] = ')' then
            stri := stri[2 ..];
          end if;
        else
          fraction := getint(stri);
          aRational.denominator := 10 ** length(fraction);
          aRational.numerator *:= aRational.denominator;
          aRational.numerator +:= integer(fraction);
          if startsWith(stri, "(") then
            stri := stri[2 ..];
            period := getint(stri);
            aRational +:= integer(period) / (pred(10 ** length(period)) * aRational.denominator);
            if stri[1] = ')' then
              stri := stri[2 ..];
            end if;
          end if;
        end if;
        reduce(aRational);
      end if;
      if stri <> "" then
        raise RANGE_ERROR;
      elsif negative then
        aRational.numerator := -aRational.numerator;
      end if;
    else
      raise RANGE_ERROR;
    end if;
  end func;


(**
 *  Convert a [[string]] to a ''rational'' number.
 *  The [[string]] must contain a fraction (e.g.: "3/5") or a decimal number
 *  (e.g.: "1.25"). In a fraction numerator and denominator are separated
 *  with a slash (/). A decimal number can have repeating decimals,
 *  which are enclosed in parentheses ("e.g.: "0.(3)"). The repeating
 *  decimals are not allowed to start before the decimal point.
 *   rational parse "3/5"         returns   3 /   5
 *   rational parse "1.25"        returns   5 /   4
 *   rational parse "0.(3)"       returns   1 /   3
 *   rational parse "1.23(45)"    returns 679 / 550
 *   rational parse "3.(142857)"  returns  22 /   7
 *   rational parse "0.(846153)"  returns  11 /  13
 *  @return the ''rational'' result of the conversion.
 *  @exception RANGE_ERROR If stri contains not a valid ''rational'' value.
 *)
const func rational: (attr rational) parse (in string: stri) is
    return rational(stri);


enable_io(rational);
DECLARE_TERNARY(rational);
DECLARE_MIN_MAX(rational);


# Allows 'array rational' everywhere without extra type definition.
const type: _rationalArray is array rational;