/*  Copyright (C) 2004 Garrett A. Kajmowicz
 *
 * This file is part of the uClibc++ Library.
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <cstdlib>
#include <iterator>
#include <utility>
#include <functional>

#ifndef __STD_HEADER_ALGORITHM
#define __STD_HEADER_ALGORITHM 1

//Eliminate any previously defined macro

#undef min
#undef max

#pragma GCC visibility push(default)

extern "C++"
{

namespace std
{

  // Subclause _lib.alg.nonmodifying_, non-modifying sequence operations:

  template<class InputIterator, class Function> _UCXXEXPORT
    Function for_each(InputIterator first, InputIterator last, Function f)
  {
    while (first !=last)
    {
      f(*first);
      ++first;
    }

    return f;
  }

  template<class InputIterator, class T> _UCXXEXPORT
    InputIterator find(InputIterator first, InputIterator last, const T& value)
  {
    while (first !=last && *first != value)
    {
      ++first;
    }

    return first;
  }

  template<class InputIterator, class Predicate> _UCXXEXPORT
    InputIterator find_if (InputIterator first, InputIterator last, Predicate pred)
  {
    while (first !=last && !pred(*first))
    {
      ++first;
    }

    return first;
  }

  template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT ForwardIterator1
    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2)
  {
    ForwardIterator1 retval = last1;
    while (first1 != last1)
    {
      ForwardIterator1 temp1(first1);
      ForwardIterator2 temp2(first2);

      while (temp2!=last2 && temp1!= last1)
      {
        if (*temp1 != *temp2)
        {
          break;    //Exit while loop
        }

        ++temp1;
        ++temp2;
        if (temp2 == last2)
        {
          //Have successfully checked the whole sequence

          retval = first1;
        }
      }
    }

    return retval;
  }

  template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator1
    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred)
  {
    ForwardIterator1 retval = last1;
    while (first1 !=last1)
    {
      ForwardIterator1 temp1(first1);
      ForwardIterator2 temp2(first2);
      while (temp2!=last2 && temp1!= last1)
      {
        if (!pred(*temp1, *temp2))
        {
          break;    //Exit while loop
        }

        ++temp1;
        ++temp2;
        if (temp2 == last2)
        {
          // Have successfully checked the whole sequence

          retval = first1;
        }
      }
    }

    return retval;
  }

  template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
    ForwardIterator1
    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2)
  {
    while (first1 != last1)
    {
      ForwardIterator2 temp2(first2);
      while (temp2 != last2)
      {
        if (*temp2 == first1)
        {
          return first1;
        }

        ++temp2;
      }
    }

    return last1;
  }

  template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator1
    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred)
  {
    while (first1 != last1)
    {
      ForwardIterator2 temp2(first2);
      while (temp2 != last2)
      {
        if (*temp2 == first1)
        {
          return first1;
        }

        ++temp2;
      }
    }

    return last1;
  }

  template<class ForwardIterator> _UCXXEXPORT ForwardIterator
    adjacent_find(ForwardIterator first, ForwardIterator last)
  {
    ForwardIterator temp;
    while (first != last)
    {
      temp = first;
      ++temp;
      if (*temp == *first)
      {
        return first;
      }

      ++first;
    }

    return first;
  }

  template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator
    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
  {
    ForwardIterator temp;
    while (first != last)
    {
      temp = first;
      ++temp;
      if (pred(*temp, *first))
      {
        return first;
      }

      ++first;
    }

    return first;
  }

  template<class InputIterator, class T> _UCXXEXPORT
    typename iterator_traits<InputIterator>::difference_type
    count(InputIterator first, InputIterator last, const T& value)
  {
    typename iterator_traits<InputIterator>::difference_type i = 0;
    while (first!=last)
    {
      if (*first == value)
      {
        ++i;
      }

      ++first;
    }

    return i;
  }

  template<class InputIterator, class Predicate> _UCXXEXPORT
    typename iterator_traits<InputIterator>::difference_type
    count_if (InputIterator first, InputIterator last, Predicate pred)
  {
    typename iterator_traits<InputIterator>::difference_type i = 0;
    while (first!=last)
    {
      if (pred(*first))
      {
        ++i;
      }

      ++first;
    }

    return i;
  }

  template<class InputIterator1, class InputIterator2> _UCXXEXPORT
    pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
  {
    while (first1 != last1)
    {
      if (*first1 != *first2)
      {
        break;
      }

      ++first1;
      ++first2;
    }

    pair<InputIterator1, InputIterator2> retval;
    retval.first = first1;
    retval.second = first2;
    return retval;
  }

  template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
    pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, BinaryPredicate pred)
  {
    while (first1 != last1)
    {
      if (!pred(*first1, *first2))
      {
        break;
      }

      ++first1;
      ++first2;
    }

    pair<InputIterator1, InputIterator2> retval;
    retval.first = first1;
    retval.second = first2;
    return retval;
  }

  template<class InputIterator1, class InputIterator2> _UCXXEXPORT
    bool
    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
  {
    while (first1 !=last1)
    {
      if (*first1 != *first2)
      {
        return false;
      }

      ++first1;
      ++first2;
    }

    return true;
  }

  template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
    bool
    equal(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, BinaryPredicate pred)
  {
    while (first1 !=last1)
    {
      if (!pred(*first1, *first2))
      {
        return false;
      }

      ++first1;
      ++first2;
    }

    return true;
  }

  template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
    ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2)
  {
    equal_to<typename iterator_traits<ForwardIterator1>::value_type> c;
    return search(first1, last1, first2, last2, c);
  }

  template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred)
  {
    while (first1 != last1)
    {
      ForwardIterator1 temp1(first1);
      ForwardIterator2 temp2(first2);
      while (temp2 != last2 && temp1 != last1)
      {
        if (!pred(*temp2, *temp1))
        {
          break;
        }

        ++temp1;
        ++temp2;
        if (temp2 == last2)
        {
          return first1;
        }
      }

      ++first1;
    }

    return last1;
  }


  template<class ForwardIterator, class Size, class T> _UCXXEXPORT
    ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
  {
    while (first != last)
    {
      if (*first == value)
      {
        ForwardIterator temp(first);
        Size i = 1;
        ++first;  // Avoid doing the same comparison over again
        while (i < count && *temp == value)
        {
          ++first;
          ++i;
        }

        if (i == count)
        {
          return first;
        }
      }

      ++first;
    }

    return first;
  }


  template<class ForwardIterator, class Size, class T, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last,
      Size count, const T& value, BinaryPredicate pred)
  {
    while (first != last)
    {
      if (pred(*first, value))
      {
        ForwardIterator temp(first);
        Size i = 1;
        ++first;  // Avoid doing the same comparison over again
        while (i < count && pred(*temp, value))
        {
          ++first;
          ++i;
        }

        if (i == count)
        {
          return first;
        }
      }
      
      ++first;
    }
    
    return first;
  }

  // Subclause _lib.alg.modifying.operations_, modifying sequence operations:

  template<class InputIterator, class OutputIterator> _UCXXEXPORT
    OutputIterator
    copy(InputIterator first, InputIterator last, OutputIterator result)
  {
    while (first != last)
    {
      *result = *first;
      ++first;
      ++result;
    }

    return result;
  }

  template<class BidirectionalIterator1, class BidirectionalIterator2> _UCXXEXPORT
    BidirectionalIterator2
    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
      BidirectionalIterator2 result)
  {
    while (first !=last)
    {
      --result;
      --last;
      *result = *last;
    }

    return result;
  }

  template<class T> _UCXXEXPORT void swap(T& a, T& b)
  {
    T temp(a);
    a = b;
    b = temp;
  }

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

    return first2;
  }

  template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
    void
    iter_swap(ForwardIterator1 a, ForwardIterator2 b)
  {
    typename iterator_traits<ForwardIterator1>::value_type temp(*a);
    *a = *b;
    *b = temp;
  }

  template<class InputIterator, class OutputIterator, class UnaryOperation> _UCXXEXPORT
    OutputIterator
    transform(InputIterator first, InputIterator last,
      OutputIterator result, UnaryOperation op)
  {
    while (first != last)
    {
      *result = op(*first);
      ++first;
      ++result;
    }

    return result;
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> _UCXXEXPORT
    OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, OutputIterator result,
      BinaryOperation binary_op)
  {
    while (first1 != last1)
    {
      *result = binary_op(*first1, *first2);
      ++first1;
      ++first2;
      ++result;
    }

    return result;
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    void
    replace(ForwardIterator first, ForwardIterator last,
      const T& old_value, const T& new_value)
  {
    while (first != last)
    {
      if (*first == old_value)
      {
        *first = new_value;
      }

      ++first;
    }
  }

  template<class ForwardIterator, class Predicate, class T> _UCXXEXPORT
    void
    replace_if (ForwardIterator first, ForwardIterator last,
      Predicate pred, const T& new_value)
  {
    while (first != last)
    {
      if (pred(*first))
      {
        *first = new_value;
      }

      ++first;
    }
  }

  template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
    OutputIterator
    replace_copy(InputIterator first, InputIterator last,
      OutputIterator result, const T& old_value, const T& new_value)
  {
    while (first != last)
    {
      if (*first == old_value)
      {
        *result = new_value;
      }
      else
      {
        *result = *first;
      }

      ++first;
      ++result;
    }

    return result;
  }

  template<class Iterator, class OutputIterator, class Predicate, class T> _UCXXEXPORT
    OutputIterator
    replace_copy_if (Iterator first, Iterator last,
      OutputIterator result, Predicate pred, const T& new_value)
  {
    while (first != last)
    {
      if (pred(*first))
      {
        *result = new_value;
      }
      else
      {
        *result = *first;
      }

      ++first;
      ++result;
    }

    return result;
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    void
    fill(ForwardIterator first, ForwardIterator last, const T& value)
  {
    while (first != last)
    {
      *first = value;
      ++first;
    }
  }

  template<class OutputIterator, class Size, class T> _UCXXEXPORT
    void
    fill_n(OutputIterator first, Size n, const T& value)
  {
    while (n != 0)
    {
      *first = value;
      --n;
      ++first;
    }
  }

  template<class ForwardIterator, class Generator> _UCXXEXPORT
    void
    generate(ForwardIterator first, ForwardIterator last, Generator gen)
  {
    while (first != last)
    {
      *first = gen();
      ++first;
    }
  }

  template<class OutputIterator, class Size, class Generator> _UCXXEXPORT
    void
    generate_n(OutputIterator first, Size n, Generator gen)
  {
    while (n !=0)
    {
      *first = gen();
      --n;
      ++first;
    }
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    ForwardIterator
    remove(ForwardIterator first, ForwardIterator last, const T& value)
  {
    ForwardIterator temp(first);
    while (temp !=last)
    {
      if (*temp == value)
      {

      }
      else
      {
        *first = *temp;
        ++first;
      }

      ++temp;
    }

    return first;
  }

  template<class ForwardIterator, class Predicate> _UCXXEXPORT
    ForwardIterator
    remove_if (ForwardIterator first, ForwardIterator last, Predicate pred)
  {
    ForwardIterator temp(first);
    while (temp !=last)
    {
      if (pred(*temp))
      {
      }
      else
      {
        *first = *temp;
        ++first;
      }

      ++temp;
    }

    return first;
  }

  template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
    OutputIterator
    remove_copy(InputIterator first, InputIterator last,
      OutputIterator result, const T& value)
  {
    while (first !=last)
    {
      if (*first != value)
      {
        *result = *first;
        ++result;
      }

      ++first;
    }

    return result;
  }

  template<class InputIterator, class OutputIterator, class Predicate> _UCXXEXPORT
    OutputIterator
    remove_copy_if (InputIterator first, InputIterator last,
      OutputIterator result, Predicate pred)
  {
    while (first !=last)
    {
      if (!pred(*first))
      {
        *result = *first;
        ++result;
      }

      ++first;
    }

    return result;
  }

  template<class ForwardIterator> _UCXXEXPORT
    ForwardIterator
    unique(ForwardIterator first, ForwardIterator last)
  {
    ForwardIterator new_val(first);
    ForwardIterator old_val(first);

    while (new_val !=last)
    {
      if (*new_val == *old_val && new_val != old_val)
      {
      }
      else
      {
        *first = *new_val;
        old_val = new_val;
        ++first;
      }

      ++new_val;
    }

    return first;
  }

  template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
    ForwardIterator
    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
  {
    ForwardIterator new_val(first);
    ForwardIterator old_val(first);

    while (new_val !=last)
    {
      if (pred(*new_val, *old_val) && new_val != old_val)
      {
      }
      else
      {
        *first = *new_val;
        old_val = new_val;
        ++first;
      }

      ++new_val;
    }

    return first;
  }

  template<class InputIterator, class OutputIterator> _UCXXEXPORT
    OutputIterator
    unique_copy(InputIterator first, InputIterator last, OutputIterator result)
  {
    InputIterator temp(first);
    while (first !=last)
    {
      if (*first == *temp && first != temp)
      {
      }
      else
      {
        *result = *first;
        temp = first;
        ++result;
      }

      ++first;
    }

    return result;
  }

  template<class InputIterator, class OutputIterator, class BinaryPredicate> _UCXXEXPORT
    OutputIterator
    unique_copy(InputIterator first, InputIterator last,
      OutputIterator result, BinaryPredicate pred)
  {
    InputIterator temp(first);
    while (first !=last)
    {
      if (pred(*first, *temp) && first != temp)
      {
      }
      else
      {
        *result = *first;
        temp = first;
        ++result;
      }

      ++first;
    }

    return result;
  }

  template<class BidirectionalIterator> _UCXXEXPORT
    void
    reverse(BidirectionalIterator first, BidirectionalIterator last)
  {
    --last;    //Don't work with one past the end element
    while (first < last)
    {
      iter_swap(first, last);
      ++first;
      --last;
    }
  }

  template<class BidirectionalIterator, class OutputIterator> _UCXXEXPORT
    OutputIterator
    reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
    OutputIterator result)
  {
    while (last > first)
    {
      --last;
      *result = *last;
      ++result;
    }

    return result;
  }

  template<class ForwardIterator> _UCXXEXPORT
    void
    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
  {
    if ((first == middle) || (last  == middle))
    {
      return;
    }

    ForwardIterator first2 = middle;

    do
    {
      swap(*first, *first2);
      first++;
      first2++;
      if (first == middle)
      {
        middle = first2;
      }
    }
    while (first2 != last);

    first2 = middle;

    while (first2 != last)
    {
      swap(*first, *first2);
      first++;
      first2++;
      if (first == middle)
      {
        middle = first2;
      }
      else if (first2 == last)
      {
        first2 = middle;
      }
    }
  }

  template<class ForwardIterator, class OutputIterator> _UCXXEXPORT
    OutputIterator
    rotate_copy(ForwardIterator first, ForwardIterator middle,
      ForwardIterator last, OutputIterator result)
  {
    ForwardIterator temp(middle);
    while (temp !=last)
    {
      *result = *temp;
      ++temp;
      ++result;
    }

    while (first != middle)
    {
      *result = *first;
      ++first;
      ++result;
    }

    return result;
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void
    random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
  {
    --last;
    while (first != last)
    {
      iter_swap(first, (first + (rand() % (last - first))));
      ++first;
    }
  }

  template<class RandomAccessIterator, class RandomNumberGenerator> _UCXXEXPORT
    void
    random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
    RandomNumberGenerator& rand)
  {
    --last;
    while (first != last)
    {
      iter_swap(first, (first + (rand(last - first))));
      ++first;
    }
  }

  // _lib.alg.partitions_, partitions:

  template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
    partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
  {
    return stable_partition(first, last, pred);
  }

  template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
    stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
  {
    // First now points to the first non-desired element

    while (first != last && pred(*first)){
      ++first;
    }

    BidirectionalIterator tempb;
    BidirectionalIterator tempe = first;

    while (tempe != last)
    {
      //Find the next desired element

      while (!pred(*tempe))
      {
        ++tempe;

        //See if we should exit

        if (tempe == last)
        {
          return first;
        }
      }

      // Rotate the element back to the begining

      tempb = tempe;
      while (tempb != first)
      {
        iter_swap(tempb, tempb-1);
        --tempb;
      }

      // First now has a desired element

      ++first;
    }

    return first;
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void sort(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    sort(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
  {
    stable_sort(first, last, comp);
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    stable_sort(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
  {
    //FIXME - bubble sort

    RandomAccessIterator temp;
    --last;
    while (last - first > 0)
    {
      temp = last;
      while (temp != first)
      {
        if (comp(*temp, *(temp-1)))
        {
          iter_swap(temp-1, temp);
        }

        --temp;
      }

      ++first;
    }
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    partial_sort(first, middle, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
      RandomAccessIterator last, Compare comp)
  {
    //Fixme - partial bubble sort

    RandomAccessIterator temp;
    --last;
    while (first < middle)
    {
      temp = last;
      while (temp != first)
      {
        if (comp(*temp, *(temp -1)))
        {
          iter_swap(temp-1, temp);
        }

        --temp;
      }

      ++first;
    }
  }

  template<class InputIterator, class RandomAccessIterator> _UCXXEXPORT
    RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
      RandomAccessIterator result_first, RandomAccessIterator result_last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    return partial_sort_copy(first, last, result_first, result_last, c);
  }

  template<class InputIterator, class RandomAccessIterator, class Compare> _UCXXEXPORT
    RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)
  {
    size_t output_size = last-first;
    size_t temp_size = result_last - result_first;
    if (temp_size < output_size)
    {
      output_size = temp_size;
    }

    RandomAccessIterator middle = result_first + output_size;
    RandomAccessIterator temp = result_first;

    while (temp != middle)
    {
      *temp = *first;
      ++temp;
      ++first;
    }

    sort(result_first, middle, comp);

    while (first != last)
    {
      if (comp(*first, *(middle-1)))
      {
        *(middle-1) = *first;
        sort(result_first, middle, comp);
      }

      ++first;
    }

    return middle;
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    nth_element(first, nth, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
      RandomAccessIterator last, Compare comp)
  {
    partial_sort(first, nth, last, comp);
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
      const T& value)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return lower_bound(first, last, value, c);
  }

  template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
    ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
      const T& value, Compare comp)
  {
    if (first == last)
    {
      return last;
    }

    // If below or equal to the first element

    if (comp(*first, value) == false)
    {
      return first;
    }

    ForwardIterator middle;

    // If greater than the top element

    middle = first;
    advance(middle, distance(first, last) - 1);
    if (comp(*middle, value))
    {
      return last;
    }

    // Now begin the actual search for the begining

    while (distance(first, last) > 1)
    {
      // Find middle

      middle = first;
      advance(middle, (distance(first, last)/2));
      if (!comp(*middle, value))
      {
        last = middle;
      }
      else
      {
        first = middle;
      }
    }

    if (!comp(*first, value))
    {
      return first;
    }

    return last;
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
      const T& value)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return upper_bound(first, last, value, c);
  }

  template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
    ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
      const T& value, Compare comp)
  {
    if (first == last)
    {
      return last;
    }

    // If below the first element

    if (comp(value, *first) == true)
    {
      return first;
    }

    ForwardIterator middle;

    // If greater than the top element

    middle = first;
    advance(middle, distance(first, last) - 1);
    if (comp(*middle, value))
    {
      return last;
    }

    // Now begin the actual search for the end

    while (distance(first, last) > 1)
    {
      // Find middle

      middle = first;
      advance(middle, (distance(first, last)/2));
      if (comp(value, *middle))
      {
        last = middle;
      }
      else
      {
        first = middle;
      }
    }

    if (comp(value, *first))
    {
      return first;
    }

    return last;
  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first, ForwardIterator last, const T& value)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return equal_range(first, last, value, c);
  }

  template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
    pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
  {
    pair<ForwardIterator, ForwardIterator> retval;
    retval.first = lower_bound(first, last, value, comp);

    //Reuse retval.first in order to (possibly) save a few comparisons

    retval.second = upper_bound(retval.first, last, value, comp);
    return retval;

  }

  template<class ForwardIterator, class T> _UCXXEXPORT
    bool binary_search(ForwardIterator first, ForwardIterator last,
      const T& value)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return binary_search(first, last, value, c);
  }

  template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
    bool binary_search(ForwardIterator first, ForwardIterator last,
      const T& value, Compare comp)
  {
    if (distance(first, last) == 0)
    {
      return false;
    }

    ForwardIterator middle;

    while (distance(first, last) > 1)
    {
      //Set middle between first and last

      middle = first;
      advance(middle, distance(first, last)/2);

      if (comp(*middle, value) == true)
      {
        first = middle;
      }
      else
      {
        last = middle;
      }
    }

    if (!comp(*first, value) && !comp(value, *first))
    {
      return true;
    }

    if (!comp(*last, value) && !comp(value, *last))
    {
      return true;
    }

    return false;
  }

  // _lib.alg.merge_, merge:

  template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
    OutputIterator
    merge(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return merge(first1, last1, first2, last2, result, c);
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
    OutputIterator
    merge(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      //If in this order so first1 elements which are equal come first

      if (comp(*first2, *first1))
      {
        *result = *first2;
        ++first2;
      }
      else
      {
        *result = *first1;
        ++first1;
      }

      ++result;
    }

    //Clean up remaining elements

    while (first1 != last1)
    {
      *result = *first1;
      ++first1;
      ++result;
    }

    while (first2 != last2)
    {
      *result = *first2;
      ++first2;
      ++result;
    }

    return result;
  }

  template<class BidirectionalIterator> _UCXXEXPORT
    void inplace_merge(BidirectionalIterator first,
      BidirectionalIterator middle, BidirectionalIterator last)
  {
    less<typename iterator_traits<BidirectionalIterator>::value_type> c;
    inplace_merge(first, middle, last, c);
  }

  template<class BidirectionalIterator, class Compare> _UCXXEXPORT
    void inplace_merge(BidirectionalIterator first,
      BidirectionalIterator middle, BidirectionalIterator last, Compare comp)
  {
    //FIXME - using a bubble exchange method

    while (first != middle && middle !=last)
    {
      if (comp(*middle, *first))
      {
        BidirectionalIterator temp(middle);
        while (temp != first)
        {
          iter_swap(temp, temp-1);
          --temp;
        }

        ++middle;
      }

      ++first;
    }
  }

  // _lib.alg.set.operations_, set operations:

  template<class InputIterator1, class InputIterator2> _UCXXEXPORT
    bool includes(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return includes(first1, last1, first2, last2, c);
  }

  template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
    bool includes(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, Compare comp)
  {
    while (first2 != last2)
    {
      //Advance the large set until no longer smaller than the element we are looking for

      while (comp(*first1, *first2))
      {
        ++first1;

        // If we are at the end of the list, we don't have the desired element

        if (first1 == last1)
        {
          return false;
        }
      }

      // If we are past the element we want, it isn't here

      if (comp(*first2, *first1))
      {
        return false;
      }

      ++first2;  //Move to next element
    }

    return true;
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
    OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return set_union(first1, last1, first2, last2, result, c);
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
    OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      if (comp(*first2, *first1))
      {
        *result = *first2;

        // Eliminate duplicates

        InputIterator2 temp = first2;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }

        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }
      }
      else
      {
        *result = *first1;

        // Eliminate duplicates

        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }

        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }
      }
      ++result;
    }

    // Clean up remaining elements

    while (first1 != last1)
    {
      *result = *first1;
      ++result;
      InputIterator1 temp = first1;
      while (first1 != last1 && !comp(*temp, *first1))
      {
        ++first1;
      }
    }

    while (first2 != last2)
    {
      *result = *first2;
      ++result;
      InputIterator2 temp = first2;
      while (first2 != last2 && !comp(*temp, *first2))
      {
        ++first2;
      }
    }

    return result;
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
    OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return set_intersection(first1, last1, first2, last2, result, c);
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
    OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      if (comp(*first2, *first1))
      {
        ++first2;
      }
      else if (comp(*first1, *first2))
      {
        ++first1;
      }
      else
      {
        *result = *first1;
        ++result;
        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }

        ++first2;
      }
    }

    return result;
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
    OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return set_difference(first1, last1, first2, last2, result, c);
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
    OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      if (comp(*first1, *first2))
      {
        *result = *first1;
        ++result;

        // Eliminate duplicates

        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }
      }
      else if (comp(*first2, *first1))
      {
        // Eliminate duplicates

        InputIterator2 temp = first2;
        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }

      }
      else
      {
        //They are identical - skip
        // Eliminate duplicates

        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }

        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }
      }
    }

    // Clean up remaining elements

    while (first1 != last1)
    {
      *result = *first1;
      ++result;
      InputIterator1 temp = first1;
      while (first1 != last1 && !comp(*temp, *first1))
      {
        ++first1;
      }
    }

    return result;
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
    OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return set_symmetric_difference(first1, last1, first2, last2, result, c);
  }

  template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
    OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      if (comp(*first1, *first2))
      {
        *result = *first1;
        ++result;

        // Eliminate duplicates

        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }
      }
      else if (comp(*first2, *first1))
      {
        *result = *first2;
        ++result;

        // Eliminate duplicates

        InputIterator2 temp = first2;
        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }

      }
      else
      {
        //They are identical - skip
        // Eliminate duplicates

        InputIterator1 temp = first1;
        while (first1 != last1 && !comp(*temp, *first1))
        {
          ++first1;
        }

        while (first2 != last2 && !comp(*temp, *first2))
        {
          ++first2;
        }
      }
    }

    // Clean up remaining elements

    while (first1 != last1)
    {
      *result = *first1;
      ++result;
      InputIterator1 temp = first1;
      while (first1 != last1 && !comp(*temp, *first1))
      {
        ++first1;
      }
    }

    while (first2 != last2)
    {
      *result = *first2;
      ++result;
      InputIterator2 temp = first2;
      while (first2 != last2 && !comp(*temp, *first2))
      {
        ++first2;
      }
    }

    return result;
  }

  // _lib.alg.heap.operations_, heap operations:

  template<class RandomAccessIterator> _UCXXEXPORT
    void push_heap(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    push_heap(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
  {
    // *(last - 1) is the last element

    RandomAccessIterator begin, middle, end;
    begin = first;
    end = last - 2;

    if (last - first < 2)
    {
      //Empty heap

      return;
    }

    if (comp(*(last-1), *end))
    {
      //Belongs past the end - already in place

      return;
    }

    while (end - begin > 1)
    {
      middle = begin + ((end - begin)/2);
      if (comp(*middle, *(last-1)))
      {
        end = middle;
      }
      else
      {
        begin = middle;
      }
    }

    if (comp(*begin, *(last-1)))
    {
      middle = begin;
    }
    else
    {
      middle = end;
    }

    // Now all we do is swap the elements up to the begining

    --last;

    while (last > middle)
    {
      iter_swap(last, last-1);
      --last;
    }
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    pop_heap(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare)
  {
    --last;
    while (first < last)
    {
      iter_swap(first, first+1);
      ++first;
    }
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void make_heap(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    make_heap(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
  {
    sort(reverse_iterator<RandomAccessIterator>(last), reverse_iterator<RandomAccessIterator>(first), comp);
  }

  template<class RandomAccessIterator> _UCXXEXPORT
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
  {
    less<typename iterator_traits<RandomAccessIterator>::value_type> c;
    sort_heap(first, last, c);
  }

  template<class RandomAccessIterator, class Compare> _UCXXEXPORT
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
  {
    sort(first, last, comp);
  }

  // _lib.alg.min.max_, minimum and maximum:

  template<class T> _UCXXEXPORT
    const T& min(const T& a, const T& b)
  {
    if (b < a)
    {
      return b;
    }

    return a;
  }

  template<class T, class Compare> _UCXXEXPORT
    const T& min(const T& a, const T& b, Compare comp)
  {
    if (comp(b, a) == true)
    {
      return b;
    }

    return a;
  }

  template<class T> _UCXXEXPORT
    const T& max(const T& a, const T& b)
  {
    if (a < b)
    {
      return b;
    }

    return a;
  }

  template<class T, class Compare> _UCXXEXPORT
    const T& max(const T& a, const T& b, Compare comp)
  {
    if (comp(a, b))
    {
      return b;
    }

    return a;
  }

  template<class ForwardIterator> _UCXXEXPORT
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return min_element(first, last, c);
  }

  template<class ForwardIterator, class Compare> _UCXXEXPORT
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp)
  {
    ForwardIterator retval = first;
    ++first;
    while (first != last)
    {
      if (comp(*first, *retval))
      {
        retval = first;
      }

      ++first;
    }

    return retval;
  }

  template<class ForwardIterator> _UCXXEXPORT
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
  {
    less<typename iterator_traits<ForwardIterator>::value_type> c;
    return max_element(first, last, c);
  }

  template<class ForwardIterator, class Compare> _UCXXEXPORT
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp)
  {
    ForwardIterator retval = first;
    ++first;
    while (first != last)
    {
      if (comp(*retval, *first))
      {
        retval = first;
      }

      ++first;
    }

    return retval;
  }

  template<class InputIterator1, class InputIterator2> _UCXXEXPORT
    bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2)
  {
    less<typename iterator_traits<InputIterator1>::value_type> c;
    return lexicographical_compare(first1, last1, first2, last2, c);
  }

  template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
    bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2, Compare comp)
  {
    while (first1 != last1 && first2 != last2)
    {
      if (comp(*first1, *first2))
      {
        return true;
      }

      if (comp(*first2, *first1))
      {
        return false;
      }

      ++first1;
      ++first2;
    }

    return first1 == last1 && first2 != last2;
  }

  // _lib.alg.permutation.generators_, permutations

  template<class BidirectionalIterator> _UCXXEXPORT
    bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
  {
    less<typename iterator_traits<BidirectionalIterator>::value_type> c;
    return next_permutation(first, last, c);
  }

  template<class BidirectionalIterator, class Compare> _UCXXEXPORT
    bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
  {
    if (first == last)
    {
      return false;  // No data
    }

    BidirectionalIterator i = last;
    --i;
    if (i == first)
    {
      return false;  //Only one element
    }

    BidirectionalIterator ii = i;
    --ii;

    // If the last two items are in order, swap them and call it done

    if (comp(*ii, *i))
    {
      iter_swap(ii, i);
      return true;
    }

    // This part of the algorithm copied from G++ header files ver. 3.4.2

    i = last;
    --i;
    for (;;)
    {
      ii = i;
      --i;
      if (comp(*i, *ii))
      {
        BidirectionalIterator j = last;
        --j;
        while (!comp(*i, *j))
        {
          --j;
        }

        iter_swap(i, j);
        reverse(ii, last);
        return true;
      }

      if (i == first)
      {
        reverse(first, last);
        return false;
      }
    }
  }

  template<class BidirectionalIterator> _UCXXEXPORT
    bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
  {
    less<typename iterator_traits<BidirectionalIterator>::value_type> c;
    return prev_permutation(first, last, c);
  }

  template<class BidirectionalIterator, class Compare> _UCXXEXPORT
    bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
  {
    if (first == last)
    {
      return false;  // No data
    }

    BidirectionalIterator i = last;
    --i;
    if (i == first)
    {
      return false;  //Only one element
    }

    BidirectionalIterator ii = i;
    --ii;

    // If the last two items are in reverse order, swap them and call it done

    if (comp(*i, *ii))
    {
      iter_swap(ii, i);
      return true;
    }

    // Copied from GNU GCC header files version 3.4.2

    i = last;
    --i;

    for (;;)
    {
      ii = i;
      --i;
      if (comp(*ii, *i))
      {
        BidirectionalIterator j = last;
        --j;
        while (!comp(*j, *i))
        {
          --j;
        }

        iter_swap(i, j);
        reverse(ii, last);
        return true;
      }

      if (i == first)
      {
        reverse(first, last);
        return false;
      }
    }
  }

} // namespace
} // extern "C++"

#pragma GCC visibility pop

#endif



