omptl_algorithm.h

omptl使用openmp多核库优化过的STL库

template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
			    const unsigned P)
{
	typedef typename
		::std::iterator_traits<ForwardIterator>::value_type value_type;
	return ::omptl::min_element(first, last, ::std::less<value_type>(), P);
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                            BinaryPredicate comp, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::max_element(first, last, comp);

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	ForwardIterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::max_element(partitions[t].first,
					 	partitions[t].second, comp);

	ForwardIterator result = results[0];
	for (unsigned int i = 1; i < P; ++i)
	{
		if ( (result != last) && (results[i] != last) &&
		      comp(*result, *results[i]) )
			result = results[i];
	}

	return result;
}

template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
			    const unsigned P)
{
	typedef typename
		::std::iterator_traits<ForwardIterator>::value_type value_type;
	return ::omptl::max_element(first, last, ::std::less<value_type>(), P);
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate,
	  class Iterator1Tag>
::std::pair<InputIterator1, InputIterator2>
_mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
         BinaryPredicate binary_pred, const unsigned P, Iterator1Tag,
	 ::std::input_iterator_tag)
{
	return ::std::mismatch(first1, last1, first2, binary_pred);
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate,
	  class Iterator2Tag>
::std::pair<InputIterator1, InputIterator2>
_mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
         BinaryPredicate binary_pred, const unsigned P, ::std::input_iterator_tag,
	 Iterator2Tag)
{
	return ::std::mismatch(first1, last1, first2, binary_pred);
}

template <class Iterator1, class Iterator2, class BinaryPredicate,
	  class Iterator1Tag, class Iterator2Tag>
::std::pair<Iterator1, Iterator2>
_mismatch(Iterator1 first1, Iterator1 last1, Iterator2 first2,
         BinaryPredicate binary_pred, const unsigned P,
	 Iterator1Tag, Iterator2Tag)
{
	if (_linear_serial_is_faster(first1, last1, P))
		return ::std::mismatch(first1, last1, first2, binary_pred);

	::std::pair<Iterator1, Iterator1> source_partitions[P];
	::omptl::_partition_range(first1, last1, source_partitions, P);

	Iterator2 dest_partitions[P];
	::omptl::_copy_partitions(source_partitions, first2,
				  dest_partitions, P);

	::std::pair<Iterator1, Iterator2> results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::mismatch(source_partitions[t].first,
					     source_partitions[t].second,
					     dest_partitions[t], binary_pred);

	// This could have been done more elegantly with select1st
	for (unsigned int i = 0; i < P - 1; ++i)
		if (results[i].first != source_partitions[i].second)
			return results[i];

	return results[P - 1];
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
::std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
         BinaryPredicate binary_pred, const unsigned P)
{
	return ::omptl::_mismatch(first1, last1, first2, binary_pred, P,
	typename ::std::iterator_traits<InputIterator1>::iterator_category(),
	typename ::std::iterator_traits<InputIterator2>::iterator_category());
}

template <class InputIterator1, class InputIterator2>
::std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
	 InputIterator2 first2, const unsigned P)
{
	typedef typename ::std::iterator_traits<InputIterator1>::value_type VT;
	return ::omptl::mismatch(first1, last1, first2, ::std::equal_to<VT>(), P);
}

// TODO How can this be parallelized ?
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last,
		 StrictWeakOrdering comp, const unsigned P)
{
	::std::nth_element(first, nth, last, comp);
}

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last, const unsigned P)
{
// 	typedef typename
// 		::std::iterator_traits<RandomAccessIterator>::value_type
// 	::std::less<VT>

	::std::nth_element(first, nth, last);
}

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
                  RandomAccessIterator middle,
                  RandomAccessIterator last,
                  StrictWeakOrdering comp, const unsigned P)
{
	const typename
	::std::iterator_traits<RandomAccessIterator>::difference_type
		N = ::std::distance(first, last);
	assert(N >= 0);

	if (2*(int)P < N)
	{
		::omptl::_pivot_range(first, last, *middle);
		::omptl::sort(first, middle, comp, P);
	}
	else
		::std::partial_sort(first, last, middle);
}

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                  RandomAccessIterator last, const unsigned P)
{
	
	typedef typename
		::std::iterator_traits<RandomAccessIterator>::value_type VT;
	::omptl::partial_sort(first, middle, last, ::std::less<VT>(), P);
}


// Not parallelized due to dependencies.
template <class InputIterator, class RandomAccessIterator,
          class StrictWeakOrdering>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last, StrictWeakOrdering comp,
		  const unsigned P)
{
	return ::std::partial_sort_copy(first, last,
					result_first, result_last, comp);
}

// Not parallelized due to dependencies.
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last, const unsigned P)
{
// 		::std::less<typename
// ::std::iterator_traits<InputIterator>::value_type>(),

	return ::std::partial_sort_copy(first, last,
					result_first, result_last);
}

// Not (yet) parallelized, not straightforward due to possible dependencies
// between subtasks.
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last,
			  Predicate pred, const unsigned P)
{
	return ::std::partition(first, last, pred);
}

// Not (yet) parallelized, not straightforward due to possible dependencies
// between subtasks.
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
                                 Predicate pred, const unsigned P)
{
	return ::std::stable_partition(first, last, pred);
}

template <class BidirectionalIterator, class StrictWeakOrdering>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
                      StrictWeakOrdering comp, const unsigned P)
{
	return ::std::next_permutation(first, last, comp);
}

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
                      const unsigned P)
{
// ::std::less<typename
// ::std::iterator_traits<BidirectionalIterator>::value_type>
	return ::std::next_permutation(first, last);
}

template <class BidirectionalIterator, class StrictWeakOrdering>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
                      StrictWeakOrdering comp, const unsigned P)
{
	return ::std::prev_permutation(first, last, comp);
}

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
                      const unsigned P)
{
// 		::std::less<typename
// ::std::iterator_traits<BidirectionalIterator>::value_type>(),
	return ::std::prev_permutation(first, last);
}


template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    const unsigned P)
{
	::std::random_shuffle(first, last);
}

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rgen, const unsigned P)
{
	::std::random_shuffle(first, last, rgen);
}

// Not (yet) parallelized, not straightforward due to possible dependencies
// between subtasks.
template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                       const T& value, const unsigned P)
{
	return ::std::remove(first, last, value);
}

// Not (yet) parallelized, not straightforward due to possible dependencies
// between subtasks.
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                          Predicate pred, const unsigned P)
{
	return ::std::remove_if(first, last, pred);
}

// Not parallelized due to possible complications with OutputIterators.
// No par_remove_copy exists due to possible dependencies between subtasks.
template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
                           OutputIterator result, const T& value,
			   const unsigned P)
{
	return ::std::remove_copy(first, last, result, value);
}

// Not parallelized due to possible complications with OutputIterators.
// No par_remove_copy_if exists due to possible dependencies between subtasks.
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
                              OutputIterator result, Predicate pred,
			      const unsigned P)
{
	return ::std::remove_copy(first, last, result, pred);
}

template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
             const T& new_value, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
	{
		::std::replace(first, last, old_value, new_value);
		return;
	}

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		::std::replace(partitions[t].first, partitions[t].second,
				old_value, new_value);
}

// TODO
template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
                            OutputIterator result, const T& old_value,
                            const T& new_value, const unsigned P)
{
	::std::replace_copy(first, last, result, old_value, new_value);
}

// TODO
template <class InputIterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(InputIterator first, InputIterator last,
                               OutputIterator result, Predicate pred,
                               const T& new_value, const unsigned P)
{
	::std::replace_copy_if(first, last, result, pred, new_value);
}

template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
                const T& new_value, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::replace_if(first, last, pred, new_value);

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		::std::replace_if(partitions[t].first, partitions[t].second,
				pred, new_value);
}

// TODO
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last,
	     const unsigned P = omp_get_max_threads())
{
	::std::reverse(first, last);
}

// TODO
template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
			    BidirectionalIterator last,
			    OutputIterator result,
			    const unsigned P = omp_get_max_threads())
{
	return ::std::reverse_copy(first, last, result);
}

// TODO
template <class ForwardIterator>
ForwardIterator rotate( ForwardIterator first, ForwardIterator middle,
			ForwardIterator last,
			const unsigned P = omp_get_max_threads())
{
	return ::std::rotate(first, middle, last);
}

// TODO
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
                           ForwardIterator last, OutputIterator result,
			   const unsigned P = omp_get_max_threads())
{
	return ::std::rotate(first, middle, last, result);
}

template <class ForwardIterator1, class ForwardIterator2,
	  class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2, ForwardIterator2 last2,
                        BinaryPredicate binary_pred, const unsigned P)
{
	if (_linear_serial_is_faster(first1, last1, P))
		return ::std::search(first1, last1, first2, last2,
					 binary_pred);

	::std::pair<ForwardIterator1, ForwardIterator1> source_partitions[P];
	::omptl::_partition_range(first1, last1, source_partitions, P);

	ForwardIterator1 results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::search(source_partitions[t].first,
					   source_partitions[t].second,
					   first2, last2, binary_pred);

	ForwardIterator1 *result = ::std::find_if(results, results + P,
		::std::bind2nd(::std::not_equal_to<ForwardIterator1>(),
				last1));

	if (result != results + P)
		return *result;

	return last1;
}

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2, ForwardIterator2 last2,
                        const unsigned P)
{
	typedef typename ::std::iterator_traits<ForwardIterator1>::value_type VT;
	return ::omptl::search(first1, last1, first2, last2,
				::std::equal_to<VT>(), P);
}

// TODO
template <class ForwardIterator, class Integer,
          class T, class BinaryPredicate>