Merge branch 'evilbluebeaver/iterator_from'

* evilbluebeaver/iterator_from:
  stdlib: Add gb_sets:iterator_from
  stdlib: Add gb_trees:iterator_from

8 files changed, 170 insertions, 15 deletions

diff --git a/lib/stdlib/doc/src/gb_sets.xml b/lib/stdlib/doc/src/gb_sets.xml
index ea96c14472..405bae5698 100644
--- a/lib/stdlib/doc/src/gb_sets.xml
+++ b/lib/stdlib/doc/src/gb_sets.xml
@@ -4,7 +4,7 @@
 <erlref>
   <header>
     <copyright>
-      <year>2001</year><year>2014</year>
+      <year>2001</year><year>2015</year>
       <holder>Ericsson AB. All Rights Reserved.</holder>
     </copyright>
     <legalnotice>
@@ -306,6 +306,17 @@
       </desc>
     </func>
     <func>
+      <name name="iterator_from" arity="2"/>
+      <fsummary>Return an iterator for a set starting from a specified element</fsummary>
+      <desc>
+        <p>Returns an iterator that can be used for traversing the
+          entries of <c><anno>Set</anno></c>; see <c>next/1</c>.
+          The difference as compared to the iterator returned by
+          <c>iterator/1</c> is that the first element greater than
+          or equal to <c><anno>Element</anno></c> is returned.</p>
+      </desc>
+    </func>
+    <func>
       <name name="largest" arity="1"/>
       <fsummary>Return largest element</fsummary>
       <desc>
diff --git a/lib/stdlib/doc/src/gb_trees.xml b/lib/stdlib/doc/src/gb_trees.xml
index b2f237e1d7..82167e1083 100644
--- a/lib/stdlib/doc/src/gb_trees.xml
+++ b/lib/stdlib/doc/src/gb_trees.xml
@@ -4,7 +4,7 @@
 <erlref>
   <header>
     <copyright>
-      <year>2001</year><year>2014</year>
+      <year>2001</year><year>2015</year>
       <holder>Ericsson AB. All Rights Reserved.</holder>
     </copyright>
     <legalnotice>
@@ -183,6 +183,17 @@
       </desc>
     </func>
     <func>
+      <name name="iterator_from" arity="2"/>
+      <fsummary>Return an iterator for a tree starting from specified key</fsummary>
+      <desc>
+        <p>Returns an iterator that can be used for traversing the
+            entries of <c><anno>Tree</anno></c>; see <c>next/1</c>.
+            The difference as compared to the iterator returned by
+            <c>iterator/1</c> is that the first key greater than
+            or equal to <c><anno>Key</anno></c> is returned.</p>
+      </desc>
+    </func>
+    <func>
       <name name="keys" arity="1"/>
       <fsummary>Return a list of the keys in a tree</fsummary>
       <desc>
diff --git a/lib/stdlib/src/gb_sets.erl b/lib/stdlib/src/gb_sets.erl
index 393fb07229..d3fbd542f7 100644
--- a/lib/stdlib/src/gb_sets.erl
+++ b/lib/stdlib/src/gb_sets.erl
@@ -137,6 +137,10 @@
 %%   approach is that it does not require the complete list of all
 %%   elements to be built in memory at one time.
 %%
+%% - iterator_from(X, S): returns an iterator that can be used for
+%%   traversing the elements of set S greater than or equal to X;
+%%   see `next'.
+%%
 %% - next(T): returns {X, T1} where X is the smallest element referred
 %%   to by the iterator T, and T1 is the new iterator to be used for
 %%   traversing the remaining elements, or the atom `none' if no
@@ -157,8 +161,8 @@
 	 insert/2, add/2, delete/2, delete_any/2, balance/1, union/2,
 	 union/1, intersection/2, intersection/1, is_disjoint/2, difference/2,
 	 is_subset/2, to_list/1, from_list/1, from_ordset/1, smallest/1,
-	 largest/1, take_smallest/1, take_largest/1, iterator/1, next/1,
-	 filter/2, fold/3, is_set/1]).
+	 largest/1, take_smallest/1, take_largest/1, iterator/1,
+         iterator_from/2, next/1, filter/2, fold/3, is_set/1]).
 
 %% `sets' compatibility aliases:
 
@@ -500,6 +504,22 @@ iterator({_, L, _} = T, As) ->
 iterator(nil, As) ->
     As.
 
+-spec iterator_from(Element, Set) -> Iter when
+      Set :: set(Element),
+      Iter :: iter(Element).
+
+iterator_from(S, {_, T}) ->
+    iterator_from(S, T, []).
+
+iterator_from(S, {K, _, T}, As) when K < S ->
+    iterator_from(S, T, As);
+iterator_from(_, {_, nil, _} = T, As) ->
+    [T | As];
+iterator_from(S, {_, L, _} = T, As) ->
+    iterator_from(S, L, [T | As]);
+iterator_from(_, nil, As) ->
+    As.
+
 -spec next(Iter1) -> {Element, Iter2} | 'none' when
       Iter1 :: iter(Element),
       Iter2 :: iter(Element).
diff --git a/lib/stdlib/src/gb_trees.erl b/lib/stdlib/src/gb_trees.erl
index 7069b61873..259e8f718b 100644
--- a/lib/stdlib/src/gb_trees.erl
+++ b/lib/stdlib/src/gb_trees.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2001-2014. All Rights Reserved.
+%% Copyright Ericsson AB 2001-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
@@ -102,6 +102,10 @@
 %%   approach is that it does not require the complete list of all
 %%   elements to be built in memory at one time.
 %%
+%% - iterator_from(K, T): returns an iterator that can be used for
+%%   traversing the entries of tree T with key greater than or
+%%   equal to K; see `next'.
+%%
 %% - next(S): returns {X, V, S1} where X is the smallest key referred to
 %%   by the iterator S, and S1 is the new iterator to be used for
 %%   traversing the remaining entries, or the atom `none' if no entries
@@ -117,7 +121,7 @@
 	 update/3, enter/3, delete/2, delete_any/2, balance/1,
 	 is_defined/2, keys/1, values/1, to_list/1, from_orddict/1,
 	 smallest/1, largest/1, take_smallest/1, take_largest/1,
-	 iterator/1, next/1, map/2]).
+	 iterator/1, iterator_from/2, next/1, map/2]).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -529,6 +533,29 @@ iterator({_, _, L, _} = T, As) ->
 iterator(nil, As) ->
     As.
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec iterator_from(Key, Tree) -> Iter when
+      Tree :: tree(Key, Value),
+      Iter :: iter(Key, Value).
+
+iterator_from(S, {_, T}) ->
+    iterator_1_from(S, T).
+
+iterator_1_from(S, T) ->
+    iterator_from(S, T, []).
+
+iterator_from(S, {K, _, _, T}, As) when K < S ->
+    iterator_from(S, T, As);
+iterator_from(_, {_, _, nil, _} = T, As) ->
+    [T | As];
+iterator_from(S, {_, _, L, _} = T, As) ->
+    iterator_from(S, L, [T | As]);
+iterator_from(_, nil, As) ->
+    As.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 -spec next(Iter1) -> 'none' | {Key, Value, Iter2} when
       Iter1 :: iter(Key, Value),
       Iter2 :: iter(Key, Value).
diff --git a/lib/stdlib/test/dict_SUITE.erl b/lib/stdlib/test/dict_SUITE.erl
index 69814e12ce..ab624e8dd2 100644
--- a/lib/stdlib/test/dict_SUITE.erl
+++ b/lib/stdlib/test/dict_SUITE.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2008-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2008-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
@@ -25,16 +25,16 @@
 -export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, 
 	 init_per_group/2,end_per_group/2,
 	 init_per_testcase/2,end_per_testcase/2,
-	 create/1,store/1]).
+         create/1,store/1,iterate/1]).
 
 -include_lib("test_server/include/test_server.hrl").
 
--import(lists, [foldl/3,reverse/1]).
+-import(lists, [foldl/3]).
 
 suite() -> [{ct_hooks,[ts_install_cth]}].
 
 all() -> 
-    [create, store].
+    [create, store, iterate].
 
 groups() -> 
     [].
@@ -93,6 +93,48 @@ store_1(List, M) ->
     D0.
 
 %%%
+%%% Test specifics for gb_trees.
+%%%
+
+iterate(Config) when is_list(Config) ->
+    test_all(fun iterate_1/1).
+
+iterate_1(M) ->
+    case M(module, []) of
+	gb_trees -> iterate_2(M);
+	_ -> ok
+    end,
+    M(empty, []).
+
+iterate_2(M) ->
+    random:seed(1, 2, 42),
+    iter_tree(M, 1000).
+
+iter_tree(_M, 0) ->
+    ok;
+iter_tree(M, N) ->
+    L = [{I, I} || I <- lists:seq(1, N)],
+    T = M(from_list, L),
+    L = lists:reverse(iterate_tree(M, T)),
+    R = random:uniform(N),
+    KV = lists:reverse(iterate_tree_from(M, R, T)),
+    KV = [P || P={K,_} <- L, K >= R],
+    iter_tree(M, N-1).
+
+iterate_tree(M, Tree) ->
+    I = M(iterator, Tree),
+    iterate_tree_1(M, M(next, I), []).
+
+iterate_tree_from(M, Start, Tree) ->
+    I = M(iterator_from, {Start, Tree}),
+    iterate_tree_1(M, M(next, I), []).
+
+iterate_tree_1(_, none, R) ->
+    R;
+iterate_tree_1(M, {K, V, I}, R) ->
+    iterate_tree_1(M, M(next, I), [{K, V} | R]).
+
+%%%
 %%% Helper functions.
 %%%
 
diff --git a/lib/stdlib/test/dict_test_lib.erl b/lib/stdlib/test/dict_test_lib.erl
index 4fdb4fa0bd..81d26ce5f8 100644
--- a/lib/stdlib/test/dict_test_lib.erl
+++ b/lib/stdlib/test/dict_test_lib.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2008-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2008-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
@@ -29,6 +29,9 @@ new(Mod, Eq) ->
 	(module, []) -> Mod;
 	(size, D) -> Mod:size(D);
 	(is_empty, D) -> Mod:is_empty(D);
+        (iterator, S) -> Mod:iterator(S);
+        (iterator_from, {Start, S}) -> Mod:iterator_from(Start, S);
+        (next, I) -> Mod:next(I);
 	(to_list, D) -> to_list(Mod, D)
     end.
 
diff --git a/lib/stdlib/test/sets_SUITE.erl b/lib/stdlib/test/sets_SUITE.erl
index c0cf1fc7e8..24f5d65f82 100644
--- a/lib/stdlib/test/sets_SUITE.erl
+++ b/lib/stdlib/test/sets_SUITE.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2004-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2004-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
@@ -28,7 +28,7 @@
 	 create/1,add_element/1,del_element/1,
 	 subtract/1,intersection/1,union/1,is_subset/1,
 	 is_set/1,fold/1,filter/1,
-	 take_smallest/1,take_largest/1]).
+	 take_smallest/1,take_largest/1, iterate/1]).
 
 -include_lib("test_server/include/test_server.hrl").
 
@@ -48,7 +48,7 @@ suite() -> [{ct_hooks,[ts_install_cth]}].
 all() -> 
     [create, add_element, del_element, subtract,
      intersection, union, is_subset, is_set, fold, filter,
-     take_smallest, take_largest].
+     take_smallest, take_largest, iterate].
 
 groups() -> 
     [].
@@ -426,6 +426,44 @@ take_largest_3(S0, List0, M) ->
 	    take_largest_3(S, List, M)
     end.
 
+iterate(Config) when is_list(Config) ->
+    test_all(fun iterate_1/1).
+
+iterate_1(M) ->
+    case M(module, []) of
+	gb_sets -> iterate_2(M);
+	_ -> ok
+    end,
+    M(empty, []).
+
+iterate_2(M) ->
+    random:seed(1, 2, 42),
+    iter_set(M, 1000).
+
+iter_set(_M, 0) ->
+    ok;
+iter_set(M, N) ->
+    L = [I || I <- lists:seq(1, N)],
+    T = M(from_list, L),
+    L = lists:reverse(iterate_set(M, T)),
+    R = random:uniform(N),
+    S = lists:reverse(iterate_set(M, R, T)),
+    S = [E || E <- L, E >= R],
+    iter_set(M, N-1).
+
+iterate_set(M, Set) ->
+    I = M(iterator, Set),
+    iterate_set_1(M, M(next, I), []).
+
+iterate_set(M, Start, Set) ->
+    I = M(iterator_from, {Start, Set}),
+    iterate_set_1(M, M(next, I), []).
+
+iterate_set_1(_, none, R) ->
+    R;
+iterate_set_1(M, {E, I}, R) ->
+    iterate_set_1(M, M(next, I), [E | R]).
+
 %%%
 %%% Helper functions.
 %%%
diff --git a/lib/stdlib/test/sets_test_lib.erl b/lib/stdlib/test/sets_test_lib.erl
index 86f009a8f9..772139406d 100644
--- a/lib/stdlib/test/sets_test_lib.erl
+++ b/lib/stdlib/test/sets_test_lib.erl
@@ -1,7 +1,7 @@
 %%
 %% %CopyrightBegin%
 %% 
-%% Copyright Ericsson AB 2004-2013. All Rights Reserved.
+%% Copyright Ericsson AB 2004-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
@@ -34,7 +34,10 @@ new(Mod, Eq) ->
 	(is_empty, S) -> is_empty(Mod, S);
 	(is_set, S) -> Mod:is_set(S);
 	(is_subset, {S,Set}) -> is_subset(Mod, Eq, S, Set);
+        (iterator, S) -> Mod:iterator(S);
+        (iterator_from, {Start, S}) -> Mod:iterator_from(Start, S);
 	(module, []) -> Mod;
+        (next, I) -> Mod:next(I);
 	(singleton, E) -> singleton(Mod, E);
 	(size, S) -> Mod:size(S);
 	(subtract, {S1,S2}) -> subtract(Mod, S1, S2);