/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* rotate.c -- time algorithms for rotating a vector	Input lines:		algnum numtests n rotdist		algnum:
		  1: reversal algorithm
		  2: juggling algorithm
		  22:  juggling algorithm with mod rather than if
		  3: gcd algorithm
		  4: slide (don't rotate): baseline alg for timing
	To test the algorithms, recompile and change main to call testrot */#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAXN 10000000int x[MAXN];int rotdist, n;/* Alg 1: Rotate by reversal */void reverse(int i, int j){	int t;	while (i < j) {		t = x[i]; x[i] = x[j]; x[j] = t;		i++;		j--;	}}void revrot(int rotdist, int n){	reverse(0, rotdist-1);	reverse(rotdist, n-1);	reverse(0, n-1);}/* Alg 2: Juggling (dolphin) rotation */int gcd(int i, int j){	int t;	while (i != 0) {		if (j >= i)			j -= i;		else {			t = i; i = j; j = t;		}	}	return j;}void jugglerot(int rotdist, int n){	int cycles, i, j, k, t;	cycles = gcd(rotdist, n);	for (i = 0; i < cycles; i++) {		/* move i-th values of blocks */		t = x[i];		j = i;		for (;;) {			k = j + rotdist;			if (k >= n)				k -= n;			if (k == i)				break;			x[j] = x[k];			j = k;		}		x[j] = t;	}}void jugglerot2(int rotdist, int n){	int cycles, i, j, k, t;	cycles = gcd(rotdist, n);	for (i = 0; i < cycles; i++) {		/* move i-th values of blocks */		t = x[i];		j = i;		for (;;) {          /* Replace with mod below			k = j + rotdist;			if (k >= n)				k -= n;           */            k = (j + rotdist) % n;			if (k == i)				break;			x[j] = x[k];			j = k;		}		x[j] = t;	}}/* Alg 3: Recursive rotate (using gcd structure) */void swap(int i, int j, int k) /* swap x[i..i+k-1] with x[j..j+k-1] */{	int t;	while (k-- > 0) {		t = x[i]; x[i] = x[j]; x[j] = t;		i++;		j++;	}}void gcdrot(int rotdist, int n){	int i, j, p;	if (rotdist == 0 || rotdist == n)		return;	i = p = rotdist;	j = n - p;	while (i != j) {		/* invariant:			x[0  ..p-i  ] is in final position			x[p-i..p-1  ] = a (to be swapped with b)			x[p  ..p+j-1] = b (to be swapped with a)			x[p+j..n-1  ] in final position		*/		if (i > j) {			swap(p-i, p, j);			i -= j;		} else {			swap(p-i, p+j-i, i);			j -= i;		}	}	swap(p-i, p, i);}int isogcd(int i, int j){	if (i == 0) return j;	if (j == 0) return i;	while (i != j) {		if (i > j)			i -= j;		else 			j -= i;	}	return i;}void testgcd(){	int i,j;	while (scanf("%d %d", &i, &j) != EOF)		printf("%d\n", isogcd(i,j) );}/* Test all algs */void slide(int rotdist, int n) /* Benchmark: slide left rotdist (lose 0..rotdist-1) */{	int i;	for (i = rotdist; i < n; i++)		x[i-rotdist] = x[i];}void initx(){	int i;	for (i = 0; i < n; i++)		x[i] = i;}void printx(){	int i;	for (i = 0; i < n; i++)		printf(" %d", x[i]);	printf("\n");}void roterror(){	fprintf(stderr, " rotate bug %d %d\n", n, rotdist);	printx();	exit (1);}void checkrot(){	int i;	for (i = 0; i < n-rotdist; i++)		if (x[i] != i+rotdist)			roterror();	for (i = 0; i < rotdist; i++)		if (x[n-rotdist+i] != i)			roterror();}void testrot(){	for (n = 1; n <= 20; n++) {		printf(" testing n=%d\n", n);		for (rotdist = 0; rotdist <= n; rotdist++) {			/* printf("  testing rotdist=%d\n", rotdist); */			initx(); revrot(rotdist, n);     checkrot();			initx(); jugglerot(rotdist, n);  checkrot();			initx(); jugglerot2(rotdist, n); checkrot();			initx(); gcdrot(rotdist, n);     checkrot();		}	}}/* Timing */void timedriver(){	int i, algnum, numtests, start, clicks;	while (scanf("%d %d %d %d", &algnum, &numtests, &n, &rotdist) != EOF) {		initx();		start = clock();		for (i = 0; i < numtests; i++) {			if (algnum == 1)				revrot(rotdist, n);			else if (algnum == 2)				jugglerot(rotdist, n);			else if (algnum == 22)				jugglerot2(rotdist, n);			else if (algnum == 3)				gcdrot(rotdist, n);			else if (algnum == 4)				slide(rotdist, n);		}		clicks = clock() - start;		printf("%d\t%d\t%d\t%d\t%d\t%g\n",			algnum, numtests, n, rotdist, clicks,			1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));	}}/* Main */int main(){	/* testrot(); */	timedriver();
	return 0;}