diff options
author | Hans Bolinder <hasse@erlang.org> | 2011-07-07 12:52:06 +0200 |
---|---|---|
committer | Hans Bolinder <hasse@erlang.org> | 2011-07-07 12:52:06 +0200 |
commit | b0b527be0caf7750908e18d2a76a662e4887e8b8 (patch) | |
tree | 8d8a87e2066bed27025b3d29ce1c9c0d87c03764 /lib | |
parent | 5eee306133a90babfd4a840e89ee14223b88a0aa (diff) | |
parent | c307a63ed1f09babc738f8cc7fc6d0adc1c29204 (diff) | |
download | otp-b0b527be0caf7750908e18d2a76a662e4887e8b8.tar.gz otp-b0b527be0caf7750908e18d2a76a662e4887e8b8.tar.bz2 otp-b0b527be0caf7750908e18d2a76a662e4887e8b8.zip |
Merge branch 'hb/stdlib/queue_contracts/OTP-9418' into dev
* hb/stdlib/queue_contracts/OTP-9418:
Modify the contracts of the queue module
Diffstat (limited to 'lib')
-rw-r--r-- | lib/stdlib/src/queue.erl | 127 |
1 files changed, 35 insertions, 92 deletions
diff --git a/lib/stdlib/src/queue.erl b/lib/stdlib/src/queue.erl index 4c6b4d710b..afe917b151 100644 --- a/lib/stdlib/src/queue.erl +++ b/lib/stdlib/src/queue.erl @@ -56,16 +56,14 @@ new() -> {[],[]}. %{RearList,FrontList} %% O(1) --spec is_queue(Term) -> boolean() when - Term :: term(). +-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) -> boolean() when - Q :: queue(). +-spec is_empty(Q :: queue()) -> boolean(). is_empty({[],[]}) -> true; is_empty({In,Out}) when is_list(In), is_list(Out) -> @@ -74,16 +72,14 @@ is_empty(Q) -> erlang:error(badarg, [Q]). %% O(len(Q)) --spec len(Q) -> non_neg_integer() when - Q :: queue(). +-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) -> list() when - Q :: queue(). +-spec to_list(Q :: queue()) -> list(). to_list({In,Out}) when is_list(In), is_list(Out) -> Out++lists:reverse(In, []); to_list(Q) -> @@ -92,8 +88,7 @@ to_list(Q) -> %% Create queue from list %% %% O(length(L)) --spec from_list(L) -> queue() when - L :: list(). +-spec from_list(L :: list()) -> queue(). from_list(L) when is_list(L) -> f2r(L); from_list(L) -> @@ -102,9 +97,7 @@ from_list(L) -> %% Return true or false depending on if element is in queue %% %% O(length(Q)) worst case --spec member(Item, Q) -> boolean() when - Item :: term(), - Q :: queue(). +-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) -> @@ -117,10 +110,7 @@ member(X, Q) -> %% Put at least one element in each list, if it is cheap %% %% O(1) --spec in(Item, Q1) -> Q2 when - Item :: term(), - Q1 :: queue(), - Q2 :: queue(). +-spec in(Item :: term(), Q1 :: queue()) -> Q2 :: queue(). in(X, {[_]=In,[]}) -> {[X], In}; in(X, {In,Out}) when is_list(In), is_list(Out) -> @@ -132,10 +122,7 @@ in(X, Q) -> %% Put at least one element in each list, if it is cheap %% %% O(1) --spec in_r(Item, Q1) -> Q2 when - Item :: term(), - Q1 :: queue(), - Q2 :: queue(). +-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) -> @@ -146,10 +133,9 @@ in_r(X, Q) -> %% Take from head/front %% %% O(1) amortized, O(len(Q)) worst case --spec out(Q1) -> Result when - Q1 :: queue(), - Q2 :: queue(), - Result :: {{value, Item :: term()}, Q2} | {empty, Q1}. +-spec out(Q1 :: queue()) -> + {{value, Item :: term()}, Q2 :: queue()} | + {empty, Q1 :: queue()}. out({[],[]}=Q) -> {empty,Q}; out({[V],[]}) -> @@ -167,10 +153,9 @@ out(Q) -> %% Take from tail/rear %% %% O(1) amortized, O(len(Q)) worst case --spec out_r(Q1) -> Result when - Q1 :: queue(), - Q2 :: queue(), - Result :: {{value, Item :: term()}, Q2} | {empty, Q1}. +-spec out_r(Q1 :: queue()) -> + {{value, Item :: term()}, Q2 :: queue()} | + {empty, Q1 :: queue()}. out_r({[],[]}=Q) -> {empty,Q}; out_r({[],[V]}) -> @@ -191,9 +176,7 @@ out_r(Q) -> %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed --spec get(Q) -> Item when - Q :: queue(), - Item :: term(). +-spec get(Q :: queue()) -> Item :: term(). get({[],[]}=Q) -> erlang:error(empty, [Q]); get({R,F}) when is_list(R), is_list(F) -> @@ -212,9 +195,7 @@ 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(Q) -> Item when - Q :: queue(), - Item :: term(). +-spec get_r(Q :: queue()) -> Item :: term(). get_r({[],[]}=Q) -> erlang:error(empty, [Q]); get_r({[H|_],F}) when is_list(F) -> @@ -229,9 +210,7 @@ get_r(Q) -> %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed --spec peek(Q) -> 'empty' | {'value',Item} when - Q :: queue(), - Item :: term(). +-spec peek(Q :: queue()) -> empty | {value,Item :: term()}. peek({[],[]}) -> empty; peek({R,[H|_]}) when is_list(R) -> @@ -246,9 +225,7 @@ peek(Q) -> %% Return the last element in the queue %% %% O(1) since the queue is supposed to be well formed --spec peek_r(Q) -> 'empty' | {'value',Item} when - Q :: queue(), - Item :: term(). +-spec peek_r(Q :: queue()) -> empty | {value,Item :: term()}. peek_r({[],[]}) -> empty; peek_r({[H|_],F}) when is_list(F) -> @@ -263,9 +240,7 @@ peek_r(Q) -> %% Remove the first element and return resulting queue %% %% O(1) amortized --spec drop(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec drop(Q1 :: queue()) -> Q2 :: queue(). drop({[],[]}=Q) -> erlang:error(empty, [Q]); drop({[_],[]}) -> @@ -283,9 +258,7 @@ drop(Q) -> %% Remove the last element and return resulting queue %% %% O(1) amortized --spec drop_r(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec drop_r(Q1 :: queue()) -> Q2 :: queue(). drop_r({[],[]}=Q) -> erlang:error(empty, [Q]); drop_r({[],[_]}) -> @@ -306,9 +279,7 @@ drop_r(Q) -> %% Return reversed queue %% %% O(1) --spec reverse(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec reverse(Q1 :: queue()) -> Q2 :: queue(). reverse({R,F}) when is_list(R), is_list(F) -> {F,R}; reverse(Q) -> @@ -318,10 +289,7 @@ reverse(Q) -> %% %% Q2 empty: O(1) %% else: O(len(Q1)) --spec join(Q1, Q2) -> Q3 when - Q1 :: queue(), - Q2 :: queue(), - Q3 :: queue(). +-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) -> @@ -335,11 +303,8 @@ join(Q1, Q2) -> %% %% N = 0..len(Q) %% O(max(N, len(Q))) --spec split(N, Q1) -> {Q2,Q3} when - N :: non_neg_integer(), - Q1 :: queue(), - Q2 :: queue(), - Q3 :: queue(). +-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) -> @@ -380,10 +345,8 @@ split_r1_to_f2(N, [X|R1], F1, R2, F2) -> %% %% Fun(_) -> List: O(length(List) * len(Q)) %% else: O(len(Q) --spec filter(Fun, Q1) -> Q2 when - Fun :: fun((Item :: term()) -> boolean() | list()), - Q1 :: queue(), - Q2 :: queue(). +-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), @@ -459,10 +422,7 @@ filter_r(Fun, [X|R0]) -> %% Cons to head %% --spec cons(Item, Q1) -> Q2 when - Item :: term(), - Q1 :: queue(), - Q2 :: queue(). +-spec cons(Item :: term(), Q1 :: queue()) -> Q2 :: queue(). cons(X, Q) -> in_r(X, Q). @@ -471,9 +431,7 @@ cons(X, Q) -> %% Return the first element in the queue %% %% O(1) since the queue is supposed to be well formed --spec head(Q) -> Item when - Q :: queue(), - Item :: term(). +-spec head(Q :: queue()) -> Item :: term(). head({[],[]}=Q) -> erlang:error(empty, [Q]); head({R,F}) when is_list(R), is_list(F) -> @@ -483,9 +441,7 @@ head(Q) -> %% Remove head element and return resulting queue %% --spec tail(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec tail(Q1 :: queue()) -> Q2 :: queue(). tail(Q) -> drop(Q). @@ -493,35 +449,22 @@ tail(Q) -> %% Cons to tail %% --spec snoc(Q1, Item) -> Q2 when - Q1 :: queue(), - Q2 :: queue(), - Item :: term(). +-spec snoc(Q1 :: queue(), Item :: term()) -> Q2 :: queue(). snoc(Q, X) -> in(X, Q). %% Return last element --spec daeh(Q) -> Item when - Q :: queue(), - Item :: term(). +-spec daeh(Q :: queue()) -> Item :: term(). daeh(Q) -> get_r(Q). --spec last(Q) -> Item when - Q :: queue(), - Item :: term(). +-spec last(Q :: queue()) -> Item :: term(). last(Q) -> get_r(Q). %% Remove last element and return resulting queue --spec liat(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec liat(Q1 :: queue()) -> Q2 :: queue(). liat(Q) -> drop_r(Q). --spec lait(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec lait(Q1 :: queue()) -> Q2 :: queue(). lait(Q) -> drop_r(Q). %% Oops, mis-spelled 'tail' reversed. Forget this one. --spec init(Q1) -> Q2 when - Q1 :: queue(), - Q2 :: queue(). +-spec init(Q1 :: queue()) -> Q2 :: queue(). init(Q) -> drop_r(Q). %%-------------------------------------------------------------------------- |