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


#ifndef MERGE_H
#define MERGE_H

#include <stddef.h>
#include "binary.H"
#include "utilities.H"
#include "pap_auxbuffer.H"

template <class Iterator>
void inplaceMerge(Iterator first, Iterator middle, Iterator last)
{
    if (first == middle || middle == last) return;
    if (last - first == 2) {
	if (*middle - *first < 0) swap(*first, *middle);
	return;
    }
    Iterator firstCut, secondCut;
    if (middle - first > last - middle) {
	firstCut = first + (middle - first)/2;
	secondCut = binaryLess(middle, last, *firstCut);
    } else {
	secondCut = middle + (last - middle)/2;
	firstCut = binaryNotGreater(first, middle, *secondCut);
    }
    inplaceRotate(firstCut, middle, secondCut);
    inplaceMerge(first, firstCut, firstCut + (secondCut - middle));
    inplaceMerge(firstCut + (secondCut - middle), secondCut, last);
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 mergeCopy(Iterator1 first1, Iterator1 last1, 
		    Iterator2 first2, Iterator2 last2, Iterator3 result)
{
    while (first1 != last1 && first2 != last2) 
	if (*first2 - *first1 < 0)
	    *result++ = *first2++;
	else
	    *result++ = *first1++;

    result = move(first1, last1, result);
    result = move(first2, last2, result);

    return result;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 mergeCopyBackwards(Iterator1 first1, Iterator1 last1,
			     Iterator2 first2, Iterator2 last2, 
			     Iterator3 result)
{
    while (first1 != last1 && first2 != last2)
        if (*(last1 - 1) - *(last2 - 1) > 0)
            *--result = *--last1;
        else
            *--result = *--last2;

    result = moveBackward(first1, last1, result);
    result = moveBackward(first2, last2, result);

    return result;
}

template <class Iterator, class BufferIterator>
void mergeAdaptive(Iterator first, Iterator middle, Iterator last, 
		   size_t bufferSize, BufferIterator buffer)
{
    if (middle - first <= last - middle && middle - first <= bufferSize) {
        move(first, middle, buffer);
        mergeCopy(buffer, buffer + (middle - first), middle, last, first);
    } else if (last - middle <= bufferSize) {
        move(middle, last, buffer);
        mergeCopyBackwards(first, middle,
                           buffer, buffer + (last - middle), last);
    } else {
        Iterator firstCut, secondCut;
        if (middle - first > last - middle) {
            firstCut = first + (middle - first)/2;
            secondCut = binaryLess(middle, last, *firstCut);
        } else {
            secondCut = middle + (last - middle)/2;
            firstCut = binaryNotGreater(first, middle, *secondCut);
        }
        rotateAdaptive(firstCut, middle, secondCut, bufferSize, buffer);
        mergeAdaptive(first, firstCut, firstCut + (secondCut - middle),
                      bufferSize, buffer);
        mergeAdaptive(firstCut + (secondCut - middle), secondCut, last,
                      bufferSize, buffer);
    }
}

template <class Iterator, class T>
void mergeAux(Iterator first, Iterator middle, Iterator last, T&)
{
    PAP_auxBuffer<T> buffer(min(last - middle, middle - first));
    if (buffer.len > 2) 
	mergeAdaptive(first, middle, last, buffer.len, buffer.ptr);
    else
	inplaceMerge(first, middle, last);
}

template <class Iterator>
void merge(Iterator first, Iterator middle, Iterator last)
{
    mergeAux(first, middle, last, *first);
}

#endif