diff options
author | Lukas Larsson <[email protected]> | 2011-05-18 16:21:34 +0200 |
---|---|---|
committer | Lukas Larsson <[email protected]> | 2011-05-18 16:21:34 +0200 |
commit | 15426ac367eed736c165a5bdbb1c051a87944f68 (patch) | |
tree | fcabce7847168a8416600fe35f94a411a5f73d6e /lib/stdlib/src/queue.erl | |
parent | 4cd0717b717803ce8f03a12de4bf89f452ed1df7 (diff) | |
parent | f44bbb331fb517e989d4d906b7f63ec110bbbc18 (diff) | |
download | otp-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.erl | 123 |
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). %%-------------------------------------------------------------------------- |