tlx
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 <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
18namespace 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 */
32template <typename InputIterator1, typename InputIterator2,
33 typename OutputIterator,
34 typename Comparator,
35 typename Combine = std::plus<
36 typename std::iterator_traits<InputIterator1>::value_type> >
37OutputIterator 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.