benchmark_algorithms.h

/*
    Copyright 2007-2008 Adobe Systems Incorporated
    Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
    or a copy at http://stlab.adobe.com/licenses.html)
    
    Shared source file for algorithms used in multiple benchmark files
*/

namespace benchmark {

/******************************************************************************/

template <typename Iterator>
bool is_sorted(Iterator first, Iterator last) {
	Iterator prev = first;
	first++;
	while (first != last) {
		if ( *first++ < *prev++)
			return false;
	}
	return true;
}

/******************************************************************************/

template <typename Iterator, typename T>
void fill(Iterator first, Iterator last, T value) {
	while (first != last) *first++ = value;
}

/******************************************************************************/

template <typename Iterator, typename T>
void fill_random(Iterator first, Iterator last) {
	while (first != last) {
		*first++ = static_cast<T>( rand() );
	}
}

/******************************************************************************/

template <class Iterator, class T>
void fill_descending(Iterator first, Iterator last, unsigned count) {
	while (first != last) {
		*first++ = static_cast<T>( --count );
	}
}

/******************************************************************************/

template <typename Iterator1, typename Iterator2>
void copy(Iterator1 firstSource, Iterator1 lastSource, Iterator2 firstDest) {
	while (firstSource != lastSource) *(firstDest++) = *(firstSource++);
}

/******************************************************************************/

template <class Iterator, class Swapper>
void reverse(Iterator begin, Iterator end, Swapper doswap)
{
	while (begin != end)
	{
		--end;
		if (begin == end)
			break;
		doswap(begin, end);
		++begin;
	}
}

/******************************************************************************/

// our accumulator function template, using iterators or pointers
template <typename Iterator, typename Number>
Number accumulate(Iterator first, Iterator last, Number result) {
	while (first != last) result =  result + *first++;
	return result;
}

/******************************************************************************/

template <typename Iterator, typename T>
void insertionSort( Iterator begin, Iterator end )
{
	Iterator p = begin;
	p++;

	while ( p != end ) {
		T tmp = *p;
		Iterator j = p;
		Iterator prev = j;

		for (  ; j != begin && tmp < *--prev; --j ) {
			*j = *prev;
		}

		*j = tmp;
		p++;
	}
}

/******************************************************************************/

template<typename Iterator, typename T>
void quicksort(Iterator begin, Iterator end)
{
	if ( (end - begin) > 1 ) {

		T middleValue = *begin;
		Iterator left = begin;
		Iterator right = end;

		for(;;) {

			while ( middleValue < *(--right) );
			if ( !(left < right ) ) break;
			
			while ( *(left) < middleValue )
				++left;
			if ( !(left < right ) ) break;

			// swap
			T temp = *right;
			*right = *left;
			*left = temp;
		}

		quicksort<Iterator,T>( begin, right + 1 );
		quicksort<Iterator,T>( right + 1, end );
	}
}

/******************************************************************************/

template<typename Iterator, typename T, class Swapper>
void quicksort(Iterator begin, Iterator end, Swapper doswap)
{
	if ( (end - begin) > 1 ) {

		T middleValue = *begin;
		Iterator left = begin;
		Iterator right = end;

		for(;;) {

			while ( middleValue < *(--right) );
			if ( !(left < right ) ) break;
			
			while ( *(left) < middleValue )
				++left;
			if ( !(left < right ) ) break;

			// swap
			doswap( right, left );
		}

		quicksort<Iterator,T, Swapper>( begin, right + 1, doswap );
		quicksort<Iterator,T, Swapper>( right + 1, end, doswap );
	}
}

/******************************************************************************/

template<typename Iterator, typename T>
void sift_in(ptrdiff_t count, Iterator begin, ptrdiff_t free_in, T next)
{
	ptrdiff_t i;
	ptrdiff_t free = free_in;

	// sift up the free node 
	for ( i = 2*(free+1); i < count; i += i) {
		if ( *(begin+(i-1)) < *(begin+i))
			i++;
		*(begin + free) = *(begin+(i-1));
		free = i-1;
	}

	// special case in sift up if the last inner node has only 1 child
	if (i == count) {
		*(begin + free) = *(begin+(i-1));
		free = i-1;
	}

	// sift down the new item next
	i = (free-1)/2;
	while( (free > free_in)  &&  *(begin+i) < next) {
		*(begin + free) = *(begin+i);
		free = i;
		i = (free-1)/2;
	}

	*(begin + free) = next;
}

template<typename Iterator, typename T>
void heapsort(Iterator begin, Iterator end)
{
	ptrdiff_t  j;
	ptrdiff_t count = end - begin;

	// build the heap structure 
	for( j = (count / 2) - 1; j >= 0; --j) {
		T  next = *(begin+j);
		sift_in< Iterator, T>(count, begin, j, next);
	}

	// search next by next remaining extremal element
	for( j = count - 1; j >= 1; --j) {
		T next = *(begin+j);
		*(begin+j) = *(begin);
		sift_in< Iterator, T>(j, begin, 0, next);
	}
}

}	// end namespace benchmark

using namespace benchmark;

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/