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