defmodule Hashids do
  @moduledoc """
  Hashids lets you obfuscate numerical identifiers via reversible mapping.

  ## Example

      h = Hashids.new(salt: "my salt")
      encoded = Hashids.encode(h, [1,2,3])
      {:ok, [1,2,3]} = Hashids.decode(h, encoded)

  """

  defstruct [
    alphabet: [], salt: [], min_len: 0,
    a_len: 0, seps: [], s_len: 0, guards: [], g_len: 0,
  ]

  @typep t :: %Hashids{
    alphabet: charlist, salt: charlist, min_len: non_neg_integer,
    a_len: non_neg_integer, seps: charlist, s_len: non_neg_integer, guards: charlist,
    g_len: non_neg_integer,
  }

  @min_alphabet_len 16
  @sep_div 3.5
  @guard_div 12

  @default_alphabet 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
  @seps 'cfhistuCFHISTU'

  alias Hashids.Helpers

  @doc """
  Create a struct containing the configuration options for Hashids. It should be passed to
  `encode/2` and `decode/2`.

  Raises `Hashids.Error` if it encounters an invalid option.

  ## Options

    * `:alphabet` – a string of characters to be used in the resulting hash value. By default,
      characters from the Latin alphabet and digits are used.
    * `:salt` – a string that will be used to permute the hash value and make it decodable only by
      using the same salt that was provided during encoding. Default: empty string.
    * `:min_len` – the minimum length of the resulting hash. Default: 0.

  """
  @spec new() :: t
  @spec new([{:alphabet, binary} | {:salt, binary} | {:min_len, non_neg_integer}]) :: t

  def new(options \\ []) do
    {uniq_alphabet, a_len} = parse_option!(:alphabet, options)
    salt = parse_option!(:salt, options)
    min_len = parse_option!(:min_len, options)

    {seps, alphabet, a_len} = calculate_seps(@seps, uniq_alphabet, a_len, salt)

    alphabet = Helpers.consistent_shuffle(alphabet, salt)
    guard_count = trunc(Float.ceil(a_len / @guard_div))
    {alphabet, guards, seps, a_len} = if a_len < 3 do
      {guards, seps} = Enum.split(seps, guard_count)
      {alphabet, guards, seps, a_len}
    else
      {guards, alphabet} = Enum.split(alphabet, guard_count)
      a_len = a_len - guard_count
      {alphabet, guards, seps, a_len}
    end
    %Hashids{
      alphabet: alphabet, salt: salt, min_len: min_len,
      a_len: a_len, seps: seps, s_len: length(seps), guards: guards, g_len: length(guards),
    }
  end

  @doc """
  Encode the given number or a list of numbers.

  Only non-negative integers are supported.
  """
  @spec encode(t, non_neg_integer) :: iodata
  @spec encode(t, [non_neg_integer]) :: iodata

  def encode(s, number) when is_integer(number) and number >= 0 do
    encode(s, [number])
  end

  def encode(s, numbers) when is_list(numbers) do
    {num_checksum, _} = Enum.reduce(numbers, {0, 100}, fn
      num, _ when num < 0 or not is_integer(num) ->
        raise Hashids.Error, message: "Expected a non-negative integer. Got: #{inspect num}"
      num, {cksm, i} ->
        {cksm + rem(num, i), i+1}
    end)

    %Hashids{
      alphabet: alphabet, salt: salt, min_len: min_len,
      a_len: a_len, seps: seps, s_len: s_len, guards: guards, g_len: g_len,
    } = s

    lottery = Enum.at(alphabet, rem(num_checksum, a_len))
    {precipher, p_len, alphabet} =
      preencode(numbers, 0, [lottery], 1, [lottery|salt], alphabet, a_len, seps, s_len)

    {interm_cipher, i_len} =
      extend_precipher1(precipher, p_len, min_len, num_checksum, guards, g_len)
    {interm_cipher, i_len} =
      extend_precipher2(interm_cipher, i_len, min_len, num_checksum, guards, g_len)

    extend_cipher(interm_cipher, i_len, min_len, alphabet, a_len)
    |> List.to_string
  end

  @doc """
  Decode the given iodata back into a list of numbers.
  """
  @spec decode(t, iodata) :: {:ok, [non_neg_integer]} | {:error, :invalid_input_data}

  def decode(
    %Hashids{alphabet: alphabet, salt: salt, a_len: a_len, seps: seps, guards: guards},
    data) when is_list(data) or is_binary(data)
  do
    try do
      cipher_split_at_guards =
        String.split(IO.iodata_to_binary(data), Enum.map(guards, &<<&1::utf8>>))
      cipher_part = case cipher_split_at_guards do
        [_, x]    -> x
        [_, x, _] -> x
        [x|_]     -> x
      end

      result = if cipher_part != "" do
        {<<lottery::utf8>>, rest_part} = String.split_at(cipher_part, 1)
        rkey = [lottery|salt]
        String.split(rest_part, Enum.map(seps, &<<&1::utf8>>))
        |> decode_parts(rkey, alphabet, a_len, [])
      else
        []
      end
      {:ok, result}
    rescue
      _error -> {:error, :invalid_input_data}
    end
  end

  def decode(_, _) do
    raise Hashids.Error, message: "Expected iodata."
  end

  @doc """
  Decode the given iodata back into a list of numbers.

  Will raise a `Hashids.DecodingError` if the provided data is not a valid hash value or a
  Hashids struct with incompatible alphabet.
  """
  @spec decode!(t, iodata) :: [non_neg_integer] | no_return

  def decode!(s, data) do
    case decode(s, data) do
      {:ok, result} -> result
      {:error, _reason} -> raise Hashids.DecodingError, message: "Invalid input data."
    end
  end

  #
  # Privates
  #

  defp uniquify_chars(charlist) do
    uniquify_chars(charlist, [], MapSet.new, 0)
  end

  defp uniquify_chars([], acc, set, nchars), do: {Enum.reverse(acc), set, nchars}

  defp uniquify_chars([char|rest], acc, set, nchars) do
    if MapSet.member?(set, char) do
      uniquify_chars(rest, acc, set, nchars)
    else
      uniquify_chars(rest, [char|acc], MapSet.put(set, char), nchars+1)
    end
  end

  defp parse_option!(:alphabet, kw) do
    list = case Keyword.fetch(kw, :alphabet) do
      :error -> @default_alphabet
      {:ok, bin} when is_binary(bin) -> String.to_charlist(bin)
      _ ->
        message = "Alphabet has to be a string of at least 16 characters/codepoints."
        raise Hashids.Error, message: message
    end
    {uniq_alphabet, set, nchars} = uniquify_chars(list)
    :ok = validate_alphabet!(set, nchars)
    {uniq_alphabet, nchars}
  end

  defp parse_option!(:salt, kw) do
    case Keyword.fetch(kw, :salt) do
      :error -> []
      {:ok, bin} when is_binary(bin) -> String.to_charlist(bin)
      _ -> raise Hashids.Error, message: "Salt has to be a (possibly empty) string."
    end
  end

  defp parse_option!(:min_len, kw) do
    case Keyword.fetch(kw, :min_len) do
      :error -> 0
      {:ok, len} when is_integer(len) and len >= 0 -> len
      _ -> raise Hashids.Error, message: "Min_len has to be a non-negative integer."
    end
  end

  defp validate_alphabet!(set, nchars) do
    cond do
      nchars < @min_alphabet_len ->
        msg = "Alphabet too short. Need at least #{@min_alphabet_len} characters/codepoints."
        raise Hashids.Error, message: msg

      # TODO: use a regex?
      Enum.find(set, &(&1 == ?\s)) ->
        msg = "Spaces in the alphabet are not allowed."
        raise Hashids.Error, message: msg

      true -> :ok
    end
  end

  defp calculate_seps(seps, alphabet, a_len, salt) do
    {seps, alphabet, a_len} = filter_seps(seps, [], alphabet, a_len)
    seps = Helpers.consistent_shuffle(seps, salt)
    s_len = length(seps)
    if s_len == 0 or a_len / s_len > @sep_div do
      new_len = max(2, trunc(Float.ceil(a_len / @sep_div)))
      if new_len > s_len do
        diff = new_len - s_len
        {left, right} = Enum.split(alphabet, diff)
        seps = seps ++ left
        alphabet = right
        a_len = a_len - diff
        {seps, alphabet, a_len}
      else
        seps = Enum.take(seps, new_len)
        {seps, alphabet, a_len}
      end
    else
      {seps, alphabet, a_len}
    end
  end

  defp filter_seps([], seps, alphabet, a_len) do
    {Enum.reverse(seps), alphabet, a_len}
  end

  defp filter_seps([char|rest], seps, alphabet, a_len) do
    if j = Enum.find_index(alphabet, &(&1 == char)) do
      # alphabet should not contains seps
      {left, [_|right]} = Enum.split(alphabet, j)
      new_alphabet = left ++ right
      filter_seps(rest, [char|seps], new_alphabet, a_len-1)
    else
      # seps should contain only characters present in alphabet
      filter_seps(rest, seps, alphabet, a_len)
    end
  end


  defp preencode([num], _, inret, p_len, rkey, alphabet, a_len, _, _) do
    {outret, step_len, new_alphabet, _} = preencode_step(num, inret, rkey, alphabet, a_len)
    {outret, p_len+step_len, new_alphabet}
  end

  defp preencode([num|rest], i, inret, p_len, rkey, alphabet, a_len, seps, seps_len) do
    {outret, step_len, new_alphabet, last} = preencode_step(num, inret, rkey, alphabet, a_len)
    ret = seps_step(last, i, num, outret, seps, seps_len)
    preencode(rest, i+1, ret, p_len+step_len+1, rkey, new_alphabet, a_len, seps, seps_len)
  end

  defp preencode_step(num, ret, rkey, alphabet, a_len) do
    skey = Stream.concat(rkey, alphabet) |> Enum.take(a_len)
    enc_alphabet = Helpers.consistent_shuffle(alphabet, skey)
    {last, last_len} = Helpers.encode(num, enc_alphabet, a_len)
    {[ret | last], last_len, enc_alphabet, last}
  end

  defp seps_step([char|_], i, num, ret, seps, seps_len) do
    index = rem(num, char+i) |> rem(seps_len)
    [ret, Enum.at(seps, index)]
  end


  defp extend_precipher1(precipher, p_len, min_len, num_cksm, guards, g_len)
    when p_len < min_len
  do
    char = nested_list_at(precipher, 0)
    index = rem(num_cksm + char, g_len)
    guard = Enum.at(guards, index)
    {[guard|precipher], p_len+1}
  end
  defp extend_precipher1(precipher, p_len, _, _, _, _), do: {precipher, p_len}

  defp extend_precipher2(precipher, p_len, min_len, num_cksm, guards, g_len)
    when p_len < min_len
  do
    char2 = nested_list_at(precipher, 2)
    index = rem(num_cksm + char2, g_len)
    guard = Enum.at(guards, index)
    {[precipher, guard], p_len+1}
  end
  defp extend_precipher2(precipher, p_len, _, _, _, _), do: {precipher, p_len}

  defp extend_cipher(cipher, c_len, min_len, alphabet, a_len)
    when c_len < min_len
  do
    new_alphabet = Helpers.consistent_shuffle(alphabet, alphabet)
    half_len = div(a_len, 2)
    {left, right} = Enum.split(new_alphabet, half_len)

    new_cipher = [right, cipher | left]
    new_c_len = c_len + a_len

    excess = new_c_len - min_len
    if excess > 0 do
      new_cipher |> List.flatten |> Enum.drop(div(excess, 2)) |> Enum.take(min_len)
    else
      extend_cipher(new_cipher, new_c_len, min_len, new_alphabet, a_len)
    end
  end

  defp extend_cipher(cipher, _, _, _, _), do: cipher


  defp decode_parts([], _, _, _, acc), do: Enum.reverse(acc)

  defp decode_parts([part|rest], rkey, alphabet, a_len, acc) do
    buffer = rkey ++ alphabet
    dec_alphabet = Helpers.consistent_shuffle(alphabet, Enum.take(buffer, a_len))
    number = Helpers.decode(String.to_charlist(part), dec_alphabet, a_len)
    decode_parts(rest, rkey, dec_alphabet, a_len, [number|acc])
  end


  defp nested_list_at(list, i) when is_integer(i) and i >= 0 do
    try do
      do_nested_list_at(list, i)
      raise "Index out of bounds"
    catch
      :throw, result -> result
    end
  end

  defp do_nested_list_at([h|rest], i) when is_list(h) do
    new_i = do_nested_list_at(h, i)
    do_nested_list_at(rest, new_i)
  end

  defp do_nested_list_at([h|_], 0) do
    throw h
  end

  defp do_nested_list_at([_|rest], i) do
    do_nested_list_at(rest, i-1)
  end

  defp do_nested_list_at([], i) do
    i
  end
end
