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