tlx
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
23namespace 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 */
43template <typename RandomAccessIterator1, typename RandomAccessIterator2,
44 typename OutputIterator,
45 typename DiffType, typename Comparator>
46OutputIterator
47merge_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 */
90template <typename RandomAccessIterator1, typename RandomAccessIterator2,
91 typename OutputIterator,
92 typename DiffType, typename Comparator>
93OutputIterator
94merge_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 */
154template <typename RandomAccessIterator1, typename RandomAccessIterator2,
155 typename OutputIterator,
156 typename DiffType, typename Comparator>
157OutputIterator
158merge_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/******************************************************************************/
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.
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.
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.