merge.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/parallel/merge.h
 *
 * Parallel implementation of std::merge().
 * Extracted from MCSTL - http://algo2.iti.uni-karlsruhe.de/singler/mcstl/
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2007 Johannes Singler <[email protected]>
 * Copyright (C) 2014 Timo Bingmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_PARALLEL_MERGE_HEADER
#define STXXL_PARALLEL_MERGE_HEADER

#include <stxxl/bits/namespace.h>
#include <stxxl/bits/parallel/compiletime_settings.h>
#include <iterator>
#include <cassert>

STXXL_BEGIN_NAMESPACE

namespace parallel {

/*!
 * Merge routine being able to merge only the \c max_length smallest elements.
 *
 * The \c begin iterators are advanced accordingly, they might not reach \c
 * end, in contrast to the usual variant.
 *
 * \param begin1 Begin iterator of first sequence.
 * \param end1 End iterator of first sequence.
 * \param begin2 Begin iterator of second sequence.
 * \param end2 End iterator of second sequence.
 * \param target Target begin iterator.
 * \param max_length Maximum number of elements to merge.
 * \param comp Comparator.
 * \return Output end iterator.
 */
template <typename RandomAccessIterator1, typename RandomAccessIterator2,
 typename OutputIterator,
 typename DiffType, typename Comparator>
OutputIterator
merge_advance_usual(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 OutputIterator target, DiffType max_length,
 Comparator comp)
{
 while (begin1 != end1 && begin2 != end2 && max_length > 0)
 {
 // array1[i1] < array0[i0]
 if (comp(*begin2, *begin1))
 *target++ = *begin2++;
 else
 *target++ = *begin1++;
 --max_length;
 }

 if (begin1 != end1)
 {
 target = std::copy(begin1, begin1 + max_length, target);
 begin1 += max_length;
 }
 else
 {
 target = std::copy(begin2, begin2 + max_length, target);
 begin2 += max_length;
 }
 return target;
}

/*!
 * Merge routine being able to merge only the \c max_length smallest elements.
 *
 * The \c begin iterators are advanced accordingly, they might not reach \c
 * end, in contrast to the usual variant. Specially designed code should allow
 * the compiler to generate conditional moves instead of branches.
 *
 * \param begin1 Begin iterator of first sequence.
 * \param end1 End iterator of first sequence.
 * \param begin2 Begin iterator of second sequence.
 * \param end2 End iterator of second sequence.
 * \param target Target begin iterator.
 * \param max_length Maximum number of elements to merge.
 * \param comp Comparator.
 * \return Output end iterator.
 */
template <typename RandomAccessIterator1, typename RandomAccessIterator2,
 typename OutputIterator,
 typename DiffType, typename Comparator>
OutputIterator
merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 OutputIterator target,
 DiffType max_length, Comparator comp)
{
 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type ValueType1;
 typedef typename std::iterator_traits<RandomAccessIterator2>::value_type ValueType2;

 while (begin1 != end1 && begin2 != end2 && max_length > 0)
 {
 RandomAccessIterator1 next1 = begin1 + 1;
 RandomAccessIterator2 next2 = begin2 + 1;
 ValueType1 element1 = *begin1;
 ValueType2 element2 = *begin2;

 if (comp(element2, element1))
 {
 element1 = element2;
 begin2 = next2;
 }
 else
 {
 begin1 = next1;
 }

 *target = element1;

 ++target;
 --max_length;
 }

 if (begin1 != end1)
 {
 target = std::copy(begin1, begin1 + max_length, target);
 begin1 += max_length;
 }
 else
 {
 target = std::copy(begin2, begin2 + max_length, target);
 begin2 += max_length;
 }

 return target;
}

/*!
 * Merge routine being able to merge only the \c max_length smallest elements.
 *
 * The \c begin iterators are advanced accordingly, they might not reach \c
 * end, in contrast to the usual variant. Static switch on whether to use the
 * conditional-move variant.
 *
 * \param begin1 Begin iterator of first sequence.
 * \param end1 End iterator of first sequence.
 * \param begin2 Begin iterator of second sequence.
 * \param end2 End iterator of second sequence.
 * \param target Target begin iterator.
 * \param max_length Maximum number of elements to merge.
 * \param comp Comparator.
 * \return Output end iterator.
 */
template <typename RandomAccessIterator1, typename RandomAccessIterator2,
 typename OutputIterator,
 typename DiffType, typename Comparator>
OutputIterator
merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 OutputIterator target,
 DiffType max_length, Comparator comp)
{
 STXXL_PARALLEL_PCALL(max_length);

 return merge_advance_movc(begin1, end1, begin2, end2, target, max_length, comp);
}

/*!
 * Merge routine fallback to sequential in case the iterators of the two input
 * sequences are of different type.
 *
 * \param begin1 Begin iterator of first sequence.
 * \param end1 End iterator of first sequence.
 * \param begin2 Begin iterator of second sequence.
 * \param end2 End iterator of second sequence.
 * \param target Target begin iterator.
 * \param max_length Maximum number of elements to merge.
 * \param comp Comparator.
 * \return Output end iterator.
 */
template <typename RandomAccessIterator1, typename RandomAccessIterator2,
 typename RandomAccessIterator3, typename Comparator>
RandomAccessIterator3
parallel_merge_advance(
 RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 // different iterators, parallel implementation not available
 RandomAccessIterator3 target,
 typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length,
 Comparator comp)
{
 return merge_advance(begin1, end1, begin2, end2, target, max_length, comp);
}

/*!
 * Parallel merge routine being able to merge only the \c max_length smallest
 * elements.
 *
 * The \c begin iterators are advanced accordingly, they might not reach \c
 * end, in contrast to the usual variant. The functionality is projected onto
 * parallel_multiway_merge.
 *
 * \param begin1 Begin iterator of first sequence.
 * \param end1 End iterator of first sequence.
 * \param begin2 Begin iterator of second sequence.
 * \param end2 End iterator of second sequence.
 * \param target Target begin iterator.
 * \param max_length Maximum number of elements to merge.
 * \param comp Comparator.
 * \return Output end iterator.
 */
template <typename RandomAccessIterator1, typename RandomAccessIterator3,
 typename Comparator>
RandomAccessIterator3
parallel_merge_advance(
 RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 RandomAccessIterator1& begin2, RandomAccessIterator1 end2,
 RandomAccessIterator3 target,
 typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length,
 Comparator comp)
{
 std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2] = {
 std::make_pair(begin1, end1), std::make_pair(begin2, end2)
 };
 RandomAccessIterator3 target_end = parallel_multiway_merge(
 seqs, seqs + 2, target, comp, max_length, true, false
 );

 return target_end;
}

} // namespace parallel

STXXL_END_NAMESPACE

#endif // !STXXL_PARALLEL_MERGE_HEADER