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 _RAIter1, typename _RAIter2,
00054 typename _OutputIterator, typename _DifferenceTp,
00055 typename _Compare>
00056 _OutputIterator
00057 __merge_advance_usual(_RAIter1& __begin1, _RAIter1 __end1,
00058 _RAIter2& __begin2, _RAIter2 __end2,
00059 _OutputIterator __target,
00060 _DifferenceTp __max_length, _Compare __comp)
00061 {
00062 typedef _DifferenceTp _DifferenceType;
00063 while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
00064 {
00065
00066 if (__comp(*__begin2, *__begin1))
00067 *__target++ = *__begin2++;
00068 else
00069 *__target++ = *__begin1++;
00070 --__max_length;
00071 }
00072
00073 if (__begin1 != __end1)
00074 {
00075 __target = std::copy(__begin1, __begin1 + __max_length, __target);
00076 __begin1 += __max_length;
00077 }
00078 else
00079 {
00080 __target = std::copy(__begin2, __begin2 + __max_length, __target);
00081 __begin2 += __max_length;
00082 }
00083 return __target;
00084 }
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101 template<typename _RAIter1, typename _RAIter2,
00102 typename _OutputIterator, typename _DifferenceTp,
00103 typename _Compare>
00104 _OutputIterator
00105 __merge_advance_movc(_RAIter1& __begin1, _RAIter1 __end1,
00106 _RAIter2& __begin2, _RAIter2 __end2,
00107 _OutputIterator __target,
00108 _DifferenceTp __max_length, _Compare __comp)
00109 {
00110 typedef _DifferenceTp _DifferenceType;
00111 typedef typename std::iterator_traits<_RAIter1>::value_type
00112 _ValueType1;
00113 typedef typename std::iterator_traits<_RAIter2>::value_type
00114 _ValueType2;
00115
00116 #if _GLIBCXX_ASSERTIONS
00117 _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0);
00118 #endif
00119
00120 while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
00121 {
00122 _RAIter1 __next1 = __begin1 + 1;
00123 _RAIter2 __next2 = __begin2 + 1;
00124 _ValueType1 __element1 = *__begin1;
00125 _ValueType2 __element2 = *__begin2;
00126
00127 if (__comp(__element2, __element1))
00128 {
00129 __element1 = __element2;
00130 __begin2 = __next2;
00131 }
00132 else
00133 __begin1 = __next1;
00134
00135 *__target = __element1;
00136
00137 ++__target;
00138 --__max_length;
00139 }
00140 if (__begin1 != __end1)
00141 {
00142 __target = std::copy(__begin1, __begin1 + __max_length, __target);
00143 __begin1 += __max_length;
00144 }
00145 else
00146 {
00147 __target = std::copy(__begin2, __begin2 + __max_length, __target);
00148 __begin2 += __max_length;
00149 }
00150 return __target;
00151 }
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167 template<typename _RAIter1, typename _RAIter2,
00168 typename _OutputIterator, typename _DifferenceTp,
00169 typename _Compare>
00170 inline _OutputIterator
00171 __merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
00172 _RAIter2& __begin2, _RAIter2 __end2,
00173 _OutputIterator __target, _DifferenceTp __max_length,
00174 _Compare __comp)
00175 {
00176 _GLIBCXX_CALL(__max_length)
00177
00178 return __merge_advance_movc(__begin1, __end1, __begin2, __end2,
00179 __target, __max_length, __comp);
00180 }
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192 template<typename _RAIter1, typename _RAIter2,
00193 typename _RAIter3, typename _Compare>
00194 inline _RAIter3
00195 __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
00196 _RAIter2& __begin2,
00197
00198
00199 _RAIter2 __end2, _RAIter3 __target, typename
00200 std::iterator_traits<_RAIter1>::
00201 difference_type __max_length, _Compare __comp)
00202 { return __merge_advance(__begin1, __end1, __begin2, __end2, __target,
00203 __max_length, __comp); }
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220 template<typename _RAIter1, typename _RAIter3,
00221 typename _Compare>
00222 inline _RAIter3
00223 __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
00224 _RAIter1& __begin2, _RAIter1 __end2,
00225 _RAIter3 __target, typename
00226 std::iterator_traits<_RAIter1>::
00227 difference_type __max_length, _Compare __comp)
00228 {
00229 typedef typename
00230 std::iterator_traits<_RAIter1>::value_type _ValueType;
00231 typedef typename std::iterator_traits<_RAIter1>::
00232 difference_type _DifferenceType1 ;
00233 typedef typename std::iterator_traits<_RAIter3>::
00234 difference_type _DifferenceType3;
00235 typedef typename std::pair<_RAIter1, _RAIter1>
00236 _IteratorPair;
00237
00238 _IteratorPair __seqs[2] = { std::make_pair(__begin1, __end1),
00239 std::make_pair(__begin2, __end2) };
00240 _RAIter3 __target_end = parallel_multiway_merge
00241 < true, false>
00242 (__seqs, __seqs + 2, __target, multiway_merge_exact_splitting
00243 < true, _IteratorPair*,
00244 _Compare, _DifferenceType1>, __max_length, __comp,
00245 omp_get_max_threads());
00246
00247 return __target_end;
00248 }
00249 }
00250
00251 #endif