Packages
mneme
0.3.3
0.10.2
0.10.1
0.10.0
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.9.0-alpha.1
0.9.0-alpha.0
0.8.2
0.8.1
0.8.0
0.7.0
0.6.1
0.6.0
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.3.0-rc.1
0.3.0-rc.0
0.2.7
0.2.6
0.2.5
0.2.4
0.2.3
0.2.2
0.2.1
0.2.0
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
0.0.5
0.0.4
0.0.3
0.0.2
0.0.1
Snapshot testing tool using familiar assertions
Current section
Files
Jump to
Current section
Files
lib/mneme/diff/priority_queue.ex
defmodule Mneme.Diff.PriorityQueue do
@moduledoc false
@opaque t :: :gb_trees.tree()
@type priority :: non_neg_integer()
@doc """
Creates a new priority queue.
"""
@spec new() :: t
def new do
:gb_trees.empty()
end
@doc """
Push a new element into the queue with a given priority.
"""
@spec push(t, term(), priority) :: t
def push(pqueue, value, priority) do
case :gb_trees.lookup(priority, pqueue) do
:none ->
queue = :queue.new()
queue = :queue.in(value, queue)
:gb_trees.insert(priority, queue, pqueue)
{:value, queue} ->
new_queue = :queue.in(value, queue)
:gb_trees.update(priority, new_queue, pqueue)
end
end
@doc """
Pop an element out of the queue, returning `{:ok, value, queue}` or
`:error` if there is not an element to pop.
"""
@spec pop(t) :: {:ok, term(), t} | :error
def pop(pqueue) do
if :gb_trees.is_empty(pqueue) do
:error
else
{priority, queue, pqueue} = :gb_trees.take_smallest(pqueue)
{{:value, value}, queue} = :queue.out(queue)
if :queue.is_empty(queue) do
{:ok, value, pqueue}
else
{:ok, value, :gb_trees.insert(priority, queue, pqueue)}
end
end
end
end