[erlang-questions] merging gb_trees

[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

----- 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 |
> http://www.linkedin.com/in/joelreymont
> ---------------------+------------+---------------------------------------
> 
> _______________________________________________
> 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

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

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