# [erlang-questions] merging gb_trees

Andreas Schultz aschultz@REDACTED
Fri Oct 21 09:33:19 CEST 2011

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

----- Original Message -----
> I withdraw my question.
>
> Switching from gb_trees to orddict and using orddict:merge/3 answers
> it.
>
> Kudos to the #erlang channel on IRC.
>
> On Oct 20, 2011, at 11:56 PM, Joel Reymont wrote:
>
> > 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?
>
> --------------------------------------------------------------------------
> - for hire: mac osx device driver ninja, kernel extensions and usb
> drivers
> ---------------------+------------+---------------------------------------
> http://wagerlabs.com | @wagerlabs |
> ---------------------+------------+---------------------------------------
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>

--
--
Dipl. Inform.
Andreas Schultz

email: as@REDACTED
phone: +49-391-819099-224
mobil: +49-179-7654368

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

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