#include <stdio.h>
// command line arg is degree in two numbers, e.g. 07, 11 etc
/*********************************************************************

# Program that computes possible type of singularities on a rational plane cuspidal curve
# The data stucture of a cuspidal singularity is a hash
# delta-> delta invariant
# omet-> omega+etha-2
# seq -> array of arrays that codes the multiplicity sequence ([m0,l0],[m1,l1],..]
#        here teh m s are strictly decreasing and l indicate the number of appears of the m
# m0  -> multiplicity
# m1  -> multiplicity in the first blow-up
***********************************************************************/

int d; // degree
int genus; // virtual genus
struct multlisttyp {
	struct multlisttyp *next;
	int multi;
	int anzahl;
	};
struct singlisttype {
	struct singlisttype *next;
	int delta;
	int omet;
	int m0;
	int m1;
	struct multlisttyp *seq;
	};  

struct singlisttype *singlist=NULL;
	
main(int argc, char *argv[])
{
int i,j;  // counter
void print_sing(struct singlisttype *sing){
int i;
struct multlisttyp *mulitypeprint;
if (sing!=NULL){
	printf("delta=%d, m0=%d, m1=%d, omet=%d\n",(*sing).delta,(*sing).m0,(*sing).m1,(*sing).omet);
	mulitypeprint=(*sing).seq;
	while (mulitypeprint!=NULL) {
		printf("[%d,%d]  ",(*mulitypeprint).multi,(*mulitypeprint).anzahl);
		mulitypeprint=(*mulitypeprint).next;
		};
	printf("  =  ");
	mulitypeprint=(*sing).seq;
	while (mulitypeprint!=NULL) {//printf("(%d x %d)  ",(*mulitypeprint).anzahl,(*mulitypeprint).multi);
		for (i=0;i<(*mulitypeprint).anzahl; i++){
			printf("%d ",(*mulitypeprint).multi);}; 
		mulitypeprint=(*mulitypeprint).next;
		};
	printf("\n");
	};
};




d= (((int)argv[1][0])-48)*10+ (((int)argv[1][1])-48); // typ conversion!!!
genus=(d-1)*(d-2)/2;
printf("degree=%d,  virtual genus=%d\n\n\n",d,genus);

//1 Construction of all singularities with delta<(d-1)/2 and multiplicity <=d-2, i.e. which may occur on a irreducible curve of degree d which at least two singulaties
//  The idea of the construction is that cuttig something away from the left of a multiplicity sequence 
//  gives still a possible multiplicity sequence. 
singlist=NULL;
printf("Computing singularities!\n\n");
printf("Initialization!\n");

//1.1 We initilze the list with all singularites that have only two different multiplizities
int m,l; //counter
struct multlisttyp *multneu1;
struct multlisttyp *multneu2;
struct singlisttype *singneu;
for (m=2; m<=d-2; m++) {
	for (l=1; l<= 2*genus/(m*(m-1)); l++){//printf( "m= %d  l=%d\n",m,l);
		multneu1=(struct multlisttyp *)malloc(sizeof(struct multlisttyp));
		(*multneu1).next=NULL;(*multneu1).multi=1;(*multneu1).anzahl=m; 
		multneu2=(struct multlisttyp *)malloc(sizeof(struct multlisttyp));
		(*multneu2).next=multneu1;(*multneu2).multi=m;(*multneu2).anzahl=l;
		singneu=(struct singlisttype *)malloc(sizeof(struct singlisttype));
		(*singneu).next=singlist;(*singneu).delta= l*m*(m-1)/2;(*singneu).seq=multneu2;
		singlist=singneu;
		;}; 
	}; 

//printf( "Finished initialization!\n\n");
struct singlisttype *singtemp;
/
//printf( "\n\n\n\n");
printf("Starting Progression\n");
//1.2 Now the progression

// find last element for appending operation
struct singlisttype *singlast;
singlast=singlist;	
while ((*singlast).next!=NULL) {singlast=(*singlast).next;};

//Now run through all elements including the new ones
singtemp=singlist;
int m0old,l0old,m1old,mfac; // m,l see above
while (singtemp!=NULL) {
//	printf("zu berabeitende Sing:\n");
//	print_sing(singtemp);print "\n";
	m0old=(*((*singtemp).seq)).multi; 
	l0old=(*((*singtemp).seq)).anzahl;  
	m1old=(*( (*((*singtemp).seq)).next)).multi; 
	for (mfac=2;mfac<=l0old;mfac++){ //normal multiplcity m0old*mfac
		m=m0old*mfac; 
		for(l=1;l*m*(m-1)/2+(*singtemp).delta<=genus;l++) {
			multneu1=(struct multlisttyp *)malloc(sizeof(struct multlisttyp));// new mult pair
			(*multneu1).next=(*singtemp).seq;(*multneu1).multi=m;(*multneu1).anzahl=l; 
			singneu=(struct singlisttype *)malloc(sizeof(struct singlisttype));//newelement
			(*singneu).next=NULL;
			(*singneu).delta=(*singtemp).delta+ l*m*(m-1)/2;
			(*singneu).seq=multneu1;
			(*singlast).next=singneu;//insert
			singlast=singneu;
			};
		};
	m=m0old*l0old+m1old; //exceptional multiplicity 
	for(l=1;l*m*(m-1)/2+(*singtemp).delta<=genus;l++) {
		multneu1=(struct multlisttyp *)malloc(sizeof(struct multlisttyp));// new mult pair
		(*multneu1).next=(*singtemp).seq;(*multneu1).multi=m;(*multneu1).anzahl=l; 
		singneu=(struct singlisttype *)malloc(sizeof(struct singlisttype));//new element
		(*singneu).next=NULL;
		(*singneu).delta=(*singtemp).delta+ l*m*(m-1)/2;
		(*singneu).seq=multneu1;
		(*singlast).next=singneu;//insert
		singlast=singneu;
		};	
	singtemp=(*singtemp).next;};

//printf("finished  constructing all singularities!\n\n");
//printf( "\n\n");


//1.3 Compute all invariants and do the Lin-Zaidenberg-Test

printf( "Computing invariants!\n\n");
int eta, omega,omet,remainder;
struct multlisttyp *multtemp;
struct singlisttype *singtemp2;
singtemp=singlist;// run through all elements, reconstruct list
singlist=NULL;
while (singtemp!=NULL) {
	(*singtemp).m0= (*((*singtemp).seq)).multi;  // compute m0 and m1
	if ( (*((*singtemp).seq)).anzahl>1) {
		(*singtemp).m1=(*((*singtemp).seq)).multi;}
	else {	
		(*singtemp).m1=(*( (*((*singtemp).seq)).next)).multi;	};
//	printf( "\n");print_sing(singtemp);	
	eta=0; //compute eta, omega and omet
	omega=1;
	multtemp=(*singtemp).seq; //run through sequence
	while ( (*multtemp).next!=NULL ){
//		printf("omega= %d, eta= %d  \n",omega,eta);
		eta+=(*multtemp).anzahl * ((*multtemp).multi -1);
		remainder=(*multtemp).multi %(*((*multtemp).next)).multi;// prepare to round up
//		printf("remainder = %d \n ",remainder); 
		if (remainder!=0) {remainder=(*((*multtemp).next)).multi-remainder;};
		omega+=( ((*multtemp).multi) +remainder) / (*((*multtemp).next)).multi    -1;
		multtemp=(*multtemp).next;
		};
	(*singtemp).omet=eta+omega-2;
//printf( "\n");print_sing(singtemp);printf( "--------------------------\n");	
	if ((*singtemp).m0+(*singtemp).m1<d) { //Lin-Zaidenberg Test nad progress
		singtemp2=(*singtemp).next; //passed
		(*singtemp).next=singlist; //insert into singlist
		singlist=singtemp;
		singtemp=singtemp2;//progess
		}
        else { //failed
//        	printf( "Ruled out by Lin-Zaidenberg\n");print_sing(singtemp);printf( "\n");
		singtemp=(*singtemp).next;
		};
	};

//count the singulaties for fun
i=0;singtemp=singlist;
while (singtemp!=NULL) {i++;singtemp=(*singtemp).next;};

printf (" \nThere are %d possible singularities:\n\n",i); 


//1.4 Sort by delta
printf( "Sorting!\n"); // by straight insertion;
struct singlisttype *singpos;
singtemp=(*singlist).next;
(*singlist).next=NULL; //first element sorted
while (singtemp!=NULL) {
	if ((*singtemp).delta<=(*singlist).delta){//new first element
		singtemp2=(*singtemp).next;
		(*singtemp).next=singlist; 
		singlist=singtemp;
		singtemp=singtemp2;}
	else{
		singpos=singlist;
		while( ((*singpos).next!=NULL) ){//search for position after which 
						  //new element will be inserted 
		if ( (*singtemp).delta<=(*((*singpos).next)).delta ) break;
			singpos=(*singpos).next;};
		singtemp2=(*singtemp).next;
		(*singtemp).next=(*singpos).next;
		(*singpos).next=singtemp;
		singtemp=singtemp2;
		};
};
singtemp=singlist;	

//printf( "\n\n");

// 2 Search for possible combinations
printf("Search for possible combinations\n\n");
struct singlisttype *singcomb[9];
int comblast; //number of elements in the  combination
int deltasum, gamma2,M;
int bezout,hurwitz;
singcomb[0]=singlist; //start list
comblast=0;//index of the last element

deltasum=(*(singcomb[0])).delta ; // Compute the sum of the dela-invariants of the combination
while (comblast>=0) {
//	printf("while with %d elements und delta=%d\n\n",comblast+1,deltasum);
	if (deltasum<genus) { // not enough delta 
		if (comblast+1<8) { //more singularities are possible
//		printf("branch 1\n");
			singcomb[comblast+1]=singcomb[comblast];
			comblast++;
			deltasum+= (*(singcomb[comblast])).delta;
			}
		else { // max singularities, increase last, after dropping the ones that are maximal 
//		printf("branch 2\n");
			while ((*(singcomb[comblast])).next== NULL) { 
	 			deltasum-=(*(singcomb[comblast])).delta;
				comblast--; 
				if (comblast<0) break;
				};
			if (comblast<0) break;
			deltasum-=(*(singcomb[comblast])).delta;
			singcomb[comblast]=(*(singcomb[comblast])).next;
			deltasum+=(*(singcomb[comblast])).delta;	
			};
		}
	else {if (deltasum>genus) { // too much delta, drop the last one, increase the one before
//		printf("branch 3\n");
		deltasum-=(*(singcomb[comblast])).delta;		
		comblast--;	
		while ((*(singcomb[comblast])).next== NULL) { 
			deltasum-=(*(singcomb[comblast])).delta;
			comblast--;
			if (comblast<0) break;
//			printf("branch 3 in while,comblast=%d \n",comblast);
			};
//		printf("branch 3 after while \n");
		if (comblast<0) break;
		deltasum-=(*(singcomb[comblast])).delta;
		singcomb[comblast]=(*(singcomb[comblast])).next;
		deltasum+=(*(singcomb[comblast])).delta;	
		}
	else {   // here we have the rational curves, do further tests
//		printf( "found combination with right delta:  \n");	
		int gamma2; gamma2=3*(3-d); // gamma2 test
		for (i=0; i<=comblast;i++){
			gamma2+=(*(singcomb[i])).omet;};
//		print "gamma2=",$gamma2,"\n";
		if ((gamma2==0) && (comblast>=2)) {// gamma passed and at least 3 sings
//			printf( "gamma passed\n");
			bezout=1; // Bezout-Test, 1=true
			for(i=0;i<=comblast;i++){
			     	for(j=i+1;j<=comblast;j++){
//					printf("Bezouttest i=%d  j=%d  multies %d %d\n",i,j,(*(singcomb[i])).m0,(*(singcomb[j])).m0);
					if ( (*(singcomb[i])).m0+(*(singcomb[j])).m0>d ) {bezout=0;};};
				};
//			printf( "Bezout result: %d\n", bezout);
			if (bezout) { //Bezout passed
//				printf( "Bezout passed\n");
				hurwitz=1; // Hurwitz-Test, 1=true
				M=0; //Compute sum of multiplicities
				for(i=0;i<=comblast;i++){ M+=( (*(singcomb[i])).m0 -1);};
//				print "M= ",$M,"\n";
				for(i=0;i<=comblast;i++) { 
//					print "Hurwitztest " ,$M+${$singlist[$index]}{"m0"}+${$singlist[$index]}{"m1"},"<=",2*$d-2,"\n";
					if ( M+(*(singcomb[i])).m0+(*(singcomb[i])).m1>2*d-2) {hurwitz=0;};
					};
//				printf( "Hurwitz result: %d\n", hurwitz);
				if (hurwitz) {
//					print "Hurwitz passed\n";
//					print"\nThe WINNER is\n";
					for(i=0;i<=comblast;i++) {print_sing(singcomb[i]);printf( "\n");};
					printf("-----------------------------------------------\n");
					};
				};
			};// gamma2 passed end
//		find next, increase last, hoping that it has the same delta (cannot add onother singularites)
//		printf("findnext\n");
		while ((*(singcomb[comblast])).next== NULL) { 
			deltasum-=(*(singcomb[comblast])).delta;
			comblast--;
			if (comblast<0) break;
			};
		if (comblast<0) break;
		deltasum-=(*(singcomb[comblast])).delta;
		singcomb[comblast]=(*(singcomb[comblast])).next;
		deltasum+=(*(singcomb[comblast])).delta;
		};}; // both else end here	
	};
	

return(0);
}