#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define MAXPAROLE 80

struct _lista
{
	char word[MAXPAROLE+1];
   struct _lista *next;
};
typedef struct _lista lista;

lista *head=NULL;
lista *tail=NULL;
int count=0;
char elemento[MAXPAROLE+1];

int insord(void)
{
   lista *p0,*p1,*temp;
   printf("Inserisci l'elemento da inserire: ");
   gets(elemento);
   if(!head)
   {
   	head=(lista*)malloc(sizeof(lista));
      strcpy(head->word,elemento);
      head->next=NULL;
	   tail=head;
      count++;
	}
   else
   {
		for(p1=head;p1!=NULL && (strcmp(p1->word,elemento)<0);p1=p1->next)
   		p0=p1;
   	if(p0)
   	{
   		temp=(lista*)malloc(sizeof(lista));
      	strcpy(temp->word,elemento);
      	temp->next=p1;
      	p0->next=temp;
         count++;
   	}
   	else
   	{
   		temp=(lista*)malloc(sizeof(lista));
      	strcpy(temp->word,elemento);
      	temp->next=head;
      	head=temp;
         count++;
   	}
	}
   return 0;
}

int deleteall(void)
{
   lista *p0,*p1;
	p1=head;
	while(p1)
	{
   	p0=p1;
      p1=p1->next;
      free(p0);
   }
   head=NULL;
  	return 0;
}

int inshead(void)
{
   lista *temp;
	printf("Inserisci il dato da inserire nella lista: ");
   gets(elemento);
	if(!head)
   {
		head=(lista*)malloc(sizeof(lista));
   	strcpy(head->word,elemento);
   	head->next=NULL;
		tail=head;
      count++;
   }
	else
   {
   	temp=head;
      head=(lista*)malloc(sizeof(lista));
   	strcpy(head->word,elemento);
   	head->next=temp;
      count++;
   }
	return 0;
}

int instail(void)
{
   lista *temp;
   printf("Inserisci il dato da inserire nella lista: ");
   gets(elemento);
   if(!head)
   {
   	head=(lista*)malloc(sizeof(lista));
      strcpy(head->word,elemento);
      head->next=NULL;
      tail=head;
      count++;
   }
   else
   {
   	temp=(lista*)malloc(sizeof(lista));
      strcpy(temp->word,elemento);
      tail->next=temp;
      tail=temp;
      tail->next=NULL;
      count++;
   }
	return 0;
}

int delhead(void)
{
   lista *p0;
   if(!head)
   	printf("Impossibile eleminare...nessun elemento presente\n");
   else
   {
   	p0=head;
   	head=head->next;
   	free(p0);
      count--;
   }
	return 0;
}

int deltail(void)
{
   lista *p0=NULL,*p1;
   if(!head)
   	printf("Impossibile eleminare...nessun elemento presente\n");
   else
   {
   	for(p1=head;p1->next!=NULL;p1=p1->next)
      	p0=p1;
      free(p1);
      tail=p0;
	  if(tail)
			tail->next=NULL;
	  else
		  head=NULL;
      count--;
   }

	return 0;
}
int printall(void)
{
   lista *p1;
   if(head==NULL)
   	printf("Nessun elemento presente nella lista\n");
   for(p1=head;p1!=NULL;p1=p1->next)
   	printf("%s\n",p1->word);
	return 0;
}

lista* find(void)
{
   char elem[MAXPAROLE+1];
   int ok=0;
   lista *p0=NULL,*p1;
   printf("inserisci l'elemento da cercare: ");
   scanf("%s",&elem);
   p1=head;
   while(ok!=1)
   {
      if(p1==NULL)
      {
      	ok=1;
         return NULL;
      }
      if(!strcmp(p1->word,elem))
   	{
      	p0=p1;
         ok=1;
      }
      p1=p1->next;
   }
   	return p0;
}

void removevalue(void)
{
   int ok=0;
   lista *p2=NULL,*p1,*p0;
   p1=find();
	if(p1==NULL)
    	printf("Elemento non disponibile,impossibile eliminare\n");
   else if(p1==head)
   {
		  head=head->next;
        free(p1);
   }
   else if(p1==tail)
   {
   	for(p0=head;p0->next!=NULL;p0=p0->next)
      	p2=p0;
      free(p1);
      tail=p2;
	  if(tail)
			tail->next=NULL;
	  else
		  head=NULL;
      count--;
   }
   else
   {
      p0=head;
   	while(!ok)
      {
      	if(!strcmp(p0->next->word,p1->word))
      	{
         	p2=p0;
      		p2->next=p1->next;
      		free(p1);
      		count--;
            ok=1;
         }
         p0=p0->next;
      }
   }
}

int sort(void)
{
   lista *p0,*p1,*p2=NULL;
   int i,j;
   p1=head;
   if(p1==NULL || p1->next==NULL)
   {
     	printf("Ordinamento inutile\n");
      return 1;
   }
   else
   {
	   for(i=count-1;i>0;i--)
      {
		   p1=head;
		   p2=NULL;
		   for(j=0;j<i;j++)
         {
			   p0=p1;
			   p1=p1->next;
			   if(strcmp(p0->word,p1->word)>0)
            {
				   if(p2)
               {
					   p2->next=p1;
					   p0->next=p1->next;
					   p1->next=p0;
				   }
				   else
               {
					   p0->next=p1->next;
					   p1->next=p0;
					   head=p1;
				   }
			   }
			   p2=p0;
		   }
	   }
   }
   for(p1=head;p1->next!=NULL;p1=p1->next);
   tail=p1;
   return 0;
}