localize

defmodule Localize.Utils.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, an 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.

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

  The digits can be converted back to normal form with
  `Localize.Utils.Digits.to_integer/1`, `Localize.Utils.Digits.to_float/1`
  and `Localize.Utils.Digits.to_decimal/1`.

  """

  import Bitwise
  import Localize.Utils.Math, only: [power_of_10: 1]
  require Integer

  @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 point
  in the number.

  * A `1` or `-1` representing the sign of the number.

  """
  @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.

  ### Arguments

  * `number` is a float, Decimal, integer, or a tuple of the form
    `{integer_list, fraction_list, sign}` as returned by `to_tuple/1`.

  ### Returns

  * An integer representing the fractional digits.

  ### Examples

      iex> Localize.Utils.Digits.fraction_as_integer(123.456)
      456

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

      iex> Localize.Utils.Digits.fraction_as_integer(1999)
      0

  """
  @spec fraction_as_integer(number() | Decimal.t() | {list, list, 1 | -1}) :: integer
  def fraction_as_integer({_integer, [], _sign}) do
    0
  end

  def fraction_as_integer({_integer, fraction, _sign})
      when is_list(fraction) do
    Integer.undigits(fraction)
  end

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

  @doc """
  Returns the fractional part of a float as an integer,
  rounding to the specified number of digits first.

  ### Arguments

  * `number` is a float.

  * `rounding` is a positive integer specifying the number of
    fractional digits.

  ### Returns

  * An integer representing the fractional digits.

  ### Examples

      iex> Localize.Utils.Digits.fraction_as_integer(1.456, 3)
      456

  """
  @spec fraction_as_integer(float(), pos_integer()) :: integer()
  def fraction_as_integer(number, rounding) when is_float(number) do
    number = Float.round(number, rounding)
    fraction_as_integer(number)
  end

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

  ### Arguments

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

  ### Returns

  * An integer count of the total number of digits.

  ### Examples

      iex> Localize.Utils.Digits.number_of_digits(1234)
      4

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

      iex> Localize.Utils.Digits.number_of_digits(1234.456)
      7

      iex> Localize.Utils.Digits.number_of_digits(1234.56789098765)
      15

      iex> Localize.Utils.Digits.number_of_digits(~c"12345")
      5

  """
  @spec number_of_digits(
          number()
          | Decimal.t()
          | 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.

  ### Arguments

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

  ### Returns

  * A non-negative integer count of integer digits.

  ### Examples

      iex> Localize.Utils.Digits.number_of_integer_digits(1234)
      4

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

      iex> Localize.Utils.Digits.number_of_integer_digits(1234.456)
      4

      iex> Localize.Utils.Digits.number_of_integer_digits(~c"12345")
      5

  """
  @spec number_of_integer_digits(
          number()
          | Decimal.t()
          | 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 `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 `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 """
  Removes trailing zeros from the integer part of a number
  and returns the integer part without trailing zeros.

  ### Arguments

  * `number` is an integer, float, Decimal, or a list of digits.

  ### Returns

  * An integer with trailing zeros removed, or a list with
    trailing zeros removed.

  ### Examples

      iex> Localize.Utils.Digits.remove_trailing_zeros(1234000)
      1234

      iex> Localize.Utils.Digits.remove_trailing_zeros(0)
      0

  """
  @spec remove_trailing_zeros(number() | Decimal.t() | [integer(), ...]) ::
          number() | [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 the fractional
  part of a number.

  ### Arguments

  * `number` is an integer, float, Decimal, or a list of digits.

  ### Returns

  * An integer count of leading zeros.

  ### Examples

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

  """
  @spec number_of_leading_zeros(number() | Decimal.t() | [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.

  ### Arguments

  * `number` is an integer or a list of digits.

  ### Returns

  * An integer count of trailing zeros.

  ### Examples

      iex> Localize.Utils.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 """
  Computes a list of the digits of the given IEEE 754 floating point number,
  together with the location of the decimal point as `{digits, place, sign}`.

  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.

  A "compact" representation is returned, so there may be fewer digits returned
  than the decimal point location.

  ### Arguments

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

  ### Returns

  * A tuple `{digits, place, sign}` where `digits` is a list of integers
    0..9, `place` is the decimal point position, and `sign` is `1` or `-1`.

  ### Examples

      iex> Localize.Utils.Digits.to_digits(0.0)
      {[0], 1, 1}

      iex> Localize.Utils.Digits.to_digits(123)
      {[1, 2, 3], 3, 1}

  """

  # 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

  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

  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

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

  def to_digits(integer) when is_integer(integer) do
    digits = Integer.digits(abs(integer))
    {digits, length(digits), -1}
  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 list for the integer part,
  a list for the fractional part, and an integer for the sign.

  ### Arguments

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

  ### Returns

  * A tuple `{integer_digits, fraction_digits, sign}` where each digit
    list contains integers 0..9 and `sign` is `1` or `-1`.

  ### Examples

      iex> Localize.Utils.Digits.to_tuple(123.456)
      {[1, 2, 3], [4, 5, 6], 1}

  """
  @spec to_tuple(Decimal.t() | number) :: {list(), list(), integer}
  def to_tuple(%Decimal{sign: sign, coef: coef, exp: exp}) do
    sign_val = if sign == 1, do: 1, else: -1
    all_digits = Integer.digits(coef)

    cond do
      exp == 0 ->
        {all_digits, [], sign_val}

      exp < 0 ->
        split_point = length(all_digits) + exp

        if split_point <= 0 do
          # All digits are fractional, need leading zeros
          padding = List.duplicate(0, abs(split_point))
          {[0], padding ++ all_digits, sign_val}
        else
          {int_digits, frac_digits} = Enum.split(all_digits, split_point)
          {int_digits, frac_digits, sign_val}
        end

      exp > 0 ->
        trailing = List.duplicate(0, exp)
        {all_digits ++ trailing, [], sign_val}
    end
  end

  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 """
  Takes a list of digits and converts them back to a number of the same
  type as `number`.

  ### Arguments

  * `digits` is a tuple `{digit_list, place, sign}` as returned by `to_digits/1`.

  * `number` is a number or atom indicating the desired return type.
    Supported values are an integer, float, `%Decimal{}`, or the atoms
    `:integer`, `:float`, `:decimal`.

  ### Returns

  * A number of the requested type.

  ### Examples

      iex> Localize.Utils.Digits.to_number({[1, 2, 3], 3, 1}, :integer)
      123

      iex> Localize.Utils.Digits.to_number({[1, 2, 3], 3, 1}, :float)
      123.0

  """
  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)

  @doc """
  Converts a digit tuple to an integer.

  ### Arguments

  * `digits` is a tuple `{digit_list, place, sign}` as returned by `to_digits/1`.

  ### Returns

  * An integer.

  ### Examples

      iex> Localize.Utils.Digits.to_integer({[1, 2, 3, 4], 4, 1})
      1234

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

  @doc """
  Converts a digit tuple to a float.

  ### Arguments

  * `digits` is a tuple `{digit_list, place, sign}` as returned by `to_digits/1`.

  ### Returns

  * A float.

  ### Examples

      iex> Localize.Utils.Digits.to_float({[1, 2, 3, 4], 2, 1})
      12.34

  """
  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

  @doc """
  Converts a digit tuple to a Decimal.

  ### Arguments

  * `digits` is a tuple `{digit_list, place, sign}` as returned by `to_digits/1`.

  ### Returns

  * A `%Decimal{}` struct.

  ### Examples

      iex> Localize.Utils.Digits.to_decimal({[1, 2, 3], 2, 1})
      Decimal.new("12.3")

  """
  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

  @doc false
  def scale(r, s, m_plus, m_minus, low_ok, high_ok, float) do
    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

  @doc false
  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

  # 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

  @doc false
  def frexp(_sign, 0, 0) do
    {0.0, 0}
  end

  # Handle denormalised values
  @doc false
  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
  @doc false
  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