[boost] [Boost.Algorithm] Proposal for addition of a new algorithm: ThreeWayMerge

Subject: [boost] [Boost.Algorithm] Proposal for addition of a new algorithm: ThreeWayMerge
From: Aleric Inglewood (aleric.inglewood_at_[hidden])
Date: 2011-01-28 11:51:25

Greetings everyone.

I don't think that Boost.Algorithm exists: I only saw it refered to on
mailinglists.
I looked at the existing libraries, but I'm not sure where this would fit in.

I'd like to propose the addition of a new algorithm, very much like
std::set_union
and companions, that I came up with recently.

This algorithm does a three-way merge of containers.

Comparing it to std::set_union, which needs five iterators to be passed,
and a compare functor (two iterators for the range of input 1, two
iterators for the range of input 2 and one output iterator), the
three_way_merge algorithm takes three iterator ranges and one
output iterator, so it takes seven iterators.

The algorithm also takes two functors: a compare and an is_equal.
The former should be the ordering Predicate used with the containers
(they must be ordered containers, like std::set or set::map), while
the is_equal functor is usd to compare the "payload" of the data
(which is not part of the sorting key).

The algorithm applies trivial merge rules in all cases where the merge
is trivial, and calls a third functor to perform the three-way merge
of the payload in those cases that a three-way merge is not trivial.

In it's current form, my algorithm looks as follows:

https://github.com/AlericInglewood/contribmerge/blob/master/src/three_way_merge.h

I used it (in that project) to three-way-merge a file with a specific
format: a list of contributors, each with a list of contributions.
The algorithm is used recursively (which is very neatly showing
it's true power, of course). For this usage example, please
see https://github.com/AlericInglewood/contribmerge/blob/master/src/contribmerge.cc

Aleric