aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/orddict.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib/src/orddict.erl')
-rw-r--r--lib/stdlib/src/orddict.erl151
1 files changed, 71 insertions, 80 deletions
diff --git a/lib/stdlib/src/orddict.erl b/lib/stdlib/src/orddict.erl
index c98d78b34d..37cf0084f0 100644
--- a/lib/stdlib/src/orddict.erl
+++ b/lib/stdlib/src/orddict.erl
@@ -1,18 +1,19 @@
%%
%% %CopyrightBegin%
%%
-%% Copyright Ericsson AB 1996-2011. All Rights Reserved.
+%% Copyright Ericsson AB 1996-2015. 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.
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%% http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
%%
%% %CopyrightEnd%
%%
@@ -25,11 +26,13 @@
-export([store/3,append/3,append_list/3,update/3,update/4,update_counter/3]).
-export([fold/3,map/2,filter/2,merge/3]).
--export_type([orddict/0]).
+-export_type([orddict/0, orddict/2]).
%%---------------------------------------------------------------------------
--type orddict() :: [{Key :: term(), Value :: term()}].
+-type orddict() :: orddict(_, _).
+
+-type orddict(Key, Value) :: [{Key, Value}].
%%---------------------------------------------------------------------------
@@ -38,8 +41,7 @@
new() -> [].
-spec is_key(Key, Orddict) -> boolean() when
- Key :: term(),
- Orddict :: orddict().
+ Orddict :: orddict(Key, Value :: term()).
is_key(Key, [{K,_}|_]) when Key < K -> false;
is_key(Key, [{K,_}|Dict]) when Key > K -> is_key(Key, Dict);
@@ -47,14 +49,14 @@ is_key(_Key, [{_K,_Val}|_]) -> true; %Key == K
is_key(_, []) -> false.
-spec to_list(Orddict) -> List when
- Orddict :: orddict(),
- List :: [{Key :: term(), Value :: term()}].
+ Orddict :: orddict(Key, Value),
+ List :: [{Key, Value}].
to_list(Dict) -> Dict.
-spec from_list(List) -> Orddict when
- List :: [{Key :: term(), Value :: term()}],
- Orddict :: orddict().
+ List :: [{Key, Value}],
+ Orddict :: orddict(Key, Value).
from_list([]) -> [];
from_list([{_,_}]=Pair) -> Pair;
@@ -73,17 +75,13 @@ is_empty([]) -> true;
is_empty([_|_]) -> false.
-spec fetch(Key, Orddict) -> Value when
- Key :: term(),
- Value :: term(),
- Orddict :: orddict().
+ Orddict :: orddict(Key, Value).
fetch(Key, [{K,_}|D]) when Key > K -> fetch(Key, D);
fetch(Key, [{K,Value}|_]) when Key == K -> Value.
-spec find(Key, Orddict) -> {'ok', Value} | 'error' when
- Key :: term(),
- Orddict :: orddict(),
- Value :: term().
+ Orddict :: orddict(Key, Value).
find(Key, [{K,_}|_]) when Key < K -> error;
find(Key, [{K,_}|D]) when Key > K -> find(Key, D);
@@ -91,17 +89,16 @@ find(_Key, [{_K,Value}|_]) -> {ok,Value}; %Key == K
find(_, []) -> error.
-spec fetch_keys(Orddict) -> Keys when
- Orddict :: orddict(),
- Keys :: [term()].
+ Orddict :: orddict(Key, Value :: term()),
+ Keys :: [Key].
fetch_keys([{Key,_}|Dict]) ->
[Key|fetch_keys(Dict)];
fetch_keys([]) -> [].
-spec erase(Key, Orddict1) -> Orddict2 when
- Key :: term(),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
erase(Key, [{K,_}=E|Dict]) when Key < K -> [E|Dict];
erase(Key, [{K,_}=E|Dict]) when Key > K ->
@@ -110,13 +107,11 @@ erase(_Key, [{_K,_Val}|Dict]) -> Dict; %Key == K
erase(_, []) -> [].
-spec store(Key, Value, Orddict1) -> Orddict2 when
- Key :: term(),
- Value :: term(),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
-store(Key, New, [{K,_}=E|Dict]) when Key < K ->
- [{Key,New},E|Dict];
+store(Key, New, [{K,_}|_]=Dict) when Key < K ->
+ [{Key,New}|Dict];
store(Key, New, [{K,_}=E|Dict]) when Key > K ->
[E|store(Key, New, Dict)];
store(Key, New, [{_K,_Old}|Dict]) -> %Key == K
@@ -124,13 +119,11 @@ store(Key, New, [{_K,_Old}|Dict]) -> %Key == K
store(Key, New, []) -> [{Key,New}].
-spec append(Key, Value, Orddict1) -> Orddict2 when
- Key :: term(),
- Value :: term(),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
-append(Key, New, [{K,_}=E|Dict]) when Key < K ->
- [{Key,[New]},E|Dict];
+append(Key, New, [{K,_}|_]=Dict) when Key < K ->
+ [{Key,[New]}|Dict];
append(Key, New, [{K,_}=E|Dict]) when Key > K ->
[E|append(Key, New, Dict)];
append(Key, New, [{_K,Old}|Dict]) -> %Key == K
@@ -138,13 +131,12 @@ append(Key, New, [{_K,Old}|Dict]) -> %Key == K
append(Key, New, []) -> [{Key,[New]}].
-spec append_list(Key, ValList, Orddict1) -> Orddict2 when
- Key :: term(),
- ValList :: [Value :: term()],
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ ValList :: [Value],
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
-append_list(Key, NewList, [{K,_}=E|Dict]) when Key < K ->
- [{Key,NewList},E|Dict];
+append_list(Key, NewList, [{K,_}|_]=Dict) when Key < K ->
+ [{Key,NewList}|Dict];
append_list(Key, NewList, [{K,_}=E|Dict]) when Key > K ->
[E|append_list(Key, NewList, Dict)];
append_list(Key, NewList, [{_K,Old}|Dict]) -> %Key == K
@@ -153,10 +145,9 @@ append_list(Key, NewList, []) ->
[{Key,NewList}].
-spec update(Key, Fun, Orddict1) -> Orddict2 when
- Key :: term(),
- Fun :: fun((Value1 :: term()) -> Value2 :: term()),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Fun :: fun((Value1 :: Value) -> Value2 :: Value),
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
update(Key, Fun, [{K,_}=E|Dict]) when Key > K ->
[E|update(Key, Fun, Dict)];
@@ -164,14 +155,13 @@ update(Key, Fun, [{K,Val}|Dict]) when Key == K ->
[{Key,Fun(Val)}|Dict].
-spec update(Key, Fun, Initial, Orddict1) -> Orddict2 when
- Key :: term(),
- Initial :: term(),
- Fun :: fun((Value1 :: term()) -> Value2 :: term()),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
-
-update(Key, _, Init, [{K,_}=E|Dict]) when Key < K ->
- [{Key,Init},E|Dict];
+ Initial :: Value,
+ Fun :: fun((Value1 :: Value) -> Value2 :: Value),
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
+
+update(Key, _, Init, [{K,_}|_]=Dict) when Key < K ->
+ [{Key,Init}|Dict];
update(Key, Fun, Init, [{K,_}=E|Dict]) when Key > K ->
[E|update(Key, Fun, Init, Dict)];
update(Key, Fun, _Init, [{_K,Val}|Dict]) -> %Key == K
@@ -179,13 +169,12 @@ update(Key, Fun, _Init, [{_K,Val}|Dict]) -> %Key == K
update(Key, _, Init, []) -> [{Key,Init}].
-spec update_counter(Key, Increment, Orddict1) -> Orddict2 when
- Key :: term(),
- Increment :: number(),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value),
+ Increment :: number().
-update_counter(Key, Incr, [{K,_}=E|Dict]) when Key < K ->
- [{Key,Incr},E|Dict];
+update_counter(Key, Incr, [{K,_}|_]=Dict) when Key < K ->
+ [{Key,Incr}|Dict];
update_counter(Key, Incr, [{K,_}=E|Dict]) when Key > K ->
[E|update_counter(Key, Incr, Dict)];
update_counter(Key, Incr, [{_K,Val}|Dict]) -> %Key == K
@@ -193,28 +182,30 @@ update_counter(Key, Incr, [{_K,Val}|Dict]) -> %Key == K
update_counter(Key, Incr, []) -> [{Key,Incr}].
-spec fold(Fun, Acc0, Orddict) -> Acc1 when
- Fun :: fun((Key :: term(), Value :: term(), AccIn :: term()) -> AccOut :: term()),
- Acc0 :: term(),
- Acc1 :: term(),
- Orddict :: orddict().
+ Fun :: fun((Key, Value, AccIn) -> AccOut),
+ Orddict :: orddict(Key, Value),
+ Acc0 :: Acc,
+ Acc1 :: Acc,
+ AccIn :: Acc,
+ AccOut :: Acc.
fold(F, Acc, [{Key,Val}|D]) ->
fold(F, F(Key, Val, Acc), D);
fold(F, Acc, []) when is_function(F, 3) -> Acc.
-spec map(Fun, Orddict1) -> Orddict2 when
- Fun :: fun((Key :: term(), Value1 :: term()) -> Value2 :: term()),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Fun :: fun((Key, Value1) -> Value2),
+ Orddict1 :: orddict(Key, Value1),
+ Orddict2 :: orddict(Key, Value2).
map(F, [{Key,Val}|D]) ->
[{Key,F(Key, Val)}|map(F, D)];
map(F, []) when is_function(F, 2) -> [].
-spec filter(Pred, Orddict1) -> Orddict2 when
- Pred :: fun((Key :: term(), Value :: term()) -> boolean()),
- Orddict1 :: orddict(),
- Orddict2 :: orddict().
+ Pred :: fun((Key, Value) -> boolean()),
+ Orddict1 :: orddict(Key, Value),
+ Orddict2 :: orddict(Key, Value).
filter(F, [{Key,Val}=E|D]) ->
case F(Key, Val) of
@@ -224,10 +215,10 @@ filter(F, [{Key,Val}=E|D]) ->
filter(F, []) when is_function(F, 2) -> [].
-spec merge(Fun, Orddict1, Orddict2) -> Orddict3 when
- Fun :: fun((Key :: term(), Value1 :: term(), Value2 :: term()) -> Value :: term()),
- Orddict1 :: orddict(),
- Orddict2 :: orddict(),
- Orddict3 :: orddict().
+ Fun :: fun((Key, Value1, Value2) -> Value),
+ Orddict1 :: orddict(Key, Value1),
+ Orddict2 :: orddict(Key, Value2),
+ Orddict3 :: orddict(Key, Value).
merge(F, [{K1,_}=E1|D1], [{K2,_}=E2|D2]) when K1 < K2 ->
[E1|merge(F, D1, [E2|D2])];