/** -*- C++ -*-
 **
 **  KAI C++ Compiler
 **
 **  Copyright (C) 1996-2001 Intel Corp. All rights reserved.
 **/
/**
 **  Lib++  : The Modena C++ Standard Library,
 **           Version 2.4, October 1997
 **
 **  Copyright (c) 1995-1997 Modena Software Inc.
 **/

#ifndef __KAI_ALGORITHM
#define __KAI_ALGORITHM

#include <mcompile.h>

#include <algobase>
#include <heap>
#include <memory>

namespace __kai {
template <class T>
class temp_buf_cleanup {
    T *ptr;
public:
    size_t n_items;
    inline temp_buf_cleanup(T *p) : ptr(p), n_items(0) { }
    //    inline void set_cleanup_length(size_t n) { n_items = n; }
    inline void clear() { ptr = NULL; n_items = 0; }
    inline ~temp_buf_cleanup() {
	if (ptr) {
	    if (n_items)
		__kai::destroy(ptr, ptr + n_items);
	    std::return_temporary_buffer(ptr);
	}
    }
};

} // namespace __kai

namespace std {

// Subclause 25.1 -- Non-modifying sequence operations

// Section 25.1.1 -- For each
template <class InputIterator, class Function>
inline Function for_each(InputIterator first, InputIterator last, Function f)
{
    for (; first != last; ++first)
	f(*first);
    return f;
}

// Section 25.1.2 -- Find
template <class InputIterator, class T>
inline InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    while (first != last && !(*first == value))	// must have ==, but not necessarily !=
	++first;
    return first;
}

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


// Section 25.1.3  Find End

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
			  ForwardIterator2 first2, ForwardIterator2 last2)
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type Distance;
    Distance d1 = 0;
    Distance d2 = 0;
    d1 = distance(first1, last1);
    d2 = distance(first2, last2);

    if (d1 < d2) return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator1 iter_save = last1;

    while ((current1 = search(first1, last1, first2, last2)) != last1) {
	iter_save =  current1;
	first1 = iter_save;
	// what about searching for "TT" in the "TTT".
	// advance(first1, d2);
	++first1;
    }

    return iter_save;
}

template <class ForwardIterator1, class ForwardIterator2,
          class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
			  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred)
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type Distance;
    Distance d1 = distance(first1, last1);
    Distance d2 = distance(first2, last2);

    ForwardIterator1 result = last1;

    if (d1 < d2)
	return result;

    ForwardIterator1 current1 = first1;
    ForwardIterator1 iter_save = last1;

    while ((current1 = search(first1, last1, first2, last2, binary_pred)) != last1) {
	iter_save =  current1;
	first1 = iter_save;
	// what about searching for "TT" in the "TTT".
	// advance(first1, d2);
	++first1;
    }

    return iter_save;
}

// Section 25.1.4 -- Find First
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
			       ForwardIterator2 first2, ForwardIterator2 last2)
{
    ForwardIterator1   current1 = first1;
    ForwardIterator2   current2 = first2;

    while (current1 != last1) {
        while (current2 != last2)
            if (*current1 == *current2)
                return current1;
            else
                ++current2;
        ++current1;
        current2 = first2;
    }
    return last1;
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
			       ForwardIterator2 first2, ForwardIterator2 last2,
			       BinaryPredicate binary_pred)
{
    ForwardIterator1   current1 = first1;
    ForwardIterator2   current2 = first2;

    while (current1 != last1) {
        while (current2 != last2)
            if (binary_pred(*current1, *current2))
                return current1;
            else
                ++current2;
        ++current1;
        current2 = first2;
    }
    return last1;
}


// Section 25.1.5 -- Adjacent find
template <class ForwardIterator>
inline ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
{
    if (first == last)
	return last;
    ForwardIterator next = first;
    while (++next != last) {
        if (*first == *next)
	    return first;
        first = next;
    }
    return last;
}

template <class ForwardIterator, class BinaryPredicate>
inline ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
{
    if (first == last)
	return last;
    ForwardIterator next = first;
    while (++next != last) {
        if (binary_pred(*first, *next))
	    return first;
        first = next;
    }
    return last;
}

// Section 25.1.6 -- Count
template <class InputIterator, class T>
inline typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value)
{
    iterator_traits <InputIterator>::difference_type n = 0;
    for (; first != last; ++first) 
        if (*first == value)
	    ++n;
    return n;
}

template <class InputIterator, class Predicate>
inline typename iterator_traits <InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
{
    iterator_traits <InputIterator>::difference_type n = 0;
    for (; first != last; ++first) 
        if (pred (*first))
	    ++n;
    return n;
}

// Section 25.1.7 -- Mismatch -- in algobase.h
// Section 25.1.8 -- Equal -- in algobase.h

// Section 25.1.9 -- Search

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
			ForwardIterator2 first2, ForwardIterator2 last2)
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type Distance1;
    typedef  typename iterator_traits<ForwardIterator2>::difference_type Distance2;
    Distance1 d1 = distance(first1, last1);
    Distance2 d2 = distance(first2, last2);

    if (d1 < d2)
	return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    while (current2 != last2) {
        if (*current1 == *current2) {
	    ++current1;
	    ++current2;
	} else if (d1 == d2)
	    return last1;
	else {
	    --d1;
	    current1 = ++first1;
	    current2 = first2;
	}
    }
    return (current2 == last2) ? first1 : last1;
}

template <class ForwardIterator1, class ForwardIterator2,
          class BinaryPredicate>
ForwardIterator1
search (ForwardIterator1 first1, ForwardIterator1 last1,
          ForwardIterator2 first2, ForwardIterator2 last2,
          BinaryPredicate binary_pred)
{
    typedef  typename iterator_traits<ForwardIterator1>::difference_type Distance1;
    typedef  typename iterator_traits<ForwardIterator2>::difference_type Distance2;
    Distance1 d1 = distance(first1, last1);
    Distance2 d2 = distance(first2, last2);

    if (d1 < d2)
	return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    for (; current2 != last2; ) {
        if (binary_pred(*current1, *current2)) {
	    ++current1;
	    ++current2;
	} else if (d1 == d2)
	    return last1;
	else {
	    --d1;
	    current1 = ++first1;
	    current2 = first2;
	}
    }
    return (current2 == last2) ? first1 : last1;
}

// Rewritten by ADR to replace earlier version by Modena that was buggy
// and quadratically slow.  Modena has fixed their version as of 2.2 and
// made it linearly fast, but ADR believes his variant may be faster
// as it uses only a single pass over the sequence.  Someone should 
// time ADR vs. Modena's code.
template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
			 Size sz, const T& value)
{
    if( sz==0 )
	return first;

    for( ; first!=last; ++first ) {
	if( *first==value ) {
	    Size count=sz; 
	    ForwardIterator result = first;
	    do {
		if( --count==0 )
		    return result;
		if( ++first==last )
		    return last;
	    } while( *first==value );
	}
    }
    return last;
}

// Rewritten by ADR.  See comments for other version of search_n above.
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size sz, const T& value, BinaryPredicate b_pred)
{
    if( sz==0 )
	return first;

    for( ; first!=last; ++first ) {
	if( b_pred(*first,value) ) {
	    Size count=sz; 
	    ForwardIterator result = first;
	    do {
		if( --count==0 )
		    return result;
		if( ++first==last )
		    return last;
	    } while( b_pred(*first,value) );
	}
    }
    return last;
}

// 25.2 -- Mutating sequence operations

// Section 25.2.1 -- Copy -- in algobase.h
// Section 25.2.1 -- Copy backward -- in algobase.h
// Section 25.2.2 -- Swap -- in algobase.h

// Section 25.2.2 -- Swap ranges
template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) 
{
    for (; first1 != last1; ++first1, ++first2)
	iter_swap(first1, first2);
    return first2;
}

template <class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
{
    typedef typename iterator_traits <ForwardIterator1>::value_type Value;
    Value tmp = *a;
    *a = *b;
    *b = tmp;
}


// Section 25.2.3 -- Transform
template <class InputIterator, class OutputIterator, class UnaryOperation>
inline OutputIterator transform(InputIterator first, InputIterator last,
				OutputIterator result, UnaryOperation op)
{
    for (; first != last; ++first, ++result)
	*result = op(*first);
    return result;
}

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

// Section 25.2.4.1 -- Replace
template <class ForwardIterator, class T>
inline 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>
inline void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value)
{
    while (first != last) {
        if (pred(*first))
	    *first = new_value;
        ++first;
    }
}

// Section 25.2.4.2 -- Replace copy
template <class InputIterator, class OutputIterator, class T>
inline OutputIterator replace_copy(InputIterator first, InputIterator last,
				   OutputIterator result, const T& old_value,
				   const T& new_value)
{
    while (first != last) {
        *result = *first == old_value ? new_value : *first;
        ++result;
        ++first;
    }
    return result;
}

template <class Iterator, class OutputIterator, class Predicate, class T>
inline OutputIterator replace_copy_if(Iterator first, Iterator last,
				      OutputIterator result, Predicate pred,
				      const T& new_value)
{
    while (first != last) {
        *result = pred(*first) ? new_value : *first;
        ++result;
        ++first;
    }
    return result;
}

// Section 25.2.5 -- Fill -- in algobase.h

// Section 25.2.6 -- Generate
template <class ForwardIterator, class Generator>
inline void generate(ForwardIterator first, ForwardIterator last, Generator gen)
{
    for (; first != last; ++first)
	*first = gen();
}

template <class OutputIterator, class Size, class Generator>
inline OutputIterator generate_n(OutputIterator first, Size n, Generator gen)
{
    for (; n > 0; --n, ++first)
	*first = gen();
    return first;
}

// Section 25.2.7 -- Remove
template <class ForwardIterator, class T>
inline ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value)
{
    first = find(first, last, value);
    ForwardIterator next = first;
    return first == last ? last : remove_copy(++next, last, first, value);
}

template <class ForwardIterator, class Predicate>
inline ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred)
{
    first = find_if(first, last, pred);
    ForwardIterator next = first;
    return first == last ? last : remove_copy_if(++next, last, first, pred);
}

template <class InputIterator, class OutputIterator, class T>
inline OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value)
{
    while (first != last) {
        if (!(*first == value)) {	// != may not be defined for T
	    *result = *first;
	    ++result;
	}
        ++first;
    }
    return result;
}

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

// Section 25.2.8 -- Unique 
template <class ForwardIterator>
inline ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
    first = adjacent_find(first, last);
    return unique_copy(first, last, first);
}

template <class ForwardIterator, class BinaryPredicate>
inline ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
{
    first = adjacent_find(first, last, binary_pred);
    return unique_copy(first, last, first, binary_pred);
}

template <class InputIterator, class OutputIterator>
inline OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result)
{
    if (first == last)
	return result;

    typename iterator_traits<InputIterator>::value_type value = *first;
    *result = value;
    while (++first != last)
        if (!(value == *first)) {	// != may not be defined for value_type
            value = *first;
            *++result = value;
        }
    return ++result;
}


template <class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
{
    if (first == last)
	return result;
    typename iterator_traits<InputIterator>::value_type value = *first;
    *result = value;
    while (++first != last)
        if (!binary_pred(value, *first)) {
            value = *first;
            *++result = value;
        }
    return ++result;
}

// Section 25.2.9.1 -- Reverse
template <class BidirectionalIterator>
inline void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag)
{
    for (; first != last && first != --last; ++first) {
	iter_swap(first, last);
    }
}

template <class RandomAccessIterator>
inline void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
    if( first==last ) return;
    --last;
    for (; first < last; ++first, --last)
	iter_swap(first, last);
}

template <class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
{
    typedef typename iterator_traits <BidirectionalIterator>::iterator_category Category;
    __reverse(first, last, Category());
}

template <class BidirectionalIterator, class OutputIterator>
inline OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
{
    for (; first != last; ++result)
	*result = *--last;
    return result;
}

// Section 25.2.10.1 -- Rotate

// The algorithm cyclicly rotates the sequence [xb,yb)[yb,ye) such that *yb is
// moved to *xb.  The algorithm is based upon the observation that generalizing
// it to cyclicly rotate the sequence [xb,xe)[yb,ye) makes it easier, because
// one simple can greedily swap *xb and *yb, and then have a smaller similar
// problem that can be solved recursively.  The recursions are tail-recursions
// and thus are easily eliminated by hand. -- adr Jan 16, 1999
template <class ForwardIterator>
inline void rotate (ForwardIterator xb, ForwardIterator yb, ForwardIterator ye)
{
    if (xb == yb || yb == ye)
	return;
    ForwardIterator xe = yb;
    ForwardIterator xp = xb;
    ForwardIterator yp = yb;
    // We don't need to keep track of xb because the first time through
    // will cause the correct elements to be placed there.
    while( xp!=xe && yp!=ye ) {
    	// Let m be min(xe-xb,ye-yb).
    	// Swap sequences [xb,xb+m) and [yb,yb+m)
        for(;;) {
            swap( *yp, *xp );
            ++yp;
            ++xp;
            if( xp==xe ) { // m==xe-xb
                xp=yb;
                yb=yp;	
                xe=yp;
   		break;
            }
            if( yp==ye ) { // m==ye-yb
                yp=yb;
                break;
            }
	}
    }     
}

// Section 25.2.10.2 -- Rotate copy

template <class ForwardIterator, class OutputIterator>
inline
OutputIterator
rotate_copy (ForwardIterator first, ForwardIterator middle,
             ForwardIterator last, OutputIterator result)
{
    return copy(first, middle, copy(middle, last, result));
}

// inlined code for the function "long_random"
// speeds up compilation times significantly on UNIX machines
 
// Section 25.2.11 -- Random Shuffle
 
class __random_generator {
protected:
    unsigned long table[55];
    size_t index1;
    size_t index2;
    __KAI_DECL_SHARED_OBJ_LOCK(simple_mutex,_mutex)
public:
    unsigned long operator()(unsigned long limit)
    {
	__KAI_SWRITE_LOCK(simple_mutex,_mutex);
        index1 = (index1 + 1) % 55;
        index2 = (index2 + 1) % 55;
        table[index1] = table[index1] - table[index2];
        return table[index1] % limit;
    }
    void seed(unsigned long j);
    __random_generator(unsigned long j) { seed (j); }
};
 
// #define MSIPL_SEED_RANDOM 161803398
extern __random_generator __msipl_rd;

inline unsigned long
__long_random(unsigned long limit)
{
    return __msipl_rd(limit);
}

template <class RandomAccessIterator>
inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    if (first == last)
	return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        iter_swap(i, first + Distance(__long_random((i - first) + 1)));
}

template <class RandomAccessIterator, class RandomNumberGenerator>
inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator rand)
{
    if (first == last)
	return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        iter_swap(i, first + rand((i - first) + 1));
}

// Section 25.2.12 -- partition
template <class BidirectionalIterator, class Predicate>
inline BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
{
    while (true) {
        while (true) {
            if (first == last)
                return first;
            else if (pred(*first))
                ++first;
            else
                break;
	}
        --last;
        while (true) {
            if (first == last)
                return first;
            else if (!pred(*last))
                --last;
            else
                break;
	}
        iter_swap(first, last);
        ++first;
    }
}

// Section 25.2.12 -- stable partition
template <class ForwardIterator, class Predicate, class Distance>
ForwardIterator __inplace_stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred, Distance len)
{
    if (len == 1)
	return pred(*first) ? last : first;
    ForwardIterator middle = first;
    Distance half = len / 2;
    advance(middle, half);
    ForwardIterator first_cut = __inplace_stable_partition(first, middle, pred, half);
    ForwardIterator second_cut = __inplace_stable_partition(middle, last, pred, len - half);
    rotate(first_cut, middle, second_cut);
    len = distance(middle, second_cut);
    advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Pointer, class Predicate, class Distance>
ForwardIterator __stable_partition_adaptive(ForwardIterator first, ForwardIterator last,
					    Predicate pred, Distance len, Pointer buffer, Distance buffer_size, size_t& fill_pointer)
{
    typedef typename iterator_traits<ForwardIterator>::value_type T;
    if (len <= buffer_size) {
        len = 0;
        ForwardIterator result1 = first;
        Pointer result2 = buffer;
        for (; first != last && len < fill_pointer; ++first) {
            if (pred(*first)) {
		*result1 = *first;
		++result1;
	    } else {
                *result2 = *first;
                ++len;
		++result2;
            }
	}
        if (first != last) {
            raw_storage_iterator<Pointer, T> result3(result2);
            while (first != last) {
                if (pred(*first)) {
		    *result1 = *first;
		    ++result1;
		} else {
                    *result3 = *first;
		    ++fill_pointer;
		    ++result3;
                    ++len;
                }
		++first;
	    }
        }
        copy(buffer, buffer + len, result1);
        return result1;
    }
    ForwardIterator middle = first;
    Distance half = len / 2;
    advance(middle, half);
    ForwardIterator first_cut = __stable_partition_adaptive(first, middle, pred, half, buffer, buffer_size, fill_pointer);
    ForwardIterator second_cut = __stable_partition_adaptive(middle, last, pred, len - half, buffer, buffer_size, fill_pointer);
    rotate(first_cut, middle, second_cut);
    len = distance(middle, second_cut);
    advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred)
{
    typedef typename iterator_traits<ForwardIterator>::difference_type Distance;
    typedef typename iterator_traits<ForwardIterator>::value_type Value;
    typedef Value * Pointer;
    Distance len = distance(first, last);
    pair<Pointer,Distance> p = get_temporary_buffer<Value>(len);
    if (p.first == 0)
        return __inplace_stable_partition(first, last, pred, len);
    __kai::temp_buf_cleanup<Value> tbc(p.first); // ensure that the temp buffer is cleaned up if an exception is thrown.
    ForwardIterator result;
    result = __stable_partition_adaptive(first, last, pred, len, p.first, p.second, tbc.n_items);
    return result;
}

// Subclause 25.3 -- Sorting and related algorithms
template <class RandomAccessIterator, class T>
inline RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot)
{
    while (1) {
        while (*first < pivot)
	    ++first;
        --last;
        while (pivot < *last)
	    --last;
        if (! (first < last))
	    return first;
        iter_swap(first, last);
        ++first;
    }
}    

template <class RandomAccessIterator, class T, class Compare>
inline RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last,
						  T pivot, Compare comp)
{
    while (1) {
        while (comp(*first, pivot))
	    ++first;
        --last;
        while (comp (pivot, *last))
	    --last;
        if (! (first < last))
	    return first;
        iter_swap(first, last);
        ++first;
    }
}

template <class T>
inline const T& __median(const T& a, const T& b, const T& c)
{
    if (a < b)
        if (b < c)
            return b;
        else if (a < c)
            return c;
        else
            return a;
    else if (a < c)
        return a;
    else if (b < c)
        return c;
    else
        return b;
}

template <class T, class Compare>
inline const T& __median(const T& a, const T& b, const T& c, Compare comp)
{
    if (comp(a, b))
        if (comp(b, c))
            return b;
        else if (comp(a, c))
            return c;
        else
            return a;
    else if (comp(a, c))
        return a;
    else if (comp(b, c))
        return c;
    else
        return b;
}

template <class RandomAccessIterator>
inline void __linear_insert(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    Value value = *last;
    if (value < *first) {
        copy_backward(first, last, last + 1);
        *first = value;
    } else {
	RandomAccessIterator next = last;
	--next;
	while (value < *next) {
	    *last = *next;
	    last = next;
	    --next;
	}
	*last = value;
    }
}

template <class RandomAccessIterator, class Compare>
inline void __linear_insert(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    Value value = *last;
    if (comp(value, *first)) {
        copy_backward (first, last, last + 1);
        *first = value;
    } else {
	RandomAccessIterator next = last;
	--next;  
	while (comp(value, *next)) {
	    *last = *next;
	    last = next;
	    --next;
	}
	*last = value;
    }
}

template <class RandomAccessIterator>
inline void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    if (first == last)
	return; 
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i);
}

template <class RandomAccessIterator, class Compare>
inline void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    if (first == last)
	return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, comp);
}


// Section 25.3.1 -- Sorting

// Section 25.3.1.1 -- sort

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last)
{
    static const int __stl_threshold = 16;
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    while (last - first > __stl_threshold) {
	Value pivot(__median(*first, * (first + (last - first)/2), *(last - 1)));
        RandomAccessIterator cut = __unguarded_partition(first, last, pivot);
        if (cut - first >= last - cut) {
            sort(cut, last);
            last = cut;
        } else {
            sort(first, cut);
            first = cut;
        }
    }
    if (last-first > 0) {
	__insertion_sort(first,last);
    }
}

template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    static const int __stl_threshold = 16;
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    while (last - first > __stl_threshold) {
	Value pivot(__median(*first, * (first + (last - first)/2), *(last - 1), comp));
        RandomAccessIterator cut = __unguarded_partition(first, last, pivot, comp);
        if (cut - first >= last - cut) {
            sort(cut, last, comp);
            last = cut;
        } else {
            sort(first, cut, comp);
            first = cut;
        }
    }
    if (last-first > 0) {
	__insertion_sort(first,last,comp);
    }
}


template <class RandomAccessIterator>
void __inplace_stable_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    if (last - first < 15) {
        __insertion_sort(first, last);
        return;
    }
    RandomAccessIterator middle = first + (last - first) / 2;
    __inplace_stable_sort(first, middle);
    __inplace_stable_sort(middle, last);
    __merge_without_buffer(first, middle, last, middle - first, last - middle);
}

template <class RandomAccessIterator, class Compare>
void __inplace_stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    if (last - first < 15) {
        __insertion_sort(first, last, comp);
        return;
    }
    RandomAccessIterator middle = first + (last - first) / 2;
    __inplace_stable_sort(first, middle, comp);
    __inplace_stable_sort(middle, last, comp);
    __merge_without_buffer(first, middle, last, middle - first, last - middle, comp);
}

// The code has been removed from here in the latest STL release.
template <class RandomAccessIterator1, class RandomAccessIterator2, class RandomAccessIterator3, class Distance, class T>
RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1, RandomAccessIterator1 last1,
					     RandomAccessIterator2 first2, RandomAccessIterator2 last2,
					     RandomAccessIterator3 result, size_t& fill_pointer, T*)
{
    Distance len = 0;
    for (; first1 != last1 && first2 != last2 && len < fill_pointer; ++len, ++result) {
        if (*first2 < *first1) {
	    *result = *first2;
	    ++first2;
	} else {
	    *result = *first1;
	    ++first1;
	}
    }
    if (fill_pointer == len) {
        raw_storage_iterator<RandomAccessIterator3, T> p(result);
        result += (last1 - first1) + (last2 - first2);
        fill_pointer += (last1 - first1) + (last2 - first2);
        for (; first1 != last1 && first2 != last2; ++p) {
            if (*first2 < *first1) {
		*p = *first2;
		++first2;
	    } else {
		*p = *first1;
		++first1;
	    }
	}
        copy(first2, last2, copy(first1, last1, p));
    } else if (first2 == last2) {
        for (; first1 != last1 && len < fill_pointer; ++len, ++result, ++first1)
            *result = *first1;
        if (fill_pointer == len) {
            raw_storage_iterator<RandomAccessIterator3, T> p(result);  
            result += last1 - first1;
            fill_pointer += last1 - first1;
	    copy(first1, last1, p);
        }
    } else {
        for (; first2 != last2 && len < fill_pointer; ++len, ++result, ++first2)
            *result = *first2;
        if (fill_pointer == len) {
            raw_storage_iterator<RandomAccessIterator3, T> p(result);  
            result += last2 - first2;
            fill_pointer += last2 - first2;
	    copy(first2, last2, p);
        }
    }
    return result;
}       

template <class RandomAccessIterator1, class RandomAccessIterator2, class RandomAccessIterator3, class Distance, class T, class Compare>
RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1, RandomAccessIterator1 last1,
				  RandomAccessIterator2 first2, RandomAccessIterator2 last2,
				  RandomAccessIterator3 result, size_t& fill_pointer, T*, Compare comp)
{
    Distance len = 0;
    for (; first1 != last1 && first2 != last2 && len < fill_pointer; ++len, ++result)
        if (comp (*first2, *first1)) {
            *result = *first2;
	    ++first2;
	} else {
            *result = *first1;
	    ++first1;
	}
    if (fill_pointer <= len) {
        raw_storage_iterator<RandomAccessIterator3, T> p(result);
        result += (last1 - first1) + (last2 - first2);
        fill_pointer += (last1 - first1) + (last2 - first2);
        for (; first1 != last1 && first2 != last2; ++p) {
            if (comp(*first2, *first1)) {
                *p = *first2;
		++first2;
	    } else {
                *p = *first1;
		++first1;
	    }
	}
        copy(first2, last2, copy(first1, last1, p));
    } else if (first2 == last2) {
        for (; first1 != last1 && len < fill_pointer; ++len, ++result, ++first1)
            *result = *first1;
        if (fill_pointer == len) {
            raw_storage_iterator<RandomAccessIterator3, T> p(result);  
            result += last1 - first1;
            fill_pointer += last1 - first1;
	    copy(first1, last1, p);
        }
    } else {
        for (; first2 != last2 && len < fill_pointer; ++len, ++result, ++first2)
            *result = *first2;
        if (fill_pointer == len) {
            raw_storage_iterator<RandomAccessIterator3, T> p(result);  
            result += last2 - first2;
            fill_pointer += last2 - first2;
	    copy(first2, last2, p);
        }
    }
    return result;
}       

#if 0 /* dcn */
template <class RandomAccessIterator1, class RandomAccessIterator2,
          class Distance, class T>
inline void __merge_sort_loop_aux (RandomAccessIterator1 first,
                            RandomAccessIterator1 last, 
                            RandomAccessIterator2 result,
                            Distance step_size,
                            size_t& fill_pointer, T*)
{
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = __merge_aux(first, first + step_size, first + step_size, first + two_step, result, fill_pointer, (T*)0);
        first += two_step;
    }
    step_size = min (Distance (last - first), step_size);

    __merge_aux(first, first + step_size, first + step_size, last, result, fill_pointer, (T*)0);
}
#endif

#if 0	/* dcn */
template <class RandomAccessIterator1, class RandomAccessIterator2,
          class Distance, class T, class Compare>
inline void __merge_sort_loop_aux (RandomAccessIterator1 first,
                            RandomAccessIterator1 last, 
                            RandomAccessIterator2 result,
                            Distance step_size,
                            size_t& fill_pointer, T*, Compare comp)
{
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = __merge_aux (first, first + step_size, first + step_size, first + two_step, result, fill_pointer, (T*)0, comp);
        first += two_step;
    }
    step_size = min (Distance (last - first), step_size);

    __merge_aux (first, first + step_size, first + step_size, last, result, fill_pointer, (T*)0, comp);
}
#endif

template <class RandomAccessIterator1, class RandomAccessIterator2, class Distance>
void __merge_sort_loop(RandomAccessIterator1 first, RandomAccessIterator1 last, 
		       RandomAccessIterator2 result, Distance step_size)
{
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = merge(first, first + step_size, first + step_size, first + two_step, result);
        first += two_step;
    }
    step_size = min(Distance(last - first), step_size);

    merge(first, first + step_size, first + step_size, last, result);
}

template <class RandomAccessIterator1, class RandomAccessIterator2, class Distance, class Compare>
void __merge_sort_loop(RandomAccessIterator1 first, RandomAccessIterator1 last, 
		       RandomAccessIterator2 result, Distance step_size,
		       Compare comp)
{
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = merge(first, first + step_size, first + step_size, first + two_step, result, comp);
        first += two_step;
    }
    step_size = min(Distance (last - first), step_size);

    merge(first, first + step_size, first + step_size, last, result, comp);
}

template <class RandomAccessIterator, class Distance>
void __chunk_insertion_sort(RandomAccessIterator first, RandomAccessIterator last,
			    Distance chunk_size)
{
    while (last - first >= chunk_size) {
        __insertion_sort(first, first + chunk_size);
        first += chunk_size;
    }
    __insertion_sort(first, last);
}

template <class RandomAccessIterator, class Distance, class Compare>
void __chunk_insertion_sort(RandomAccessIterator first, RandomAccessIterator last,
			    Distance chunk_size, Compare comp)
{
    while (last - first >= chunk_size) {
        __insertion_sort(first, first + chunk_size, comp);
        first += chunk_size;
    }
    __insertion_sort(first, last, comp);
}

template <class RandomAccessIterator, class Pointer>
void __merge_sort_with_buffer(RandomAccessIterator first, RandomAccessIterator last,
			      Pointer buffer)
{
    static const int __stl_chunk_size = 7;
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Pointer buffer_last = buffer + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size);
    while (step_size < len) {
        __merge_sort_loop(first, last, buffer, step_size);
        step_size *= 2;
        __merge_sort_loop(buffer, buffer_last, first, step_size);
        step_size *= 2;
    }
}

template <class RandomAccessIterator, class Pointer, class Compare>
void __merge_sort_with_buffer (RandomAccessIterator first, RandomAccessIterator last,
			       Pointer buffer, Compare comp)
{
    static const int __stl_chunk_size = 7;

    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Pointer buffer_last = buffer + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size, comp);

    while (step_size < len)
    {
        __merge_sort_loop(first, last, buffer, step_size, comp);
        step_size *= 2;
        __merge_sort_loop(buffer, buffer_last, first, step_size, comp);
        step_size *= 2;
    }
}

template <class RandomAccessIterator, class Pointer, class Distance>
void __stable_sort_adaptive(RandomAccessIterator first, RandomAccessIterator last,
			    Pointer buffer, Distance buffer_size)
{
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer_size) {
        __stable_sort_adaptive(first, middle, buffer, buffer_size);
        __stable_sort_adaptive(middle, last, buffer, buffer_size);
    } else {
        __merge_sort_with_buffer(first, middle, buffer);
        __merge_sort_with_buffer(middle, last, buffer);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first), Distance(last - middle), buffer, buffer_size);
}

template <class RandomAccessIterator, class Pointer, class Distance, class Compare>
void __stable_sort_adaptive(RandomAccessIterator first, RandomAccessIterator last,
			    Pointer buffer, Distance buffer_size, Compare comp)
{
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer_size) {
        __stable_sort_adaptive(first, middle, buffer, buffer_size, comp);
        __stable_sort_adaptive(middle, last, buffer, buffer_size, comp);
    } else {
        __merge_sort_with_buffer(first, middle, buffer, comp);
        __merge_sort_with_buffer(middle, last, buffer, comp);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first), Distance(last - middle), buffer, buffer_size, comp);
}


// Section 25.3.1.2 -- stable sort

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef  typename iterator_traits<RandomAccessIterator>::value_type Value;
    pair<Value*, Distance> p = get_temporary_buffer<Value>(Distance(last - first));
    if (p.first == 0) {
        __inplace_stable_sort(first, last);
        return;
    }
    __kai::temp_buf_cleanup<Value> tbc(p.first); // ensure that the temp buffer is cleaned up if an exception is thrown.
    Distance len = min(p.second, Distance(last-first));
    uninitialized_copy(first, first + len, p.first);
    tbc.n_items = len;
    __stable_sort_adaptive(first, last, p.first, p.second);
    // the cleanup object will free the temporary buffer.
}

template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef  typename iterator_traits<RandomAccessIterator>::value_type Value;
    pair<Value*, Distance> p = get_temporary_buffer<Value>(Distance(last - first));
    if (p.first == 0) {
        __inplace_stable_sort(first, last, comp);
        return;
    }
    __kai::temp_buf_cleanup<Value> tbc(p.first); // ensure that the temp buffer is cleaned up if an exception is thrown.
    Distance len = min(p.second, Distance(last - first));
    uninitialized_copy(first, first + len, p.first);
    tbc.n_items = len;
    __stable_sort_adaptive(first, last, p.first, p.second, comp);
}

// Section 25.3.1.3 -- partial sort
template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    make_heap(first, middle);
    for (RandomAccessIterator i = middle; i < last; ++i)
	if (*i < *first)
	   __kai::__pop_heap(first, middle, i, Value(*i));
    sort_heap(first, middle);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last,
			 Compare comp)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    make_heap (first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
	    __kai::__pop_heap(first, middle, i, Value(*i), comp);
    sort_heap (first, middle, comp);
}

// Section 25.3.1.4 -- partial sort copy
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
				       RandomAccessIterator result_first,
				       RandomAccessIterator result_last)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef  typename iterator_traits<InputIterator>::value_type T;
    if (result_first == result_last)
	return result_last;
    RandomAccessIterator result_real_last = result_first;
    for (; first != last && result_real_last != result_last; ++result_real_last, ++first)
        *result_real_last = *first;
    make_heap (result_first, result_real_last);
    while (first != last) {
        if (*first < *result_first) 
            __kai::__adjust_heap(result_first, Distance(0), Distance(result_real_last - result_first),
				 T(*first));
        ++first;
    }
    sort_heap(result_first, result_real_last);
    return result_real_last;
}

template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
				       RandomAccessIterator result_first,
				       RandomAccessIterator result_last, Compare comp)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    typedef  typename iterator_traits<InputIterator>::value_type T;
    if (result_first == result_last)
        return result_last;

    RandomAccessIterator result_real_last = result_first;

    for (; first != last && result_real_last != result_last; ++result_real_last, ++first)
        *result_real_last = *first;

    make_heap(result_first, result_real_last, comp);

    while (first != last) {
      if (comp (*first, *result_first)) 
	  __kai::__adjust_heap(result_first, Distance(0), Distance(result_real_last - result_first),
			       T(*first), comp);
        ++first;
    }
    sort_heap(result_first, result_real_last, comp);
    return result_real_last;
}

// Section 25.3.2 -- Nth element

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    while (last - first > 3) {
	Value pivot(__median(*first, * (first + (last - first)/2), *(last - 1)));
        RandomAccessIterator cut = __unguarded_partition(first, last, pivot);
        if (cut <= nth)
            first = cut;
        else 
            last = cut;
    }
    __insertion_sort(first, last);
}

template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
		 RandomAccessIterator last, Compare comp)
{
    typedef typename iterator_traits <RandomAccessIterator>::value_type Value;
    while (last - first > 3) {
	Value pivot(__median (*first, * (first + (last - first)/2), *(last - 1), comp));
        RandomAccessIterator cut = __unguarded_partition(first, last, pivot, comp);
        if (cut <= nth)
            first = cut;
        else 
            last = cut;
    }
    __insertion_sort(first, last, comp);
}

// Section 25.3.3 -- Binary search

// Section 25.3.3.1 -- lower_bound

template <class ForwardIterator, class T, class Compare>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Compare comp, forward_iterator_tag *)
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type Distance;
    Distance len =  distance(first, last);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first;
        advance(middle, half);
        if (comp(*middle, value)) {
            first = middle;
            ++first;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator __lower_bound (RandomAccessIterator first, RandomAccessIterator last,
				    const T& value, Compare comp, random_access_iterator_tag *)
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first + half;
        if (comp(*middle, value)) {
            first = middle + 1;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __lower_bound(first, last, value, __kai::default_less<T>(), (Category *)0);
}

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value,
			    Compare comp)
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __lower_bound (first, last, value, comp, (Category *)0);
}

// Section 25.3.3.2 -- upper_bound

template <class ForwardIterator, class T, class Compare>
ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Compare comp, forward_iterator_tag *)
{
    typedef typename iterator_traits<ForwardIterator>::difference_type Distance;
    Distance len = distance(first, last);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first;
        advance(middle, half);
        if (comp(value, *middle))
            len = half;
        else {
            first = middle;
            ++first;
            len = len - half - 1;
        }
    }
    return first;
}

template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator __upper_bound(RandomAccessIterator first, RandomAccessIterator last,
				   const T& value, Compare comp, random_access_iterator_tag *)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first + half;
        if (comp (value, *middle))
            len = half;
        else {
            first = middle + 1;
            len = len - half - 1;
        }
    }
    return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value)
{
    typedef typename iterator_traits<ForwardIterator>::difference_type Distance;
    typedef typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __upper_bound(first, last, value, __kai::default_less<T>(), (Category *)0);
}

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    typedef typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __upper_bound(first, last, value, comp, (Category *)0);
}

//  Section 25.3.3.3 -- equal range

template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator> 
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	      Compare comp, forward_iterator_tag *)
{
    typedef typename iterator_traits<ForwardIterator>::difference_type Distance;
    Distance len = distance(first, last);
    Distance half;
    ForwardIterator middle, left, right;

    while (len > 0) {
        half = len / 2;
        middle = first;
        advance (middle, half);
        if (comp (*middle, value)) {
            first = middle;
            ++first;
            len = len - half - 1;
        } else if (comp (value, *middle))
            len = half;
        else {
            left = lower_bound(first, middle, value, comp);
            advance (first, len);
            right = upper_bound (++middle, first, value, comp);
            return pair<ForwardIterator, ForwardIterator>(left, right);
        }
    }
    return pair<ForwardIterator, ForwardIterator>(first, first);
}           

template <class RandomAccessIterator, class T, class Compare>
pair<RandomAccessIterator, RandomAccessIterator> 
__equal_range(RandomAccessIterator first, RandomAccessIterator last,
	      const T& value, Compare comp, random_access_iterator_tag *)
{
    typedef typename iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle, left, right;

    while (len > 0) {
        half = len / 2;
        middle = first + half;
        if (comp (*middle, value)) {
            first = middle + 1;
            len = len - half - 1;
        } else if (comp(value, *middle))
            len = half;
        else {
            left = lower_bound(first, middle, value, comp);
            right = upper_bound(++middle, first + len, value, comp);
            return pair<RandomAccessIterator, RandomAccessIterator>(left, right);
        }
    }
    return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}           

template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value)
{
    typedef typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __equal_range(first, last, value, __kai::default_less<T>(), (Category *)0);
}

template <class ForwardIterator, class T, class Compare>
inline pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last,
							  const T& value, Compare comp)
{
    typedef typename iterator_traits<ForwardIterator>::iterator_category Category;
    return __equal_range(first, last, value, comp, (Category *)0);
}    

//  Section 25.3.3.4 -- binary search

template <class ForwardIterator, class T>
inline
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
    ForwardIterator i = lower_bound(first, last, value);
    return i != last && !(value < *i);
}

template <class ForwardIterator, class T, class Compare>
inline
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    ForwardIterator i = lower_bound(first, last, value, comp);
    return i != last && !comp(value, *i);
}

// Section 25.3.4 -- Merge

// Section 25.3.4.1 -- merge

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
		     InputIterator2 first2, InputIterator2 last2,
		     OutputIterator result)
{
    for (; first1 != last1 && first2 != last2; ++result)
        if (*first2 < *first1) {
	    *result = *first2;
	    ++first2;
	} else {
	    *result = *first1;
	    ++first1;
	}
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
		     InputIterator2 first2, InputIterator2 last2,
		     OutputIterator result, Compare comp)
{
    for (; first1 != last1 && first2 != last2; ++result)
        if (comp(*first2, *first1)) {
	    *result = *first2;
	    ++first2;
	} else {
	    *result = *first1;
	    ++first1;
	}
    return copy(first2, last2, copy(first1, last1, result));
}

template <class BidirectionalIterator, class Distance>
void __merge_without_buffer(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
			    Distance len1, Distance len2)
{
    if (len1 == 0 || len2 == 0)
	return;
    if (len1 + len2 == 2) {
        if (*middle < *first)
	    iter_swap(first, middle);
        return;
    }
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;
    if (len1 > len2) {
        len11 = len1 / 2;
        advance (first_cut, len11);
        second_cut = lower_bound(middle, last, *first_cut);
        len22 = distance(middle, second_cut);
    } else {
        len22 = len2 / 2;
        advance (second_cut, len22);
        first_cut = upper_bound(first, middle, *second_cut);
        len11 = distance(first, first_cut);
    }
    rotate(first_cut, middle, second_cut);
    BidirectionalIterator new_middle = first_cut;
    advance(new_middle, len22);
    __merge_without_buffer(first, first_cut, new_middle, len11, len22);
    __merge_without_buffer(new_middle, second_cut, last, len1 - len11, len2 - len22);
}

template <class BidirectionalIterator, class Distance, class Compare>
void __merge_without_buffer(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
			    Distance len1, Distance len2, Compare comp)
{
    if (len1 == 0 || len2 == 0)
	return;
    if (len1 + len2 == 2) {
        if (comp(*middle, *first))
	    iter_swap(first, middle);
        return;
    }
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;
    if (len1 > len2) {
        len11 = len1 / 2;
        advance(first_cut, len11);
        second_cut = lower_bound(middle, last, *first_cut, comp);
        len22 = distance(middle, second_cut);
    } else {
        len22 = len2 / 2;
        advance(second_cut, len22);
        first_cut = upper_bound(first, middle, *second_cut, comp);
        len11 = distance(first, first_cut);
    }
    rotate(first_cut, middle, second_cut);
    BidirectionalIterator new_middle = first_cut;
    advance(new_middle, len22);
    __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
    __merge_without_buffer(new_middle, second_cut, last, len1 - len11, len2 - len22, comp);
}


template <class BidirectionalIterator1, class BidirectionalIterator2, class Distance>
inline
BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first, BidirectionalIterator1 middle,
					 BidirectionalIterator1 last, Distance len1, Distance len2,
					 BidirectionalIterator2 buffer, Distance buffer_size)
{
    BidirectionalIterator2 buffer_end;
    if (len1 > len2 && len2 <= buffer_size) {
        buffer_end = copy(middle, last, buffer);
        copy_backward(first, middle, last);
        return copy(buffer, buffer_end, first);
    } else if (len1 <= buffer_size) {
        buffer_end = copy(first, middle, buffer);
        copy(middle, last, first);
        return copy_backward(buffer, buffer_end, last);
    } else {
        rotate(first, middle, last);
        advance(first, len2);
        return first;
    }
}

template <class BidirectionalIterator1, class BidirectionalIterator2, class BidirectionalIterator3>
BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
					BidirectionalIterator2 first2, BidirectionalIterator2 last2,
					BidirectionalIterator3 result)
{
    if (first1 == last1)
	return copy_backward(first2, last2, result);
    if (first2 == last2)
	return copy_backward(first1, last1, result);
    --last1;
    --last2;
    while (true) {
        if (*last2 < *last1) {
            *--result = *last1;
            if (first1 == last1)
                return copy_backward(first2, ++last2, result);
            --last1;
        } else {
	    *--result = *last2;
	    if (first2 == last2)
		return copy_backward(first1, ++last1, result);
	    --last2;
	}
    }
}

template <class BidirectionalIterator1, class BidirectionalIterator2, class BidirectionalIterator3, class Compare>
BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
					BidirectionalIterator2 first2, BidirectionalIterator2 last2,
					BidirectionalIterator3 result, Compare comp)
{
    if (first1 == last1)
	return copy_backward(first2, last2, result);
    if (first2 == last2)
	return copy_backward(first1, last1, result);
    --last1;
    --last2;
    while (true) {
        if (comp(*last2, *last1)) {
            *--result = *last1;
            if (first1 == last1)
                return copy_backward(first2, ++last2, result);
            --last1;
        } else {
            *--result = *last2;
            if (first2 == last2)
                return copy_backward(first1, ++last1, result);
            --last2;
        }
    }
}

template <class BidirectionalIterator, class Distance, class Pointer>
void __merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle, 
		      BidirectionalIterator last, Distance len1, Distance len2,
		      Pointer buffer, Distance buffer_size)
{
    if (len1 <= len2 && len1 <= buffer_size) {
        Pointer end_buffer = copy(first, middle, buffer);
        merge(buffer, end_buffer, middle, last, first);
    } else if (len2 <= buffer_size) {
        Pointer end_buffer = copy(middle, last, buffer);
        __merge_backward(first, middle, buffer, end_buffer, last);
    } else {
        BidirectionalIterator first_cut = first;
        BidirectionalIterator second_cut = middle;
        Distance len11 = 0;
        Distance len22 = 0;
        if (len1 > len2) {
            len11 = len1 / 2;
            advance(first_cut, len11);
            second_cut = lower_bound(middle, last, *first_cut);
            len22 = distance(middle, second_cut);
        } else {
            len22 = len2 / 2;
            advance(second_cut, len22);
            first_cut = upper_bound(first, middle, *second_cut);
            len11 = distance(first, first_cut);
        }
        BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
							     len22, buffer, buffer_size);
        __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size);
        __merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size);
    }
}

template <class BidirectionalIterator, class Distance, class Pointer, class Compare>
void __merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
		      Distance len1, Distance len2,
		      Pointer buffer, Distance buffer_size, Compare comp)
{
    typedef  typename iterator_traits<BidirectionalIterator>::value_type T;
    if (len1 <= len2 && len1 <= buffer_size) {
        Pointer end_buffer = copy(first, middle, buffer);
        merge(buffer, end_buffer, middle, last, first, comp);
    } else if (len2 <= buffer_size) {
        Pointer end_buffer = copy(middle, last, buffer);
        __merge_backward(first, middle, buffer, end_buffer, last, comp);
    } else {
        BidirectionalIterator first_cut = first;
        BidirectionalIterator second_cut = middle;
        Distance len11 = 0;
        Distance len22 = 0;
        if (len1 > len2) {
            len11 = len1 / 2;
            advance (first_cut, len11);
            second_cut = lower_bound(middle, last, *first_cut, comp);
            len22 = distance(middle, second_cut);
        } else {
            len22 = len2 / 2;
            advance(second_cut, len22);
            first_cut = upper_bound(first, middle, *second_cut, comp);
            len11 = distance(first, first_cut);
	}
        BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, len22,
							     buffer, buffer_size);
        __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size, comp);
        __merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size, comp);
    }
}

// Section 25.3.4.2 -- inplace_merge
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
{
    typedef  typename iterator_traits<BidirectionalIterator>::difference_type Distance;
    typedef  typename iterator_traits<BidirectionalIterator>::value_type Value;
    if (first == middle || middle == last)
	return;
    Distance len1 = distance(first, middle);
    Distance len2 = distance(middle, last);
    pair<Value*, Distance> p = get_temporary_buffer<Value>(len1+len2);
    //__inplace_merge(first, middle, last, len1, len2, p); 
    if (p.first == 0) {
        __merge_without_buffer(first, middle, last, len1, len2);
        return; 
    }
    __kai::temp_buf_cleanup<Value> tbc(p.first); // ensure that the temp buffer is cleaned up if an exception is thrown.
    Distance len = min(p.second, len1 + len2);
    uninitialized_fill_n(p.first, len, *first);
    tbc.n_items = len;
    __merge_adaptive(first, middle, last, len1, len2, p.first, p.second);
    // the cleanup item will clean up the temp buffer.
}

template <class BidirectionalIterator, class Compare>
inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
			  Compare comp)
{
    typedef  typename iterator_traits<BidirectionalIterator>::difference_type Distance;
    typedef  typename iterator_traits<BidirectionalIterator>::value_type Value;
    if (first == middle || middle == last)
	return;
    Distance len1 = distance(first, middle);
    Distance len2 = distance(middle, last);
    pair<Value*, Distance> p = get_temporary_buffer<Value>(len1+len2);
    if (p.first == 0) {
        __merge_without_buffer(first, middle, last, len1, len2, comp);
        return;
    }
    __kai::temp_buf_cleanup<Value> tbc(p.first); // ensure that the temp buffer is cleaned up if an exception is thrown.
    Distance len = min (p.second, len1 + len2);
    uninitialized_fill_n(p.first, len, *first);
    tbc.n_items = len;
    __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, comp);
    // the cleanup item will clean up the temp buffer.
}


// Section 25.3.5 -- Set operations on sorted structures

// Section 25.3.5.1 -- includes

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
	      InputIterator2 first2, InputIterator2 last2)
{
    while (first1 != last1 && first2 != last2)
        if (*first2 < *first1)
            return false;
        else if (*first1 < *first2) 
            ++first1;
        else
            ++first1, ++first2;

    return first2 == last2;
}

template <class InputIterator1, class InputIterator2, class Compare>
bool includes (InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2, Compare comp)
{
    while (first1 != last1 && first2 != last2)
        if (comp(*first2, *first1))
            return false;
        else if (comp(*first1, *first2)) 
            ++first1;
        else
            ++first1, ++first2;

    return first2 == last2;
}

// Section 25.3.5.2 -- set union
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result)
{
    for (; first1 != last1 && first2 != last2; ++result)
        if (*first1 < *first2) {
	    *result = *first1;
	    ++first1;
	} else if (*first2 < *first1) {
	    *result = *first2;
	    ++first2;
	} else {
            *result = *first1;
            ++first1;
            first2++;
        }
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, Compare comp)
{
    for (; first1 != last1 && first2 != last2; ++result)
        if (comp (*first1, *first2)) {
	    *result = *first1;
	    ++first1;
	} else if (comp (*first2, *first1)) {
	    *result = *first2;
	    ++first2;
	} else {
            *result = *first1;
            ++first1;
            ++first2;
        }
    return copy(first2, last2, copy(first1, last1, result));
}

// Section 25.3.5.3 -- set intersection

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

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

// Section 25.3.5.4 -- set difference

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
			      InputIterator2 first2, InputIterator2 last2,
			      OutputIterator result)
{
    while (first1 != last1 && first2 != last2)
        if (*first1 < *first2) {
	    *result = *first1;
	    ++result;
	    ++first1;
	} else if (*first2 < *first1)
            ++first2;
        else {
            ++first1;
            ++first2;
        }
    return copy(first1, last1, result);
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
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;
	    ++first1;
	} else if (comp(*first2, *first1))
            ++first2;
        else {
            ++first1;
	    ++first2;
	}
    return copy(first1, last1, result);
}

// Section 25.3.5.5 -- set symmetric difference

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
					InputIterator2 first2, InputIterator2 last2,
					OutputIterator result)
{
    while (first1 != last1 && first2 != last2)
        if (*first1 < *first2) {
	    *result = *first1;
	    ++result;
	    ++first1;
	} else if (*first2 < *first1) {
	    *result = *first2;
	    ++result;
	    ++first2;
	} else {
            ++first1;
            ++first2;
        }
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
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;
	    ++first1;
	} else if (comp(*first2, *first1)) {
            *result = *first2;
            ++result;
	    ++first2;
        } else {
            ++first1;
            ++first2;
        }
    return copy (first2, last2, copy (first1, last1, result));
}

// Section 25.3.6 -- Heap operations
// Section 25.3.6.1 -- push_heap -- in heap.h
// Section 25.3.6.2 -- pop_heap  -- in heap.h
// Section 25.3.6.3 -- make_heap -- in heap.h
// Section 25.3.6.4 -- sort_heap -- in heap.h

// Section 25.3.7 -- Minimum and Maximum

// Section 25.3.7.1 -- min  -- in algobase.h
// Section 25.3.7.2 -- max  -- in algobase.h

// Section 25.3.7.3 -- max_element

template <class ForwardIterator>
inline ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
{
    if (first == last)
	return first;
    ForwardIterator result = first;
    while (++first != last) 
        if (*result < *first)
	    result = first;
    return result;
}

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

// Section 25.3.7.4 -- min_element

template <class ForwardIterator>
inline ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
{
    if (first == last)
	return first;
    ForwardIterator result = first;
    while (++first != last) 
        if (*first < *result)
	    result = first;
    return result;
}

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

// Section 25.3.8 -- Lexicographical comparison -- in algobase.h

// Section 25.3.9 -- Permutation generators

// Section 25.3.9.1 -- next permutation

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    if (first == last)
	return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last)
	return false;
    i = last;
    --i;

    for (;;) {
        BidirectionalIterator ii = i;
        --i;
        if (*i < *ii) {
            BidirectionalIterator j = last;
            --j;
            while (!(*i < *j))
		--j;
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
	if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
    if (first == last)
	return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last)
	return false;
    i = last;
    --i;

    for (;;) {
        BidirectionalIterator 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;
        }
    }
}

// Section 25.3.9.2 -- previous permutation

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    if (first == last)
	return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last)
	return false;
    i = last;
    --i;

    for (;;) {
        BidirectionalIterator ii = i;
        --i;
        if (*ii < *i) {
            BidirectionalIterator j = last;
	    do {
		--j;
            } while (!(*j < *i));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
    if (first == last)
	return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last)
	return false;
    i = last;
    --i;

    for (;;) {
        BidirectionalIterator ii = i;
        --i;
        if (comp (*ii, *i)) {
            BidirectionalIterator j = last;
	    do {
		--j;
            } while (!comp(*j, *i));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

} // namespace std

#endif /* __KAI_ALGORITHM */