/******************************************************************
* Written by Adam Piggott, 29-30 June 2005.
*
* This program allows the user to enter words in {x, y, X, Y}*
* and then tests to see if the word is a reduced primitive in F(x, y).
*
* The algorithm for testing cyclically reduced primitive elements 
* is very fast (linear in length of input)
* and follows from Osborne and Zieshang (Invent. Math, 1981).
*
* TESTING RESULTS:  The IsPrimitive function was used to correctly
* count 3188 primitives in the reduced words in {x, y, X, Y}* of 
* length at most 9.
*
* Use this code if you would like, but please acknowledge its source.
*
*****************************************************************/


#include <stdio.h>

#define c1 'x'
#define c2 'y'
#define MAXL 100

int InverseChars(char d1, char d2)
/******************************************************************
* This function returns 1 if d1 and d2 are upper and lower case
* instances of the same letter (or vice-versa), 0 otherwise.
*
* No library functions are called.
*
******************************************************************/
{
	return (((d1 - d2) == 'A' - 'a') || ((d2-d1) == 'A' - 'a'));
}


int IsCRPrimitive(const char crw[], int L, int esX, int esY)
/******************************************************************
* crw is a CYCLICALLY reduced word in {x, X, y, Y}*
* L is the length of crw
* esX is the exponent sum of x in crw
* esY is the exponent sum of y in crw
*
* This function returns 1 if crw is a reduced primitive in F(x, y), 
* 0 otherwise.
*
* There is no error checking of input in this function, so make
* sure the inputs are consistent before calling.
*
* The algorithm follows from Osbourne and Zieschang (Invent. Math, 1981).
*
* No library functions are called.
******************************************************************/
{

	int absX, absY;				/* For storing |esX| and |esY| 	*/
	int i, r;				/* Indexing variables 		*/
	char firstLetter;			/* The first letter in crw	*/

	int step;				/* The right gap between cyclic	*/
						/* occurences of firstLetter	*/
						/* in a primitive word with the	*/
						/* given exponent sums		*/

	int countForwards, countBackwards;	/* Used for countings number of */
						/* occurences of firstLetter 	*/
						/* "in the right places"	*/

	if (L==0)
		return 0;

	/******************************************************************
	* calculate absX and absY
	******************************************************************/	
	if (esX >= 0)
		absX = esX;
	else
		absX = -esX;

	if (esY >= 0)
		absY = esY;
	else
		absY = -esY;


	/******************************************************************
	* perform some initial checks which give fast returns
	******************************************************************/
	if (absX + absY < L)
		return 0;

	if (absX == 1)
		return 1;

	if (absY == 1)
		return 1;
	
	if (absX == 0)
		return 0; /* since we know absY <> 1 */

	if (absY == 0)
		return 0; /* since we know absX <> 1 */

	/******************************************************************
	* since we have passed the initial tests, 
	* (absX + absY) == L and  min{absX, absY} > 1.
	*
	* We now calculate step, during which we also establish whether
	* or not absX and absY are relatively prime.
	******************************************************************/
	if (absX < absY)
	{	step = 1;
		r = (step*absX) % L;
		while ((r != 1) && (step < L))
		{	step = step + 1;
			r = (step*absX) % L;
		}
	}
	else
	{	step = 1;
		r = (step*absY) % L;
		while ((r != 1) && (step < L))
		{	step = step + 1;
			r = (step*absY) % L ;
		}
	}

	/* (r == L) iff (absX && absY are not relatively prime). 	*/
	if (step == L)
		return 0;

	/******************************************************************
	* We now know that gcd{absX, absY} = 1 and the congruence class of
	* step * absx (or absY as appropriate) congruent to 1 modulo L.
	*
	* We now apply the algorithm which follows from 
	* Osbourne and Zieschang (Invent. Math, 1981).
	******************************************************************/
	firstLetter = crw[0];
	countForwards = 0;
	i = step;
	while (crw[i] == firstLetter)
	{	countForwards = countForwards + 1;
		i = (i+step) % L;	
	}
	countBackwards = 0;
	i = L - step;
	while (crw[i] == firstLetter)
	{	countBackwards = countBackwards + 1;
		i = (i-step);
		if (i < 0)
			i = i+L;	
	}

	if ((firstLetter == c1) || (firstLetter == c1 + 'A' - 'a'))
		return (countForwards + countBackwards + 1 == absX);
	else
		return (countForwards + countBackwards + 1 == absY);
}	


int IsPrimitive(const char rw[])
/******************************************************************
* rw is a word
*
* This function returns 1 if rw is a reduced primitive in F(x, y), 
* 0 otherwise.
*
* There is some error checking of input.  The error checking will
* pick up the following difficulties: 
*	rw is the empty word;
* 	rw contains letters other than x, X, y, Y;
*	rw is not reduced;
*
* This function calculates the exponent sums, cyclically reduces
* rw if necessary, then calls IsCRPrimitive.
* 
* Of course, some of the error checking can be removed if you are
* confident of the input.
*
* No library functions are called.
******************************************************************/
{
	int L, esX, esY;	/* Length and exponent sums 	*/
	int i, j;		/* Indexing variables		*/

	char crw[MAXL];		/* Cyclically reduced word	*/
				/* corresponding to rw		*/
	
	/******************************************************************
	* Check that rw is reduced in {x, y, X, Y}* and calculate string 
	* length and exponent sums whilst doing so
	******************************************************************/
	if (rw[0] == '\0')
	{	return 0;
	}
	else
	{	/* treat first letter outside loop because
		 we don't check for possible free reduction */
		switch(rw[0])
		{
			case c1: 
				esX = 1;
				esY = 0;
				break;
			case c2: 
				esX = 0;
				esY = 1;
				break;
			case c1+'A'-'a':
				esX = -1;
				esY = 0;
				break;
			case c2+'A'-'a':
				esX = 0; 
				esY = - 1;
				break;
			default:
				/* printf("\n(The word contains a weird letter.)\n\n"); */
				return 0;
		}

		/* deal with other letters in a loop */
		i = 1;
		while(rw[i] != '\0')
		{
			
			/* update exponent sums so far */
			switch(rw[i])
			{
				case c1: 
					esX = esX + 1;
					break;
				case c2: 
					esY = esY + 1;
					break;
				case c1+'A'-'a': 
					esX = esX - 1;
					break;
				case c2+'A'-'a': 
					esY = esY - 1;
					break;
				default:
					/* printf("\n(The word contains a weird letter.)\n\n"); */
					return 0;
			}


			/* check for possible free reduction */
			if (InverseChars(rw[i], rw[i-1]))
			{	/* printf("\n(The word is not reduced.) \n\n"); */
				return 0;
			}
			i = i+1;

		}
		L = i;
	}

	/******************************************************************
	* Cyclically reduce word if necessary
	******************************************************************/
	i = 0;
	while(InverseChars(rw[i], rw[L-i-1]))
		i = i+1;
	for(j = 0; j < L - 2*i; j++)
		crw[j] = rw[j+i];
	crw[j] = '\0';

	/******************************************************************
	* Call IsCRPrimitive and return the result.
	******************************************************************/
	return(IsCRPrimitive(crw, L-2*i, esX, esY));
}

main()
/******************************************************************
* A little program to test IsPrimitive.
******************************************************************/
{
	char theWord[100];	/* The input word to consider */ 

	printf("*********************** \n\n");
	printf("This program tests words in {x, y, X, Y}* to ");
	printf("see if they are reduced primitives in F(x, y).\n\n");
	printf("It uses an algorithm based on Osborne and Zieschang (Invent. Math, 1981).\n\n");

	printf("Enter a reduced word in {x, y, X, Y}* or \'q\' to quit: ");
	scanf("%s", theWord);

	while(theWord[0]!='q')
	{
		printf("The word ");
		printf(theWord);
		if (IsPrimitive(theWord))
			printf(" is ");
		else
			printf(" is NOT ");

		printf("a reduced primitive in F(x, y).\n\n");
	
		printf("Enter a reduced word in {x, y, X, Y}* or \'q\' to quit: ");
		scanf("%s", theWord);
	}
	printf("Bye.\n");
	printf("\n***********************\n\n");
}