tlx
Toggle main menu visibility
Loading...
Searching...
No Matches
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
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
/******************************************************************************/
tlx::merge_combine
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.
Definition
merge_combine.hpp:37
tlx
Definition
exclusive_scan.hpp:17
tlx
algorithm
merge_combine.hpp
Generated on
for tlx by
1.17.0