#include <stdio.h>
#include <stdlib.h> //per allocazione dinamica
//Strutture dati

typedef struct 
{
	char *e;	//Elementi dell'insieme
	int n;		//Cardinalita' dell'insieme: n>=0 sempre, e n==0 sse insieme vuoto,
				//nel qual caso deve valere e==NULL
} Ins;

//Dichiarazioni delle funzioni

void stampa(Ins *A); 	//Visualizza A su stdout
int app(char c, Ins *A);//returns: 1 se c appartiene ad A, 0 altrimenti
int sub(Ins *A, Ins *B);//returns: 1 se A e' sottoinsieme di B, 0 altrimenti
int eq(Ins *A, Ins *B); //returns: 1 se A=B, 0 altrimenti
int add(char c, Ins *A);//A = A U {c}. returns: 1 se operazione riesce, 0 altrimenti
Ins *strtoins(char *s); //Restituisce un puntatore all'insieme i cui elementi sono quelli
						//della stringa s. returns: puntatore all'insieme 
						//se operazione riesce, NULL altrimenti. Assume s != NULL
Ins *dup(Ins *A);		//Restituisce un puntatore a una copia dell'insieme A
						//returns: puntatore alla copia se operazione riesce, NULL 
						//altrimenti.

Ins *uni(Ins *A, Ins *B);	//Restituisce un puntatore all'insieme A unione B
							//returns: puntatore all'insieme unione
							//se operazione riesce, NULL altrimenti. Assume s != NULL


Ins *inter(Ins *A, Ins *B);	//restituisce un puntatore l'insieme A intersezione B
							//returns: puntatore all'insieme itersezione
							//se operazione riesce, NULL altrimenti. assume s != NULL

int main(int argc, char *argv[])
{

	if (argc < 4)
	{
		printf("Numero degli argomenti insufficiente.\n");
		return -1;
	}
	
	if (argv[1][0]!='-')
	{
		printf("Formato degli argomenti errato.\n");
		return -1;
	}
	
	for (int i=1; argv[1][i]!='\0'; i++)
	{
		Ins *A = strtoins(argv[2]);
		Ins	*B = strtoins(argv[3]);
		
		switch (argv[1][i])
		{
			case 'I': case 'i':
			{
				Ins *I=inter(A,B);
				if (I==NULL)
				{
					printf("Errore nell'allocazione della memoria.\n");
					break;	
				}
				stampa(A);
				putchar(argv[1][i]);
				stampa(B);
				putchar('=');
				stampa(I);
				putchar('\n');
				free(I);
			}
			break;
			case 'U': case 'u':
			{
				Ins *U=uni(A,B);
				if (U==NULL)
				{
					printf("Errore nell'allocazione della memoria.\n");
					break;	
				}
				stampa(A);
				putchar(argv[1][i]);
				stampa(B);
				putchar('=');
				stampa(U);
				putchar('\n');
				free(U);
			}
			break;
			case 'S': case 's':
			{
				stampa(A);
				putchar(argv[1][i]);
				stampa(B);
				putchar(':');
				if (sub(A,B))
					printf("True.\n");				
				else
					printf("False.\n");
			}
			break;
			case '=': case 'E':
			{
				stampa(A);
				putchar(argv[1][i]);
				stampa(B);
				putchar(':');
				if (eq(A,B))
					printf("True.\n");				
				else
					printf("False.\n");
			}
		}
	}		
}

void stampa(Ins *A)
{
	int i; 
	putchar('{');
	for (i=0; i<A->n-1; i++) //<n-1 per omettere la virgola dopo ultimo elemento
	{
		putchar((A->e)[i]);
		putchar(',');
	}
	if (A->n!=0) //se l'insieme non e' vuoto, rimane da emettere ultimo elemento
		putchar((A->e)[i]);
	putchar('}');
}

int app(char c, Ins *A) //returns: 1 se c appartiene ad A, 0 altrimenti
{
	int i;
	
	for (i=0; (i< (A->n) ) && ( c != (A->e)[i] ); i++);
	
	return ( i<(A->n) );
}

int sub(Ins *A, Ins *B) //returns: 1 se A e' sottoinsieme di B, 0 altrimenti
//Implementazione ricorsiva, come richiesto dal tema
{
	if (A->n==0) //Caso base 1
		return 1;
		
	if (A->n==1) //Caso base 2
		return app(*(A->e),B);
		
	Ins C = { (A->e)+1, (A->n)-1 }; //Caso passo
	return ( (app(*(A->e),B)) && (sub(&C,B)) );
}

int eq(Ins *A, Ins *B) //returns: 1 se A=B, 0 altrimenti
{
	return (sub(A,B)&&sub(B,A));
}

int add(char c, Ins *A) // A = A U {c}. returns: 1 se operazione riesce, 0 altrimenti
{
	if (app(c,A))
		return 1;
	
	char *tmp = realloc( A->e, (sizeof (char))* ((A->n)+1) );
	
	if ( tmp==NULL )	//errore nell'allocazione della memoria
		return 0;		//A e' invariato
	
	A->e=tmp;
	(A->e)[(A->n)]=c;
	(A->n)++;
	
	return 1;
}

Ins *strtoins(char *s)	//Restituisce un puntatore all'insieme i cui elementi sono quelli
						//della stringa s. returns: puntatore all'insieme 
						//se operazione riesce, NULL altrimenti. Assume s != NULL
{
	Ins *A = malloc(sizeof (Ins));
	if (A==NULL)
		return NULL;
	
	A->e=NULL;
	A->n=0; //A e' l'insieme vuoto
	
	while ((*s)!='\0')
	{
		if (!add(*s,A))
		{
			free(A);
			return NULL;
		}
		s++;
	}
	
	return A;
}

Ins *dup(Ins *A)			//Restituisce un puntatore a una copia dell'insieme A
							//returns: puntatore alla copia se operazione riesce, NULL 
							// altrimenti.
{
	Ins *B = malloc(sizeof (Ins));
	if (B==NULL)
		return NULL;
	
	if ( (A->n) == 0)		//Caso: |A|=0. Necessario distinguerlo da |A|>0 perche' 
							//malloc su size 0 e' implementation-dependent	
	{						
		B->e=NULL;
		B->n=0;
		return B;
	}
	
	//Caso: |A|>0
	if ( ( B->e=malloc((sizeof (char)) * (A->n)) )==NULL)
	{
		free(B);
		return NULL;
	}
	
	//Copia dei dati. Nota bene: 
	//Qui e' un errore scrivere semplicemente (*C)=(*A) perche' le specifiche
	//richiedono duplicazione dei *dati*, non solo dei puntatori.
	
	for (int i=0; i<(A->n); i++)
		(B->e)[i]=(A->e)[i];
	B->n=A->n;
		
	return B;
}
Ins *uni(Ins *A, Ins *B)	//Restituisce un puntatore all'insieme A unione B
							//returns: puntatore all'insieme unione
							//se operazione riesce, NULL altrimenti. 
{
	Ins *C = dup(A);
	if (C==NULL)
		return NULL;

	for (int i=0; i<(B->n); i++)
		if (!add((B->e)[i],C))
		{
			free(C->e);
			free(C);
			return NULL;
		}
	
	return C;
}


Ins *inter(Ins *A, Ins *B)	//restituisce un puntatore l'insieme A intersezione B
							//returns: puntatore all'insieme itersezione
							//se operazione riesce, NULL altrimenti. assume s != NULL
{
	Ins *C = malloc(sizeof (Ins));
	if (C==NULL)
		return NULL;
	
	C->e=NULL; //Inizializza: C={}
	C->n=0;
	
	for (int i=0; i<(A->n); i++)
		if (app((A->e)[i],B))
			if (!add((A->e)[i],C))
			{
				free(C->e);
				free(C);
				return NULL;
			}
		
	return C;
}