#pragma once

#ifndef TCG_ALGORITHM_H

#define TCG_ALGORITHM_H

// tcg includes

#include "traits.h"

// STD includes

#include <functional></functional>

/*!

  \file     algorithm.h

  \brief    This file contains useful algorithms complementary to those

            in the standard \p \<algorithm\> and in \p boost::algorithm.</algorithm\>

*/

namespace tcg {

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

//    Binary find  algorithms

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

/*!

  \brief    Performs a binary search for the a value in a sorted,

            random access iterators range, and returns its position.

  \return   The \a first range position whose value is \a equivalent to

            the specified one.

*/

template <typename ranit,="" t="" typename=""></typename>

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 sorted,

            random access iterators range, and returns its position.

  \return   The \a first range position whose value is \a equivalent to

            the specified one.

*/

template <typename compare="" ranit,="" t,="" typename=""></typename>

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 comp="" forit,="" func,="" typename=""></typename>

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;</func>

  typedef typename tcg::remove_cref<ret_type>::type value_type;</ret_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,="" func="" typename=""></typename>

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;</func>

  typedef typename tcg::remove_cref<ret_type>::type value_type;</ret_type>

  return min_transform(begin, end, func, std::less<value_type>());</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 comp="" forit,="" func,="" typename=""></typename>

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;</func>

  typedef typename tcg::remove_cref<ret_type>::type value_type;</ret_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,="" func="" typename=""></typename>

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;</func>

  typedef typename tcg::remove_cref<ret_type>::type value_type;</ret_type>

  return max_transform(begin, end, func, std::less<value_type>());</value_type>

}

}  // namespace tcg

#endif  // TCG_ALGORITHM_H