aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/orddict.erl
diff options
context:
space:
mode:
authorErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
committerErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
commit84adefa331c4159d432d22840663c38f155cd4c1 (patch)
treebff9a9c66adda4df2106dfd0e5c053ab182a12bd /lib/stdlib/src/orddict.erl
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'lib/stdlib/src/orddict.erl')
-rw-r--r--lib/stdlib/src/orddict.erl173
1 files changed, 173 insertions, 0 deletions
diff --git a/lib/stdlib/src/orddict.erl b/lib/stdlib/src/orddict.erl
new file mode 100644
index 0000000000..c7b52b933e
--- /dev/null
+++ b/lib/stdlib/src/orddict.erl
@@ -0,0 +1,173 @@
+%%
+%% %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(orddict).
+
+%% Standard interface.
+-export([new/0,is_key/2,to_list/1,from_list/1,size/1]).
+-export([fetch/2,find/2,fetch_keys/1,erase/2]).
+-export([store/3,append/3,append_list/3,update/3,update/4,update_counter/3]).
+-export([fold/3,map/2,filter/2,merge/3]).
+
+%%---------------------------------------------------------------------------
+
+-type orddict() :: [{term(), term()}].
+
+%%---------------------------------------------------------------------------
+
+-spec new() -> orddict().
+
+new() -> [].
+
+-spec is_key(Key::term(), Dictionary::orddict()) -> boolean().
+
+is_key(Key, [{K,_}|_]) when Key < K -> false;
+is_key(Key, [{K,_}|Dict]) when Key > K -> is_key(Key, Dict);
+is_key(_Key, [{_K,_Val}|_]) -> true; %Key == K
+is_key(_, []) -> false.
+
+-spec to_list(orddict()) -> [{term(), term()}].
+
+to_list(Dict) -> Dict.
+
+-spec from_list([{term(), term()}]) -> orddict().
+
+from_list(Pairs) ->
+ lists:foldl(fun ({K,V}, D) -> store(K, V, D) end, [], Pairs).
+
+-spec size(orddict()) -> non_neg_integer().
+
+size(D) -> length(D).
+
+-spec fetch(Key::term(), Dictionary::orddict()) -> term().
+
+fetch(Key, [{K,_}|D]) when Key > K -> fetch(Key, D);
+fetch(Key, [{K,Value}|_]) when Key == K -> Value.
+
+-spec find(Key::term(), Dictionary::orddict()) -> {'ok', term()} | 'error'.
+
+find(Key, [{K,_}|_]) when Key < K -> error;
+find(Key, [{K,_}|D]) when Key > K -> find(Key, D);
+find(_Key, [{_K,Value}|_]) -> {ok,Value}; %Key == K
+find(_, []) -> error.
+
+-spec fetch_keys(Dictionary::orddict()) -> [term()].
+
+fetch_keys([{Key,_}|Dict]) ->
+ [Key|fetch_keys(Dict)];
+fetch_keys([]) -> [].
+
+-spec erase(Key::term(), Dictionary::orddict()) -> orddict().
+
+erase(Key, [{K,_}=E|Dict]) when Key < K -> [E|Dict];
+erase(Key, [{K,_}=E|Dict]) when Key > K ->
+ [E|erase(Key, Dict)];
+erase(_Key, [{_K,_Val}|Dict]) -> Dict; %Key == K
+erase(_, []) -> [].
+
+-spec store(Key::term(), Value::term(), Dictionary::orddict()) -> orddict().
+
+store(Key, New, [{K,_}=E|Dict]) when Key < K ->
+ [{Key,New},E|Dict];
+store(Key, New, [{K,_}=E|Dict]) when Key > K ->
+ [E|store(Key, New, Dict)];
+store(Key, New, [{_K,_Old}|Dict]) -> %Key == K
+ [{Key,New}|Dict];
+store(Key, New, []) -> [{Key,New}].
+
+-spec append(Key::term(), Value::term(), Dictionary::orddict()) -> orddict().
+
+append(Key, New, [{K,_}=E|Dict]) when Key < K ->
+ [{Key,[New]},E|Dict];
+append(Key, New, [{K,_}=E|Dict]) when Key > K ->
+ [E|append(Key, New, Dict)];
+append(Key, New, [{_K,Old}|Dict]) -> %Key == K
+ [{Key,Old ++ [New]}|Dict];
+append(Key, New, []) -> [{Key,[New]}].
+
+-spec append_list(Key::term(), ValueList::[term()], orddict()) -> orddict().
+
+append_list(Key, NewList, [{K,_}=E|Dict]) when Key < K ->
+ [{Key,NewList},E|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
+ [{Key,Old ++ NewList}|Dict];
+append_list(Key, NewList, []) ->
+ [{Key,NewList}].
+
+-spec update(Key::term(), Fun::fun((term()) -> term()), orddict()) -> orddict().
+
+update(Key, Fun, [{K,_}=E|Dict]) when Key > K ->
+ [E|update(Key, Fun, Dict)];
+update(Key, Fun, [{K,Val}|Dict]) when Key == K ->
+ [{Key,Fun(Val)}|Dict].
+
+-spec update(term(), fun((term()) -> term()), term(), orddict()) -> orddict().
+
+update(Key, _, Init, [{K,_}=E|Dict]) when Key < K ->
+ [{Key,Init},E|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
+ [{Key,Fun(Val)}|Dict];
+update(Key, _, Init, []) -> [{Key,Init}].
+
+-spec update_counter(Key::term(), Incr::number(), orddict()) -> orddict().
+
+update_counter(Key, Incr, [{K,_}=E|Dict]) when Key < K ->
+ [{Key,Incr},E|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
+ [{Key,Val+Incr}|Dict];
+update_counter(Key, Incr, []) -> [{Key,Incr}].
+
+-spec fold(fun((term(),term(),term()) -> term()), term(), orddict()) -> term().
+
+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((term(), term()) -> term()), orddict()) -> orddict().
+
+map(F, [{Key,Val}|D]) ->
+ [{Key,F(Key, Val)}|map(F, D)];
+map(F, []) when is_function(F, 2) -> [].
+
+-spec filter(fun((term(), term()) -> term()), orddict()) -> orddict().
+
+filter(F, [{Key,Val}=E|D]) ->
+ case F(Key, Val) of
+ true -> [E|filter(F, D)];
+ false -> filter(F, D)
+ end;
+filter(F, []) when is_function(F, 2) -> [].
+
+-spec merge(fun((term(), term(), term()) -> term()), orddict(), orddict()) ->
+ orddict().
+
+merge(F, [{K1,_}=E1|D1], [{K2,_}=E2|D2]) when K1 < K2 ->
+ [E1|merge(F, D1, [E2|D2])];
+merge(F, [{K1,_}=E1|D1], [{K2,_}=E2|D2]) when K1 > K2 ->
+ [E2|merge(F, [E1|D1], D2)];
+merge(F, [{K1,V1}|D1], [{_K2,V2}|D2]) -> %K1 == K2
+ [{K1,F(K1, V1, V2)}|merge(F, D1, D2)];
+merge(F, [], D2) when is_function(F, 3) -> D2;
+merge(F, D1, []) when is_function(F, 3) -> D1.