tlx
Toggle main menu visibility
Loading...
Searching...
No Matches
merge_advance.hpp
Go to the documentation of this file.
1
/*******************************************************************************
2
* tlx/algorithm/merge_advance.hpp
3
*
4
* Variants of binary merge with output size limit.
5
*
6
* Copied and modified from STXXL, see http://stxxl.org, which itself extracted
7
* it from MCSTL http://algo2.iti.uni-karlsruhe.de/singler/mcstl/. Both are
8
* distributed under the Boost Software License, Version 1.0.
9
*
10
* Part of tlx - http://panthema.net/tlx
11
*
12
* Copyright (C) 2007 Johannes Singler <singler@ira.uka.de>
13
* Copyright (C) 2014-2018 Timo Bingmann <tb@panthema.net>
14
*
15
* All rights reserved. Published under the Boost Software License, Version 1.0
16
******************************************************************************/
17
18
#ifndef TLX_ALGORITHM_MERGE_ADVANCE_HEADER
19
#define TLX_ALGORITHM_MERGE_ADVANCE_HEADER
20
21
#include <algorithm>
22
23
namespace
tlx
{
24
25
//! \addtogroup tlx_algorithm
26
//! \{
27
28
/*!
29
* Merge routine being able to merge only the \c max_size smallest elements.
30
*
31
* The \c begin iterators are advanced accordingly, they might not reach \c end,
32
* in contrast to the usual variant.
33
*
34
* \param begin1 Begin iterator of first sequence.
35
* \param end1 End iterator of first sequence.
36
* \param begin2 Begin iterator of second sequence.
37
* \param end2 End iterator of second sequence.
38
* \param target Target begin iterator.
39
* \param max_size Maximum number of elements to merge.
40
* \param comp Comparator.
41
* \return Output end iterator.
42
*/
43
template
<
typename
RandomAccessIterator1,
typename
RandomAccessIterator2,
44
typename
OutputIterator,
45
typename
DiffType,
typename
Comparator>
46
OutputIterator
47
merge_advance_usual
(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
48
RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
49
OutputIterator target, DiffType max_size,
50
Comparator comp) {
51
while
(begin1 != end1 && begin2 != end2 && max_size > 0)
52
{
53
// array1[i1] < array0[i0]
54
if
(comp(*begin2, *begin1))
55
*target++ = *begin2++;
56
else
57
*target++ = *begin1++;
58
--max_size;
59
}
60
61
if
(begin1 != end1)
62
{
63
target = std::copy(begin1, begin1 + max_size, target);
64
begin1 += max_size;
65
}
66
else
67
{
68
target = std::copy(begin2, begin2 + max_size, target);
69
begin2 += max_size;
70
}
71
return
target;
72
}
73
74
/*!
75
* Merge routine being able to merge only the \c max_size smallest elements.
76
*
77
* The \c begin iterators are advanced accordingly, they might not reach \c end,
78
* in contrast to the usual variant. Specially designed code should allow the
79
* compiler to generate conditional moves instead of branches.
80
*
81
* \param begin1 Begin iterator of first sequence.
82
* \param end1 End iterator of first sequence.
83
* \param begin2 Begin iterator of second sequence.
84
* \param end2 End iterator of second sequence.
85
* \param target Target begin iterator.
86
* \param max_size Maximum number of elements to merge.
87
* \param comp Comparator.
88
* \return Output end iterator.
89
*/
90
template
<
typename
RandomAccessIterator1,
typename
RandomAccessIterator2,
91
typename
OutputIterator,
92
typename
DiffType,
typename
Comparator>
93
OutputIterator
94
merge_advance_movc
(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
95
RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
96
OutputIterator target,
97
DiffType max_size, Comparator comp) {
98
using
ValueType1 =
typename
std::iterator_traits<RandomAccessIterator1>::value_type;
99
using
ValueType2 =
typename
std::iterator_traits<RandomAccessIterator2>::value_type;
100
101
while
(begin1 != end1 && begin2 != end2 && max_size > 0)
102
{
103
RandomAccessIterator1 next1 = begin1 + 1;
104
RandomAccessIterator2 next2 = begin2 + 1;
105
ValueType1 element1 = *begin1;
106
ValueType2 element2 = *begin2;
107
108
if
(comp(element2, element1))
109
{
110
element1 = element2;
111
begin2 = next2;
112
}
113
else
114
{
115
begin1 = next1;
116
}
117
118
*target = element1;
119
120
++target;
121
--max_size;
122
}
123
124
if
(begin1 != end1)
125
{
126
target = std::copy(begin1, begin1 + max_size, target);
127
begin1 += max_size;
128
}
129
else
130
{
131
target = std::copy(begin2, begin2 + max_size, target);
132
begin2 += max_size;
133
}
134
135
return
target;
136
}
137
138
/*!
139
* Merge routine being able to merge only the \c max_size smallest elements.
140
*
141
* The \c begin iterators are advanced accordingly, they might not reach \c end,
142
* in contrast to the usual variant. Static switch on whether to use the
143
* conditional-move variant.
144
*
145
* \param begin1 Begin iterator of first sequence.
146
* \param end1 End iterator of first sequence.
147
* \param begin2 Begin iterator of second sequence.
148
* \param end2 End iterator of second sequence.
149
* \param target Target begin iterator.
150
* \param max_size Maximum number of elements to merge.
151
* \param comp Comparator.
152
* \return Output end iterator.
153
*/
154
template
<
typename
RandomAccessIterator1,
typename
RandomAccessIterator2,
155
typename
OutputIterator,
156
typename
DiffType,
typename
Comparator>
157
OutputIterator
158
merge_advance
(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
159
RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
160
OutputIterator target,
161
DiffType max_size, Comparator comp) {
162
return
merge_advance_movc
(
163
begin1, end1, begin2, end2, target, max_size, comp);
164
}
165
166
//! \}
167
168
}
// namespace tlx
169
170
#endif
// !TLX_ALGORITHM_MERGE_ADVANCE_HEADER
171
172
/******************************************************************************/
tlx::merge_advance_movc
OutputIterator merge_advance_movc(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
Merge routine being able to merge only the max_size smallest elements.
Definition
merge_advance.hpp:94
tlx::merge_advance_usual
OutputIterator merge_advance_usual(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
Merge routine being able to merge only the max_size smallest elements.
Definition
merge_advance.hpp:47
tlx::merge_advance
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
Merge routine being able to merge only the max_size smallest elements.
Definition
merge_advance.hpp:158
tlx
Definition
exclusive_scan.hpp:17
tlx
algorithm
merge_advance.hpp
Generated on
for tlx by
1.17.0