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


#ifndef PARTITION_H
#define PARTITION_H

#include <stddef.h>
#include "utilities.H"
#include "pair.H"

template <class Iterator, class Predicate>
Iterator partition(Iterator first, Iterator last, Predicate pred)
{
    while (1) {
	while (1) 
	    if (first == last)
		return first;
	    else if (pred(*first))
		first++;
	    else
		break;
	last--;
	while (1)
	    if (first == last)
		return first;
	    else if (!pred(*last))
		last--;
	    else
		break;
	swap(*first, *last);
	first++;
    }
}

template <class Iterator, class T>
Pair<Iterator, Iterator>  threePartition(Iterator first, Iterator last, T x)
{

    Iterator firstUnknown = first;
    Iterator firstEqual = first;
    Iterator firstGreater = last;
    
    while (firstUnknown < firstGreater) {
	int c = int(*firstUnknown - x);
	if (c < 0)
	    swap(*firstUnknown++, *firstEqual++);
	else if (c > 0)
	    swap(*firstUnknown, *--firstGreater);
	else
	    firstUnknown++;
    }
    
    return Pair<Iterator, Iterator>(firstEqual, firstGreater); 
}

template <class Iterator, class Predicate>
Iterator inplaceStablePartition(Iterator first, Iterator last, Predicate pred)
{
    if (last == first + 1) 
	return first + pred(*first);

    Iterator middle = first + (last - first)/2;
    Iterator firstCut = inplaceStablePartition(first, middle, pred);
    Iterator secondCut = inplaceStablePartition(middle, last, pred);
    inplaceRotate(firstCut, middle, secondCut);
    return firstCut + (secondCut - middle);
}

template <class Iterator, class BufferIterator, class Predicate>
Iterator stablePartitionWithBuffer(Iterator first, Iterator last, 
				   Predicate pred, BufferIterator buffer)
{
    Iterator previous = first;
    BufferIterator nextBuffer = buffer;

    while (first != last) 
	if (pred(*first))
	    *previous++ = *first++;
	else 
	    *nextBuffer++ = *first++;

    Iterator result = previous;

    while (previous != last) *previous++ = *buffer++;

    return result;
}

template <class Iterator, class BufferIterator, class Predicate>
Iterator stablePartitionAdaptive(Iterator first, Iterator last, Predicate pred,
				 size_t bufferSize, BufferIterator buffer)
{
    if (last - first <= bufferSize) 
	return stablePartitionWithBuffer(first, last, pred, buffer);
    Iterator middle = first + (last - first)/2;
    Iterator firstCut = 
	stablePartitionAdaptive(first, middle, pred, bufferSize, buffer);
    Iterator secondCut = 
	stablePartitionAdaptive(middle, last, pred, bufferSize, buffer);
    rotateAdaptive(firstCut, middle, secondCut, bufferSize, buffer);
    return firstCut + (secondCut - middle);
}

template <class Iterator, class Predicate, class T>
Iterator stablePartitionAux(Iterator first, Iterator last, Predicate pred, T&)
{
    PAP_auxBuffer<T> buffer(last - first);
    return buffer.len
	? stablePartitionAdaptive(first, last, pred, buffer.len, buffer.ptr) 
	: inplaceStablePartition(first, last, pred);
}

template <class Iterator, class Predicate>
Iterator stablePartition(Iterator first, Iterator last, Predicate pred)
{
    return stablePartitionAux(first, last, pred, *first);
}

template <class Iterator, class Predicate>
int isPartitioned(Iterator first, Iterator middle,
		  Iterator last, Predicate pred)
{
    while (first != middle)
	if (!pred(*first++)) return 0;
    while (first != last)
	if (pred(*first++)) return 0;
    return 1;
}

template <class Iterator, class T>
Pair<Iterator, Iterator> inplaceStable3Partition(Iterator first, 
						 Iterator last, T value)
{
    if (first == last) return Pair<Iterator, Iterator>(first, first);
    if (first + 1 == last) {
	int c = int(*first - value);
	if (c < 0)
	    return Pair<Iterator, Iterator>(last, last);
	else if (c > 0)
	    return Pair<Iterator, Iterator>(first, first);
	else
	    return Pair<Iterator, Iterator>(first, last);
    }
    Iterator middle = first + (last - first)/2;
    Pair<Iterator, Iterator> i = inplaceStable3Partition(first, middle, value);
    Pair<Iterator, Iterator> j = inplaceStable3Partition(middle, last, value);
    inplaceRotate(i.second, middle, j.second);
    inplaceRotate(i.first, i.second, i.second + (j.first - middle));
    return Pair<Iterator, Iterator>(i.first + (j.first - middle),
                                    j.second - (middle - i.second));
}

template <class Iterator, class T, class BufferIterator>
Pair<Iterator, Iterator> stable3PartitionWithBuffer(Iterator first, 
						    Iterator last, T value,
						    BufferIterator buffer)
{
    Iterator nextLess = first;
    BufferIterator nextEqual = buffer;
    BufferIterator nextGreater = buffer + (last - first);
    Iterator next = first;
    while (next != last) {
	T x = *next++;
	int c = int(x - value);
	if (c < 0)
	    *nextLess++ = x;
	else if (c > 0)
	    *--nextGreater = x;
	else
	    *nextEqual++ = x;
    }
    move(buffer, nextEqual, nextLess);
    reverseCopy(nextGreater, buffer + (last - first),
		nextLess + (nextEqual - buffer));
    return Pair<Iterator, Iterator>(nextLess, 
				    nextLess + (nextEqual - buffer));
}

template <class Iterator, class T, class BufferIterator>
Pair<Iterator, Iterator> stable3PartitionAdaptive(Iterator first, 
						  Iterator last, 
						  T value,
			      			  size_t bufferSize, 
						  BufferIterator buffer)
{
    if (bufferSize < last - first) {
	Iterator middle = first + (last - first) / 2;
	Pair<Iterator, Iterator> i = 
	    stable3PartitionAdaptive(first, middle, value, bufferSize, buffer);
	Pair<Iterator, Iterator> j = 
	    stable3PartitionAdaptive(middle, last, value, bufferSize, buffer);
	rotateAdaptive(i.second, middle, j.second, bufferSize, buffer);
	rotateAdaptive(i.first, i.second, i.second + (j.first - middle), 
		       bufferSize, buffer);
	return Pair<Iterator, Iterator>(i.first + (j.first - middle),
					j.second - (middle - i.second));
    } else
	return stable3PartitionWithBuffer(first, last, value, buffer);
}

template <class Iterator, class Predicate, class T>
Iterator stable3PartitionAux(Iterator first, Iterator last, Predicate pred, T&)
{
    PAP_auxBuffer<T> buffer(last - first);
    return buffer.len
	? stable3PartitionAdaptive(first, last, pred, buffer.len, buffer.ptr) 
	: inplaceStable3Partition(first, last, pred);
}

template <class Iterator, class Predicate>
Iterator stable3Partition(Iterator first, Iterator last, Predicate pred)
{
    return stable3PartitionAux(first, last, pred, *first);
}

#endif