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