/*

Implements the STL generic partial_sort function using a different 
algorithm from the one in HP STL.  This algorithm makes a heap of
the entire sequence and then repeatedly extracts elements from it
with pop_heap.  Since STL heap operations are defined to extract
the maximum element, and the minimum is needed here, we first
define a converse_functor to compute the converse of the given
comparison function.

*/

/*
 * Copyright (c) 1997 Rensselaer Polytechnic Institute
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Rensselaer Polytechnic Institute makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

#ifndef PARTIAL_SORT_H
#define PARTIAL_SORT_H

#include <iterator.h>

template <class Function>
struct converse_functor
  : public binary_function<Function::second_argument_type,
                           Function::first_argument_type,
                           Function::result_type>
{
protected:
  Function f;
public:
  converse_functor(Function fun) : f(fun) { }

  result_type operator()(const first_argument_type& x,
                         const second_argument_type& y) const {
    return f(y, x);
  }
};

template <class Function>
inline converse_functor<Function> converse(const Function& f)
{
  return converse_functor<Function>(f);
}

template <class RandomAccessIterator, class T, class Compare>
void ___partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, last, converse_functor<Compare>(comp));
    for (RandomAccessIterator i = last; last - (middle - first) < i; --i)
       pop_heap(first, i, converse_functor<Compare>(comp));
    reverse(first, last);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort1(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp) {
    ___partial_sort(first, middle, last, value_type(first), comp);
}

#endif