/***************************************************************************
* File: ArgMinMax.hh
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* Implementation of two algorithms, ArgMin and ArgMax, which take as inputs
* a range of iterators and a function to call, then return iterators to the
* elements in the range for which the function obtains its minimum (maximum)
* value.  These functions are similar to the STL min_element and max_element
* functions, but are significantly easier to use when a simple function is
* being applied.  For example, compare:
*
*    double Haversine(double x) {
*       return (1.0 - cos(x)) / 2.0;
*    }
*
*    bool CompareByHaversines(double x, double y) {
*       return Haversine(x) < Haversine(y);
*    }
*
*    iterator itr = max_element(begin, end, CompareByHaversines);
*
* To
*
*    double Haversine(double x) {
*       return (1.0 - cos(x)) / 2.0;
*    }
*
*    iterator itr = ArgMax(begin, end, Haversine);
*/

#ifndef ArgMinMax_Included
#define ArgMinMax_Included

/**
* ForwardIterator ArgMax(ForwardIterator begin, ForwardIterator end,
*                        UnaryFunction function)
* Usage: ForwardIterator itr = ArgMax(begin, end, Haversine);
* -------------------------------------------------------------------------
* Given a range of iterators [begin, end), returns an iterator to an element
* in the range for which function attains a maximum value.
*/

template <typename ForwardIterator, typename UnaryFunction>
ForwardIterator ArgMax(ForwardIterator begin, ForwardIterator end,
UnaryFunction function);

/**
* ForwardIterator ArgMin(ForwardIterator begin, ForwardIterator end,
*                        UnaryFunction function)
* Usage: ForwardIterator itr = ArgMin(begin, end, Haversine);
* -------------------------------------------------------------------------
* Given a range of iterators [begin, end), returns an iterator to an element
* in the range for which function attains a minimum value.
*/

template <typename ForwardIterator, typename UnaryFunction>
ForwardIterator ArgMin(ForwardIterator begin, ForwardIterator end,
UnaryFunction function);

/* * * * * Implementation Below This Point * * * * */
template <typename ForwardIterator, typename UnaryFunction>
ForwardIterator ArgMax(ForwardIterator begin, ForwardIterator end,
UnaryFunction function) {
/* Initially, our guess is that the first argument is the max element. */
ForwardIterator result = begin;

/* Scan across the values, updating our guess at each point. */
for (; begin != end; ++begin)
if (function(*result) < function(*begin))
result = begin;

return result;
}
template <typename ForwardIterator, typename UnaryFunction>
ForwardIterator ArgMin(ForwardIterator begin, ForwardIterator end,
UnaryFunction function) {
/* Initially, our guess is that the first argument is the min element. */
ForwardIterator result = begin;

/* Scan across the values, updating our guess at each point. */
for (; begin != end; ++begin)
if (function(*begin) < function(*result))
result = begin;

return result;
}

#endif