Thrill  0.1
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 <[email protected]>
13  * Copyright (C) 2014-2018 Timo Bingmann <[email protected]>
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 /******************************************************************************/
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.
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.