gb_trees:search/3

[Ulf Wiger (AL/EAB)]

Sven-Olof Nyström wrote:
> 
> Ulf Wiger (AL/EAB) writes:
>  > The first example doesn't really introduce
>  > anything new, as it scans the whole tree
>  > (most likely less efficient than iterator())
> 
> or to_list().

Yes, well, I've grown a bit allergic to functions
that return the whole contents of a data structure
designed to be scalable. Given how the garbage 
collector works, you should only use them if you
are sure that the number of objects is relatively
small; and then you might as well use orddict or
similar with very little performance penalty. (:

That's not to say that to_list() isn't useful.

> So you scan the part of a tree where keys are smaller than 5.
> 
> See my comment at the end for alternative ways to provide this
> functionality in gb_trees.

With ets:select(), you can do much more than that.
A fairly common type of pattern could be to 
have objects with a structured key, e.g.:

{{DocId, [Chapter, SubChapter, Table, Row]}, Value}
(fictitious example)

and with ordered_set ets, you can quite easily
then extract all rows in a given table in a given
sub-chapter, ... etc in this fashion

ets:select(
  docs, 
  [{{DocId, [Chapter,SubChapter,Table,'$1']},'$2'},
   [],
   [{{'$1', '$2'}}]}])

The syntax is horrible, but that's partly because 
you can't really copy each object to the process
heap just to determine whether it's a match, and 
you don't have a context within ets for evaluating
a fun. gb_trees can do much better, IMO.

You could read up on the match specification
syntax in the ERTS user's guide
(http://erlang.se/doc/doc-5.4.8/erts-5.4.8/doc/html/match_spec.html#1)
but I think that a functional data structure
should just disregard match specifications
and allow the user to provide a fun instead.


>  > Forgetting about this particular example, having
>  > previous(), next() and an efficient way to select
>  > nodes in a tree without having to traverse the 
>  > whole tree would be useful, don't you think?
> 
> Sure, previous() and next() could be useful. I would
> prefer more descriptive names, such as lookup_smaller()
> and lookup_larger(). Also, I think they should always
> return a strictly smaller/larger key, even
> if the given key is present.

Yes, since all keys are unique, that's how it
ought to work. The fun thing about ets ordered_sets
is that next/2 and previous/2 work even if the given
key is not present. This is not true for sets.
More descriptive names is perfectly OK. (:


> Currently, iterators can only be used to scan the
> tree from start, One might consider iterators that
> start the scan from a point in the middle of the
> tree (from a given key), or iterators that scan the
> tree backwards.
> 
> Another way to do partial scans might be a function 
> 
> to_list(Key1, Key2) 
> 
> that returns a list of the entries in the tree between
> the two keys.

Nice, but decidedly less flexible than the ets:select()
function.

Perhaps it's just me, but I would like to see some 
functional data structures offer some of the power
of ets, and perhaps manage to lure some people 
away from ets. For one thing, using a functional 
data structure, you get "undo" for free.

/Uffe