/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 */


#ifndef SORT_UTILITIES_H
#define SORT_UTILITIES_H

#include <stddef.h>

extern "C" {
    double drand48 ();
}

template <class Iterator>
inline static Iterator medianOf3Select(Iterator first, Iterator last)
{
    Iterator middle = first;
    middle += ((last - first) >> 1);
    last--;
    
    if (*first - *middle <= 0)
	if (*middle - *last <= 0)
	    return middle;
	else if (*first - *last <= 0)
	    return last;
	else
	    return first;
    else if (*first - *last <= 0)
        return first;
    else if (*middle - *last <= 0)
        return last;
    else
        return middle;
}

template <class Iterator, class Compare>
inline static Iterator medianOf3Select(Iterator first, Iterator last,
				       Compare comp)
{
    Iterator middle = first;
    middle += ((last - first) >> 1);
    last--;
    
    if (comp(*first, *middle) <= 0)
	if (comp(*middle, *last) <= 0)
	    return middle;
	else if (comp(*first, *last) <= 0)
	    return last;
	else
	    return first;
    else if (comp(*first, *last) <= 0)
        return first;
    else if (comp(*middle, *last) <= 0)
        return last;
    else
        return middle;
}

template <class Iterator>
inline static Iterator randomSelect(Iterator first, Iterator last)
{
    return first + ptrdiff_t(drand48() * (last - first));
}

template <class Iterator>
int isSorted(Iterator first, Iterator last)
{
    if (first == last) return 1;
    Iterator next = first;
    next++;
    while (!(next == last)) {
	if (*first > *next)
	    return 0;
	next++;
	first++;
    }
    return 1;
}

template <class Iterator>
int isInverselySorted(Iterator first, Iterator last)
{
    if (first == last) return 1;
    Iterator next = first;
    next++;
    while (!(next == last)) {
	if (*first < *next)
	    return 0;
	next++;
	first++;
    }
    return 1;
}

#endif