32 #ifndef _GLIBCXX_PARALLEL_MERGE_H
33 #define _GLIBCXX_PARALLEL_MERGE_H 1
38 namespace __gnu_parallel
53 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
54 typename OutputIterator,
typename _DifferenceTp,
58 RandomAccessIterator1 end1,
59 RandomAccessIterator2& begin2,
60 RandomAccessIterator2 end2, OutputIterator target,
61 _DifferenceTp max_length, Comparator comp)
63 typedef _DifferenceTp difference_type;
64 while (begin1 != end1 && begin2 != end2 && max_length > 0)
67 if (comp(*begin2, *begin1))
68 *target++ = *begin2++;
70 *target++ = *begin1++;
76 target = std::copy(begin1, begin1 + max_length, target);
81 target = std::copy(begin2, begin2 + max_length, target);
102 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
103 typename OutputIterator,
typename _DifferenceTp,
107 RandomAccessIterator1 end1,
108 RandomAccessIterator2& begin2,
109 RandomAccessIterator2 end2,
110 OutputIterator target,
111 _DifferenceTp max_length, Comparator comp)
113 typedef _DifferenceTp difference_type;
114 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
116 typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
119 #if _GLIBCXX_ASSERTIONS
120 _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
123 while (begin1 != end1 && begin2 != end2 && max_length > 0)
125 RandomAccessIterator1 next1 = begin1 + 1;
126 RandomAccessIterator2 next2 = begin2 + 1;
127 value_type1 element1 = *begin1;
128 value_type2 element2 = *begin2;
130 if (comp(element2, element1))
145 target = std::copy(begin1, begin1 + max_length, target);
146 begin1 += max_length;
150 target = std::copy(begin2, begin2 + max_length, target);
151 begin2 += max_length;
170 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
171 typename OutputIterator,
typename _DifferenceTp,
173 inline OutputIterator
175 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
176 OutputIterator target, _DifferenceTp max_length,
195 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
196 typename RandomAccessIterator3,
typename Comparator>
197 inline RandomAccessIterator3
199 RandomAccessIterator1 end1,
200 RandomAccessIterator2& begin2,
203 RandomAccessIterator2 end2,
204 RandomAccessIterator3 target,
typename
206 difference_type max_length, Comparator comp)
225 template<
typename RandomAccessIterator1,
typename RandomAccessIterator3,
227 inline RandomAccessIterator3
229 RandomAccessIterator1 end1,
230 RandomAccessIterator1& begin2,
231 RandomAccessIterator1 end2,
232 RandomAccessIterator3 target,
typename
234 difference_type max_length, Comparator comp)
237 std::iterator_traits<RandomAccessIterator1>::value_type value_type;
239 difference_type difference_type1 ;
241 difference_type difference_type3;
246 seqs[2] = { std::make_pair(begin1, end1),
247 std::make_pair(begin2, end2) };
248 RandomAccessIterator3
251 seqs, seqs + 2, target,
253 <
true, iterator_pair*,
254 Comparator, difference_type1>,
255 max_length, comp, omp_get_max_threads());
pair holds two objects of arbitrary type.
OutputIterator merge_advance_movc(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
void multiway_merge_exact_splitting(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
Exact splitting for parallel multiway-merge routine.
RandomAccessIterator3 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Splitter splitter, _DifferenceTp length, Comparator comp, thread_index_t num_threads)
Parallel multi-way merge routine.
A pair of iterators. The usual iterator operations are applied to both child iterators.
OutputIterator merge_advance_usual(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.