algo

defmodule Algo.List do
  @moduledoc """
  Utility functions for lists.
  """

  @doc """
  Alternates elements from two lists.

  When one list is longer, the remaining elements from that list are appended to
  the result.

  ## Examples

      iex> Algo.List.interweave([1, 2, 3], [:a, :b])
      [1, :a, 2, :b, 3]

      iex> Algo.List.interweave([], [:a, :b])
      [:a, :b]
  """
  @spec interweave(list, list) :: list
  def interweave(list1, list2), do: interweave_impl([], list1, list2)

  @spec interweave_impl(list, list, list) :: list
  defp interweave_impl(acc, list1, list2) do
    # Enum.reverse/2 is an optimisation for `Enum.reverse(arg1) |> Enum.concat(arg2)`
    case {list1, list2} do
      {[], _} -> Enum.reverse(acc, list2)
      {_, []} -> Enum.reverse(acc, list1)
      {[head1 | tail1], [head2 | tail2]} -> interweave_impl([head2, head1 | acc], tail1, tail2)
    end
  end

  @doc """
  Returns the Cartesian product of two lists.

  Pass `:lists` to return each pair as a two-item list, or `:tuples` to return
  each pair as a tuple.

  ## Examples

      iex> Algo.List.get_cartesian_product([1, 2], [:a, :b], :tuples)
      [{1, :a}, {1, :b}, {2, :a}, {2, :b}]

      iex> Algo.List.get_cartesian_product([1, 2], [:a], :lists)
      [[1, :a], [2, :a]]
  """
  @spec get_cartesian_product(list, list, :lists | :tuples) :: [list] | [{any, any}]
  def get_cartesian_product(list1, list2, output_as) do
    Enum.flat_map(list1, fn x ->
      Enum.map(list2, fn y -> if output_as == :lists, do: [x, y], else: {x, y} end)
    end)
  end

  @doc """
  Returns all permutations of a list.

  Duplicate input values may produce duplicate permutations.

  ## Examples

      iex> Algo.List.get_permutations([1, 2, 3])
      [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

      iex> Algo.List.get_permutations([])
      [[]]
  """
  @spec get_permutations(list) :: [list]
  def get_permutations(list) do
    case list do
      [] -> [[]]
      _ -> Enum.flat_map(list, fn x -> get_permutations(list -- [x]) |> Enum.map(&[x | &1]) end)
    end
  end

  @doc """
  Returns every subsequence of a list.

  The empty list is included. Subsequence order follows the recursive generation
  order used by the function.

  ## Examples

      iex> Algo.List.get_subsequences([1, 2])
      [[], [1], [2], [1, 2]]

      iex> Algo.List.get_subsequences([])
      [[]]
  """
  @spec get_subsequences(list) :: [list]
  def get_subsequences(list) do
    case list do
      [] -> [[]]
      [head | tail] -> Enum.flat_map(get_subsequences(tail), fn x -> [x, [head | x]] end)
    end
  end

  @doc """
  Returns all unique unordered pairs from a list.

  Pass `:lists` to return pairs as two-item lists, or `:tuples` to return pairs
  as tuples.

  ## Examples

      iex> Algo.List.get_unique_pairs([1, 2, 3], :lists)
      [[1, 2], [1, 3], [2, 3]]

      iex> Algo.List.get_unique_pairs([1, 2], :tuples)
      [{1, 2}]

      iex> Algo.List.get_unique_pairs([1], :lists)
      []
  """
  @spec get_unique_pairs(list, :lists | :tuples) :: [list] | [{any, any}]
  def get_unique_pairs(list, output_as) do
    case list do
      [] -> []
      [_] -> []
      [a, b] -> if output_as == :lists, do: [list], else: [{a, b}]
      [head | tail] -> pairs(head, tail, output_as) ++ get_unique_pairs(tail, output_as)
    end
  end

  @spec pairs(any, list, :lists | :tuples) :: [list] | [{any, any}]
  defp pairs(x, list, output_as) do
    list
    |> Enum.map(fn y -> if output_as == :lists, do: [x, y], else: {x, y} end)
  end

  @doc """
  Maps a list while threading an accumulator from left to right.

  The function receives each element and the current accumulator, and must return
  `{mapped_element, next_accumulator}`.

  ## Examples

      iex> Algo.List.map_accum([1, 2, 3], 0, fn x, sum -> {x * 2, sum + x} end)
      {[2, 4, 6], 6}
  """
  @spec map_accum(list, any, (any, any -> {any, any})) :: {list, any}
  def map_accum(list, acc, fun) when is_list(list) and is_function(fun, 2) do
    {mapped, final_acc} =
      Enum.reduce(list, {[], acc}, fn element, {mapped_acc, current_acc} ->
        {mapped_element, next_acc} = fun.(element, current_acc)
        {[mapped_element | mapped_acc], next_acc}
      end)

    {Enum.reverse(mapped), final_acc}
  end

  @doc """
  Maps a list while threading an accumulator from right to left.

  The function receives each element and the current accumulator, and must return
  `{mapped_element, next_accumulator}`. The returned mapped list keeps the input
  order.

  ## Examples

      iex> Algo.List.map_accum_right([1, 2, 3], 0, fn x, sum -> {x + sum, sum + x} end)
      {[6, 5, 3], 6}
  """
  @spec map_accum_right(list, any, (any, any -> {any, any})) :: {list, any}
  def map_accum_right(list, acc, fun) when is_list(list) and is_function(fun, 2) do
    Enum.reduce(Enum.reverse(list), {[], acc}, fn element, {mapped_acc, current_acc} ->
      {mapped_element, next_acc} = fun.(element, current_acc)
      {[mapped_element | mapped_acc], next_acc}
    end)
  end

  @doc """
  Chunks adjacent elements while a predicate holds for each neighbouring pair.

  The predicate receives the previous element and the current element. A truthy
  result keeps the current element in the active chunk; a falsy result starts a
  new chunk.

  ## Examples

      iex> Algo.List.chunk_while_adjacent([1, 2, 3, 1, 2], fn left, right -> right == left + 1 end)
      [[1, 2, 3], [1, 2]]
  """
  @spec chunk_while_adjacent(list, (any, any -> as_boolean(term()))) :: [list]
  def chunk_while_adjacent([], fun) when is_function(fun, 2), do: []

  def chunk_while_adjacent([first | rest], fun) when is_function(fun, 2) do
    {chunks, chunk, _previous} =
      Enum.reduce(rest, {[], [first], first}, fn element, {chunks, chunk, previous} ->
        if fun.(previous, element) do
          {chunks, [element | chunk], element}
        else
          {[Enum.reverse(chunk) | chunks], [element], element}
        end
      end)

    Enum.reverse([Enum.reverse(chunk) | chunks])
  end

  @doc """
  Splits a list before every element that satisfies a predicate.

  Matching elements are retained as the first element of their new chunk. Empty
  chunks are not emitted.

  ## Examples

      iex> Algo.List.split_whenever([1, 2, 3, 2, 4], &(&1 == 2))
      [[1], [2, 3], [2, 4]]

      iex> Algo.List.split_whenever([:a, :b], fn _ -> false end)
      [[:a, :b]]
  """
  @spec split_whenever(list, (any -> as_boolean(term()))) :: [list]
  def split_whenever(list, fun) when is_list(list) and is_function(fun, 1) do
    {chunks, chunk} =
      Enum.reduce(list, {[], []}, fn element, {chunks, chunk} ->
        if fun.(element) && chunk != [] do
          {[Enum.reverse(chunk) | chunks], [element]}
        else
          {chunks, [element | chunk]}
        end
      end)

    case chunk do
      [] -> Enum.reverse(chunks)
      _ -> Enum.reverse([Enum.reverse(chunk) | chunks])
    end
  end

  @doc """
  Transposes a rectangular list of rows.

  All rows must be lists with the same length. An empty list of rows returns an
  empty list. If rows are not of equal lengths, the transposition stops at the end
  of the shortest row, matching the behaviour of `Enum.zip`.

  ## Examples

      iex> Algo.List.transpose([[1, 2, 3], [:a, :b, :c]])
      [[1, :a], [2, :b], [3, :c]]
  """
  @spec transpose([list]) :: [list]
  def transpose([]), do: []

  def transpose([first | _] = rows) when is_list(first) do
    rows
    |> Enum.zip()
    |> Enum.map(&Tuple.to_list/1)
  end

  @doc """
  Moves the element at one index to another index.

  Indexes are zero-based. Negative indexes count back from the end, like
  `Enum.at/2`. Both indexes must point at existing elements; otherwise
  `ArgumentError` is raised.

  ## Examples

      iex> Algo.List.move_at([:a, :b, :c, :d], 0, 2)
      [:b, :c, :a, :d]

      iex> Algo.List.move_at([:a, :b, :c], -1, 0)
      [:c, :a, :b]
  """
  @spec move_at(list, integer, integer) :: list
  def move_at(list, from_index, to_index) when is_list(list) and is_integer(from_index) and is_integer(to_index) do
    count = length(list)
    from_index = normalise_existing_index(from_index, count)
    to_index = normalise_existing_index(to_index, count)

    {element, rest} = List.pop_at(list, from_index)
    List.insert_at(rest, to_index, element)
  end

  @doc """
  Returns unique elements according to a comparator.

  The first occurrence is kept. The comparator receives an already kept element
  and the candidate element; a truthy return value means the two elements are
  considered the same.

  ## Examples

      iex> Algo.List.unique_with(["a", "bb", "c"], Algo.eq_by?(&String.length/1))
      ["a", "bb"]
  """
  @spec unique_with(Enumerable.t(), (any, any -> as_boolean(term()))) :: list
  def unique_with(enumerable, fun) when is_function(fun, 2) do
    enumerable
    |> Enum.reduce([], fn element, unique ->
      if Enum.any?(unique, &fun.(&1, element)), do: unique, else: [element | unique]
    end)
    |> Enum.reverse()
  end

  @doc """
  Builds a map by indexing each element with a key function.

  If multiple elements produce the same key, the later element wins.

  ## Examples

      iex> Algo.List.index_by([%{id: 1, name: "old"}, %{id: 1, name: "new"}], & &1.id)
      %{1 => %{id: 1, name: "new"}}
  """
  @spec index_by(Enumerable.t(), (any -> any)) :: map
  def index_by(enumerable, fun) when is_function(fun, 1) do
    Map.new(enumerable, fn element -> {fun.(element), element} end)
  end

  @doc """
  Reduces elements into groups selected by a key function.

  Each new key starts with `initial_acc`. The reducer receives the element and
  the current accumulator for that key.

  ## Examples

      iex> Algo.List.reduce_by(["a", "bb", "c"], &String.length/1, 0, fn _value, count -> count + 1 end)
      %{1 => 2, 2 => 1}
  """
  @spec reduce_by(Enumerable.t(), (any -> any), any, (any, any -> any)) :: map
  def reduce_by(enumerable, key_fun, initial_acc, reduce_fun)
      when is_function(key_fun, 1) and is_function(reduce_fun, 2) do
    Enum.reduce(enumerable, %{}, fn element, groups ->
      key = key_fun.(element)
      current_acc = Map.get(groups, key, initial_acc)
      Map.put(groups, key, reduce_fun.(element, current_acc))
    end)
  end

  @doc """
  Expands maps by replacing a list field with each of its values.

  Items with a list field emit one item per field value. An empty list emits no
  items. Missing fields and non-list fields are left unchanged.

  ## Examples

      iex> Algo.List.unwind([%{id: 1, tags: [:a, :b]}, %{id: 2, tags: []}], :tags)
      [%{id: 1, tags: :a}, %{id: 1, tags: :b}]

      iex> Algo.List.unwind([%{id: 1}, %{id: 2, tags: :a}], :tags)
      [%{id: 1}, %{id: 2, tags: :a}]
  """
  @spec unwind(Enumerable.t(), any) :: list
  def unwind(enumerable, field) do
    Enum.flat_map(enumerable, fn item ->
      case item do
        %{^field => values} when is_list(values) -> Enum.map(values, &Map.put(item, field, &1))
        _ -> [item]
      end
    end)
  end

  @doc """
  Maps each element into one of two partitions.

  The mapping function must return `{:left, value}` or `{:right, value}`. The
  result is `{left_values, right_values}` with input order preserved in each
  partition.

  ## Examples

      iex> Algo.List.partition_map([1, 2, 3], fn x -> if rem(x, 2) == 0, do: {:right, x * 10}, else: {:left, x} end)
      {[1, 3], [20]}
  """
  @spec partition_map(Enumerable.t(), (any -> {:left, any} | {:right, any})) :: {list, list}
  def partition_map(enumerable, fun) when is_function(fun, 1) do
    {left, right} =
      Enum.reduce(enumerable, {[], []}, fn element, {left, right} ->
        case fun.(element) do
          {:left, value} -> {[value | left], right}
          {:right, value} -> {left, [value | right]}
          other -> raise ArgumentError, "expected {:left, value} or {:right, value}, got: #{inspect(other)}"
        end
      end)

    {Enum.reverse(left), Enum.reverse(right)}
  end

  @doc """
  Returns elements from the first enumerable whose derived keys are absent from
  the second enumerable.

  Duplicate elements from the first enumerable are preserved when their key is
  absent from the second enumerable.

  ## Examples

      iex> Algo.List.difference_by([%{id: 1}, %{id: 2}], [%{id: 2}], & &1.id)
      [%{id: 1}]
  """
  @spec difference_by(Enumerable.t(), Enumerable.t(), (any -> any)) :: list
  def difference_by(left, right, key_fun) when is_function(key_fun, 1) do
    right_keys = right |> Enum.map(key_fun) |> MapSet.new()
    Enum.reject(left, &MapSet.member?(right_keys, key_fun.(&1)))
  end

  @doc """
  Returns elements from the first enumerable that have no comparator match in the
  second enumerable.

  The comparator receives `{left_element, right_element}` and a truthy return
  value means the elements match.

  ## Examples

      iex> Algo.List.difference_with(["a", "bb"], ["c"], Algo.eq_by?(&String.length/1))
      ["bb"]
  """
  @spec difference_with(Enumerable.t(), Enumerable.t(), (any, any -> as_boolean(term()))) :: list
  def difference_with(left, right, fun) when is_function(fun, 2) do
    right = Enum.to_list(right)
    Enum.reject(left, fn left_element -> Enum.any?(right, &fun.(left_element, &1)) end)
  end

  @doc """
  Returns elements from the first enumerable whose derived keys are present in
  the second enumerable.

  Input order and duplicate elements from the first enumerable are preserved.

  ## Examples

      iex> Algo.List.intersect_by([%{id: 1}, %{id: 2}, %{id: 2}], [%{id: 2}], & &1.id)
      [%{id: 2}, %{id: 2}]
  """
  @spec intersect_by(Enumerable.t(), Enumerable.t(), (any -> any)) :: list
  def intersect_by(left, right, key_fun) when is_function(key_fun, 1) do
    right_keys = right |> Enum.map(key_fun) |> MapSet.new()
    Enum.filter(left, &MapSet.member?(right_keys, key_fun.(&1)))
  end

  @doc """
  Returns elements from the first enumerable that have a comparator match in the
  second enumerable.

  The comparator receives `{left_element, right_element}` and a truthy return
  value means the elements match.

  ## Examples

      iex> Algo.List.intersect_with(["a", "bb"], ["c"], Algo.eq_by?(&String.length/1))
      ["a"]
  """
  @spec intersect_with(Enumerable.t(), Enumerable.t(), (any, any -> as_boolean(term()))) :: list
  def intersect_with(left, right, fun) when is_function(fun, 2) do
    right = Enum.to_list(right)
    Enum.filter(left, fn left_element -> Enum.any?(right, &fun.(left_element, &1)) end)
  end

  @doc """
  Returns elements whose derived keys are present in only one enumerable.

  Items from the first enumerable are returned before items from the second.
  Duplicates are preserved for keys that are exclusive to their side.

  ## Examples

      iex> Algo.List.get_symmetric_difference_by([%{id: 1}, %{id: 2}], [%{id: 2}, %{id: 3}], & &1.id)
      [%{id: 1}, %{id: 3}]
  """
  @spec get_symmetric_difference_by(Enumerable.t(), Enumerable.t(), (any -> any)) :: list
  def get_symmetric_difference_by(left, right, key_fun) when is_function(key_fun, 1) do
    left = Enum.to_list(left)
    right = Enum.to_list(right)
    left_keys = left |> Enum.map(key_fun) |> MapSet.new()
    right_keys = right |> Enum.map(key_fun) |> MapSet.new()

    Enum.reject(left, &MapSet.member?(right_keys, key_fun.(&1))) ++
      Enum.reject(right, &MapSet.member?(left_keys, key_fun.(&1)))
  end

  @doc """
  Returns elements from both enumerables that have no comparator match in the
  other enumerable.

  Items from the first enumerable are returned before items from the second. For
  first-side items, the comparator receives `{left_element, right_element}`; for
  second-side items, it receives `{right_element, left_element}`.

  ## Examples

      iex> Algo.List.get_symmetric_difference_with(["a", "bb"], ["c", "ddd"], Algo.eq_by?(&String.length/1))
      ["bb", "ddd"]
  """
  @spec get_symmetric_difference_with(Enumerable.t(), Enumerable.t(), (any, any -> as_boolean(term()))) :: list
  def get_symmetric_difference_with(left, right, fun) when is_function(fun, 2) do
    left = Enum.to_list(left)
    right = Enum.to_list(right)

    difference_with(left, right, fun) ++ difference_with(right, left, fun)
  end

  @doc """
  Returns all matching pairs from two enumerables.

  The predicate receives a left element and a right element. Every truthy match
  is emitted as `{left_element, right_element}`.

  ## Examples

      iex> Algo.List.inner_join([%{id: 1}], [%{user_id: 1}, %{user_id: 2}], fn left, right -> left.id == right.user_id end)
      [{%{id: 1}, %{user_id: 1}}]
  """
  @spec inner_join(Enumerable.t(), Enumerable.t(), (any, any -> as_boolean(term()))) :: [{any, any}]
  def inner_join(left, right, fun) when is_function(fun, 2) do
    right = Enum.to_list(right)

    for left_element <- left,
        right_element <- right,
        fun.(left_element, right_element) do
      {left_element, right_element}
    end
  end

  defp normalise_existing_index(index, count) do
    normalised = if index < 0, do: count + index, else: index

    if normalised < 0 or normalised >= count do
      raise ArgumentError, "index #{index} is out of bounds for list of length #{count}"
    end

    normalised
  end
end