The R13B03 release.OTP_R13B03

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]}.