%% %% %CopyrightBegin% %% %% Copyright Ericsson AB 1996-2011. All Rights Reserved. %% %% The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in %% compliance with the License. You should have received a copy of the %% Erlang Public License along with this software. If not, it can be %% retrieved online at http://www.erlang.org/. %% %% Software distributed under the License is distributed on an "AS IS" %% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See %% the License for the specific language governing rights and limitations %% under the License. %% %% %CopyrightEnd% %% -module(queue). %% Creation, inspection and conversion -export([new/0,is_queue/1,is_empty/1,len/1,to_list/1,from_list/1,member/2]). %% Original style API -export([in/2,in_r/2,out/1,out_r/1]). %% Less garbage style API -export([get/1,get_r/1,peek/1,peek_r/1,drop/1,drop_r/1]). %% Higher level API -export([reverse/1,join/2,split/2,filter/2]). %% Okasaki API from klacke -export([cons/2,head/1,tail/1, snoc/2,last/1,daeh/1,init/1,liat/1,lait/1]). %%-------------------------------------------------------------------------- %% Efficient implementation of double ended fifo queues %% %% Queue representation %% %% {RearList,FrontList} %% %% The first element in the queue is at the head of the FrontList %% The last element in the queue is at the head of the RearList, %% that is; the RearList is reversed. %% %% A declaration equivalent to the following is currently hard-coded %% in erl_types.erl %% %% -opaque queue() :: {list(), list()}. %% Creation, inspection and conversion %% O(1) -spec new() -> queue(). new() -> {[],[]}. %{RearList,FrontList} %% O(1) -spec is_queue(Term :: term()) -> boolean(). is_queue({R,F}) when is_list(R), is_list(F) -> true; is_queue(_) -> false. %% O(1) -spec is_empty(Q :: queue()) -> boolean(). is_empty({[],[]}) -> true; is_empty({In,Out}) when is_list(In), is_list(Out) -> false; is_empty(Q) -> erlang:error(badarg, [Q]). %% O(len(Q)) -spec len(Q :: queue()) -> non_neg_integer(). len({R,F}) when is_list(R), is_list(F) -> length(R)+length(F); len(Q) -> erlang:error(badarg, [Q]). %% O(len(Q)) -spec to_list(Q :: queue()) -> list(). to_list({In,Out}) when is_list(In), is_list(Out) -> Out++lists:reverse(In, []); to_list(Q) -> erlang:error(badarg, [Q]). %% Create queue from list %% %% O(length(L)) -spec from_list(L :: list()) -> queue(). from_list(L) when is_list(L) -> f2r(L); from_list(L) -> erlang:error(badarg, [L]). %% Return true or false depending on if element is in queue %% %% O(length(Q)) worst case -spec member(Item :: term(), Q :: queue()) -> boolean(). member(X, {R,F}) when is_list(R), is_list(F) -> lists:member(X, R) orelse lists:member(X, F); member(X, Q) -> erlang:error(badarg, [X,Q]). %%-------------------------------------------------------------------------- %% Original style API %% Append to tail/rear %% Put at least one element in each list, if it is cheap %% %% O(1) -spec in(Item :: term(), Q1 :: queue()) -> Q2 :: queue(). in(X, {[_]=In,[]}) -> {[X], In}; in(X, {In,Out}) when is_list(In), is_list(Out) -> {[X|In],Out}; in(X, Q) -> erlang:error(badarg, [X,Q]). %% Prepend to head/front %% Put at least one element in each list, if it is cheap %% %% O(1) -spec in_r(Item :: term(), Q1 :: queue()) -> Q2 :: queue(). in_r(X, {[],[_]=F}) -> {F,[X]}; in_r(X, {R,F}) when is_list(R), is_list(F) -> {R,[X|F]}; in_r(X, Q) -> erlang:error(badarg, [X,Q]). %% Take from head/front %% %% O(1) amortized, O(len(Q)) worst case -spec out(Q1 :: queue()) -> {{value, Item :: term()}, Q2 :: queue()} | {empty, Q1 :: queue()}. out({[],[]}=Q) -> {empty,Q}; out({[V],[]}) -> {{value,V},{[],[]}}; out({[Y|In],[]}) -> [V|Out] = lists:reverse(In, []), {{value,V},{[Y],Out}}; out({In,[V]}) when is_list(In) -> {{value,V},r2f(In)}; out({In,[V|Out]}) when is_list(In) -> {{value,V},{In,Out}}; out(Q) -> erlang:error(badarg, [Q]). %% Take from tail/rear %% %% O(1) amortized, O(len(Q)) worst case -spec out_r(Q1 :: queue()) -> {{value, Item :: term()}, Q2 :: queue()} | {empty, Q1 :: queue()}. out_r({[],[]}=Q) -> {empty,Q}; out_r({[],[V]}) -> {{value,V},{[],[]}}; out_r({[],[Y|Out]}) -> [V|In] = lists:reverse(Out, []), {{value,V},{In,[Y]}}; out_r({[V],Out}) when is_list(Out) -> {{value,V},f2r(Out)}; out_r({[V|In],Out}) when is_list(Out) -> {{value,V},{In,Out}}; out_r(Q) -> erlang:error(badarg, [Q]). %%-------------------------------------------------------------------------- %% Less garbage style API. %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed -spec get(Q :: queue()) -> Item :: term(). get({[],[]}=Q) -> erlang:error(empty, [Q]); get({R,F}) when is_list(R), is_list(F) -> get(R, F); get(Q) -> erlang:error(badarg, [Q]). -spec get(list(), list()) -> term(). get(R, [H|_]) when is_list(R) -> H; get([H], []) -> H; get([_|R], []) -> % malformed queue -> O(len(Q)) lists:last(R). %% Return the last element in the queue %% %% O(1) since the queue is supposed to be well formed -spec get_r(Q :: queue()) -> Item :: term(). get_r({[],[]}=Q) -> erlang:error(empty, [Q]); get_r({[H|_],F}) when is_list(F) -> H; get_r({[],[H]}) -> H; get_r({[],[_|F]}) -> % malformed queue -> O(len(Q)) lists:last(F); get_r(Q) -> erlang:error(badarg, [Q]). %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed -spec peek(Q :: queue()) -> empty | {value,Item :: term()}. peek({[],[]}) -> empty; peek({R,[H|_]}) when is_list(R) -> {value,H}; peek({[H],[]}) -> {value,H}; peek({[_|R],[]}) -> % malformed queue -> O(len(Q)) {value,lists:last(R)}; peek(Q) -> erlang:error(badarg, [Q]). %% Return the last element in the queue %% %% O(1) since the queue is supposed to be well formed -spec peek_r(Q :: queue()) -> empty | {value,Item :: term()}. peek_r({[],[]}) -> empty; peek_r({[H|_],F}) when is_list(F) -> {value,H}; peek_r({[],[H]}) -> {value,H}; peek_r({[],[_|R]}) -> % malformed queue -> O(len(Q)) {value,lists:last(R)}; peek_r(Q) -> erlang:error(badarg, [Q]). %% Remove the first element and return resulting queue %% %% O(1) amortized -spec drop(Q1 :: queue()) -> Q2 :: queue(). drop({[],[]}=Q) -> erlang:error(empty, [Q]); drop({[_],[]}) -> {[],[]}; drop({[Y|R],[]}) -> [_|F] = lists:reverse(R, []), {[Y],F}; drop({R, [_]}) when is_list(R) -> r2f(R); drop({R, [_|F]}) when is_list(R) -> {R,F}; drop(Q) -> erlang:error(badarg, [Q]). %% Remove the last element and return resulting queue %% %% O(1) amortized -spec drop_r(Q1 :: queue()) -> Q2 :: queue(). drop_r({[],[]}=Q) -> erlang:error(empty, [Q]); drop_r({[],[_]}) -> {[],[]}; drop_r({[],[Y|F]}) -> [_|R] = lists:reverse(F, []), {R,[Y]}; drop_r({[_], F}) when is_list(F) -> f2r(F); drop_r({[_|R], F}) when is_list(F) -> {R,F}; drop_r(Q) -> erlang:error(badarg, [Q]). %%-------------------------------------------------------------------------- %% Higher level API %% Return reversed queue %% %% O(1) -spec reverse(Q1 :: queue()) -> Q2 :: queue(). reverse({R,F}) when is_list(R), is_list(F) -> {F,R}; reverse(Q) -> erlang:error(badarg, [Q]). %% Join two queues %% %% Q2 empty: O(1) %% else: O(len(Q1)) -spec join(Q1 :: queue(), Q2 :: queue()) -> Q3 :: queue(). join({R,F}=Q, {[],[]}) when is_list(R), is_list(F) -> Q; join({[],[]}, {R,F}=Q) when is_list(R), is_list(F) -> Q; join({R1,F1}, {R2,F2}) when is_list(R1), is_list(F1), is_list(R2), is_list(F2) -> {R2,F1++lists:reverse(R1,F2)}; join(Q1, Q2) -> erlang:error(badarg, [Q1,Q2]). %% Split a queue in two %% %% N = 0..len(Q) %% O(max(N, len(Q))) -spec split(N :: non_neg_integer(), Q1 :: queue()) -> {Q2 :: queue(),Q3 :: queue()}. split(0, {R,F}=Q) when is_list(R), is_list(F) -> {{[],[]},Q}; split(N, {R,F}=Q) when is_integer(N), N >= 1, is_list(R), is_list(F) -> Lf = erlang:length(F), if N < Lf -> % Lf >= 2 [X|F1] = F, split_f1_to_r2(N-1, R, F1, [], [X]); N > Lf -> Lr = length(R), M = Lr - (N-Lf), if M < 0 -> erlang:error(badarg, [N,Q]); M > 0 -> [X|R1] = R, split_r1_to_f2(M-1, R1, F, [X], []); true -> % M == 0 {Q,{[],[]}} end; true -> % N == Lf {f2r(F),r2f(R)} end; split(N, Q) -> erlang:error(badarg, [N,Q]). %% Move N elements from F1 to R2 split_f1_to_r2(0, R1, F1, R2, F2) -> {{R2,F2},{R1,F1}}; split_f1_to_r2(N, R1, [X|F1], R2, F2) -> split_f1_to_r2(N-1, R1, F1, [X|R2], F2). %% Move N elements from R1 to F2 split_r1_to_f2(0, R1, F1, R2, F2) -> {{R1,F1},{R2,F2}}; split_r1_to_f2(N, [X|R1], F1, R2, F2) -> split_r1_to_f2(N-1, R1, F1, R2, [X|F2]). %% filter, or rather filtermap with insert, traverses in queue order %% %% Fun(_) -> List: O(length(List) * len(Q)) %% else: O(len(Q) -spec filter(Fun, Q1 :: queue()) -> Q2 :: queue() when Fun :: fun((Item :: term()) -> boolean() | list()). filter(Fun, {R0,F0}) when is_function(Fun, 1), is_list(R0), is_list(F0) -> F = filter_f(Fun, F0), R = filter_r(Fun, R0), if R =:= [] -> f2r(F); F =:= [] -> r2f(R); true -> {R,F} end; filter(Fun, Q) -> erlang:error(badarg, [Fun,Q]). %% Call Fun in head to tail order filter_f(_, []) -> []; filter_f(Fun, [X|F]) -> case Fun(X) of true -> [X|filter_f(Fun, F)]; false -> filter_f(Fun, F); L when is_list(L) -> L++filter_f(Fun, F) end. %% Call Fun in reverse order, i.e tail to head %% and reverse list result from fun to match queue order filter_r(_, []) -> []; filter_r(Fun, [X|R0]) -> R = filter_r(Fun, R0), case Fun(X) of true -> [X|R]; false -> R; L when is_list(L) -> lists:reverse(L, R) end. %%-------------------------------------------------------------------------- %% Okasaki API inspired by an Erlang user contribution "deque.erl" %% by Claes Wikstrom <klacke@kaja.klacke.net> 1999. %% %% This implementation does not use the internal data format from Klacke's %% doubly ended queues that was "shamelessly stolen" from %% "Purely Functional Data structures" by Chris Okasaki, since the data %% format of this module must remain the same in case some application %% has saved a queue in external format or sends it to an old node. %% %% This implementation tries to do the best of the situation and should %% be almost as efficient as Okasaki's queues, except for len/1 that %% is O(n) in this implementation instead of O(1). %% %% The new representation in this module again adds length field and %% fixes this, but it is not yet default. %% %% The implementation keeps at least one element in both the forward %% and the reversed lists to ensure that i.e head/1 or last/1 will %% not have to reverse a list to find the element. %% %% To be compatible with the old version of this module, as much data as %% possible is moved to the receiving side using lists:reverse/2 when data %% is needed, except for two elements (when possible). These two elements %% are kept to prevent alternating tail/1 and init/1 operations from %% moving data back and forth between the sides. %% %% An alternative would be to balance for equal list length when one side %% is exhausted. Although this could be better for a general double %% ended queue, it would more han double the amortized cost for %% the normal case (one way queue). %% Cons to head %% -spec cons(Item :: term(), Q1 :: queue()) -> Q2 :: queue(). cons(X, Q) -> in_r(X, Q). %% Return head element %% %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed -spec head(Q :: queue()) -> Item :: term(). head({[],[]}=Q) -> erlang:error(empty, [Q]); head({R,F}) when is_list(R), is_list(F) -> get(R, F); head(Q) -> erlang:error(badarg, [Q]). %% Remove head element and return resulting queue %% -spec tail(Q1 :: queue()) -> Q2 :: queue(). tail(Q) -> drop(Q). %% Functions operating on the other end of the queue %% Cons to tail %% -spec snoc(Q1 :: queue(), Item :: term()) -> Q2 :: queue(). snoc(Q, X) -> in(X, Q). %% Return last element -spec daeh(Q :: queue()) -> Item :: term(). daeh(Q) -> get_r(Q). -spec last(Q :: queue()) -> Item :: term(). last(Q) -> get_r(Q). %% Remove last element and return resulting queue -spec liat(Q1 :: queue()) -> Q2 :: queue(). liat(Q) -> drop_r(Q). -spec lait(Q1 :: queue()) -> Q2 :: queue(). lait(Q) -> drop_r(Q). %% Oops, mis-spelled 'tail' reversed. Forget this one. -spec init(Q1 :: queue()) -> Q2 :: queue(). init(Q) -> drop_r(Q). %%-------------------------------------------------------------------------- %% Internal workers -compile({inline, [{r2f,1},{f2r,1}]}). %% Move all but two from R to F, if there are at least three r2f([]) -> {[],[]}; r2f([_]=R) -> {[],R}; r2f([X,Y]) -> {[X],[Y]}; r2f([X,Y|R]) -> {[X,Y],lists:reverse(R, [])}. %% Move all but two from F to R, if there are enough f2r([]) -> {[],[]}; f2r([_]=F) -> {F,[]}; f2r([X,Y]) -> {[Y],[X]}; f2r([X,Y|F]) -> {lists:reverse(F, []),[X,Y]}.