123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116 |
- -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.
|