[erlang-questions] Ordered set with lower_bound

[Igor Ribeiro Sucupira]

On Thu, Oct 8, 2009 at 11:34 PM, Richard O'Keefe <ok@REDACTED> wrote:
>
> 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.


Hi, Richard.

My question was actually "Do I need to implement it?". So, I was not
questioning the capability of gb_sets to support that.

But, thank you for the code. Although I realized I don't really need
the iterators now, I'll certainly need them some day, since I happened
to need STL's lower_bound a couple of times in the past.

Also, I've had a glance at your code and it makes sense to me.  :-)
geq_iterator rearranges the tree to not contain the elements smaller
than Min and then returns an iterator to that new tree. Looks OK.  :-)

Thanks.
Igor.


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



-- 
"The secret of joy in work is contained in one word - excellence. To
know how to do something well is to enjoy it." - Pearl S. Buck.