digits.ex

defmodule Cldr.Digits do
  @moduledoc """
  Abstract representation of number (integer, float, Decimal) in tuple form
  and functions for transformations on number parts.

  Representing a number as a list of its digits, and integer representing
  where the decimal point is placed and an integer representing the sign
  of the number allow more efficient transforms on the various parts of
  the number as happens during the formatting of a number for string output.
  """

  import Bitwise
  import Cldr.Math, only: [power_of_10: 1]
  require Integer
  alias Cldr.Math

  @typedoc """
  Defines a number in a tuple form of three parts:

  * A list of digits (0..9) representing the number

  * A digit representing the place of the decimal points
  in the number

  * a `1` or `-1` representing the sign of the number

  A number in integer, float or Decimal form can be converted
  to digit form with `Digits.to_digits/1`.

  The digits can be converted back to normal form with
  `Cldr.Digits.to_integer/1`, `Cldr.Digits.to_float/1` and
  `Cldr.Digits.to_decimal/1`.
  """
  @type t :: {[0..9, ...], non_neg_integer, 1 | -1}

  @two52 bsl(1, 52)
  @two53 bsl(1, 53)
  @float_bias 1022
  @min_e -1074

  @doc """
  Returns the fractional part of an integer, float or Decimal as an integer.

  * `number` can be either a float, Decimal or integer although an integer has
    no fraction part and will therefore always return 0.

  ## Examples

      iex> Cldr.Digits.fraction_as_integer(123.456)
      456

      iex> Cldr.Digits.fraction_as_integer(Decimal.new("123.456"))
      456

      iex> Cldr.Digits.fraction_as_integer(1999)
      0

  """
  @spec fraction_as_integer(Math.number_or_decimal() | {list, list, 1 | -1}) :: integer
  def fraction_as_integer({_integer, fraction, _sign})
      when is_list(fraction) do
    Integer.undigits(fraction)
  end

  def fraction_as_integer({_integer, [], _sign}) do
    0
  end

  def fraction_as_integer(number) do
    number
    |> to_tuple
    |> fraction_as_integer
  end

  def fraction_as_integer(number, rounding) do
    number = Float.round(number, rounding)
    fraction_as_integer(number)
  end

  @doc """
  Returns the number of decimal digits in a number
  (integer, float, Decimal)

  ## Options

  * `number` is an integer, float or `Decimal`
  or a list (which is assumed to contain digits).

  ## Examples

      iex> Cldr.Digits.number_of_digits(1234)
      4

      iex> Cldr.Digits.number_of_digits(Decimal.new("123456789"))
      9

      iex> Cldr.Digits.number_of_digits(1234.456)
      7

      iex> Cldr.Digits.number_of_digits(1234.56789098765)
      15

      iex> Cldr.Digits.number_of_digits '12345'
      5

  """
  @spec number_of_digits(
          Math.number_or_decimal()
          | list()
          | {[integer(), ...], integer | [integer(), ...], -1 | 1}
        ) :: integer

  def number_of_digits(%Decimal{} = number) do
    number
    |> to_digits
    |> number_of_digits
  end

  def number_of_digits(number) when is_number(number) do
    number
    |> to_digits
    |> number_of_digits
  end

  def number_of_digits(list) when is_list(list) do
    length(list)
  end

  def number_of_digits({integer, place, _sign})
      when is_list(integer) and is_integer(place) do
    length(integer)
  end

  @doc """
  Returns the number of decimal digits in the integer
  part of a number.

  ## Options

  * `number` is an integer, float or `Decimal` or
  a list (which is assumed to contain digits).

  ## Examples

      iex> Cldr.Digits.number_of_integer_digits(1234)
      4

      iex> Cldr.Digits.number_of_integer_digits(Decimal.new("123456789"))
      9

      iex> Cldr.Digits.number_of_integer_digits(1234.456)
      4

      iex> Cldr.Digits.number_of_integer_digits '12345'
      5

  """
  @spec number_of_integer_digits(
          Math.number_or_decimal()
          | list()
          | {[integer(), ...], integer | [integer(), ...], -1 | 1}
        ) :: integer
  def number_of_integer_digits(%Decimal{} = number) do
    number
    |> to_digits
    |> number_of_integer_digits
  end

  def number_of_integer_digits(number) when is_number(number) do
    number
    |> to_digits
    |> number_of_integer_digits
  end

  # A decomposed integer might be charlist or a list of integers
  # since for certain transforms this is more efficient.  Note
  # that we are not checking if the list elements are actually
  # digits.
  def number_of_integer_digits(list) when is_list(list) do
    length(list)
  end

  # For a tuple returned by `Digits.to_digits/1`
  def number_of_integer_digits({integer, place, _sign})
      when is_list(integer) and is_integer(place) and place <= 0 do
    0
  end

  def number_of_integer_digits({integer, place, _sign})
      when is_list(integer) and is_integer(place) do
    place
  end

  # For a tuple returned by `Digits.to_tuple/1`
  def number_of_integer_digits({[], _fraction, _sign}) do
    0
  end

  def number_of_integer_digits({integer, fraction, _sign})
      when is_list(integer) and is_list(fraction) do
    number_of_integer_digits(integer)
  end

  @doc """
  Remove trailing zeroes from the integer part of a number
  and returns the integer part without trailing zeros.

  * `number` is an integer, float or Decimal.

  ## Examples

      iex> Cldr.Digits.remove_trailing_zeros(1234000)
      1234

  """
  @spec remove_trailing_zeros(Math.number_or_decimal() | [integer(), ...]) ::
          integer | [integer(), ...]
  def remove_trailing_zeros(0) do
    0
  end

  def remove_trailing_zeros(number) when is_number(number) do
    {integer_digits, _fraction_digits, sign} = to_tuple(number)
    removed = remove_trailing_zeros(integer_digits)
    to_integer({removed, length(removed), sign})
  end

  def remove_trailing_zeros(%Decimal{} = number) do
    {integer_digits, _fraction_digits, sign} = to_tuple(number)
    removed = remove_trailing_zeros(integer_digits)
    to_integer({removed, length(removed), sign})
  end

  # Filters either a charlist or a list of integers.
  def remove_trailing_zeros(number) when is_list(number) do
    Enum.take_while(number, fn c ->
      (c >= ?1 and c <= ?9) or c > 0
    end)
  end

  @doc """
  Returns the number of leading zeros in a
  Decimal fraction.

  * `number` is an integer, float or Decimal

  Returns the number of leading zeros in the fractional
  part of a number.

  ## Examples

      iex> Cldr.Digits.number_of_leading_zeros(Decimal.new("0.0001"))
      3

  """
  @spec number_of_leading_zeros(Math.number_or_decimal() | [integer(), ...]) :: integer
  def number_of_leading_zeros(%Decimal{} = number) do
    {_integer_digits, fraction_digits, _sign} = to_tuple(number)
    number_of_leading_zeros(fraction_digits)
  end

  def number_of_leading_zeros(number) when is_number(number) do
    {_integer_digits, fraction_digits, _sign} = to_tuple(number)
    number_of_leading_zeros(fraction_digits)
  end

  def number_of_leading_zeros(number) when is_list(number) do
    Enum.take_while(number, fn c -> c == ?0 or c == 0 end)
    |> length
  end

  @doc """
  Returns the number of trailing zeros in an
  integer number.

  * `number` is an integer.

  Returns the number of trailing zeros in the fractional
  part of an integer.

  ## Examples

      iex> Cldr.Digits.number_of_trailing_zeros(123000)
      3

  """
  def number_of_trailing_zeros(number) when is_integer(number) do
    {integer_digits, _fraction_digits, _sign} = to_tuple(number)
    number_of_trailing_zeros(integer_digits)
  end

  def number_of_trailing_zeros(number) when is_list(number) do
    number
    |> Enum.reverse
    |> Enum.take_while(fn c -> c == ?0 or c == 0 end)
    |> length
  end

  @doc """
  Converts given number to a list representation.

  Given an IEEE 754 float, computes the shortest, correctly rounded list of
  digits that converts back to the same Double value when read back with
  String.to_float/1.  Implements the algorithm from "Printing Floating-Point
  Numbers Quickly and Accurately" in Proceedings of the SIGPLAN '96 Conference
  on Programming Language Design and Implementation.

  Returns a tuple comprising a charlist for the integer part,
  a charlist for the fractional part and an integer for the sign.
  """

  # Code extracted from:
  # https://github.com/ewildgoose/elixir-float_pp/blob/master/lib/float_pp/digits.ex,
  # which is licensed under http://www.apache.org/licenses/LICENSE-2.0

  @spec to_tuple(Decimal.t() | number) :: {list(), list(), integer}
  def to_tuple(number) do
    {mantissa, exp, sign} = to_digits(number)

    mantissa =
      cond do
        # Need to right fill with zeros
        exp > length(mantissa) ->
          mantissa ++ :lists.duplicate(exp - length(mantissa), 0)

        # Need to left fill with zeros
        exp < 0 ->
          :lists.duplicate(abs(exp), 0) ++ mantissa

        true ->
          mantissa
      end

    cond do
      # Its an integer
      exp == length(mantissa) ->
        {mantissa, [], sign}

      # It's a fraction with no integer part
      exp <= 0 ->
        {[], mantissa, sign}

      # It's a fraction
      exp > 0 and exp < length(mantissa) ->
        {integer, fraction} = :lists.split(exp, mantissa)
        {integer, fraction, sign}
    end
  end

  @doc """
  Computes a iodata list of the digits of the given IEEE 754 floating point number,
  together with the location of the decimal point as {digits, place, positive}.

  A "compact" representation is returned, so there may be fewer digits returned
  than the decimal point location.
  """
  def to_digits(float_0) when float_0 == 0.0, do: {[0], 1, 1}
  def to_digits(0), do: {[0], 1, 1}

  def to_digits(float) when is_float(float) do
    # Find mantissa and exponent from IEEE-754 packed notation
    {frac, exp} = frexp(float)

    # Scale fraction to integer (and adjust mantissa to compensate)
    frac = trunc(abs(frac) * @two53)
    exp = exp - 53

    # Compute digits
    flonum(float, frac, exp)
  end

  if Code.ensure_loaded?(Decimal) and function_exported?(Decimal, :normalize, 1) do
    def to_digits(%Decimal{} = number) do
      %Decimal{coef: coef, exp: exp, sign: sign} = Decimal.normalize(number)
      {digits, _place, _sign} = to_digits(coef)
      {digits, length(digits) + exp, sign}
    end
  else
    def to_digits(%Decimal{} = number) do
      %Decimal{coef: coef, exp: exp, sign: sign} = Decimal.reduce(number)
      {digits, _place, _sign} = to_digits(coef)
      {digits, length(digits) + exp, sign}
    end
  end

  def to_digits(integer) when is_integer(integer) when integer >= 0 do
    digits = Integer.digits(integer)
    {digits, length(digits), 1}
  end

  def to_digits(integer) when is_integer(integer) do
    digits = Integer.digits(integer)
    {digits, length(digits), -1}
  end

  @doc """
  Takes a list of digits and coverts them back to a number of the same
  type as `number`.
  """
  def to_number(digits, number) when is_integer(number), do: to_integer(digits)
  def to_number(digits, number) when is_float(number), do: to_float(digits)
  def to_number(digits, %Decimal{}), do: to_decimal(digits)

  def to_number(digits, :integer), do: to_integer(digits)
  def to_number(digits, :float), do: to_float(digits)
  def to_number(digits, :decimal), do: to_decimal(digits)

  def to_integer({digits, place, sign}) do
    {int_digits, _fraction_digits} = Enum.split(digits, place)
    Integer.undigits(int_digits) * sign
  end

  def to_float({[0], _place, _sign}) do
    0.0
  end

  def to_float({digits, place, sign}) when length(digits) >= place do
    Integer.undigits(digits) / power_of_10(length(digits) - place) * sign
  end

  def to_float({digits, place, sign}) do
    Integer.undigits(digits) * power_of_10(place - length(digits)) * sign * 1.0
  end

  def to_decimal({digits, place, sign}) do
    %Decimal{coef: Integer.undigits(digits), exp: place - length(digits), sign: sign}
  end

  ############################################################################
  # The following functions are Elixir translations of the original paper:
  # "Printing Floating-Point Numbers Quickly and Accurately"
  # http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
  # See the paper for further explanation

  _ = """
  Set initial values {r, s, m+, m-}
  based on table 1 from FP-Printing paper
  Assumes frac is scaled to integer (and exponent scaled appropriately)
  """

  defp flonum(float, frac, exp) do
    round = Integer.is_even(frac)

    if exp >= 0 do
      b_exp = bsl(1, exp)

      if frac !== @two52 do
        scale(frac * b_exp * 2, 2, b_exp, b_exp, round, round, float)
      else
        scale(frac * b_exp * 4, 4, b_exp * 2, b_exp, round, round, float)
      end
    else
      if exp === @min_e or frac !== @two52 do
        scale(frac * 2, bsl(1, 1 - exp), 1, 1, round, round, float)
      else
        scale(frac * 4, bsl(1, 2 - exp), 2, 1, round, round, float)
      end
    end
  end

  @log_0_approx -60
  def scale(r, s, m_plus, m_minus, low_ok, high_ok, float) do
    # TODO: Benchmark removing the log10 and using the approximation given in original paper?
    est =
      if float == 0 do
        @log_0_approx
      else
        trunc(Float.ceil(:math.log10(abs(float)) - 1.0e-10))
      end

    if est >= 0 do
      fixup(r, s * power_of_10(est), m_plus, m_minus, est, low_ok, high_ok, float)
    else
      scale = power_of_10(-est)
      fixup(r * scale, s, m_plus * scale, m_minus * scale, est, low_ok, high_ok, float)
    end
  end

  def fixup(r, s, m_plus, m_minus, k, low_ok, high_ok, float) do
    too_low = if high_ok, do: r + m_plus >= s, else: r + m_plus > s

    if too_low do
      {generate(r, s, m_plus, m_minus, low_ok, high_ok), k + 1, sign(float)}
    else
      {generate(r * 10, s, m_plus * 10, m_minus * 10, low_ok, high_ok), k, sign(float)}
    end
  end

  defp generate(r, s, m_plus, m_minus, low_ok, high_ok) do
    d = div(r, s)
    r = rem(r, s)

    tc1 = if low_ok, do: r <= m_minus, else: r < m_minus
    tc2 = if high_ok, do: r + m_plus >= s, else: r + m_plus > s

    if not tc1 do
      if not tc2 do
        [d | generate(r * 10, s, m_plus * 10, m_minus * 10, low_ok, high_ok)]
      else
        [d + 1]
      end
    else
      if not tc2 do
        [d]
      else
        if r * 2 < s do
          [d]
        else
          [d + 1]
        end
      end
    end
  end

  ############################################################################
  # Utility functions

  # FIXME: We don't handle +/-inf and NaN inputs. Not believed to be an issue in
  # Elixir, but beware future-self reading this...

  # The frexp() function is as per the clib function with the same name. It breaks
  # the floating-point number value into a normalized fraction and an integral
  # power of 2.
  #
  # Returns {frac, exp}, where the magnitude of frac is in the interval
  # [1/2, 1) or 0, and value = frac*(2^exp).

  @doc false
  def frexp(value) do
    <<sign::1, exp::11, frac::52>> = <<value::float>>
    frexp(sign, frac, exp)
  end

  def frexp(_Sign, 0, 0) do
    {0.0, 0}
  end

  # Handle denormalised values
  def frexp(sign, frac, 0) do
    exp = bitwise_length(frac)
    <<f::float>> = <<sign::1, @float_bias::11, frac - 1::52>>
    {f, -@float_bias - 52 + exp}
  end

  # Handle normalised values
  def frexp(sign, frac, exp) do
    <<f::float>> = <<sign::1, @float_bias::11, frac::52>>
    {f, exp - @float_bias}
  end

  _ = """
  Return the number of significant bits needed to store the given number
  """

  defp bitwise_length(value) do
    bitwise_length(value, 0)
  end

  defp bitwise_length(0, n), do: n
  defp bitwise_length(value, n), do: bitwise_length(bsr(value, 1), n + 1)

  defp sign(float) when float < 0, do: -1
  defp sign(_float), do: 1
end