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 /******************************************************************************/
173