aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/gb_trees.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib/src/gb_trees.erl')
-rw-r--r--lib/stdlib/src/gb_trees.erl36
1 files changed, 31 insertions, 5 deletions
diff --git a/lib/stdlib/src/gb_trees.erl b/lib/stdlib/src/gb_trees.erl
index 7069b61873..2cbfd8fd2a 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]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -156,11 +160,10 @@
-type gb_tree_node(K, V) :: 'nil'
| {K, V, gb_tree_node(K, V), gb_tree_node(K, V)}.
--type gb_tree_node() :: gb_tree_node(_, _).
-opaque tree(Key, Value) :: {non_neg_integer(), gb_tree_node(Key, Value)}.
--opaque tree() :: tree(_, _).
+-type tree() :: tree(_, _).
-opaque iter(Key, Value) :: [gb_tree_node(Key, Value)].
--opaque iter() :: [gb_tree_node()].
+-type iter() :: iter(_, _).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -529,6 +532,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).