Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
merge_combine.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/algorithm/merge_combine.hpp
3  *
4  * Part of tlx - http://panthema.net/tlx
5  *
6  * Copyright (C) 2018 Timo Bingmann <[email protected]>
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> >
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 /******************************************************************************/
OutputIterator merge_combine(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Comparator cmp=Comparator(), Combine combine=Combine())
Merge two sorted ranges and add all items comparing equal.