From f584a60d0e5a6fa0a8002a13e8dda2a790031427 Mon Sep 17 00:00:00 2001 From: Hans Bolinder Date: Tue, 12 May 2015 14:15:40 +0200 Subject: stdlib: Add gb_sets:iterator_from --- lib/stdlib/doc/src/gb_sets.xml | 13 +++++++++++- lib/stdlib/src/gb_sets.erl | 24 +++++++++++++++++++-- lib/stdlib/test/sets_SUITE.erl | 44 ++++++++++++++++++++++++++++++++++++--- lib/stdlib/test/sets_test_lib.erl | 5 ++++- 4 files changed, 79 insertions(+), 7 deletions(-) (limited to 'lib') 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 @@
- 20012014 + 20012015 Ericsson AB. All Rights Reserved. @@ -305,6 +305,17 @@ memory at one time.

+ + + Return an iterator for a set starting from a specified element + +

Returns an iterator that can be used for traversing the + entries of Set; see next/1. + The difference as compared to the iterator returned by + iterator/1 is that the first element greater than + or equal to Element is returned.

+ + Return largest element 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/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); -- cgit v1.2.3