From 0e4b0ae7ce57117a561f70fa51026d85b4702aaa Mon Sep 17 00:00:00 2001
From: Magnus Henoch <magnus.henoch@gmail.com>
Date: Wed, 4 Sep 2013 14:08:34 +0100
Subject: 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.
---
 lib/stdlib/doc/src/dict.xml       |  7 +++++++
 lib/stdlib/doc/src/orddict.xml    |  7 +++++++
 lib/stdlib/src/dict.erl           |  7 ++++++-
 lib/stdlib/src/orddict.erl        |  8 +++++++-
 lib/stdlib/test/dict_SUITE.erl    | 11 ++++++++++-
 lib/stdlib/test/dict_test_lib.erl |  1 +
 6 files changed, 38 insertions(+), 3 deletions(-)

(limited to 'lib/stdlib')

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
@@ -176,6 +176,13 @@ merge(Fun, D1, D2) ->
         <p>Returns the number of elements in a <c><anno>Dict</anno></c>.</p>
       </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>
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
@@ -186,6 +186,13 @@ merge(Fun, D1, D2) ->
         <p>Returns the number of elements in an <c><anno>Orddict</anno></c>.</p>
       </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>
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.
 
-- 
cgit v1.2.3