# [erlang-questions] Ordered set with lower_bound

Richard O'Keefe ok@REDACTED
Fri Oct 9 04:34:12 CEST 2009

On Oct 9, 2009, at 12:12 PM, Igor Ribeiro Sucupira wrote:

> Hi.
>
> I need some ordered set that allows me to "search and then iterate"
> efficiently. In other words, I need this functionality:
> http://www.cplusplus.com/reference/stl/set/lower_bound/

What you want is a function something like
iterator_beginning_at(Set, Element) -> Iterator

The existing gb_sets *module* does not support that, but the
*data structure* easily could.

Look at the code for constructing and using iterators.
reverse_iterator/1 and previous/1 are mine.

tree --> {key,tree,tree} | 'nil'.
iterator --> [tree|iterator] | [].
The (sub)trees in an iterator are there for the sake of the key
and _one_ of the subtrees.

iterator({_Size, Tree}) ->
iterator(Tree, []).

iterator({_X, nil, _Right} = Tree, As) ->
[Tree|As];
iterator({_X, Left, _Right} = Tree, As) ->
iterator(Left, [Tree|As]);
iterator(nil, As) ->
As.

next([{X, _Left, Right}|As]) ->
{X, iterator(Right, As)};
next([]) ->
none.

reverse_iterator({_Size, Tree}) ->
reverse_iterator(Tree, []).

reverse_iterator({_X, _Left, nil} = Tree, As) ->
[Tree|As];
reverse_iterator({_X, _Left, Right} = Tree, As) ->
reverse_iterator(Right, [Tree|As]);
reverse_iterator(nil, As) ->
As.

previous([{X, Left, _Right}|As]) ->
{X, reverse_iterator(Left, As)};
previous([]) ->
none.

Perhaps the simplest way to do it would be to use
iterator(remove_less(Set, Start))
or  reverse_iterator(remove_greater(Set, Start))
where

remove_less(Set, X)    -> {Y \in Set | Y >= X}
remove_greater(Set, X) -> {Y \in Set | X >= Y}

However, since the size of a gb_set is stored only at the top,
exporting these functions in the interface, returning GB sets,
would require time linear in the result.  It's OK to use them
internally, though, as iterators don't need to know the size.

So

geq_iterator({_Size, Tree}, Min) ->
iterator(remove_less(Tree, Min), []).

leq_iterator({_Size, Tree}, Max) ->
iterator(remove_greater(Tree, Max), []).

range_iterator({_Size, Tree}, Min, Max) ->
iterator(remove_less(remove_greater(Tree, Max), Min), []).

geq_reverse_iterator({_Size, Tree}, Min) ->
reverse_iterator(remove_less(Tree, Min), []).

leq_reverse_iterator({_Size, Tree}, Max) ->
reverse_iterator(remove_greater(Tree, Max), []).

range_reverse_iterator({_Size, Tree}, Min, Max) ->
reverse_iterator(remove_less(remove_greater(Tree, Max), Min), []).

remove_less({Key,Left,Right}, Min) ->
if Key < Min -> remove_less(Right, Min)
; Key > Min -> {Key, remove_less(Left, Min), Right}
; true      -> {Key, nil, Right}
end;
remove_less(nil, _) ->
nil.

remove_greater({Key,Left,Right}, Max) ->
if Key > Max -> remove_greater(Left, Max)
; Key < Max -> {Key, Left, remove_greater(Right, Max)}
; true      -> {Key, Left, nil}
end;
remove_greater(nil, _) ->
nil.

I made a copy of gb_sets.erl called gb_sets2.erl,

-export([reverse_iterator/1, previous/1,
geq_iterator/2,     geq_reverse_iterator/2,
leq_iterator/2,     leq_reverse_iterator/2,
range_iterator/3,   range_reverse_iterator/3]).

and put the stuff through some testing, and it seemed to work.
This has been tested, BUT NOT THOROUGHLY TESTED.