merkle_patricia_tree

defmodule MerklePatriciaTree.ListHelper do
  @moduledoc """
  Helpers for navigating lists, specifically for
  finding shared prefixes and postfixes.
  """

  @doc """
  Returns the post of list A if starts with list B, otherwise nil

  ## Examples

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2,3], [1,2])
    [3]

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2,3,4], [1,2])
    [3,4]

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2,3,4], [1])
    [2,3,4]

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2,3,4], [0,1])
    nil

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2,3,4], [])
    [1,2,3,4]

    iex> MerklePatriciaTree.ListHelper.get_postfix([1,2], [1,2,3])
    nil

    iex> MerklePatriciaTree.ListHelper.get_postfix([], [])
    []
  """
  @spec get_postfix([integer()], [integer()]) :: [integer()] | nil
  def get_postfix([h0 | t0], [h1 | t1]) do
    if h0 == h1 do
      get_postfix(t0, t1)
    else
      nil
    end
  end

  def get_postfix(l, []), do: l
  def get_postfix([], [_ | _]), do: nil

  @doc """
  Returns the overlap of two lists in terms of a shared prefix, then the relative postfixes

  ## Examples

    iex> MerklePatriciaTree.ListHelper.overlap([1,2,3], [1,2])
    {[1,2],[3],[]}

    iex> MerklePatriciaTree.ListHelper.overlap([1,2,3], [1,2,3,4])
    {[1,2,3],[],[4]}

    iex> MerklePatriciaTree.ListHelper.overlap([1,2,3], [2,3,4])
    {[],[1,2,3],[2,3,4]}

    iex> MerklePatriciaTree.ListHelper.overlap([], [2,3,4])
    {[],[],[2,3,4]}

    iex> MerklePatriciaTree.ListHelper.overlap([1,2,3], [])
    {[],[1,2,3],[]}

    iex> MerklePatriciaTree.ListHelper.overlap([15, 10, 5, 11], [15, 11, 1, 14])
    {[15], [10, 5, 11], [11, 1, 14]}
  """
  @spec overlap([integer()], [integer()]) :: {[integer()], [integer()], [integer()]}
  def overlap([], b = [_ | _]), do: {[], [], b}
  def overlap(a = [_ | _], []), do: {[], a, []}
  def overlap([], []), do: {[], [], []}

  def overlap([a0 | a], [b0 | b]) when a0 == b0 do
    {o1, a1, b1} = overlap(a, b)
    {[a0 | o1], a1, b1}
  end

  def overlap(a, b), do: {[], a, b}
end