omptl_algorithm.h

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

ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Integer count, const T& value,
                         BinaryPredicate binary_pred, const unsigned P)
{
	return ::std::search_n(first, last, count, value, binary_pred);
}

template <class ForwardIterator, class Integer, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
			 Integer count, const T& value, const unsigned P)
{
// ::std::equal_to<typename
// ::std::iterator_traits<ForwardIterator>::value_type>
	return ::std::search_n(first, last, count, value);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, InputIterator2 last2,
				OutputIterator result, StrictWeakOrdering comp,
				const unsigned P)
{
	return ::std::set_difference(first1, last1,
				     first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, InputIterator2 last2,
				OutputIterator result, const unsigned P)
{
	return ::std::set_difference(first1, last1, first2, last2, result);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, InputIterator2 last2,
				OutputIterator result, StrictWeakOrdering comp,
			 	const unsigned P)
{
	return ::std::set_intersection( first1, last1,
					first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, InputIterator2 last2,
				OutputIterator result, const unsigned P)
{
	return ::std::set_intersection( first1, last1, first2, last2, result);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, StrictWeakOrdering comp,
			 const unsigned P)
{
	return ::std::set_symmetric_difference( first1, last1,
						first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, const unsigned P)
{
	return ::std::set_symmetric_difference( first1, last1,
						first2, last2, result);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, StrictWeakOrdering comp,
			 const unsigned P)
{
	return ::std::set_union(first1, last1, first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, const unsigned P)
{
	return ::std::set_union(first1, last1, first2, last2, result);
}

template<typename RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
	  StrictWeakOrdering comp, const unsigned P = omp_get_max_threads())
{
	if ( ::omptl::_nlogn_serial_is_faster(first, last, P) )
	{
		::std::sort(first, last, comp);
		return;
	}

	// Generate pivots
	typedef typename
	    ::std::iterator_traits<RandomAccessIterator>::value_type value_type;

	::std::vector<value_type> pivots;
	_find_pivots(first, last, pivots, P);

	// Sort sufficiently to respect pivot order
	::std::pair<RandomAccessIterator, RandomAccessIterator> partitions[P];
	::omptl::_partition_range_by_pivots(first, last, pivots,
					    partitions, comp, P);

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

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

template<typename RandomAccessIterator, class StrictWeakOrdering>
void _par_stable_sort(RandomAccessIterator first, RandomAccessIterator last,
	StrictWeakOrdering comp, const unsigned P = omp_get_max_threads())
{
	if ( ::omptl::_nlogn_serial_is_faster(first, last, P) )
	{
		::std::stable_sort(first, last, comp);
		return;
	}

	// Generate pivots
	::std::vector<typename 
		::std::iterator_traits<RandomAccessIterator>::value_type> 
			pivots;
	_find_pivots(first, last, pivots, P);

	// Sort sufficiently to respect pivot order
	::std::pair<RandomAccessIterator, RandomAccessIterator> partitions[P];
	::omptl::_partition_range_stable_by_pivots(first, last, pivots,
						   partitions, comp, P);

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

template<typename RandomAccessIterator, class StrictWeakOrdering>
void _stable_sort(RandomAccessIterator first, RandomAccessIterator last,
	StrictWeakOrdering comp, const unsigned P = omp_get_max_threads())
{
	::std::stable_sort(first, last, comp);
}

template<typename RandomAccessIterator>
void _stable_sort(RandomAccessIterator first, RandomAccessIterator last,
	std::less<typename ::std::iterator_traits<RandomAccessIterator>::value_type>
	 comp, const unsigned P)
{
	::omptl::_par_stable_sort(first, last, comp, P);
}

// template<typename RandomAccessIterator>
// void _stable_sort(RandomAccessIterator first, RandomAccessIterator last,
// 	std::greater<
// 	typename ::std::iterator_traits<RandomAccessIterator>::value_type> comp,
//  	const unsigned P)
// {
// 	::omptl::_par_stable_sort(first, last, comp, P);
// }

template<typename RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
	StrictWeakOrdering comp, const unsigned P = omp_get_max_threads())
{
}

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

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

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

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

	ForwardIterator2 results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::swap_ranges(source_partitions[t].first,
					     source_partitions[t].second,
					     dest_partitions[t]);

	return results[P - 1];
}

template <class InputIterator, class OutputIterator, class UnaryFunction,
	 class IteratorInTag>
OutputIterator _transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryFunction op,
			 const unsigned P, IteratorInTag,
			 ::std::output_iterator_tag)
{
	return ::std::transform(first, last, result, op);
}

template <class InputIterator, class OutputIterator, class UnaryFunction,
	 class IteratorOutTag>
OutputIterator _transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryFunction op,
			 const unsigned P, ::std::input_iterator_tag,
			 IteratorOutTag)
{
	return ::std::transform(first, last, result, op);
}

template <class IteratorIn, class IteratorOut, class UnaryFunction,
	 class IteratorInTag, class IteratorOutTag>
IteratorOut _transform(IteratorIn first, IteratorIn last,
			IteratorOut result, UnaryFunction op,
			const unsigned P, IteratorInTag, IteratorOutTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::transform(first, last, result, op);

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

	IteratorOut dest_partitions[P];
	::omptl::_copy_partitions(source_partitions, result,
				  dest_partitions, P);

	IteratorOut results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::transform(source_partitions[t].first,
					     source_partitions[t].second,
					     dest_partitions[t], op);

	return results[P - 1];
}

template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryFunction op,
			 const unsigned P)
{
	return ::omptl::_transform(first, last, result, op, P,
	typename ::std::iterator_traits<InputIterator>::iterator_category(),
	typename ::std::iterator_traits<OutputIterator>::iterator_category());
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class BinaryFunction, class Iterator2Tag, class IteratorOutTag>
OutputIterator _transform(InputIterator1 first1, InputIterator1 last1,
			InputIterator2 first2, OutputIterator result,
			BinaryFunction binary_op, const unsigned P,
			::std::input_iterator_tag, Iterator2Tag, IteratorOutTag)
{
	return ::std::transform(first1, last1, first2, result, binary_op);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class BinaryFunction, class Iterator1Tag, class IteratorOutTag>
OutputIterator _transform(InputIterator1 first1, InputIterator1 last1,
			InputIterator2 first2, OutputIterator result,
			BinaryFunction binary_op, const unsigned P,
			Iterator1Tag, ::std::input_iterator_tag, IteratorOutTag)
{
	return ::std::transform(first1, last1, first2, result, binary_op);
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class BinaryFunction, class Iterator1Tag, class Iterator2Tag>
OutputIterator _transform(InputIterator1 first1, InputIterator1 last1,
			InputIterator2 first2, OutputIterator result,
			BinaryFunction binary_op, const unsigned P,
			Iterator1Tag, Iterator2Tag, ::std::output_iterator_tag)
{
	return ::std::transform(first1, last1, first2, result, binary_op);
}

template <class Iterator1, class Iterator2, class IteratorOut,
          class BinaryFunction, class Iterator1Tag, class Iterator2Tag,
	  class IteratorOutTag>
IteratorOut _transform(Iterator1 first1, Iterator1 last1,
			Iterator2 first2, IteratorOut result,
			BinaryFunction binary_op, const unsigned P,
			Iterator1Tag, Iterator2Tag, IteratorOutTag)
{
	if (_linear_serial_is_faster(first1, last1, P))
		return ::std::transform(first1, last1, first2,
					 result, binary_op);

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

	Iterator2 source_partitions2[P];
	::omptl::_copy_partitions(source_partitions1, first2,
				 source_partitions2 , P);

	IteratorOut dest_partitions[P];
	::omptl::_copy_partitions(source_partitions1, result,
				  dest_partitions, P);

	IteratorOut results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::transform(source_partitions1[t].first,
					      source_partitions1[t].second,
					      source_partitions2[t],
					      dest_partitions[t], binary_op);

	return results[P - 1];
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, OutputIterator result,
                         BinaryFunction binary_op, const unsigned P)
{
	return ::omptl::_transform(first1, last1, first2, result, binary_op, P,
	typename ::std::iterator_traits<InputIterator1>::iterator_category(),
	typename ::std::iterator_traits<InputIterator2>::iterator_category(),
	typename ::std::iterator_traits<OutputIterator>::iterator_category());
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                       BinaryPredicate binary_pred, const unsigned P)
{
	return ::std::unique(first, last, binary_pred);
}

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
		       const unsigned P)
{
// 		       ::std::equal_to<typename
// ::std::iterator_traits<ForwardIterator>::value_type>(),
	return ::std::unique(first, last);
}

template <class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryPredicate binary_pred,
		       const unsigned P)
{
	return ::std::unique_copy(first, last, result, binary_pred);
}

template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result,
		       const unsigned P)
{
// 		       ::std::equal_to<typename
// ::std::iterator_traits<InputIterator>::value_type>(),
	return ::std::unique_copy(first, last, result);
}

template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, StrictWeakOrdering comp,
			    const unsigned P)
{
	if (_logn_serial_is_faster(first, last, P))
		return ::std::upper_bound(first, last, value, 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::upper_bound(partitions[t].first,
					 	partitions[t].second,
						value, comp);

	// There has to be a better way...
	for (unsigned int i = P - 1; i > 0; --i)
		if (results[i] != last)
			return results[i];

	return results[0];
}

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

} /* namespace omptl */

#endif /* OMPTL_ALGORITHM_H */