elixir_ds

defmodule ElixirDS.Deque do
  @moduledoc """
  Double Ended Queue.

  Supports O(1) (amortized) insertions and deletions at both ends

  #### TODO: Add usage instructions

  ##### API
  - [x] new()
  - [x] from_list(lst)
  - [x] is_empty(q)
  - [x] size(q)
  - [x] push_front(q, elem)
  - [x] push_back(q, elem)
  - [x] pop_front(q)
  - [x] pop_back(q)
  - [x] peek_front(q)
  - [x] peek_back(q)
  - [x] rotate(q, n)
  """

  alias __MODULE__

  defstruct front: [], back: []

  @type t :: %Deque{front: list(), back: list()}

  @doc """
  Create a new deque.
  """
  @spec new() :: t()
  def new(), do: %Deque{front: [], back: []}

  @doc """
  Create a new deque from a list.
  """
  @spec from_list(list()) :: t()
  def from_list(lst) when is_list(lst) do
    %Deque{front: lst}
  end

  @doc """
  Get the number of elements in the deque.
  """
  @spec size(t()) :: non_neg_integer
  def size(%Deque{front: front, back: back}), do: length(front) + length(back)

  @doc """
  Is the deque empty?
  """
  @spec is_empty?(t) :: boolean
  def is_empty?(%Deque{} = dq), do: Deque.size(dq) == 0

  @doc """
  Peek the first element in the queue.

  This function does not modify the deque.
  In case the queue is empty, it will return an `:error`.
  """
  @spec peek_front(t) :: :error | any()
  def peek_front(%Deque{front: [], back: []}), do: :error
  def peek_front(%Deque{front: [val | _]}), do: val
  def peek_front(%Deque{back: back, front: []}), do: List.last(back)

  @doc """
  Peek the last element in the queue.

  This function does not modify the deque.
  In case the queue is empty, it will return an `:error`.
  """
  @spec peek_back(t) :: :error | any()
  def peek_back(%Deque{front: [], back: []}), do: :error
  def peek_back(%Deque{back: [val | _]}), do: val
  def peek_back(%Deque{front: front, back: []}), do: List.last(front)

  @doc """
  Insert a value at the front of the deque.
  """
  @spec push_front(t, any) :: t
  def push_front(%Deque{front: front} = dq, val), do: %Deque{dq | front: [val | front]}

  @doc """
  Insert a value at the back of the deque.
  """
  @spec push_back(t, any) :: t
  def push_back(%Deque{back: back} = dq, val), do: %Deque{dq | back: [val | back]}

  @doc """
  Removes the value at the front of the deque and retuns the value and the updated deque.
  """
  @spec pop_front(t) :: {any, t} | :error
  def pop_front(%Deque{front: [], back: []}), do: :error
  def pop_front(%Deque{front: [val | tail]} = dq), do: {val, %Deque{dq | front: tail}}

  def pop_front(%Deque{front: [], back: back} = dq) do
    [val | tail] = Enum.reverse(back)
    {val, %Deque{dq | front: tail, back: []}}
  end

  @doc """
  Removes the value at the back of the deque and retuns the value and the updated deque.
  """
  @spec pop_back(t) :: {any, t} | :error
  def pop_back(%Deque{front: [], back: []}), do: :error
  def pop_back(%Deque{back: [val | tail]} = dq), do: {val, %Deque{dq | back: tail}}

  def pop_back(%Deque{front: front, back: []} = dq) do
    [val | tail] = Enum.reverse(front)
    {val, %Deque{dq | front: [], back: tail}}
  end

  @doc """
  Rotates the list by n elements (front to back).
  In case n is negative, moves the items in the other direction
  """
  @spec rotate(t, integer) :: t
  def rotate(dq, n) when n >= 0 do
    Enum.reduce(1..n, dq, fn _i, acc -> rotate_one_f(acc) end)
  end

  def rotate(dq, n) when n < 0 do
    Enum.reduce(n..-1, dq, fn _i, acc -> rotate_one_r(acc) end)
  end

  @spec rotate_one_f(t) :: t
  defp rotate_one_f(%Deque{front: [], back: []} = dq), do: dq

  defp rotate_one_f(dq) do
    {last, dq} = Deque.pop_back(dq)
    Deque.push_front(dq, last)
  end

  @spec rotate_one_r(t) :: t
  defp rotate_one_r(%Deque{front: [], back: []} = dq), do: dq

  defp rotate_one_r(dq) do
    {first, dq} = Deque.pop_front(dq)
    Deque.push_back(dq, first)
  end
end