aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/queue.erl
diff options
context:
space:
mode:
authorLukas Larsson <[email protected]>2011-05-18 16:21:34 +0200
committerLukas Larsson <[email protected]>2011-05-18 16:21:34 +0200
commit15426ac367eed736c165a5bdbb1c051a87944f68 (patch)
treefcabce7847168a8416600fe35f94a411a5f73d6e /lib/stdlib/src/queue.erl
parent4cd0717b717803ce8f03a12de4bf89f452ed1df7 (diff)
parentf44bbb331fb517e989d4d906b7f63ec110bbbc18 (diff)
downloadotp-15426ac367eed736c165a5bdbb1c051a87944f68.tar.gz
otp-15426ac367eed736c165a5bdbb1c051a87944f68.tar.bz2
otp-15426ac367eed736c165a5bdbb1c051a87944f68.zip
Merge branch 'dev' of super:otp into dev
* 'dev' of super:otp: (166 commits) Corrected documentation error and added examples to Users Guide In TLS 1.1, failure to properly close a connection no longer requires that a session not be resumed. This is a change from TLS 1.0 to conform with widespread implementation practice. Erlang ssl will now in TLS 1.0 conform to the widespread implementation practice instead of the specification to avoid performance issues. Add escript to bootstrap/bin Remove unused variable warning in inet_res Remove unused variable in epmd_port Remove compiler warnings in inet_drv Add SASL test suite Allow same module name in multiple applications if explicitely excluded Fix bugs concerning the option report_missing_types Fix default encoding in SAX parser. re: remove gratuitous "it " in manpage Spelling in (backward *compatibility*) comment. Improve erl_docgen's support for Dialyzer specs and types dialyzer warning on mnesia_tm Add documentation text about majority checking add mnesia_majority_test suite where_to_wlock optimization + change_table_majority/2 bug in mnesia_tm:needs_majority/2 optimize sticky_lock maj. check check majority for sticky locks ...
Diffstat (limited to 'lib/stdlib/src/queue.erl')
-rw-r--r--lib/stdlib/src/queue.erl123
1 files changed, 93 insertions, 30 deletions
diff --git a/lib/stdlib/src/queue.erl b/lib/stdlib/src/queue.erl
index c09079e8d2..4c6b4d710b 100644
--- a/lib/stdlib/src/queue.erl
+++ b/lib/stdlib/src/queue.erl
@@ -1,7 +1,7 @@
%%
%% %CopyrightBegin%
%%
-%% Copyright Ericsson AB 1996-2009. All Rights Reserved.
+%% 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
@@ -56,14 +56,16 @@
new() -> {[],[]}. %{RearList,FrontList}
%% O(1)
--spec is_queue(term()) -> boolean().
+-spec is_queue(Term) -> boolean() when
+ Term :: term().
is_queue({R,F}) when is_list(R), is_list(F) ->
true;
is_queue(_) ->
false.
%% O(1)
--spec is_empty(queue()) -> boolean().
+-spec is_empty(Q) -> boolean() when
+ Q :: queue().
is_empty({[],[]}) ->
true;
is_empty({In,Out}) when is_list(In), is_list(Out) ->
@@ -72,14 +74,16 @@ is_empty(Q) ->
erlang:error(badarg, [Q]).
%% O(len(Q))
--spec len(queue()) -> non_neg_integer().
+-spec len(Q) -> non_neg_integer() when
+ Q :: queue().
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().
+-spec to_list(Q) -> list() when
+ Q :: queue().
to_list({In,Out}) when is_list(In), is_list(Out) ->
Out++lists:reverse(In, []);
to_list(Q) ->
@@ -88,7 +92,8 @@ to_list(Q) ->
%% Create queue from list
%%
%% O(length(L))
--spec from_list(list()) -> queue().
+-spec from_list(L) -> queue() when
+ L :: list().
from_list(L) when is_list(L) ->
f2r(L);
from_list(L) ->
@@ -97,7 +102,9 @@ from_list(L) ->
%% Return true or false depending on if element is in queue
%%
%% O(length(Q)) worst case
--spec member(term(), queue()) -> boolean().
+-spec member(Item, Q) -> boolean() when
+ Item :: term(),
+ Q :: queue().
member(X, {R,F}) when is_list(R), is_list(F) ->
lists:member(X, R) orelse lists:member(X, F);
member(X, Q) ->
@@ -110,7 +117,10 @@ member(X, Q) ->
%% Put at least one element in each list, if it is cheap
%%
%% O(1)
--spec in(term(), queue()) -> queue().
+-spec in(Item, Q1) -> Q2 when
+ Item :: term(),
+ Q1 :: queue(),
+ Q2 :: queue().
in(X, {[_]=In,[]}) ->
{[X], In};
in(X, {In,Out}) when is_list(In), is_list(Out) ->
@@ -122,7 +132,10 @@ in(X, Q) ->
%% Put at least one element in each list, if it is cheap
%%
%% O(1)
--spec in_r(term(), queue()) -> queue().
+-spec in_r(Item, Q1) -> Q2 when
+ Item :: term(),
+ Q1 :: queue(),
+ Q2 :: queue().
in_r(X, {[],[_]=F}) ->
{F,[X]};
in_r(X, {R,F}) when is_list(R), is_list(F) ->
@@ -133,7 +146,10 @@ in_r(X, Q) ->
%% Take from head/front
%%
%% O(1) amortized, O(len(Q)) worst case
--spec out(queue()) -> {'empty' | {'value',term()}, queue()}.
+-spec out(Q1) -> Result when
+ Q1 :: queue(),
+ Q2 :: queue(),
+ Result :: {{value, Item :: term()}, Q2} | {empty, Q1}.
out({[],[]}=Q) ->
{empty,Q};
out({[V],[]}) ->
@@ -151,7 +167,10 @@ out(Q) ->
%% Take from tail/rear
%%
%% O(1) amortized, O(len(Q)) worst case
--spec out_r(queue()) -> {'empty' | {'value',term()}, queue()}.
+-spec out_r(Q1) -> Result when
+ Q1 :: queue(),
+ Q2 :: queue(),
+ Result :: {{value, Item :: term()}, Q2} | {empty, Q1}.
out_r({[],[]}=Q) ->
{empty,Q};
out_r({[],[V]}) ->
@@ -172,7 +191,9 @@ out_r(Q) ->
%% Return the first element in the queue
%%
%% O(1) since the queue is supposed to be well formed
--spec get(queue()) -> term().
+-spec get(Q) -> Item when
+ Q :: queue(),
+ Item :: term().
get({[],[]}=Q) ->
erlang:error(empty, [Q]);
get({R,F}) when is_list(R), is_list(F) ->
@@ -191,7 +212,9 @@ get([_|R], []) -> % malformed queue -> O(len(Q))
%% Return the last element in the queue
%%
%% O(1) since the queue is supposed to be well formed
--spec get_r(queue()) -> term().
+-spec get_r(Q) -> Item when
+ Q :: queue(),
+ Item :: term().
get_r({[],[]}=Q) ->
erlang:error(empty, [Q]);
get_r({[H|_],F}) when is_list(F) ->
@@ -206,7 +229,9 @@ get_r(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()}.
+-spec peek(Q) -> 'empty' | {'value',Item} when
+ Q :: queue(),
+ Item :: term().
peek({[],[]}) ->
empty;
peek({R,[H|_]}) when is_list(R) ->
@@ -221,7 +246,9 @@ peek(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()}.
+-spec peek_r(Q) -> 'empty' | {'value',Item} when
+ Q :: queue(),
+ Item :: term().
peek_r({[],[]}) ->
empty;
peek_r({[H|_],F}) when is_list(F) ->
@@ -236,7 +263,9 @@ peek_r(Q) ->
%% Remove the first element and return resulting queue
%%
%% O(1) amortized
--spec drop(queue()) -> queue().
+-spec drop(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
drop({[],[]}=Q) ->
erlang:error(empty, [Q]);
drop({[_],[]}) ->
@@ -254,7 +283,9 @@ drop(Q) ->
%% Remove the last element and return resulting queue
%%
%% O(1) amortized
--spec drop_r(queue()) -> queue().
+-spec drop_r(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
drop_r({[],[]}=Q) ->
erlang:error(empty, [Q]);
drop_r({[],[_]}) ->
@@ -275,7 +306,9 @@ drop_r(Q) ->
%% Return reversed queue
%%
%% O(1)
--spec reverse(queue()) -> queue().
+-spec reverse(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
reverse({R,F}) when is_list(R), is_list(F) ->
{F,R};
reverse(Q) ->
@@ -285,7 +318,10 @@ reverse(Q) ->
%%
%% Q2 empty: O(1)
%% else: O(len(Q1))
--spec join(queue(), queue()) -> queue().
+-spec join(Q1, Q2) -> Q3 when
+ 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) ->
@@ -299,7 +335,11 @@ join(Q1, Q2) ->
%%
%% N = 0..len(Q)
%% O(max(N, len(Q)))
--spec split(non_neg_integer(), queue()) -> {queue(),queue()}.
+-spec split(N, Q1) -> {Q2,Q3} when
+ 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) ->
@@ -340,7 +380,10 @@ split_r1_to_f2(N, [X|R1], F1, R2, F2) ->
%%
%% Fun(_) -> List: O(length(List) * len(Q))
%% else: O(len(Q)
--spec filter(fun((term()) -> boolean() | list()), queue()) -> queue().
+-spec filter(Fun, Q1) -> Q2 when
+ Fun :: fun((Item :: term()) -> boolean() | list()),
+ Q1 :: queue(),
+ Q2 :: 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),
@@ -416,7 +459,10 @@ filter_r(Fun, [X|R0]) ->
%% Cons to head
%%
--spec cons(term(), queue()) -> queue().
+-spec cons(Item, Q1) -> Q2 when
+ Item :: term(),
+ Q1 :: queue(),
+ Q2 :: queue().
cons(X, Q) ->
in_r(X, Q).
@@ -425,7 +471,9 @@ cons(X, Q) ->
%% Return the first element in the queue
%%
%% O(1) since the queue is supposed to be well formed
--spec head(queue()) -> term().
+-spec head(Q) -> Item when
+ Q :: queue(),
+ Item :: term().
head({[],[]}=Q) ->
erlang:error(empty, [Q]);
head({R,F}) when is_list(R), is_list(F) ->
@@ -435,7 +483,9 @@ head(Q) ->
%% Remove head element and return resulting queue
%%
--spec tail(queue()) -> queue().
+-spec tail(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
tail(Q) ->
drop(Q).
@@ -443,22 +493,35 @@ tail(Q) ->
%% Cons to tail
%%
--spec snoc(queue(), term()) -> queue().
+-spec snoc(Q1, Item) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue(),
+ Item :: term().
snoc(Q, X) ->
in(X, Q).
%% Return last element
--spec daeh(queue()) -> term().
+-spec daeh(Q) -> Item when
+ Q :: queue(),
+ Item :: term().
daeh(Q) -> get_r(Q).
--spec last(queue()) -> term().
+-spec last(Q) -> Item when
+ Q :: queue(),
+ Item :: term().
last(Q) -> get_r(Q).
%% Remove last element and return resulting queue
--spec liat(queue()) -> queue().
+-spec liat(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
liat(Q) -> drop_r(Q).
--spec lait(queue()) -> queue().
+-spec lait(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
lait(Q) -> drop_r(Q). %% Oops, mis-spelled 'tail' reversed. Forget this one.
--spec init(queue()) -> queue().
+-spec init(Q1) -> Q2 when
+ Q1 :: queue(),
+ Q2 :: queue().
init(Q) -> drop_r(Q).
%%--------------------------------------------------------------------------