1 /*******************************************************************************
2 * tlx/algorithm/merge_combine.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2018 Timo Bingmann <tb@panthema.net>
7 *
8 * All rights reserved. Published under the Boost Software License, Version 1.0
9 ******************************************************************************/
10
11 #ifndef TLX_ALGORITHM_MERGE_COMBINE_HEADER
12 #define TLX_ALGORITHM_MERGE_COMBINE_HEADER
13
14 #include <algorithm>
15 #include <functional>
16 #include <iterator>
17
18 namespace tlx {
19
20 //! \addtogroup tlx_algorithm
21 //! \{
22
23 /*!
24 * Merge two sorted ranges and add all items comparing equal. Both ranges must
25 * be sorted using the three-way Comparator (with memcmp() semantics). Item
26 * pairs comparing equal (cmp returns 0) are combined together using a combine
27 * operator.
28 *
29 * \warning This method does not check if the ranges are sorted. Also make sure
30 * that the comparator does not work with unsigned types.
31 */
32 template <typename InputIterator1, typename InputIterator2,
33 typename OutputIterator,
34 typename Comparator,
35 typename Combine = std::plus<
36 typename std::iterator_traits<InputIterator1>::value_type> >
merge_combine(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result,Comparator cmp=Comparator (),Combine combine=Combine ())37 OutputIterator merge_combine(
38 InputIterator1 first1, InputIterator1 last1,
39 InputIterator2 first2, InputIterator2 last2,
40 OutputIterator result, Comparator cmp = Comparator(),
41 Combine combine = Combine()) {
42
43 while (true)
44 {
45 // if either range is done -> copy the rest of the other
46 if (first1 == last1)
47 return std::copy(first2, last2, result);
48 if (first2 == last2)
49 return std::copy(first1, last1, result);
50
51 // compare both items, copy or combine.
52 if (cmp(*first1, *first2) < 0) {
53 *result = *first1;
54 ++first1;
55 }
56 else if (cmp(*first1, *first2) > 0) {
57 *result = *first2;
58 ++first2;
59 }
60 else {
61 *result = combine(*first1, *first2);
62 ++first1, ++first2;
63 }
64 ++result;
65 }
66 }
67
68 //! \}
69
70 } // namespace tlx
71
72 #endif // !TLX_ALGORITHM_MERGE_COMBINE_HEADER
73
74 /******************************************************************************/
75