#pragma once
 
#ifndef TCG_ALGORITHM_H
#define TCG_ALGORITHM_H
 
// tcg includes
#include "traits.h"
 
// STD includes
#include <functional>
 
/*!
  \file     algorithm.h
 
  \brief    This file contains useful algorithms complementary to those
            in the standard \p \<algorithm\> and in \p boost::algorithm.
*/
 
namespace tcg
{
 
//***************************************************************************
//    Binary find  algorithms
//***************************************************************************
 
/*!
  \brief    Performs a binary search for the a value in a <I>sorted,
            random access</I> iterators range, and returns its position.
 
  \return   The \a first range position whose value is \a equivalent to
            the specified one.
*/
template <typename RanIt, typename T>
RanIt binary_find(RanIt begin,	//!< Start of the sorted range.
				  RanIt end,	  //!< End of the sorted range.
				  const T &value) //!< Value to look up.
{
	RanIt it = std::lower_bound(begin, end, value);
	return (it != end && !(value < *it)) ? it : end;
}
 
//---------------------------------------------------------------------
 
/*!
  \brief    Performs a binary search for the a value in a <I>sorted,
            random access</I> iterators range, and returns its position.
 
  \return   The \a first range position whose value is \a equivalent to
            the specified one.
*/
template <typename RanIt, typename T, typename Compare>
RanIt binary_find(RanIt begin,	//!< Start of the sorted range.
				  RanIt end,	  //!< End of the sorted range.
				  const T &value, //!< Value to look up.
				  Compare comp)   //!< Comparator functor sorting the range.
{
	RanIt it = std::lower_bound(begin, end, value, comp);
	return (it != end && !comp(value, *it)) ? it : end;
}
 
//***************************************************************************
//    Min/Max iterator range  algorithms
//***************************************************************************
 
/*!
  \brief    Calculates the minimal transformed element from the
            input iterators range.
 
  \return   The position of the minimal transform.
 
  \details  This function is similar to std::min_element(), but
            operating a unary transforming function on dereferenced
            objects.
 
            Furthermore, the minimal transformed value is cached
            during computation.
*/
template <typename ForIt, typename Func, typename Comp>
ForIt min_transform(ForIt begin, //!< Start of the input iterators range.
					ForIt end,   //!< End of the input iterators range.
					Func func,   //!< The transforming function.
					Comp comp)   //!< The comparator object for transformed values.
{
	typedef typename tcg::function_traits<Func>::ret_type ret_type;
	typedef typename tcg::remove_cref<ret_type>::type value_type;
 
	if (begin == end)
		return end;
 
	ForIt minPos = begin;
	value_type minimum = func(*begin);
 
	for (; begin != end; ++begin) {
		const value_type &candidate = func(*begin);
 
		if (comp(candidate, minimum))
			minPos = begin, minimum = candidate;
	}
 
	return minPos;
}
 
//---------------------------------------------------------------------
 
/*!
  \brief    Calculates the minimal transformed element from the
            input iterators range.
 
  \return   The position of the minimal transform.
 
  \remark   This variation uses \p operator< as comparator for the
            transformed values.
*/
template <typename ForIt, typename Func>
ForIt min_transform(ForIt begin, //!< Start of the input iterators range.
					ForIt end,   //!< End of the input iterators range.
					Func func)   //!< The transforming function.
{
	typedef typename tcg::function_traits<Func>::ret_type ret_type;
	typedef typename tcg::remove_cref<ret_type>::type value_type;
 
	return min_transform(begin, end, func, std::less<value_type>());
}
 
//---------------------------------------------------------------------
 
/*!
  \brief    Calculates the maximal transformed element from the
            input iterators range.
 
  \return   The position of the maximal transform.
 
  \sa       See min_transform() for a detailed explanation.
*/
template <typename ForIt, typename Func, typename Comp>
ForIt max_transform(ForIt begin, //!< Start of the input iterators range.
					ForIt end,   //!< End of the input iterators range.
					Func func,   //!< The transforming function.
					Comp comp)   //!< The comparator object for transformed values.
{
	typedef typename tcg::function_traits<Func>::ret_type ret_type;
	typedef typename tcg::remove_cref<ret_type>::type value_type;
 
	if (begin == end)
		return end;
 
	ForIt maxPos = begin;
	value_type maximum = func(*begin);
 
	for (; begin != end; ++begin) {
		const value_type &candidate = func(*begin);
 
		if (comp(maximum, candidate))
			maxPos = begin, maximum = candidate;
	}
 
	return maxPos;
}
 
//---------------------------------------------------------------------
 
/*!
  \brief    Calculates the maximal transformed element from the
            input iterators range.
 
  \return   The position of the maximal transform.
 
  \sa       See min_transform() for a detailed explanation.
*/
template <typename ForIt, typename Func>
ForIt max_transform(ForIt begin, //!< Start of the input iterators range.
					ForIt end,   //!< End of the input iterators range.
					Func func)   //!< The transforming function.
{
	typedef typename tcg::function_traits<Func>::ret_type ret_type;
	typedef typename tcg::remove_cref<ret_type>::type value_type;
 
	return max_transform(begin, end, func, std::less<value_type>());
}
 
} // namespace tcg
 
#endif // TCG_ALGORITHM_H