//  IBM_PROLOG_BEGIN_TAG
//  This is an automatically generated prolog.
//
//  $Source: src/include/algorithm $
//
//  IBM CONFIDENTIAL
//
//  COPYRIGHT International Business Machines Corp. 2011
//
//  p1
//
//  Object Code Only (OCO) source materials
//  Licensed Internal Code Source Materials
//  IBM HostBoot Licensed Internal Code
//
//  The source code for this program is not published or other-
//  wise divested of its trade secrets, irrespective of what has
//  been deposited with the U.S. Copyright Office.
//
//  Origin: 30
//
//  IBM_PROLOG_END
#ifndef ALGORITHM
#define ALGORITHM

#include <iterator>

#ifdef __cplusplus
namespace std
{
    /**
     * Copy a range of elements
     * @param[in] first InputIterator to the initial position in the source sequence.
     * @param[in] last  InputIterator to last position + 1 in the source sequence.
     * @param[in] result OutputIterator to initial position in the destination sequence.
     * @return an iterator to the last element in the destination range
     * @note If both ranges overlap in such a way that result points to an elmenent in the source
     * range then fuction copy_backward should be used.
     */
    template <class InputIterator, class OutputIterator>
    inline OutputIterator
    copy (InputIterator first, InputIterator last, OutputIterator result )
    {
        while(first!=last)
        {
            *result = *first;
            ++result;
            ++first;
        }
        return result;
    }

    /**
     * Copy a range of elements backwards
     * @param[in] first Bidirectional iterator to the initial source position
     * @param[in] last  Bidirectional iterator to the final source position + 1
     * @param[in] result Bidirectional iterator to end of the destination sequence + 1.
     * @return an iterator to the first element in the destination sequence.
     * @note If both ranges overlap in such a way that result points to an element in the  source
     * range, the function copy should be used instead.
     */
    template <class BidirectionalIterator1, class BidirectionalIterator2>
    inline BidirectionalIterator2 
    copy_backward (  BidirectionalIterator1 first,
                     BidirectionalIterator1 last,
                     BidirectionalIterator2 result )
    {
        while(last!=first)
        {
            --result;
            --last;
            *result = *last;
        }
        return result;
    }

    /**
     * Exchange values of two objects
     * @param[in] a reference to an object to be swaped with b
     * @param[in] b reference to an object to be swaped with a
     * @note this function may not be an efficient way to swap large objects.
     */
    template <class T> 
        inline void 
        swap(T& a, T&b )
    {
        T c(a);
        a=b;
        b=c;
    }

    /**
     * Fill a range with value
     * @param[in] first ForwardIterator to the first position in the source range.
     * @param[in] last  ForwardIterator to the last position +1 in the source range.
     * @param[in] value reference to the object used to fill the sequence.
     */
    template < class ForwardIterator, class T >
    inline void
    fill (ForwardIterator first, ForwardIterator last, const T& value )
    {
        while (first != last)
        {
            *first = value;
            ++first;
        }
    }

    /**
     * Fill a sequence with value
     * @param[in] first OutputIterator to the first position in the sequence.
     * @param[in] n number of elements in the sequence
     * @param[in] value reference to the value used to fill the sequence.
     */
    template < class OutputIterator, class Size, class T >
    inline void
    fill_n( OutputIterator first, Size n, const T& value )
    {
        for(; n>0; --n)
        {
            *first = value;
            ++first;
        }
    }

    /**
     * Return the lesser of two arguments
     * @param[in] a object reference
     * @param[in] b object reference
     * @return reference to te lesser object
     */
    template <class T>
    inline const T& 
    min(const T& a, const T& b)
    {
        if( b < a) return b;
        return a;
    }

    /**
     * Return the greater of two arguments
     * @param[in] a object reference
     * @param[in] b object reference
     * @return reference to te greater object
     */    
    template <class T>
    inline const T&
    max(const T& a, const T& b)
    {
        if(a < b) return b;
        return a;
    }

    /**
     * Find the location of an element within a range.
     * @param[in] first InputIterator to the first position in the range.
     * @param[in] last  InputIterator to the last position in the range.
     * @param[in] value Value to use for comparison.
     *
     * Returns the first iterator i in the range [first,last) such that
     *     (*i == value) or else last if no element is found.
     *
     * @return An iterator in the range [first,last].  last implies that no
     *         matching element was found.
     */
    template <typename InputIterator, typename EqualityComparable>
    inline InputIterator
    find(InputIterator first, InputIterator last,
         const EqualityComparable& value)
    {
        while(first != last)
        {
            if ((*first) == value)
                return first;

            first++;
        }

        return last;
    }

    /**
     * Find the minimum element within a range.
     * @param[in] first - FwdIterator to the first position in the range.
     * @param[in] last - FwdIterator to the last position in the range.
     *
     * Returns the first element (i) such that (*j) < (*i) is false for all
     * other iterators.
     *
     * The iterator last is returned only when the range contains no elements.
     *
     * @return An iterator in [first, last) containing the minimum element.
     *
     */
    template <typename FwdIterator>
    inline FwdIterator min_element(FwdIterator first, FwdIterator last)
    {
        if (first == last) return last;
        FwdIterator e = first++;
        while(first != last)
        {
            if ((*first) < (*e)) 
            {
                e = first;
            }
            first++;
        }
        return e;
    }

    /**
     * Find the minimum element within a range.
     * @param[in] first - FwdIterator to the first position in the range.
     * @param[in] last - FwdIterator to the last position in the range.
     * @param[in] comp - BinaryPredicate used to perform comparison.
     *
     * Returns the first element (i) such that comp(*j,*i) is false for all
     * other iterators.
     *
     * The iterator last is returned only when the range contains no elements.
     *
     * @return An iterator in [first, last) containing the minimum element.
     *
     */
    template <typename FwdIterator, typename BinaryPredicate>
    inline FwdIterator min_element(FwdIterator first, FwdIterator last, 
                                   BinaryPredicate comp)
    {
        if (first == last) return last;
        FwdIterator e = first++;
        while(first != last)
        {
            if (comp((*first),(*e)))
            {
                e = first;
            }
            first++;
        }
        return e;
    }

    /**
     * Find the element value in an ordered range [first, last].  Specifically,
     * it returns the first position where value could be inserted without
     * violating the ordering.
     *
     * @param[in] first ForwardIterator to the first position in the range.
     * @param[in] last  ForwardIterator to the last position in the range.
     * @param[in] value Value to use for comparison.
     */

    template <class ForwardIterator, class LessThanComparable>
    inline ForwardIterator
    lower_bound ( ForwardIterator first,
                  ForwardIterator last,
                  const LessThanComparable& value )
    {
        ForwardIterator it;
        int num = 0x0;
        int range = std::distance<ForwardIterator>( first,
                                                    last );

        while( range > 0 )
        {
            it = first;
            num = range / 2;
            std::advance( it, num );

            if( (*it) < value )
            {
                first = ++it;
                range = (range - (num+1));
            }
            else
            {
                range = num;
            }
        }

        return first;
    }

    /**
     * Find the element value in an ordered range [first, last].  Specifically,
     * it returns the first position where value could be inserted without
     * violating the ordering.  This is done using the comparison function
     * parameter that is passed in.
     *
     * @param[in] first ForwardIterator to the first position in the range.
     * @param[in] last  ForwardIterator to the last position in the range.
     * @param[in] value Value to use for comparison.
     * @param[in] comp  Function to do the comparison
     */
    template <class ForwardIterator, class T, class StrictWeakOrdering>
    inline ForwardIterator
    lower_bound ( ForwardIterator first,
                  ForwardIterator last,
                  const T& value,
                  StrictWeakOrdering comp )
    {
        ForwardIterator it;
        int num = 0x0;
        int range = std::distance<ForwardIterator>( first,
                                                    last );

        while( range > 0 )
        {
            it = first;
            num = range / 2;
            std::advance( it, num );

            if( comp( (*it), value ) )
            {
                first = ++it;
                range = (range - (num+1));
            }
            else
            {
                range = num;
            }
        }

        return first;
    }

};
#endif

#endif
/* vim: set filetype=cpp : */