ebb/src/priority_queue.erl

-module(priority_queue).

-export([empty/0, is_empty/1, size/1, values/1, priorities/1]).
-export([to_list/1, to_orddict/1, from_list/1, from_orddict/1, map_values/2]).
-export([insert/3, insert_many/3]).
-export([find_value/2, delete_value/2, take_value/2, modify_priority/3]).
-export([minimum/1, take_minimum/1, maximum/1, take_maximum/1]).

empty() ->
    gb_trees:empty().

is_empty(Queue) ->
    gb_trees:is_empty(Queue).

size(Queue) ->
    gb_trees:size(Queue).

values(Queue) ->
    lists:append(gb_trees:values(Queue)).

priorities(Queue) ->
    gb_trees:keys(Queue).

to_orddict(Queue) ->
    gb_trees:to_list(Queue).

to_list(Queue) ->
    lists:append([ [ {Priority, Val} || Val <- Vals ]
		   || {Priority, Vals} <- gb_trees:to_list(Queue) ]).

from_orddict(List) ->
    gb_trees:from_orddict(List).

from_list(List) ->
    lists:foldl(fun({Priority, Val}, Queue) -> insert(Priority, Val, Queue) end,
		empty(), List).

map_values(Func, Queue) ->
    gb_trees:map(fun(_Key, Vals) -> lists:map(Func, Vals) end, Queue).

insert(Priority, Val, Queue) ->
    case gb_trees:lookup(Priority, Queue) of
	none ->
	    gb_trees:insert(Priority, [Val], Queue);
	{value, Prev} ->
	    gb_trees:update(Priority, [Val|Prev], Queue)
    end.

insert_many(Priority, Vals, Queue) when is_list(Vals) ->
    case gb_trees:lookup(Priority, Queue) of
	none ->
	    gb_trees:insert(Priority, Vals, Queue);
	{value, Prev} ->
	    gb_trees:update(Priority, Vals++Prev, Queue)
    end.

find_value(Val, Queue) ->
    case [ {P, V} || {P, Vs} <- to_orddict(Queue), V <- Vs, V == Val ] of
	[{Priority, Val}] -> {Priority, Val};
	[] -> none
    end.

delete_value(Val, Queue) ->
    gb_trees:map(fun(_Key, Vs) -> [ V || V <- Vs, V =/= Val ] end, Queue).

take_value(Val, Queue) ->
    case [ {P, V, Vs} || {P, Vs} <- to_orddict(Queue), V <- Vs, V == Val ] of
	[{Priority, Val, Vals}] ->
	    Queue2 = case [ V || V <- Vals, V =/= Val ] of
			 [] -> gb_trees:delete(Priority, Queue);
			 Vals2 -> gb_trees:update(Priority, Vals2, Queue)
		     end,
	    {Priority, Val, Queue2};
	[] -> none
    end.

modify_priority(Val, Func, Queue) when is_function(Func) ->
    case take_value(Val, Queue) of
	{Priority, Val, Queue2} ->
	    insert(Func(Priority), Val, Queue2);
	none ->
	    Queue
    end.

minimum(Queue) ->
    case gb_trees:smallest(Queue) of
	{Priority, [Val|_]} -> {Priority, Val};
	{Priority, []} -> minimum(gb_trees:delete(Priority, Queue))
    end.

maximum(Queue) ->
    case gb_trees:largest(Queue) of
	{Priority, [Val|_]} -> {Priority, Val};
	{Priority, []} -> maximum(gb_trees:delete(Priority, Queue))
    end.

take_minimum(Queue) ->
    case gb_trees:take_smallest(Queue) of
	{_Priority, [], Queue2} ->
	    take_minimum(Queue2);
	{Priority, [Val], Queue2} ->
	    {Priority, Val, Queue2};
	{Priority, [Val|Vals], Queue2} ->
	    {Priority, Val, gb_trees:insert(Priority, Vals, Queue2)}
    end.

take_maximum(Queue) ->
    case gb_trees:take_largest(Queue) of
	{_Priority, [], Queue2} ->
	    take_maximum(Queue2);
	{Priority, [Val], Queue2} ->
	    {Priority, Val, Queue2};
	{Priority, [Val|Vals], Queue2} ->
	    {Priority, Val, gb_trees:insert(Priority, Vals, Queue2)}
    end.