qu

defmodule Qu do
  @readme "README.md"
  @external_resource @readme
  @moduledoc_readme @readme
                    |> File.read!()
                    |> String.split("<!-- END HEADER -->")
                    |> Enum.fetch!(1)
                    |> String.trim()

  @moduledoc """
  #{@moduledoc_readme}
  """

  alias Qu.Queue

  @typedoc """
  Type of queue.
  """
  @type queue_type() :: :fifo | :lifo | :circular | :priority

  @typedoc """
  Maximum queue size. A value of `nil` indicates that the queue has no maximum
  size.
  """
  @type max_size() :: non_neg_integer() | nil

  @typedoc """
  Current size of the queue.
  """
  @type size() :: non_neg_integer()

  @typedoc """
  A queue item, either a single value or, in the case of a priority queue, a
  tuple of a priority key and a value.
  """
  @type item() :: any() | {any(), any()}

  @opts_schema [
    max_size: [
      type: {:or, [:non_neg_integer, nil]},
      default: nil,
      doc: """
      Maximum size of the queue. A value of `nil` indicates that the queue has
      no maximum size. When the queue type is `:circular`, the maximum must be
      a positive integer.
      """
    ],
    priority_order: [
      type:
        {:or,
         [
           {:in, [:desc, :asc]},
           {:tuple, [{:in, [:desc, :asc]}, :atom]}
         ]},
      default: :asc,
      doc: """
      Key order in which items are removed when the queue type is
      `:priority`. When a tuple like `{:desc, DateTime}` is given, the key is
      assumed to be a `DateTime`, and `DateTime.compare/2` is used compare
      keys.
      """
    ]
  ]

  @doc """
  Create a new queue of the given type and maximum size.

  ## Options

  #{NimbleOptions.docs(@opts_schema)}

  ## Examples

      iex> Qu.new(:fifo, max_size: 10)
      #FIFO<read: [], write: [], size: 0, max_size: 10>

      iex> Qu.new(:priority, priority_order: {:asc, DateTime})
      #Priority<heap: #PairingHeap<root: :empty, size: 0, mode: {:min, DateTime}>, size: 0, max_size: nil>
  """
  @spec new(type :: queue_type(), opts :: keyword()) :: Queue.t()
  def new(type, opts \\ []) do
    opts_map = validate_options!(opts, type, @opts_schema)

    case type do
      :fifo ->
        Qu.FIFO.new(opts_map.max_size)

      :lifo ->
        Qu.LIFO.new(opts_map.max_size)

      :circular ->
        Qu.Circular.new(opts_map.max_size)

      :priority ->
        Qu.Priority.new(opts_map.priority_order, opts_map.max_size)
    end
  end

  @doc """
  Insert an item into the queue.

  If the queue size is less than the maximum size, this returns
  `{:ok, updated_queue}`. With the exception of a cirular queue, if the queue
  size equals the maximum size, `:error` is returned. For a circular queue,
  `Qu.put/2` never returns `:error`.

  ## Examples

      iex> {:ok, q} = Qu.new(:fifo, max_size: 1) |> Qu.put("a")
      iex> q
      #FIFO<read: [], write: ["a"], size: 1, max_size: 1>
      iex> Qu.put(q, "b")
      :error

      iex> {:ok, q}  = Qu.new(:priority, priority_order: :asc) |> Qu.put({1, "a"})
      iex> q
      #Priority<heap: #PairingHeap<root: {1, "a"}, size: 1, mode: :min>, size: 1, max_size: nil>
  """
  @spec put(Queue.t(), item()) :: {:ok, Queue.t()} | :error
  def put(queue, item), do: Queue.put(queue, item)

  @doc """
  Pop the item at the head of the queue.

  If there is at least one item in the queue, this returns
  `{:ok, item, updated_queue}`. If the queue is empty, `:error` is returned.

  ## Examples

      iex> {:ok, q} = Qu.new(:fifo) |> Qu.put("a")
      iex> {:ok, "a", q} = Qu.pop(q)
      iex> q
      #FIFO<read: [], write: [], size: 0, max_size: nil>
      iex> Qu.pop(q)
      :error
  """
  @spec pop(Queue.t()) :: {:ok, item(), Queue.t()} | :error
  def pop(queue), do: Queue.pop(queue)

  @doc """
  Get the item at the head of the queue.

  If there is at least one item in the queue, this returns
  `{:ok, item}`. If the queue is empty, `:error` is returned.

  ## Examples

      iex> {:ok, q} = Qu.new(:fifo, max_size: 1) |> Qu.put("a")
      iex> {:ok, "a"} = Qu.peek(q)
  """
  @spec peek(Queue.t()) :: {:ok, item()} | :error
  def peek(queue), do: Queue.peek(queue)

  @doc """
  Return the first `n` items in the queue and the final state of the heap.

  If the queue size is less than `n`, all items are returned along with
  an empty heap.

  Note that `pull` is often more convenient than `pop`, because of it can pop
  multiple items at once, and because it never returns `:error`.

  ## Examples

      iex> {:ok, q} = Qu.new(:fifo, max_size: 1) |> Qu.put("a")
      iex> {["a"], _} = Qu.pull(q, 1)
  """
  @spec pull(Queue.t(), non_neg_integer()) :: {[item()], Queue.t()}
  def pull(queue, n) when is_integer(n) and n >= 0, do: pull(queue, n, [])

  @spec pull(Queue.t(), non_neg_integer(), [item()]) :: {[item()], Queue.t()}
  defp pull(queue, 0, items), do: {Enum.reverse(items), queue}

  defp pull(queue, n, items) do
    case pop(queue) do
      {:ok, item, queue} ->
        pull(queue, n - 1, [item | items])

      :error ->
        {items, queue}
    end
  end

  @doc """
  Return the size of the queue.

  ## Examples

      iex> q = Qu.new(:fifo, max_size: 1)
      iex> Qu.size(q)
      0
      iex> {:ok, q} = Qu.put(q, "a")
      iex> Qu.size(q)
      1
  """
  @spec size(Queue.t()) :: size()
  def size(queue), do: Queue.size(queue)

  @spec validate_options!(keyword(), queue_type(), keyword()) :: map()
  defp validate_options!(opts, _queue_type, schema) do
    opts |> NimbleOptions.validate!(schema) |> Map.new()
  end
end