Elixir wrapper for `:queue`

queue.ex

defmodule Queue do
  @moduledoc """
  Wrapper for Erlang's :queue with optional `max_length` and O(1) `.length` query.
  """

  alias __MODULE__

  @type t :: %Queue{
          q: {list(), list()},
          length: pos_integer(),
          max_length: pos_integer() | :infinity
        }

  @derive {Inspect, only: [:max_length, :length]}

  defstruct [max_length: :infinity, q: :queue.new(), length: 0]

  @spec new :: t()
  @spec new(pos_integer()) :: t()
  def new(), do: struct(Queue)
  def new(size) when size > 0, do: struct(Queue, max_length: size)

  @spec enqueue(t(), any()) :: t() | {:error, :queue_full}
  def enqueue(%Queue{length: length, max_length: max_length}, _)
      when max_length != :infinity and length >= max_length do
    {:error, :queue_full}
  end

  def enqueue(%Queue{q: q, length: length} = queue, item) do
    %{
      queue
      | q: :queue.in(item, q),
        length: length + 1
    }
  end

  @spec dequeue(t()) :: {:empty | {:value, any()}, t()}
  def dequeue(%Queue{q: q, length: length} = queue) do
    {out, q} = :queue.out(q)
    {out, %{queue | q: q, length: max(length - 1, 0)}}
  end

  @spec length(t()) :: pos_integer()
  def length(%Queue{length: length}), do: length
end

queue_test.exs

defmodule QueueTest do
  use ExUnit.Case

  describe ".new/0" do
    test "creates an unbounded queue" do
      assert %Queue{max_length: :infinity} = Queue.new()
    end
  end

  describe ".new/1" do
    test "creates a bounded queue" do
      assert %Queue{max_length: 10_000} = Queue.new(10_000)
    end
  end

  describe ".enqueue/2" do
    test "puts new item on queue" do
      for item <- 1..10_000_000, reduce: Queue.new() do
        queue ->
          assert %Queue{length: ^item} = queue = Queue.enqueue(queue, item)
          queue
      end
    end

    test "rejects new item if full" do
      queue = Queue.new(3)
      assert %Queue{length: 1} = queue = Queue.enqueue(queue, "一")
      assert %Queue{length: 2} = queue = Queue.enqueue(queue, "二")
      assert %Queue{length: 3} = queue = Queue.enqueue(queue, "三")
      assert {:error, :queue_full} = Queue.enqueue(queue, "四")
    end
  end

  describe ".dequeue/1" do
    test "takes the front-most item out of the queue and returns smaller queue" do
      queue = Queue.new()
      queue = Queue.enqueue(queue, "Huey")
      queue = Queue.enqueue(queue, "Dewey")
      queue = Queue.enqueue(queue, "Lewey")

      assert {{:value, "Huey"}, %Queue{length: 2} = queue} = Queue.dequeue(queue)
      assert {{:value, "Dewey"}, %Queue{length: 1} = queue} = Queue.dequeue(queue)
      assert {{:value, "Lewey"}, %Queue{length: 0} = queue} = Queue.dequeue(queue)
      assert {:empty, %Queue{length: 0}} = Queue.dequeue(queue)
    end
  end

  describe ".length/1" do
    test "returns queue length without traversing the queue" do
      queue1 =
        for item <- 1..5, reduce: Queue.new() do
          queue -> Queue.enqueue(queue, item)
        end

      queue2 =
        for item <- 1..5_000_000, reduce: Queue.new() do
          queue -> Queue.enqueue(queue, item)
        end

      assert {time1, 5} = :timer.tc(fn -> Queue.length(queue1) end)
      assert {time2, 5_000_000} = :timer.tc(fn -> Queue.length(queue2) end)

      time1 = max(time1, 1)
      time2 = max(time2, 1)

      assert max(time1, time2) < min(time1, time2) * 2
    end
  end
end