[erlang-questions] merging gb_trees

[Joel Reymont]

Suppose I have 2 gb_trees T1 and T2.

I want to merge them such that all the values with equal keys are summed up in the resulting tree.

What is the most elegant way to accomplish this?

Thanks, Joel

--------------------------------------------------------------------------
- for hire: mac osx device driver ninja, kernel extensions and usb drivers
---------------------+------------+---------------------------------------
http://wagerlabs.com | @wagerlabs | http://www.linkedin.com/in/joelreymont
---------------------+------------+---------------------------------------

_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

[Joel Reymont]

Forgot to mention a constraint…

Some keys may exist in one tree but not in the other.

The resulting tree should have all the keys and the values should be copied if a key does not exist in one of the tree and summed up otherwise.

I actually have multiple trees to merge into a single one but I figure I could repeat the operation two trees at a time.

On Oct 20, 2011, at 11:43 PM, Joel Reymont wrote:

> Suppose I have 2 gb_trees T1 and T2.
>
> I want to merge them such that all the values with equal keys are summed up in the resulting tree.
>
> What is the most elegant way to accomplish this?

--------------------------------------------------------------------------

[Joel Reymont]

I withdraw my question.

Switching from gb_trees to orddict and using orddict:merge/3 answers it.

Kudos to the #erlang channel on IRC.

[Andreas Schultz]

Hi,

Still an interesting problem, what about getting iterators on both
of them and running a merge sort like process over them?

Something like this (untested):

merge(Tree1, Tree2, Fun) ->
Iter1 = gb_trees:iterator(Tree1),
Next1 = gb_trees:next(Iter1),
Iter2 = gb_trees:iterator(Tree2)
Next2 = gb_trees:next(Iter2),
do_merge({Iter1, Next1}, {Iter2, Next2}, Fun, gb_trees:empty()).

do_merge({Iter1, Next1 = {Key1, Val1 Iter1Next}},
{Iter2, Next2 = {Key2, Val2 Iter2Next}},
Fun, Tree) when Key1 == Key2 ->
NewTree = gb_trees:insert(Key1, Fun(Key1, Val1, Val2), Tree),
do_merge({Iter1Next, gb_trees:next(Iter1Next)},
{Iter2Next, gb_trees:next(Iter2Next)},
Fun, NewTree);

do_merge({Iter1, Next1 = {Key1, Val1 Iter1Next}},
{Iter2, Next2 = {Key2, Val2 Iter2Next}},
Fun, Tree) when Key1 < Key2 ->
NewTree = gb_trees:insert(Key1, Val1, Tree),
do_merge({Iter1Next, gb_trees:next(Iter1Next)},
{Iter2, Next2},
Fun, NewTree);

do_merge({Iter1, Next1 = {Key1, Val1 Iter1Next}},
{Iter2, Next2 = {Key2, Val2 Iter2Next}},
Fun, Tree) when Key1 > Key2 ->
NewTree = gb_trees:insert(Key2, Val2, Tree),
do_merge({Iter1, Next1},
{Iter2, gb_trees:next(Iter2Next)},
Fun, NewTree).

Might even be faster not to build the tree directly, but instead
build a list and use gb_trees:from_orddict()

Andreas

--
--
Dipl. Inform.
Andreas Schultz

email: a...@travelping.com
phone: +49-391-819099-224
mobil: +49-179-7654368

------------------ managed broadband access ------------------

Travelping GmbH phone: +49-391-8190990
Roentgenstr. 13 fax: +49-391-819099299
D-39108 Magdeburg email: in...@travelping.com
GERMANY web: http://www.travelping.com

Company Registration: HRB21276 Handelsregistergericht Chemnitz
Geschaeftsfuehrer: Holger Winkelmann | VAT ID No.: DE236673780
--------------------------------------------------------------