defmodule Dmp.Cursor do
  @moduledoc """
  A container for Elixir lists, that can be used to iterate forward
  and backward, with a focused "current" item in the list, and "prev" and "next"
  lists of items that come before and after the current item.

  In Elm this has been described as a "Zipper".
  """

  defstruct prev: [], current: nil, next: []

  alias __MODULE__

  @type t() :: %Cursor{
          prev: list(),
          current: term(),
          next: list()
        }

  @typedoc """
  A value used to set the Cursor position.

    * `-1` means before the first item in the container.
    * `0` means at the first item.
    * `:last` means at the last item.
    * `:tail` means after the last item.
  """
  @type position_value() :: -1 | non_neg_integer() | :last | :tail

  @type init_option() :: {:position, position_value()}

  @typedoc """
  Use `position: 0` for example, to set the initial
  position of the Cursor to the first item.
  """
  @type init_options() :: list(init_option())

  @doc """
  Create a Cursor containing no items.

  ## Examples

      iex> Cursor.new()
      %Cursor{current: nil, next: [], prev: []}

  """

  @spec new() :: t()
  def new(), do: %Cursor{prev: [], current: nil, next: []}

  @doc """
  Create a Cursor from a list of items.

    * `opts` - The keyword `:position` can specify a position value,
      such as `-1`, `0`, `1`, `:last`, or `tail` in order to set the
      position of the created Cursor.

  ## Examples

      iex> Cursor.from_list([1, 2, 3])
      %Cursor{current: nil, next: [1, 2, 3], prev: []}

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.move_forward()
      %Cursor{current: 1, next: [2, 3], prev: []}

      iex> Cursor.from_list([1, 2, 3], position: 1)
      %Cursor{current: 2, next: [3], prev: [1]}

  """
  @spec from_list(list(), init_options()) :: t()
  def from_list(items, opts \\ []) when is_list(items) do
    %Cursor{prev: [], current: nil, next: items} |> with_init_options(opts)
  end

  @doc """
  Create a Cursor from two lists.

    * `opts` - the keyword `:position` can specify a position value,
      such as `-1`, `0`, `1`, `:last`, or `tail` in order to set the
      position of the created Cursor.

  ## Examples

      iex> Cursor.from_split([1, 2, 3], [4, 5, 6])
      %Cursor{current: 4, next: [5, 6], prev: [3, 2, 1]}

  """
  @spec from_split(list(), list(), init_options()) :: t()
  def from_split(prev, next, opts \\ [])

  def from_split([], next, opts) when is_list(next) do
    %Cursor{prev: [], current: nil, next: next} |> with_init_options(opts)
  end

  def from_split(prev, [], opts) when is_list(prev) do
    %Cursor{prev: Enum.reverse(prev), current: nil, next: []} |> with_init_options(opts)
  end

  def from_split(prev, [h | t], opts) when is_list(prev) do
    %Cursor{prev: Enum.reverse(prev), current: h, next: t} |> with_init_options(opts)
  end

  @spec with_init_options(t(), init_options()) :: t()
  defp with_init_options(%Cursor{} = c, opts) do
    case Keyword.get(opts, :position, nil) do
      pos when is_integer(pos) -> move_to(c, pos)
      _ -> c
    end
  end

  @doc """
  Extract the list from a Cursor.

  ## Examples

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.to_list()
      [1, 2, 3]

  """
  @spec to_list(t()) :: list()
  def to_list(%Cursor{prev: prev, current: nil, next: next}) do
    Enum.reverse(prev) ++ next
  end

  def to_list(%Cursor{prev: prev, current: current, next: next}) do
    Enum.reverse(prev) ++ [current | next]
  end

  @doc """
  Returns `true` if there are no items in the Cursor.

  ## Examples

      iex> Cursor.from_list([]) |> Cursor.empty?()
      true

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.empty?()
      false

  """
  @spec empty?(t()) :: boolean()
  def empty?(%Cursor{prev: prev, current: nil, next: next}),
    do: Enum.empty?(prev) && Enum.empty?(next)

  def empty?(%Cursor{}), do: false

  @doc """
  Returns `true` if the Cursor is positioned before the first item.

  ## Examples

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.before_first?()
      true

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.move_forward() |> Cursor.before_first?()
      false

  """
  @spec before_first?(t()) :: boolean()
  def before_first?(%Cursor{prev: [], current: nil}), do: true
  def before_first?(%Cursor{}), do: false

  @doc """
  Returns `false` if the Cursor is positioned at or before the first item.

  ## Examples

      iex> Cursor.from_list([1, 2]) |> Cursor.has_previous?()
      false

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward() |> Cursor.has_previous?()
      false

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(2) |> Cursor.has_previous?()
      true

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(3) |> Cursor.has_previous?()
      true

  """
  @spec has_previous?(t()) :: boolean()
  def has_previous?(%Cursor{prev: []}), do: false
  def has_previous?(%Cursor{}), do: true

  @doc """
  Returns `true` if the Cursor is positioned after the last item.

  ## Examples

      iex> Cursor.from_list([1, 2]) |> Cursor.after_last?()
      false

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(2) |> Cursor.after_last?()
      false

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(3) |> Cursor.after_last?()
      true

  """
  @spec after_last?(t()) :: boolean()
  def after_last?(%Cursor{current: nil, next: []}), do: true
  def after_last?(%Cursor{}), do: false

  @doc """
  Returns `false` if the Cursor is positioned at or after the last item.

  ## Examples

      iex> Cursor.from_list([1, 2]) |> Cursor.has_next?()
      true

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(2) |> Cursor.has_next?()
      false

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(3) |> Cursor.has_next?()
      false

  """
  @spec has_next?(t()) :: boolean()
  def has_next?(%Cursor{next: []}), do: false
  def has_next?(%Cursor{}), do: true

  @doc """
  Returns the total number of items in the Cursor.

  ## Examples

      iex> Cursor.from_list([1, 2, 3]) |> Cursor.count()
      3

  """
  @spec count(t()) :: non_neg_integer()
  def count(%Cursor{prev: prev, current: nil, next: next}),
    do: Enum.count(prev) + Enum.count(next)

  def count(%Cursor{prev: prev, next: next}), do: Enum.count(prev) + Enum.count(next) + 1

  @doc """
  Returns the current position of the Cursor.

  A return value of `-1` means the Cursor is positioned before the first item.
  A return value of `Cursor.count(c)` means the Cursor is positioned after the last item.

  ## Examples

      iex> Cursor.from_list([1, 2]) |> Cursor.position()
      -1

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward() |> Cursor.position()
      0

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(2) |> Cursor.position()
      1

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(3) |> Cursor.position()
      2

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(4) |> Cursor.position()
      2

  """
  @spec position(t()) :: integer()
  def position(%Cursor{prev: [], current: nil}), do: -1
  def position(%Cursor{prev: prev}), do: Enum.count(prev)

  @doc """
  Changes the current position of the Cursor.

    * `pos` - The desired position.

    * `-1` means the Cursor is positioned before the first item.
    * `0` means the Cursor is positioned at the first item (if it is not empty).
    * `:last` means the Cursor is positioned at the last item (if it is not empty).
    * `:tail` means the Cursor is positioned after the last item.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_to(-1)
      %Cursor{current: nil, next: [1, 2, 3, 4, 5], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_to(0)
      %Cursor{current: 1, next: [2, 3, 4, 5], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_to(1)
      %Cursor{current: 2, next: [3, 4, 5], prev: [1]}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_to(:last)
      %Cursor{current: 5, next: [], prev: [4, 3, 2, 1]}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_to(:tail)
      %Cursor{current: nil, next: [], prev: [5, 4, 3, 2, 1]}

  """
  @spec move_to(t(), position_value()) :: t()
  def move_to(%Cursor{prev: prev, current: current, next: next}, :tail) do
    current_and_next =
      if is_nil(current) do
        prev
      else
        [current | next]
      end

    %Cursor{prev: Enum.reverse(current_and_next) ++ prev, current: nil, next: []}
  end

  def move_to(%Cursor{} = c, :last), do: c |> move_to(:tail) |> move_back(1)

  def move_to(%Cursor{prev: prev, current: current, next: next}, -1) do
    current_and_next =
      if is_nil(current) do
        next
      else
        [current | next]
      end

    %Cursor{prev: [], current: nil, next: Enum.reverse(prev) ++ current_and_next}
  end

  def move_to(%Cursor{} = c, pos) when is_integer(pos) and pos >= 0 do
    c |> move_to(-1) |> move_forward(pos + 1)
  end

  @doc """
  Resets the position of the Cursor to before the first item.
  An alias for `Cursor.move_to(c, -1)`.

  ## Examples

      iex> Cursor.new() |> Cursor.reset()
      %Cursor{current: nil, next: [], prev: []}

      iex> Cursor.from_list([1]) |> Cursor.move_forward() |> Cursor.reset()
      %Cursor{current: nil, next: [1], prev: []}

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward() |> Cursor.reset()
      %Cursor{current: nil, next: [1, 2], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.reset()
      %Cursor{current: nil, next: [1, 2, 3, 4, 5], prev: []}

  """
  def reset(%Cursor{} = c), do: move_to(c, -1)

  @doc """
  Moves the position of the Cursor to the first item.
  An alias of `Cursor.move_to(c, 0)`.

  ## Examples

      iex> Cursor.new() |> Cursor.move_first()
      %Cursor{current: nil, next: [], prev: []}

      iex> Cursor.from_list([1]) |> Cursor.move_first()
      %Cursor{current: 1, next: [], prev: []}

      iex> Cursor.from_list([1, 2]) |> Cursor.move_first()
      %Cursor{current: 1, next: [2], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_first()
      %Cursor{current: 1, next: [2, 3, 4, 5], prev: []}

  """
  @spec move_first(t()) :: t()
  def move_first(%Cursor{} = c), do: move_to(c, 0)

  @doc """
  Moves the position of the Cursor forward a number of steps.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_forward()
      %Cursor{current: 4, next: [5], prev: [3, 2, 1]}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_forward(2)
      %Cursor{current: 5, next: [], prev: [4, 3, 2, 1]}

      iex> Cursor.from_list([1, 2, 3, 4, 5]) |> Cursor.move_forward(3)
      %Cursor{current: 3, next: [4, 5], prev: [2, 1]}

      iex> Cursor.from_list([1, 2, 3, 4, 5]) |> Cursor.move_forward(5)
      %Cursor{current: 5, next: [], prev: [4, 3, 2, 1]}

      iex> Cursor.from_list([1, 2, 3, 4, 5]) |> Cursor.move_forward(6)
      %Cursor{current: nil, next: [], prev: [5, 4, 3, 2, 1]}

      iex> %Cursor{current: {:delete, "abc"}, next: [{:equal, "xxx"}, {:insert, "def"}], prev: []} |> Cursor.move_forward(1)
      %Cursor{current: {:equal, "xxx"}, next: [{:insert, "def"}], prev: [{:delete, "abc"}]}

      iex> %Cursor{current: {:delete, "abc"}, next: [{:equal, "xxx"}, {:insert, "def"}], prev: []} |> Cursor.move_forward(2)
      %Cursor{current: {:insert, "def"}, next: [], prev: [{:equal, "xxx"}, {:delete, "abc"}]}

      iex> %Cursor{current: {:delete, "abc"}, next: [{:equal, "xxx"}, {:insert, "def"}], prev: []} |> Cursor.move_forward(3)
      %Cursor{current: nil, next: [], prev: [{:insert, "def"}, {:equal, "xxx"}, {:delete, "abc"}]}

  """
  @spec move_forward(t(), integer()) :: t()
  def move_forward(cursor, count \\ 1)
  def move_forward(%Cursor{} = c, count) when is_integer(count) and count <= 0, do: c

  def move_forward(%Cursor{prev: prev, current: current, next: next}, count)
      when is_integer(count) do
    current_and_prev =
      if is_nil(current) do
        prev
      else
        [current | prev]
      end

    if count > Enum.count(next) do
      %Cursor{prev: Enum.reverse(next) ++ current_and_prev, current: nil, next: []}
    else
      {moved, next_next} = Enum.split(next, count)

      {next_cur, to_prev} =
        if Enum.empty?(moved) do
          {nil, []}
        else
          [next_cur | to_prev] = Enum.reverse(moved)
          {next_cur, to_prev}
        end

      %Cursor{prev: to_prev ++ current_and_prev, current: next_cur, next: next_next}
    end
  end

  @doc """
  Moves the position of the Cursor forward through the "next" list
  until the given item is found. Returns `nil` and if the item cannot be found.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_forward(5)
      %Cursor{current: 5, next: [], prev: [4, 3, 2, 1]}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_forward(1)
      nil

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_forward(3)
      nil

  """
  @spec find_forward(t(), term()) :: nil | t()
  def find_forward(%Cursor{next: next} = c, item) do
    case Enum.find_index(next, fn i -> i == item end) do
      nil -> nil
      i -> move_forward(c, i + 1)
    end
  end

  @doc """
  Moves the position of the Cursor back a number of steps.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_back(1)
      %Cursor{current: 2, next: [3, 4, 5], prev: [1]}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_back(2)
      %Cursor{current: 1, next: [2, 3, 4, 5], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.move_back(3)
      %Cursor{current: nil, next: [1, 2, 3, 4, 5], prev: []}

  """
  @spec move_back(t(), integer()) :: t()
  def move_back(cursor, count \\ 1)
  def move_back(%Cursor{} = c, count) when is_integer(count) and count <= 0, do: c

  def move_back(%Cursor{prev: prev, current: current, next: next}, count)
      when is_integer(count) do
    current_and_next =
      if is_nil(current) do
        next
      else
        [current | next]
      end

    if count > Enum.count(prev) do
      %Cursor{prev: [], current: nil, next: Enum.reverse(prev) ++ current_and_next}
    else
      {moved, next_prev} = Enum.split(prev, count)

      {next_cur, to_next} =
        if Enum.empty?(moved) do
          {nil, []}
        else
          [next_cur | to_next] = Enum.reverse(moved)
          {next_cur, to_next}
        end

      %Cursor{prev: next_prev, current: next_cur, next: to_next ++ current_and_next}
    end
  end

  @doc """
  Moves the position of the Cursor back through the "prev" list
  until the given item is found. Returns `nil` and if the item cannot be found.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_back(1)
      %Cursor{current: 1, next: [2, 3, 4, 5], prev: []}

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_back(5)
      nil

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.find_back(3)
      nil

  """
  @spec find_back(t(), term()) :: nil | t()
  def find_back(%Cursor{prev: prev} = c, item) do
    case Enum.find_index(prev, fn i -> i == item end) do
      nil -> nil
      i -> move_back(c, i + 1)
    end
  end

  @doc """
  Moves the position of the Cursor back through the "prev" list to the given item.

  Raises if the item cannot be found.
  """
  @spec find_back!(t(), term()) :: t()
  def find_back!(%Cursor{} = c, item) do
    case find_back(c, item) do
      nil -> raise "item #{inspect(item)} not found in Cursor"
      found -> found
    end
  end

  @doc """
  Return a 3-tuple of the previous, current, and next items relative to
  the Cursor's current position.

  Any elements of the tuple may be `nil`.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.get()
      {2, 3, 4}

      iex> Cursor.from_list([]) |> Cursor.get()
      {nil, nil, nil}

      iex> Cursor.from_list([1, 2]) |> Cursor.get()
      {nil, nil, 1}

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward() |> Cursor.get()
      {nil, 1, 2}

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(2) |> Cursor.get()
      {1, 2, nil}

      iex> Cursor.from_list([1, 2]) |> Cursor.move_forward(3) |> Cursor.get()
      {2, nil, nil}

  """
  @spec get(t()) :: {term(), term(), term()}
  def get(%Cursor{prev: prev, current: current, next: next}) do
    {List.first(prev), current, List.first(next)}
  end

  @doc """
  Remove items at the Cursor's current position, leaving the previous items alone.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.delete(1)
      %Cursor{current: 4, next: [5], prev: [2, 1]}

  """
  @spec delete(t(), integer()) :: t()
  def delete(cursor, count \\ 1)
  def delete(%Cursor{} = c, count) when is_integer(count) and count <= 0, do: c

  def delete(%Cursor{current: current, next: next} = c, count) when is_integer(count) do
    next_next =
      if is_nil(current) do
        Enum.drop(next, count)
      else
        Enum.drop(next, count - 1)
      end

    case next_next do
      [] -> %Cursor{c | current: nil, next: []}
      [next_cur | rest] -> %Cursor{c | current: next_cur, next: rest}
    end
  end

  @doc """
  Remove items before the Cursor's current position, leaving the current and next items alone.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.delete_before(1)
      %Cursor{current: 3, next: [4, 5], prev: [1]}

  """
  @spec delete_before(t(), integer()) :: t()
  def delete_before(cursor, count \\ 1)
  def delete_before(%Cursor{} = c, count) when is_integer(count) and count <= 0, do: c

  def delete_before(%Cursor{prev: prev} = c, count) when is_integer(count) do
    %Cursor{c | prev: Enum.drop(prev, count)}
  end

  @doc """
  Insert items at the Cursor's current position, leaving the previous items alone.

  After the insertion, the Cursor points to the first inserted item.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.insert([10, 11])
      %Cursor{current: 10, next: [11, 3, 4, 5], prev: [2, 1]}

  """
  @spec insert(t(), list()) :: t()
  def insert(%Cursor{} = c, []), do: c

  def insert(%Cursor{current: nil, next: next} = c, [next_cur | rest]) do
    %Cursor{c | current: next_cur, next: rest ++ next}
  end

  def insert(%Cursor{current: current, next: next} = c, [next_cur | rest]) do
    %Cursor{c | current: next_cur, next: rest ++ [current | next]}
  end

  @doc """
  Insert items before the Cursor's current position, leaving the current and next items alone.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.insert_before([10, 11])
      %Cursor{current: 3, next: [4, 5], prev: [11, 10, 2, 1]}

  """
  @spec insert_before(t(), list()) :: t()
  def insert_before(%Cursor{} = c, []), do: c

  def insert_before(%Cursor{prev: prev} = c, items) when is_list(items) do
    %Cursor{c | prev: Enum.reverse(items) ++ prev}
  end

  @doc """
  Insert items at the Cursor's head position, leaving the current position pointer alone.

  ## Examples

      iex> %Cursor{current: 3, next: [4, 5], prev: [2, 1]} |> Cursor.insert_at_head([10, 11])
      %Cursor{current: 3, next: [4, 5], prev: [2, 1, 11, 10]}

  """
  @spec insert_at_head(t(), list()) :: t()
  def insert_at_head(%Cursor{} = c, []), do: c

  def insert_at_head(%Cursor{prev: prev} = c, items) when is_list(items) do
    %Cursor{c | prev: prev ++ Enum.reverse(items)}
  end
end