aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib
diff options
context:
space:
mode:
authorbeaver <[email protected]>2015-03-25 18:03:26 +0300
committerHans Bolinder <[email protected]>2015-05-18 09:04:52 +0200
commitddc4e717df1da722682b6ccdbf152a6b7e15f378 (patch)
tree4d88c65a1ffcfe3bcb03b52ba638844297eb2292 /lib/stdlib
parent9a81b28598fadc44bf506354c9227e41aac786f6 (diff)
downloadotp-ddc4e717df1da722682b6ccdbf152a6b7e15f378.tar.gz
otp-ddc4e717df1da722682b6ccdbf152a6b7e15f378.tar.bz2
otp-ddc4e717df1da722682b6ccdbf152a6b7e15f378.zip
stdlib: Add gb_trees:iterator_from
Diffstat (limited to 'lib/stdlib')
-rw-r--r--lib/stdlib/doc/src/gb_trees.xml13
-rw-r--r--lib/stdlib/src/gb_trees.erl31
-rw-r--r--lib/stdlib/test/dict_SUITE.erl50
-rw-r--r--lib/stdlib/test/dict_test_lib.erl5
4 files changed, 91 insertions, 8 deletions
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_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.