[erlang-questions] Ordered set with lower_bound

[Richard O'Keefe]

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,
added this code to it, added an -export declaration

-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.