aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMagnus Henoch <[email protected]>2013-09-04 14:08:34 +0100
committerMagnus Henoch <[email protected]>2013-09-13 10:44:23 +0100
commit0e4b0ae7ce57117a561f70fa51026d85b4702aaa (patch)
tree4a0aba55aaeef71d6f2abed3b8aec50cd0018c6a
parent5b56a49d15d10ad4a35dbc8b2a4b01486f1d5294 (diff)
downloadotp-0e4b0ae7ce57117a561f70fa51026d85b4702aaa.tar.gz
otp-0e4b0ae7ce57117a561f70fa51026d85b4702aaa.tar.bz2
otp-0e4b0ae7ce57117a561f70fa51026d85b4702aaa.zip
Add dict:is_empty/1 and orddict:is_empty/1
dict:size/1 runs in constant time, but orddict:size/1 does not. With this change, the two modules stay API compatible and gain a constant-time function for checking whether a dictionary is empty.
-rw-r--r--lib/stdlib/doc/src/dict.xml7
-rw-r--r--lib/stdlib/doc/src/orddict.xml7
-rw-r--r--lib/stdlib/src/dict.erl7
-rw-r--r--lib/stdlib/src/orddict.erl8
-rw-r--r--lib/stdlib/test/dict_SUITE.erl11
-rw-r--r--lib/stdlib/test/dict_test_lib.erl1
6 files changed, 38 insertions, 3 deletions
diff --git a/lib/stdlib/doc/src/dict.xml b/lib/stdlib/doc/src/dict.xml
index b8cf61af80..6ff81b56ee 100644
--- a/lib/stdlib/doc/src/dict.xml
+++ b/lib/stdlib/doc/src/dict.xml
@@ -177,6 +177,13 @@ merge(Fun, D1, D2) ->
</desc>
</func>
<func>
+ <name name="is_empty" arity="1"/>
+ <fsummary>Return true if the dictionary is empty</fsummary>
+ <desc>
+ <p>Returns <c>true</c> if <c><anno>Dict</anno></c> has no elements, <c>false</c> otherwise.</p>
+ </desc>
+ </func>
+ <func>
<name name="store" arity="3"/>
<fsummary>Store a value in a dictionary</fsummary>
<desc>
diff --git a/lib/stdlib/doc/src/orddict.xml b/lib/stdlib/doc/src/orddict.xml
index b6aee7a7d6..6d1702bc59 100644
--- a/lib/stdlib/doc/src/orddict.xml
+++ b/lib/stdlib/doc/src/orddict.xml
@@ -187,6 +187,13 @@ merge(Fun, D1, D2) ->
</desc>
</func>
<func>
+ <name name="is_empty" arity="1"/>
+ <fsummary>Return true if the dictionary is empty</fsummary>
+ <desc>
+ <p>Returns <c>true</c> if <c><anno>Orddict</anno></c> has no elements, <c>false</c> otherwise.</p>
+ </desc>
+ </func>
+ <func>
<name name="store" arity="3"/>
<fsummary>Store a value in a dictionary</fsummary>
<desc>
diff --git a/lib/stdlib/src/dict.erl b/lib/stdlib/src/dict.erl
index e3bfb6c2e2..e67433ffb7 100644
--- a/lib/stdlib/src/dict.erl
+++ b/lib/stdlib/src/dict.erl
@@ -36,7 +36,7 @@
-module(dict).
%% Standard interface.
--export([new/0,is_key/2,to_list/1,from_list/1,size/1]).
+-export([new/0,is_key/2,to_list/1,from_list/1,size/1,is_empty/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]).
@@ -112,6 +112,11 @@ from_list(L) ->
size(#dict{size=N}) when is_integer(N), N >= 0 -> N.
+-spec is_empty(Dict) -> boolean() when
+ Dict :: dict().
+
+is_empty(#dict{size=N}) -> N =:= 0.
+
-spec fetch(Key, Dict) -> Value when
Key :: term(),
Dict :: dict(),
diff --git a/lib/stdlib/src/orddict.erl b/lib/stdlib/src/orddict.erl
index 45d3c84b3e..da60fc1bb6 100644
--- a/lib/stdlib/src/orddict.erl
+++ b/lib/stdlib/src/orddict.erl
@@ -20,7 +20,7 @@
-module(orddict).
%% Standard interface.
--export([new/0,is_key/2,to_list/1,from_list/1,size/1]).
+-export([new/0,is_key/2,to_list/1,from_list/1,size/1,is_empty/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]).
@@ -64,6 +64,12 @@ from_list(Pairs) ->
size(D) -> length(D).
+-spec is_empty(Orddict) -> boolean() when
+ Orddict :: orddict().
+
+is_empty([]) -> true;
+is_empty([_|_]) -> false.
+
-spec fetch(Key, Orddict) -> Value when
Key :: term(),
Value :: term(),
diff --git a/lib/stdlib/test/dict_SUITE.erl b/lib/stdlib/test/dict_SUITE.erl
index 0223240479..69814e12ce 100644
--- a/lib/stdlib/test/dict_SUITE.erl
+++ b/lib/stdlib/test/dict_SUITE.erl
@@ -17,7 +17,7 @@
%% %CopyrightEnd%
%%
-%% This module tests the ordsets, sets, and gb_sets modules.
+%% This module tests the orddict, dict, and gb_trees modules.
%%
-module(dict_SUITE).
@@ -68,6 +68,7 @@ create_1(M) ->
D0 = M(empty, []),
[] = M(to_list, D0),
0 = M(size, D0),
+ true = M(is_empty, D0),
D0.
store(Config) when is_list(Config) ->
@@ -81,6 +82,14 @@ store_1(List, M) ->
D1 = foldl(fun({K,V}, Dict) -> M(enter, {K,V,Dict}) end,
M(empty, []), List),
true = M(equal, {D0,D1}),
+ case List of
+ [] ->
+ true = M(is_empty, D0),
+ true = M(is_empty, D1);
+ [_|_] ->
+ false = M(is_empty, D0),
+ false = M(is_empty, D1)
+ end,
D0.
%%%
diff --git a/lib/stdlib/test/dict_test_lib.erl b/lib/stdlib/test/dict_test_lib.erl
index e308fd0721..4fdb4fa0bd 100644
--- a/lib/stdlib/test/dict_test_lib.erl
+++ b/lib/stdlib/test/dict_test_lib.erl
@@ -28,6 +28,7 @@ new(Mod, Eq) ->
(from_list, L) -> from_list(Mod, L);
(module, []) -> Mod;
(size, D) -> Mod:size(D);
+ (is_empty, D) -> Mod:is_empty(D);
(to_list, D) -> to_list(Mod, D)
end.