diff options
Diffstat (limited to 'lib/stdlib/src/queue.erl')
| -rw-r--r-- | lib/stdlib/src/queue.erl | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/lib/stdlib/src/queue.erl b/lib/stdlib/src/queue.erl new file mode 100644 index 0000000000..c09079e8d2 --- /dev/null +++ b/lib/stdlib/src/queue.erl @@ -0,0 +1,487 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 1996-2009. 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()) -> boolean(). +is_queue({R,F}) when is_list(R), is_list(F) -> + true; +is_queue(_) -> + false. + +%% O(1) +-spec is_empty(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(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(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(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(term(), 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(term(), queue()) -> 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(term(), queue()) -> 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(queue()) -> {'empty' | {'value',term()}, 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(queue()) -> {'empty' | {'value',term()}, 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(queue()) -> 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(queue()) -> 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(queue()) -> 'empty' | {'value',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(queue()) -> 'empty' | {'value',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(queue()) -> 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(queue()) -> 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(queue()) -> 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(queue(), queue()) -> 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(non_neg_integer(), queue()) -> {queue(),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((term()) -> boolean() | list()), queue()) -> queue(). +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 <[email protected]> 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(term(), queue()) -> 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(queue()) -> 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(queue()) -> queue(). +tail(Q) -> + drop(Q). + +%% Functions operating on the other end of the queue + +%% Cons to tail +%% +-spec snoc(queue(), term()) -> queue(). +snoc(Q, X) -> + in(X, Q). + +%% Return last element +-spec daeh(queue()) -> term(). +daeh(Q) -> get_r(Q). +-spec last(queue()) -> term(). +last(Q) -> get_r(Q). + +%% Remove last element and return resulting queue +-spec liat(queue()) -> queue(). +liat(Q) -> drop_r(Q). +-spec lait(queue()) -> queue(). +lait(Q) -> drop_r(Q). %% Oops, mis-spelled 'tail' reversed. Forget this one. +-spec init(queue()) -> 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]}. |