00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef _GLIBCXX_PARALLEL_MERGE_H
00039 #define _GLIBCXX_PARALLEL_MERGE_H 1
00040
00041 #include <parallel/basic_iterator.h>
00042 #include <bits/stl_algo.h>
00043
00044 namespace __gnu_parallel
00045 {
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00060 typename OutputIterator, typename _DifferenceTp,
00061 typename Comparator>
00062 OutputIterator
00063 merge_advance_usual(RandomAccessIterator1& begin1,
00064 RandomAccessIterator1 end1,
00065 RandomAccessIterator2& begin2,
00066 RandomAccessIterator2 end2, OutputIterator target,
00067 _DifferenceTp max_length, Comparator comp)
00068 {
00069 typedef _DifferenceTp difference_type;
00070 while (begin1 != end1 && begin2 != end2 && max_length > 0)
00071 {
00072
00073 if (comp(*begin2, *begin1))
00074 *target++ = *begin2++;
00075 else
00076 *target++ = *begin1++;
00077 --max_length;
00078 }
00079
00080 if (begin1 != end1)
00081 {
00082 target = std::copy(begin1, begin1 + max_length, target);
00083 begin1 += max_length;
00084 }
00085 else
00086 {
00087 target = std::copy(begin2, begin2 + max_length, target);
00088 begin2 += max_length;
00089 }
00090 return target;
00091 }
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00109 typename OutputIterator, typename _DifferenceTp,
00110 typename Comparator>
00111 OutputIterator
00112 merge_advance_movc(RandomAccessIterator1& begin1,
00113 RandomAccessIterator1 end1,
00114 RandomAccessIterator2& begin2,
00115 RandomAccessIterator2 end2,
00116 OutputIterator target,
00117 _DifferenceTp max_length, Comparator comp)
00118 {
00119 typedef _DifferenceTp difference_type;
00120 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00121 value_type1;
00122 typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
00123 value_type2;
00124
00125 #if _GLIBCXX_ASSERTIONS
00126 _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
00127 #endif
00128
00129 while (begin1 != end1 && begin2 != end2 && max_length > 0)
00130 {
00131 RandomAccessIterator1 next1 = begin1 + 1;
00132 RandomAccessIterator2 next2 = begin2 + 1;
00133 value_type1 element1 = *begin1;
00134 value_type2 element2 = *begin2;
00135
00136 if (comp(element2, element1))
00137 {
00138 element1 = element2;
00139 begin2 = next2;
00140 }
00141 else
00142 begin1 = next1;
00143
00144 *target = element1;
00145
00146 ++target;
00147 --max_length;
00148 }
00149 if (begin1 != end1)
00150 {
00151 target = std::copy(begin1, begin1 + max_length, target);
00152 begin1 += max_length;
00153 }
00154 else
00155 {
00156 target = std::copy(begin2, begin2 + max_length, target);
00157 begin2 += max_length;
00158 }
00159 return target;
00160 }
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00177 typename OutputIterator, typename _DifferenceTp,
00178 typename Comparator>
00179 inline OutputIterator
00180 merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
00181 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
00182 OutputIterator target, _DifferenceTp max_length,
00183 Comparator comp)
00184 {
00185 _GLIBCXX_CALL(max_length)
00186
00187 return merge_advance_movc(begin1, end1, begin2, end2, target,
00188 max_length, comp);
00189 }
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00202 typename RandomAccessIterator3, typename Comparator>
00203 inline RandomAccessIterator3
00204 parallel_merge_advance(RandomAccessIterator1& begin1,
00205 RandomAccessIterator1 end1,
00206 RandomAccessIterator2& begin2,
00207
00208
00209 RandomAccessIterator2 end2,
00210 RandomAccessIterator3 target, typename
00211 std::iterator_traits<RandomAccessIterator1>::
00212 difference_type max_length, Comparator comp)
00213 { return merge_advance(begin1, end1, begin2, end2, target,
00214 max_length, comp); }
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231 template<typename RandomAccessIterator1, typename RandomAccessIterator3,
00232 typename Comparator>
00233 inline RandomAccessIterator3
00234 parallel_merge_advance(RandomAccessIterator1& begin1,
00235 RandomAccessIterator1 end1,
00236 RandomAccessIterator1& begin2,
00237 RandomAccessIterator1 end2,
00238 RandomAccessIterator3 target, typename
00239 std::iterator_traits<RandomAccessIterator1>::
00240 difference_type max_length, Comparator comp)
00241 {
00242 typedef typename
00243 std::iterator_traits<RandomAccessIterator1>::value_type value_type;
00244 typedef typename std::iterator_traits<RandomAccessIterator1>::
00245 difference_type difference_type1 ;
00246 typedef typename std::iterator_traits<RandomAccessIterator3>::
00247 difference_type difference_type3;
00248 typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1>
00249 iterator_pair;
00250
00251 std::pair<RandomAccessIterator1, RandomAccessIterator1>
00252 seqs[2] = { std::make_pair(begin1, end1),
00253 std::make_pair(begin2, end2) };
00254 RandomAccessIterator3
00255 target_end = parallel_multiway_merge
00256 < true, false>(
00257 seqs, seqs + 2, target, comp,
00258 multiway_merge_exact_splitting
00259 < true, iterator_pair*,
00260 Comparator, difference_type1>,
00261 max_length);
00262
00263 return target_end;
00264 }
00265 }
00266
00267 #endif