<commit_before>defmodule Gullintanni.Queue do
  @moduledoc """
  Provides priority queues in a relatively efficient manner.

  Queues are double-ended. The mental picture of a queue is a line of people
  (items) waiting for their turn. The queue *front* is the end with the item
  that has waited the longest. The queue *rear* is the end an item enters when
  it starts to wait. If instead using the mental picture of a list, the front
  is called head and the rear is called tail. A priority queue adds the idea
  that an item can skip ahead in line according to its importance (priority).

  Each item in a priority queue is represented as a tuple with both its *value*
  and *priority*. Priorities must be integers, with higher integers being
  treated as higher in priority. Multiple items may exist with the same
  priority and are used in First-In First-Out (FIFO) order.

  The data representing a priority queue as used by this module is to be
  regarded as opaque by other modules.
  """

  alias __MODULE__, as: Queue

  @typedoc "The value of an item"
  @type value :: any

  @typedoc "The priority of an item"
  @type priority :: integer

  @typedoc "A priority queue item"
  @type item :: {value, priority}

  @typedoc "The underlying data structure of a priority queue"
  @opaque data :: :gb_trees.tree

  @typedoc "The priority queue type"
  @type t :: %Queue{items: data, size: non_neg_integer}

  defstruct [:items, :size]

  @doc """
  Creates a new empty priority queue.
  """
  # FIXME: dialyzer throws a badarg error if the return type is `t`
  @spec new :: struct
  def new, do: %Queue{items: :gb_trees.empty, size: 0}

  @doc """
  Returns `true` if the `queue` is empty, otherwise `false`.
  """
  @spec empty?(t) :: boolean
  def empty?(%Queue{size: 0}), do: true
  def empty?(%Queue{}), do: false

  @doc """
  Inserts an `item` into the `queue`.

  Returns a new queue which is a copy of `queue` but with the item's value
  inserted at the specified priority. If there are existing values at the
  specified priority, the new value will have the lowest relative priority of
  those values.
  """
  @spec insert(t, item) :: t
  def insert(%Queue{} = queue, {value, priority} = _item) when is_integer(priority) do
    values =
      case :gb_trees.lookup(priority, queue.items) do
        :none -> [value]
        {:value, rest} -> [value|rest]
      end

    %{queue |
      :items => :gb_trees.enter(priority, values, queue.items),
      :size => queue.size + 1
    }
  end

  @doc """
  Deletes an `item` from the `queue`.

  Returns a new queue which is a copy of `queue` but without `item`. If the
  item did not exist previously, returns the queue unmodified. If the item's
  value occurs more than once at the specified priority, just the item with the
  highest relative priority is removed.
  """
  @spec delete(t, item) :: t
  def delete(%Queue{} = queue, {value, priority} = _item) when is_integer(priority) do
    case :gb_trees.lookup(priority, queue.items) do
      :none ->
        queue
      {:value, [^value]} ->
        %{queue |
           :items => :gb_trees.delete(priority, queue.items),
           :size => queue.size - 1
        }
      {:value, old_values} ->
        new_values =
          old_values
          |> Enum.reverse
          |> List.delete(value)
          |> Enum.reverse

        if new_values == old_values do
          # no item was deleted
          queue
        else
          %{queue |
            :items => :gb_trees.update(priority, new_values, queue.items),
            :size => queue.size - 1
          }
        end
    end
  end

  @doc """
  Moves an `item` to a different priority in the `queue`.

  Returns a new queue which is a copy of `queue` but with the item's value
  moved to the specified priority. If the item did not exist previously,
  returns the queue unmodified. If the item's value occurs more than once at
  the specified priority, just the item with the highest relative priority is
  moved.
  """
  @spec move(t, item, priority) :: t
  def move(%Queue{} = queue, {value, old_priority} = _item, new_priority) do
    new_queue = delete(queue, {value, old_priority})

    if new_queue == queue do
      # no item was deleted
      queue
    else
      insert(new_queue, {value, new_priority})
    end
  end

  @doc """
  Returns the highest priority `item` in the `queue`.

  Returns `:empty` if the queue is empty.
  """
  @spec peek(t) :: item | :empty
  def peek(%Queue{size: 0}), do: :empty
  def peek(%Queue{} = queue) do
    {priority, values, _queue} = :gb_trees.take_largest(queue.items)
    {List.last(values), priority}
  end

  @doc """
  Returns the lowest priority `item` in the `queue`.

  Returns `:empty` if the queue is empty.
  """
  @spec peek_r(t) :: item | :empty
  def peek_r(%Queue{size: 0}), do: :empty
  def peek_r(%Queue{} = queue) do
    {priority, values, _queue} = :gb_trees.take_smallest(queue.items)
    {List.first(values), priority}
  end<commit_msg>Use bodyless clauses for forcing doc proper names<commit_after>defmodule Gullintanni.Queue do
  @moduledoc """
  Provides priority queues in a relatively efficient manner.

  Queues are double-ended. The mental picture of a queue is a line of people
  (items) waiting for their turn. The queue *front* is the end with the item
  that has waited the longest. The queue *rear* is the end an item enters when
  it starts to wait. If instead using the mental picture of a list, the front
  is called head and the rear is called tail. A priority queue adds the idea
  that an item can skip ahead in line according to its importance (priority).

  Each item in a priority queue is represented as a tuple with both its *value*
  and *priority*. Priorities must be integers, with higher integers being
  treated as higher in priority. Multiple items may exist with the same
  priority and are used in First-In First-Out (FIFO) order.

  The data representing a priority queue as used by this module is to be
  regarded as opaque by other modules.
  """

  alias __MODULE__, as: Queue

  @typedoc "The value of an item"
  @type value :: any

  @typedoc "The priority of an item"
  @type priority :: integer

  @typedoc "A priority queue item"
  @type item :: {value, priority}

  @typedoc "The underlying data structure of a priority queue"
  @opaque data :: :gb_trees.tree

  @typedoc "The priority queue type"
  @type t :: %Queue{items: data, size: non_neg_integer}

  defstruct [:items, :size]

  @doc """
  Creates a new empty priority queue.
  """
  # FIXME: dialyzer throws a badarg error if the return type is `t`
  @spec new :: struct
  def new, do: %Queue{items: :gb_trees.empty, size: 0}

  @doc """
  Returns `true` if the `queue` is empty, otherwise `false`.
  """
  @spec empty?(t) :: boolean
  def empty?(%Queue{size: 0}), do: true
  def empty?(%Queue{}), do: false

  @doc """
  Inserts an `item` into the `queue`.

  Returns a new queue which is a copy of `queue` but with the item's value
  inserted at the specified priority. If there are existing values at the
  specified priority, the new value will have the lowest relative priority of
  those values.
  """
  @spec insert(t, item) :: t
  def insert(queue, item)
  def insert(%Queue{} = queue, {value, priority}) when is_integer(priority) do
    values =
      case :gb_trees.lookup(priority, queue.items) do
        :none -> [value]
        {:value, rest} -> [value|rest]
      end

    %{queue |
      :items => :gb_trees.enter(priority, values, queue.items),
      :size => queue.size + 1
    }
  end

  @doc """
  Deletes an `item` from the `queue`.

  Returns a new queue which is a copy of `queue` but without `item`. If the
  item did not exist previously, returns the queue unmodified. If the item's
  value occurs more than once at the specified priority, just the item with the
  highest relative priority is removed.
  """
  @spec delete(t, item) :: t
  def delete(queue, item)
  def delete(%Queue{} = queue, {value, priority}) when is_integer(priority) do
    case :gb_trees.lookup(priority, queue.items) do
      :none ->
        queue
      {:value, [^value]} ->
        %{queue |
           :items => :gb_trees.delete(priority, queue.items),
           :size => queue.size - 1
        }
      {:value, old_values} ->
        new_values =
          old_values
          |> Enum.reverse
          |> List.delete(value)
          |> Enum.reverse

        if new_values == old_values do
          # no item was deleted
          queue
        else
          %{queue |
            :items => :gb_trees.update(priority, new_values, queue.items),
            :size => queue.size - 1
          }
        end
    end
  end

  @doc """
  Moves an `item` to a different priority in the `queue`.

  Returns a new queue which is a copy of `queue` but with the item's value
  moved to the specified priority. If the item did not exist previously,
  returns the queue unmodified. If the item's value occurs more than once at
  the specified priority, just the item with the highest relative priority is
  moved.
  """
  @spec move(t, item, priority) :: t
  def move(queue, item, new_priority)
  def move(%Queue{} = old_queue, {value, old_priority}, new_priority) do
    new_queue = delete(old_queue, {value, old_priority})

    if new_queue == old_queue do
      # no item was deleted
      old_queue
    else
      insert(new_queue, {value, new_priority})
    end
  end

  @doc """
  Returns the highest priority `item` in the `queue`.

  Returns `:empty` if the queue is empty.
  """
  @spec peek(t) :: item | :empty
  def peek(%Queue{size: 0}), do: :empty
  def peek(%Queue{} = queue) do
    {priority, values, _queue} = :gb_trees.take_largest(queue.items)
    {List.last(values), priority}
  end

  @doc """
  Returns the lowest priority `item` in the `queue`.

  Returns `:empty` if the queue is empty.
  """
  @spec peek_r(t) :: item | :empty
  def peek_r(%Queue{size: 0}), do: :empty
  def peek_r(%Queue{} = queue) do
    {priority, values, _queue} = :gb_trees.take_smallest(queue.items)
    {List.first(values), priority}
  end
{'fraction_non_alphanumeric': 0.10252084160381103, 'fraction_numerical': 0.001389440254069075, 'mean_word_length': 2.939405785770133, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3185873', 'n_tokens_mistral': 3105, 'n_tokens_neox': 2994, 'n_words': 1273}