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


#ifndef PERMUTATION_H
#define PERMUTATION_H

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

template <class Iterator>
void reverse(Iterator first, Iterator last)
{
    while (first < last)
	swap(*first++, *--last);
}

template <class Iterator1, class Iterator2>
inline Iterator2 reverseCopy(Iterator1 first, Iterator1 last, 
			     Iterator2 result)
{
    while (first != last)
        *result++ = *--last;
    return result;
}

template <class Iterator>
void randomShuffle(Iterator first, Iterator last)
{
    if (first == last) return;
    Iterator current = first;
    current++;
    if (current == last) return;
    ptrdiff_t index = 1;
    while (current != last) {
	Iterator tmp = first;
	tmp += ptrdiff_t(drand48() * ++index);
	swap(*current, *tmp);
	current++;
    }
}

template <class Iterator, class T>
static void rotateCycle(Iterator initial, Iterator first, ptrdiff_t shift, 
			ptrdiff_t len, T value)
{
    Iterator ptr1 = initial;
    ptrdiff_t ptr2Index = initial - first + shift;
    Iterator ptr2 = 
	ptr2Index < len ? ptr1 + shift : (ptr2Index -= len, first + ptr2Index);
    while (ptr2 != initial) {
	*ptr1 = *ptr2;
	ptr1 = ptr2;
	ptr2Index += shift;
	ptr2 = ptr2Index < len ? ptr1 + shift 
	    : (ptr2Index -= len, first + ptr2Index);
    }
    *ptr1 = value;
}

template <class Iterator>
void rotate1(Iterator i, Iterator j, ptrdiff_t shift)
{
    if (i >= j) return;
    ptrdiff_t len = j - i;
    shift %= len;
    if (shift < 0) shift += len;
    if (shift == 0) return;
    shift = len - shift;
    ptrdiff_t gcdValue = gcd(len, shift);
    while (gcdValue--) {
	Iterator k = i + gcdValue;
	rotateCycle(k, i, shift, len, *k);
    }
}

template <class Iterator>
void inplaceRotate(Iterator first, Iterator middle, Iterator last)
{
    if (first == middle || middle == last) return;
    reverse(first, middle);
    reverse(middle, last);
    reverse(first, last);
}
/*
template <class Iterator>
void rotate(Iterator i, Iterator j, ptrdiff_t shift)
{
    if (i >= j) return;
    ptrdiff_t len = j - i;
    shift %= len;
    if (shift < 0) shift += len;
    if (shift == 0) return;
    inplaceRotate(i, i + shift, j);
}
*/
template <class Iterator>
void rotate2(Iterator i, Iterator j, ptrdiff_t shift)
{
    if (i >= j) return;
    ptrdiff_t len = j - i;
    shift %= len;
    if (shift < 0) shift += len;
    if (shift == 0) return;
    Iterator k = j - shift;
    while (1) 
	if (j - k < k - i) {
	    swapRanges(i, i + (j - k), k);
	    i = i + (j - k);
	    if (i == k) return;
	} else {
	    swapRanges(i, k, j - (k - i));
	    j = j - (k - i);
	    if (k == j) return;
	}
}

template <class Iterator, class BufferIterator>
void rotateAdaptive(Iterator first, Iterator middle, Iterator last,
		    size_t bufferSize, BufferIterator buffer)
{
    if (middle - first > last - middle) 
	if (last - middle <= bufferSize) {
	    move(middle, last, buffer);
	    moveBackward(first, middle, last);
	    move(buffer, buffer + (last - middle), first);
	} else
	    inplaceRotate(first, middle, last);
    else
	if (middle - first <= bufferSize) {
            move(first, middle, buffer);
	    move(middle, last, first);
	    moveBackward(buffer, buffer + (middle - first), last);
	} else
	    inplaceRotate(first, middle, last);
}

template <class Iterator1, class Iterator2>
Iterator2 rotateCopy(Iterator1 first, Iterator1 middle, Iterator1 last, 
		     Iterator2 result)
{
    return move(first, middle, move(middle, last, result));
}

#endif