omptl_algorithm.h

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

// Copyright (C) 2006 Fokko Beekhof
// Email contact: [e-mail]

// The OMPTL library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.

// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA


#ifndef OMPTL_ALGORITHM_H
#define OMPTL_ALGORITHM_H

#ifndef OMPTL_ALGORITHM
#warning <omptl/omptl_algorithm> not included. Do not include \
	<omptl_algorithm.h>!
#include <omptl/omptl_algorithm>
#endif /* OMPTL_ALGORITHM */

#include <omptl/omptl_tools.h>
#include <omptl/omptl_numeric>

#include <iterator>

namespace omptl
{

/*
 * Not (yet) paralellized due to data dependance.
 */
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
			      const unsigned P)
{
	return ::std::adjacent_find(first, last);
}

/*
 * Not (yet) paralellized due to data dependance.
 */
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                              BinaryPredicate binary_pred, const unsigned P)
{
	return ::std::adjacent_find(first, last, binary_pred);
}

template <class ForwardIterator, class T, class StrictWeakOrdering>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
                   StrictWeakOrdering comp, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::binary_search(first, last, value, comp);

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

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

	return ::std::count(static_cast<bool *>(results), results + P, false);
}

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

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

	::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::copy(source_partitions[t].first,
					     source_partitions[t].second,
					     dest_partitions[t]);

	return results[P - 1];
}

template <class InputIterator, class OutputIterator, class InputIteratorTag>
OutputIterator _copy(InputIterator first, InputIterator last,
		    OutputIterator result, const unsigned P,
		    InputIteratorTag, ::std::output_iterator_tag)
{
	return ::std::copy(first, last, result);
}

template <class InputIterator, class OutputIterator, class OutputIteratorTag>
OutputIterator _copy(InputIterator first, InputIterator last,
		    OutputIterator result, const unsigned P,
		    ::std::input_iterator_tag, OutputIteratorTag)
{
	return ::std::copy(first, last, result);
}

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

template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
                                     BidirectionalIterator1 last,
                                     BidirectionalIterator2 result,
				     const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::copy_backward(first, last, result);

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

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

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

	return results[P - 1];
}

template <class Iterator, class EqualityComparable, class IteratorTag>
typename ::std::iterator_traits<Iterator>::difference_type
_count(Iterator first, Iterator last, const EqualityComparable& value,
	const unsigned P, ::std::input_iterator_tag)
{
	return ::std::count(first, last, value);
}

template <class Iterator, class EqualityComparable, class IteratorTag>
typename ::std::iterator_traits<Iterator>::difference_type
_count(Iterator first, Iterator last,
      const EqualityComparable& value, const unsigned P, IteratorTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::count(first, last, value);

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

	typedef typename ::std::iterator_traits<Iterator>::difference_type Tdif;
	Tdif results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::count(partitions[t].first,
					 partitions[t].second, value);

	return ::std::accumulate(static_cast<Tdif *>(results),
					 results + P, 0);
}

template <class InputIterator, class EqualityComparable>
typename ::std::iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last,
      const EqualityComparable& value, const unsigned P)
{
	return ::omptl::_count(first, last, value, P,
	typename ::std::iterator_traits<InputIterator>::iterator_category());
}

template <class InputIterator, class EqualityComparable, class Size>
void count(InputIterator first, InputIterator last,
           const EqualityComparable& value, Size& n, const unsigned P)
{
	n = ::omptl::count(first, last, value, P);
}


template <class InputIterator, class Predicate>
typename ::std::iterator_traits<InputIterator>::difference_type
_count_if(InputIterator first, InputIterator last, Predicate pred,
	 const unsigned P, ::std::input_iterator_tag)
{
	return ::std::count_if(first, last, pred);
}

template <class Iterator, class Predicate, class IteratorTag>
typename ::std::iterator_traits<Iterator>::difference_type
_count_if(Iterator first, Iterator last, Predicate pred,
	 const unsigned P, IteratorTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::count_if(first, last, pred);

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

	typedef typename ::std::iterator_traits<Iterator>::difference_type Tdif;
	Tdif results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::count_if(partitions[t].first,
					 partitions[t].second, pred);

	return ::omptl::accumulate<Tdif>(&results[0], results + P, Tdif(0));
}

template <class InputIterator, class Predicate>
typename ::std::iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last,
	 Predicate pred, const unsigned P)
{
	return ::omptl::_count_if(first, last, pred,
	typename ::std::iterator_traits<InputIterator>::iterator_category());
}

template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last,
              Predicate pred, Size& n, const unsigned P)
{
	n = ::omptl::count_if(first, last, pred, P);
}

/*
template <class InputIterator1, class InputIterator2,
          class BinaryPredicate, class InputIterator1Tag,
	  class InputIterator2Tag>
bool _equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, BinaryPredicate binary_pred, const unsigned P,
	  InputIterator1Tag, InputIterator2Tag)
{
	return ::std::equal(first1, last1, first2, binary_pred);
}

template <class Iterator1, class Iterator2, class BinaryPredicate>
bool _equal(Iterator1 first1, Iterator1 last1,
	    Iterator2 first2, BinaryPredicate binary_pred,
	    const unsigned P, std::random_access_iterator_tag,
	    std::random_access_iterator_tag)
{
	if (_linear_serial_is_faster(first1, last1, P))
		return ::std::equal(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);

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

	return ::std::count(static_cast<bool *>(results), results + P, false);
}
*/

template <class InputIterator1, class InputIterator2,
          class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, BinaryPredicate binary_pred, const unsigned P)
{
	return ::std::equal(first1, last1, first2, binary_pred);

// 	return ::omptl::_equal(first1, last1, first2, binary_pred,
// 	typename ::std::iterator_traits<InputIterator1>::iterator_category(),
// 	typename ::std::iterator_traits<InputIterator2>::iterator_category());

}

template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, const unsigned P)
{
	typedef typename ::std::iterator_traits<InputIterator1>::value_type VT;

	return ::omptl::equal(first1, last1, first2, ::std::equal_to<VT>());
}

//TODO
template <class ForwardIterator, class T, class StrictWeakOrdering>
::std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
            StrictWeakOrdering comp, const unsigned P)
{
	return ::std::equal_range(first, last, value, comp);
}

template <class ForwardIterator, class T>
::std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
            const unsigned P)
{
	typedef typename ::std::iterator_traits<ForwardIterator>::value_type VT;

// 	return ::omptl::equal_range(first, last, value, ::std::less<VT>(), P);
	return ::std::equal_range(first, last, value);
}

template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last,
	  const T& value, const unsigned P)
{
	assert(P > 0u);
	if (_linear_serial_is_faster(first, last, P))
	{
		::std::fill(first, last, value);
		return;
	}
	assert(std::distance(first, last) >= 0);
	assert(2*(int)P <= std::distance(first, last));

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

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

template <class Iterator, class Size, class T, class IteratorTag>
Iterator _fill_n(Iterator first, Size n, const T& value,
			const unsigned P, IteratorTag)
{
	assert(P > 0u);
	Iterator last = first;
	std::advance(last, n);
	if (_linear_serial_is_faster(first, last, P))
		return ::std::fill_n(first, n, value);

	const Size range = (n / P) + ( (n % P) ? 1 : 0 );
	Size ranges[P];
	::std::fill_n(&ranges[0], P - 1, range);
	ranges[P - 1] = n - (P - 1) * range;

	Iterator source_partitions[P];
	source_partitions[0] = first;
	for (unsigned int i = 1; i < P; ++i)
	{
		source_partitions[i] = source_partitions[i - 1];
		::std::advance(source_partitions[i], range);
	}

	Iterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::fill_n(source_partitions[t], ranges[t],
					   value);

	return results[P - 1];
}

template <class OutputIterator, class Size, class T>
OutputIterator _fill_n(OutputIterator first, Size n, const T& value,
			const unsigned P, ::std::output_iterator_tag)
{
	return ::std::fill_n(first, n, value);
}

template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n,
		      const T& value, const unsigned P)
{
	return ::omptl::_fill_n(first, n, value, P,
	typename ::std::iterator_traits<OutputIterator>::iterator_category());
}

template<class InputIterator, class EqualityComparable>
InputIterator _find(InputIterator first, InputIterator last,
                   const EqualityComparable& value, const unsigned P,
		   ::std::input_iterator_tag)
{
	return std::find(first, last, value);
}

template<class Iterator, class EqualityComparable, class IteratorTag>
Iterator _find(Iterator first, Iterator last, const EqualityComparable& value,
		const unsigned P, IteratorTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::find(first, last, value);

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

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

	Iterator *result = ::std::find_if(results, results + P,