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

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_me... 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... Aleric
participants (1)
-
Aleric Inglewood