path: root/src/include/algorithm

/* IBM_PROLOG_BEGIN_TAG                                                   */
/* This is an automatically generated prolog.                             */
/*                                                                        */
/* $Source: src/include/algorithm $                                       */
/*                                                                        */
/* OpenPOWER HostBoot Project                                             */
/*                                                                        */
/* Contributors Listed Below - COPYRIGHT 2011,2016                        */
/* [+] International Business Machines Corp.                              */
/*                                                                        */
/*                                                                        */
/* Licensed under the Apache License, Version 2.0 (the "License");        */
/* you may not use this file except in compliance with the License.       */
/* You may obtain a copy of the License at                                */
/*                                                                        */
/*     http://www.apache.org/licenses/LICENSE-2.0                         */
/*                                                                        */
/* Unless required by applicable law or agreed to in writing, software    */
/* distributed under the License is distributed on an "AS IS" BASIS,      */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
/* implied. See the License for the specific language governing           */
/* permissions and limitations under the License.                         */
/*                                                                        */
/* IBM_PROLOG_END_TAG                                                     */
#ifndef ALGORITHM
#define ALGORITHM

#include <iterator>
#include <util/impl/qsort.H>
#include <utility>

#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;
    }

    /**
     * Swaps the values of the elements the given iterators are pointing to.
     * @param[in] a iterator to the elements to swap
     * @param[in] b iterator to the elements to swap
     */
    template<class ForwardIterator1, class ForwardIterator2>
    inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
    {
        swap(*a, *b);
    }

    /**
     * Swaps the values of the elements the given iterators are pointing to.
     * @param[in] first1 iterator of the beginning of first range
     * @param[in] last1 iterator of the end of first range
     * @param[in] first2 iterator of the beginning of the second range
     * @return Iterator to the element past the last element exchanged in the
     *         range beginning with first2.
     */

    template< class ForwardIterator1, class ForwardIterator2 >
    inline ForwardIterator2 swap_ranges(ForwardIterator1 first1,
                                        ForwardIterator1 last1,
                                        ForwardIterator2 first2)
    {
        while (first1 != last1)
        {
            iter_swap(first1++, first2++);
        }
        return first2;
    }

    /**
     * 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 tmp(std::move(a));
        a = std::move(b);
        b = std::move(tmp);
    }

    /**
     * Swaps the arrays a and b. In effect calls std::swap_ranges(a, a+N, b)
     * @param[in] a reference to an object to be swaped with b
     * @param[in] b reference to an object to be swaped with a
     */
    template< class T, size_t N>
    inline void swap(T(&a)[N], T(&b)[N])
    {
        swap_ranges(a, a+N, b);
    }

    /**
     * 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;
        }
    }

    /**
     * Fill a sequence with a generated value
     * @param[in] first OutputIterator to the first position in the sequence.
     * @param[in] n number of elements in the sequence
     * @param[in] gen functor to create values used to fill the sequence.
     */
    template <typename OutputIterator, typename Size, typename Generator>
    OutputIterator generate_n(OutputIterator first, Size n, Generator gen)
    {
        for(; n>0; --n)
        {
            *first = gen();
            ++first;
        }

        return 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 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] pred  Predicate used to compare equality.
     *
     * Returns the first iterator i in the range [first,last) such that
     *     pred(*i) is true 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 Predicate>
    inline InputIterator
    find_if(InputIterator first, InputIterator last,
            Predicate pred)
    {
        while(first != last)
        {
            if (pred(*first))
                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 maximum 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 (*i) < (*j) 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 max_element(FwdIterator first, FwdIterator last)
    {
        if (first == last) return last;
        FwdIterator e = first++;
        while(first != last)
        {
            if ((*e) < (*first))
            {
                e = first;
            }
            ++first;
        }
        return e;
    }

    /**
     * Find the maximum 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(*i,*j) 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 max_element(FwdIterator first, FwdIterator last,
                                   BinaryPredicate comp)
    {
        if (first == last) return last;
        FwdIterator e = first++;
        while(first != last)
        {
            if (comp((*e),(*first)))
            {
                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;
        auto range = std::distance<ForwardIterator>( first, last );
        auto num = decltype(range)();

        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;
        auto range = std::distance<ForwardIterator>( first, last );
        auto num = decltype(range)();

        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;
    }

    /**
     * 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 GreaterThanComparable>
    inline ForwardIterator
    upper_bound ( ForwardIterator first,
                  ForwardIterator last,
                  const GreaterThanComparable& value )
    {
        ForwardIterator it;

        auto range = std::distance<ForwardIterator>( first, last );
        auto num = decltype(range)();

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

            if( !(value < *it))
            {
                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
    upper_bound ( ForwardIterator first,
                  ForwardIterator last,
                  const T& value,
                  StrictWeakOrdering comp )
    {
        ForwardIterator it;
        auto range = std::distance<ForwardIterator>( first, last );
        auto num = decltype(range)();

        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;
    }

    /**
     * Test if value exists in sorted sequence
     *
     * @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.
     *
     * @return true if any element in the range [first,last) is
    *               equivalent to value
     *         false otherwise
     */
    template<class ForwardIterator, class T>
    bool binary_search(ForwardIterator first,
                       ForwardIterator last, const T& value)
    {
        first = std::lower_bound(first, last, value);
        return (!(first == last) && !(value < *first));
    }

    /**
     * Test if value exists in sorted sequence using comparison function
     *
     * @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
     *
     * @return true if any element in the range [first,last) is
     *              equivalent to value
     *         false otherwise
     */
    template<class ForwardIterator, class T,  class StrictWeakOrdering>
    bool binary_search(ForwardIterator first,
                       ForwardIterator last,
                       const T& value,
                       StrictWeakOrdering comp)
    {
        first = std::lower_bound(first, last, value);
        return (!(first == last) && !(comp(value,*first)));
    }

    /**
     * Apply a functor to each element in a range.
     *
     * Applies functor 'f' to each element in [first, last).
     *
     * @param[in] first - The beginning of the range.
     * @param[in] last - The end of the range.
     * @param[in] f - The functor.
     *
     * @return The functor after being having been applied.
     */
    template <typename InputIterator, typename UnaryFunction>
    UnaryFunction for_each(InputIterator first, InputIterator last,
                           UnaryFunction f)
    {
        while(first != last)
        {
            f(*first);
            ++first;
        }
        return f;
    }

    /**
     * Remove a value from a range.
     *
     * Removes all instances matching 'value' in the range [first, last)
     * and returns an iterator to the end of the new range [first, new_last)
     * where nothing in the new range has 'value'.
     *
     * Remove does not decrease the size of the container.
     *
     * @param[in] first - The beginning of the range.
     * @param[in] last - The end of the range.
     * @param[in] value - The value to remove.
     *
     * @return An iterator 'new_last' from [first, new_last).
     */
    template <typename ForwardIterator, typename T>
    ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                           const T& value)
    {
        // Find first match.
        first = find(first, last, value);

        if (first == last) // No match found, return un-changed 'last'.
        {
            return last;
        }

        // Match was found.  'new_last' is now the first removed element.
        ForwardIterator new_last = first;
        ++first;

        // Iterate through all the others.
        while(first != last)
        {
            // If 'first' is a desired value, we need to copy it and move
            // 'new_last'.
            if (!(*first == value))
            {
                *new_last = *first;
                ++new_last;
            }

            ++first;
        }

        return new_last;

    }

    /**
     * Remove a value from a range using a predicate.
     *
     * Removes all instances pred(*i) is true in the range [first, last)
     * and returns an iterator to the end of the new range [first, new_last)
     * where nothing in the new range has pred(*i) true.
     *
     * Remove does not decrease the size of the container.
     *
     * @param[in] first - The beginning of the range.
     * @param[in] last - The end of the range.
     * @param[in] pred - The predicate to use for comparison.
     *
     * @return An iterator 'new_last' from [first, new_last).
     */
    template <typename ForwardIterator, typename Predicate>
    ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                              Predicate pred)
    {
        // Find first match.
        first = find_if(first, last, pred);

        if (first == last) // No match found, return un-changed 'last'.
        {
            return last;
        }

        // Match was found.  'new_last' is now the first removed element.
        ForwardIterator new_last = first;
        ++first;

        // Iterate through all the others.
        while(first != last)
        {
            // If 'first' is a desired value, we need to copy it and move
            // 'new_last'.
            if (!(pred(*first)))
            {
                *new_last = *first;
                ++new_last;
            }

            ++first;
        }

        return new_last;

    }

    /**
     * Removes consecutive duplicate entries from a range.
     *
     * Removes all instances where (*i == *(i-1)) in the range [first, last)
     * and returns an iterator to the end of the new range [first, new_last)
     * where nothing in the new range is a consecutive duplicate.
     *
     * Unique does not decrease the size of the container.
     *
     * @param[in] first - The beginning of the range.
     * @param[in] last - The end of the range.
     *
     * @return An iterator 'new_last' from [first, new_last).
     *
     */
    template <typename ForwardIterator>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last)
    {
        // Trivial case of 0 items, return.
        if (first == last) return last;

        // The algorithm keeps 3 iterators 'prev', 'first', and 'last'.  The
        // 'prev' iterator is always the last instance to be kept.  'last' is
        // the end of the original range.  'first' is kept to be the item
        // being compared.

        // Point 'prev' at the first element of the range since first item is
        // a keeper.
        ForwardIterator prev = first;
        ++first;

        while (first != last)
        {
            // If the two items are not the same, we found a new item to keep.
            if (!(*prev == *first))
            {
                // Increment the "keep slot".
                ++prev;

                // If the "keep slot" is not the element being compared, we
                // need to move the new item down to that keep slot.
                if (prev != first)
                {
                    *prev = *first;
                }
            }

            // Advance to the next element.
            ++first;
        }

        // 'prev' points to the last item to be kept.  Increment it to make
        // it point to the one past.
        ++prev;
        return prev;
    }

    /**
     * Removes consecutive duplicate entries from a range by predicate.
     *
     * Removes all instances where pred(*i,*(i-1)) is true in the
     * range [first, last) and returns an iterator to the end of the new
     * range [first, new_last) where nothing in the new range is a
     * consecutive duplicate.
     *
     * Unique does not decrease the size of the container.
     *
     * @param[in] first - The beginning of the range.
     * @param[in] last - The end of the range.
     * @param[in] pred - The predicate.
     *
     * @return An iterator 'new_last' from [first, new_last).
     *
     */
    template <typename ForwardIterator, typename BinaryPredicate>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                           BinaryPredicate pred)
    {
        // Trivial case of 0 items, return.
        if (first == last) return last;

        // The algorithm keeps 3 iterators 'prev', 'first', and 'last'.  The
        // 'prev' iterator is always the last instance to be kept.  'last' is
        // the end of the original range.  'first' is kept to be the item
        // being compared.

        // Point 'prev' at the first element of the range since first item is
        // a keeper.
        ForwardIterator prev = first;
        ++first;

        while (first != last)
        {
            // If the two items are not the same, we found a new item to keep.
            if (!(pred(*prev,*first)))
            {
                // Increment the "keep slot".
                ++prev;

                // If the "keep slot" is not the element being compared, we
                // need to move the new item down to that keep slot.
                if (prev != first)
                {
                    *prev = *first;
                }
            }

            // Advance to the next element.
            ++first;
        }

        // 'prev' points to the last item to be kept.  Increment it to make
        // it point to the one past.
        ++prev;
        return prev;
    }

    /** Sort a range.
     *
     *  Sorts all the elements in [first, last) using such that *i < *(i+1)
     *  for all items in the range.
     *
     *  @param[in] first - The beginning of the range.
     *  @param[in] last - The end of the range.
     */
    template <typename RandomAccessIterator>
    void sort(RandomAccessIterator first, RandomAccessIterator last)
    {
        Util::__Util_QSort_Impl::sort(first, last);
    }

    /** Sort a range using a predicate
     *
     *  Sorts all the elements in [first, last) using such that
     *  pred(*i, *(i+1)) is true for all items in the range.
     *
     *  @param[in] first - The beginning of the range.
     *  @param[in] last - The end of the range.
     *  @param[in] pred - The predicate to use for comparison.
     */
    template <typename RandomAccessIterator, typename StrictWeakOrdering>
    void sort(RandomAccessIterator first, RandomAccessIterator last,
              StrictWeakOrdering pred)
    {
        Util::__Util_QSort_Impl::sort(first, last, pred);
    }

    /** Transform one sequence into another.
     *
     *  Executes an operator against all elements in [first, last) and writes
     *  the result to another sequence.
     *
     *  @param first - Beginning of the input range.
     *  @param last - Ending of the input range.
     *  @param result - Beginning of the output range.
     *  @param op - The transformation operator.
     */
    template <typename InputIterator, typename OutputIterator,
              typename UnaryFunction>
    OutputIterator transform(InputIterator first, InputIterator last,
                             OutputIterator result, UnaryFunction op)
    {
        while (first != last)
        {
            *result = op(*first);
            ++result;
            ++first;
        }
        return result;
    }

    /** Transform two sequences into another.
     *
     *  Executes an operator against all elements in [first1, last1) along
     *  with the peer from [first2, ...) and writes the result to
     *  another sequence.
     *
     *  @param first1 - Beginning of the first input range.
     *  @param last1 - Ending of the first input range.
     *  @param first2 - Beginning of the second input range.
     *  @param result - Beginning of the output range.
     *  @param op - The transformation operator.
     */
    template <typename InputIterator1, typename InputIterator2,
              typename OutputIterator, typename BinaryFunction>
    OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, OutputIterator result,
                             BinaryFunction op)
    {
        while (first1 != last1)
        {
            *result = op(*first1, *first2);
            ++result;
            ++first1; ++first2;
        }
        return result;
    }

    /** Returns true if the range [first1, last1) is equal to the range
     *  [first2, first2 + (last1 - first1)), and false otherwise
     *
     * The two ranges are considered equal if, for every iterator i in the range
     * [first1,last1), *i equals *(first2 + (i - first1)). The overloads use
     * operator== to determine if two elements are equal.
     *
     *  @param[in] first1 - The beginning of the first range.
     *  @param[in] last1 - The end of the first range.
     *  @param[in] first2 - The beginning of the second range.
     *  @return - Returns true equal, false otherwise
     */
    template < typename InputIterator1, typename InputIterator2 >
    bool equal(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2)
    {
        while(first1 != last1)
        {
            if (!(*first1 == *first2))
            {
                return false;
            }
            ++first1; ++first2;
        }
        return true;
    }

    /** Returns true if the range [first1, last1) is equal, using a predicate,
     *  to the range [first2, first2 + (last1 - first1)), and false otherwise
     *
     * The two ranges are considered equal if, for every iterator i in the range
     * [first1,last1), *i equals *(first2 + (i - first1)). The overloads use
     * operator== to determine if two elements are equal.
     *
     *  @param[in] first1 - The beginning of the first range.
     *  @param[in] last1 - The end of the first range.
     *  @param[in] first2 - The beginning of the second range.
     *  @param[in] comp - Binary predicate which returns true if the elements
     *                    should be treated as equal.
     *  @return - Returns true equal, false otherwise
     */
    template < typename InputIterator1, typename InputIterator2,
               typename BinaryPredicate >
    bool equal( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, BinaryPredicate comp )
    {
        while(first1 != last1)
        {
            if (!comp(*first1, *first2))
            {
                return false;
            }
            ++first1; ++first2;
        }
        return true;
    }

    /** Checks if the first range [first1, last1) is lexicographically less than
     *  the second range [first2, last2).
     *
     *  Elements are compared using operator<.
     *  Lexicographical comparison is a operation with the following properties:
     *  - Two ranges are compared element by element.
     *  - The first mismatching element defines which range is lexicographically
     *    less or greater than the other.
     *  - If one range is a prefix of another, the shorter range is
     *    lexicographically less than the other.
     *  - If two ranges have equivalent elements and are of the same length,
     *    then the ranges are lexicographically equal.
     *  - An empty range is lexicographically less than any non-empty range.
     *  - Two empty ranges are lexicographically equal.
     *
     *  @param[in] first1 - The beginning of the first range.
     *  @param[in] last1 - The end of the first range.
     *  @param[in] first2 - The beginning of the second range.
     *  @param[in] last2 - The end of the second range.
     *  @return - true if the first range is lexicographically less than the
     *            second.
     */
    template < typename InputIterator1, typename InputIterator2 >
    bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                                 InputIterator2 first2, InputIterator2 last2)
    {
        while( (first1 != last1) && (first2 != last2) )
        {
            if (*first1 < *first2)
            {
                return true;
            }
            if (*first2 < *first1)
            {
                return false;
            }
            first1++; first2++;
        }
        return (first1 == last1) && (first2 != last2);
    }

};
#endif

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