/* 
===========
Esercizio 1
=========== 
Definire una funzione che, data una ListaDiTipo, restituisce la sua lunghezza.
*/

/* versione iterativa */
int length (ListaDiTipo lista) {
  int lunghezza = 0;
  while (lista != NULL) {
    lunghezza++;
    lista = lista -> next;
  }
  return lunghezza;
}


/* versione ricorsiva */
int lengthRic (ListaDiTipo lista) {
  if (lista == NULL) return 0;
  else return 1 + lengthRic(lista->next);
}

/* 
===========
Esercizio 2
===========
Scrivere una funzione che presa una lista, inserisca un elemento che e' 
il successivo del precedente
 */

/* versione iterativa */
void succPrec(ListaDiInteri *lista) {
  ListaDiInteri aux, nuovo;
  if (*lista != NULL) {
    inserisciInTesta(&((*lista)->next), (*lista)->info + 1);
    aux = ((*lista)->next)->next;
    while (aux != NULL) {
      nuovo = malloc(sizeof(ElementoLista));
      nuovo->info =  aux->info + 1;
      nuovo->next = aux->next;
      aux->next = nuovo;
      aux = nuovo->next;
    }
  } 
}


/* versione ricorsiva */
void succPrecRic(ListaDiInteri *lista) {
  if (*lista != NULL) {
    inserisciInTesta(&((*lista)->next), (*lista)->info + 1);
    succPrecRic(&((*lista)->next)->next);
  }
}

/* 
===========
Esercizio 3
===========
Scrivere una funzione che presa una lista, inserisca un elemento che e'
il precedente del successivo.
*/

/* versione iterativa */
void precSucc(ListaDiInteri *lista) {
  ListaDiInteri aux, nuovo;
  if (*lista != NULL) {
    inserisciInTesta(&(lista, (*lista)->info - 1);
    aux = (*lista)->next;
    while (aux->next != NULL) {
      nuovo = malloc(sizeof(ElementoLista));
      nuovo->info =  (aux->next)->info - 1;
      nuovo->next = aux->next;
      aux->next = nuovo;
      aux = nuovo->next;
    }
  } 
}

/* versione ricorsiva */
void precSucc(ListaDiInteri *lista) {
  if (*lista != NULL) {
    inserisciInTesta(lista, (*lista)->info - 1);
    precSucc(&((*lista)->next)->next);
  }
}

					 
/* 
===========
Esercizio 4
===========
Scrivere una procedura che, data una lista di interi, ne elimini tutti 
gli elementi che contengono valori dispari. 
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum {false, true} boolean;

typedef struct EL {
    int elem;
    struct EL *next;	
} ElementoLista;

typedef ElementoLista *ListaDiInteri; 

ListaDiInteri crealista(int n){
  int num;
  int i;
  ListaDiInteri aux,lista;
  if(n == 0) return NULL;
  printf("Inserisci un intero: ");
  scanf("%d",&num);
  lista = malloc(sizeof(ElementoLista));
  lista->elem = num; 
  aux = lista;
  i=1;
  while(i < n) {
    printf("Inserisci un intero: ");
    scanf("%d",&num);
    aux->next = malloc(sizeof(ElementoLista));
    aux = aux->next;
    aux->elem = num;
    i++;
  }
  aux->next=NULL;
  return lista;
}	  

void stampa(ListaDiInteri lis) { 
  while (lis!= NULL) { 
    printf("%d ", lis->elem); 
    lis = lis->next; 
  } 
  printf("//\n"); 
}  

void cancellaPrimo(ListaDiInteri *lista)
{
  ListaDiInteri aux;
  if(*lista != NULL) {
    aux = *lista;
    *lista = (*lista)->next;
    free(aux);
  }
}


void cancellaTutti(ListaDiInteri *lista, int x) {
  ListaDiInteri prec;    /* puntatore all'elemento precedente */
  ListaDiInteri corr;    /* puntatore all'elemento corrente */
  boolean eliminaPrimo = true;
  while ((*lista != NULL) && eliminaPrimo)  /* cancella le occorrenze */
    if ((*lista)->elem != x)              /* di elem in testa       */
      eliminaPrimo = false;
    else cancellaPrimo(lista);
  
  if (*lista != NULL) {
    prec = *lista; corr = prec->next;
    while (corr != NULL)
      if (corr->elem == x) {   /* cancella l'elemento */
	prec->next = corr->next;
	free(corr);
	corr = prec->next;}
      else {
	prec = prec->next;    /* avanzamento dei due puntatori */
	corr = corr->next;   
      }
  }
}


void cancellaDispari(ListaDiInteri *lista) {
  ListaDiInteri prec, corr;
  boolean eliminaPrimo = true;
  while ((*lista != NULL) && eliminaPrimo)  
    if ((*lista)->elem % 2 == 0) eliminaPrimo = false;
    else cancellaPrimo(lista);
  if (*lista != NULL) {
    prec = *lista; corr = prec->next;
    while (corr != NULL)
      if (corr->elem % 2 == 1) {   /* cancella l'elemento */
	prec->next = corr->next;
	free(corr);
	corr = prec->next;}
      else {
	prec = prec->next;    /* avanzamento dei due puntatori */
	corr = corr->next;   
      }
  }
}


void cancellaDispariRic(ListaDiInteri *lista) {
  if (*lista != NULL) {
    if ((*lista)->elem % 2 == 1) {
      cancellaPrimo(lista);
      cancellaDispariRic(lista);
    }
    else cancellaDispariRic(&((*lista)->next));
  }
}


main() {

  ListaDiInteri lista; 
  int n;
  printf("Numero di elementi della lista: ");
  scanf("%d", &n);
  lista = crealista(n);
  stampa(lista);  
  cancellaDispariRic(&lista);
  stampa(lista);
}
					 
					 

/* 
===========
Esercizio 5
=========== 
Definire una funzione FirstEven che, data una ListaDiInteri,
restituisce la posizione (puntatore) del primo elemento pari nella 
lista (restituisce NULL se la lista non contiene elementi pari).
*/

/* versione iterativa */

ListaDiInteri FirstEven(ListaDiInteri lista) {
  boolean trovato = false;
  ListaDiInteri risultato = NULL;
  while(lista != NULL && !trovato)
    if (lista->info % 2 == 0) {
      risultato = lista;
      trovato = true;
    }
    else lista = lista -> next;
  return risultato;
}


/* versione ricorsiva */
ListaDiInteri FirstEvenRic(ListaDiInteri lista) {
  ListaDiInteri risultato = NULL;
  if (lista != NULL)
    if (lista->info % 2 == 0) risultato = lista;
    else risultato = FirstEvenRic(lista->next);
  return risultato;
}

/* 
===========
Esercizio 6
===========
Definire una funzione MinEven che, data una ListaDiInteri,
restituisce la posizione (puntatore) del minimo elemento pari nella
lista (restituisce NULL se la lista non contiene elementi pari).
*/

/* versione iterativa */

ListaDiInteri MinEven(ListaDiInteri Lista) {
  ListaDiInteri risultato = NULL;
  boolean trovatoPari = false;
  while(lista != NULL) {
   if (lista->info % 2 == 0)
     if (!trovatoPari) {
       trovatoPari = true;
       risultato = lista;
     }
     else if (risultato->info > lista->info) risultato = lista;
   lista = lista -> next;
  }         
  return risultato;
}


/* versione ricorsiva */
ListaDiInteri MinEvenRic(ListaDiInteri Lista) {
  ListaDiInteri risultato = NULL;
  if (lista != NULL) {
    risultato = MinEvenRic(lista->next);
    if (lista->info % 2 == 0)
      if (risultato==NULL) risultato = lista;
      else if (risultato->info > lista->info) risultato = lista;
  }
  return risultato;
}



/* 
===========
Esercizio 7 
===========
Definire una procedura che, data una ListaDiInteri lista ed un
intero elem, inserisce elem dopo l'ultimo elemento di lista maggiore di elem.
Se lista non contiene alcun elemento maggiore di elem, la procedura lo
inserisce in ultima posizione.
*/

ListaDiInteri ultimoMaggiore(ListaDiInteri lista, int elem) {
  ListaDiInteri risultato = NULL;
  while (lista != NULL) {
    if (lista->info > elem) risultato = lista;
    lista = lista->next;
  }
  return risultato;
}

void procedura1(ListaDiInteri *lista, int elem) {
  ListaDiInteri aux;
  aux = ultimoMaggiore(*lista, elem);
  if (aux==NULL) InserisciInCoda(lista, elem);
  else InserisciInTesta(&(aux->next), elem);
}

/* La soluzione proposta scandisce due volte la lista
   nel caso questa non contenga elementi maggiori di elem   
   Una soluzione piu' efficiente e' la seguente  
*/

void procedura2(ListaDiInteri *lista, int elem) {
   ListaDiInteri posizione, curr, prec;
   if (*lista == NULL) InserisciInTesta(lista, elem);
   else {
      prec = *lista;
      curr = prec -> next;
      posizione = NULL;
      while (curr != NULL) {
	if (curr->info > elem) posizione = curr;
	prec = prec -> next;
	curr = curr -> next;
      }
      if (posizione == NULL) InserisciInTesta(&(prec->next), elem);
      else InserisciInTesta(&(posizione->next), elem);
     }
}

/* 
===========
Esercizio 8 
===========
Definire una procedura EliminaXElementi che elimini i primi x elementi 
da una lista di interi.
*/

/* versione iterativa */

void EliminaXElementi (ListaDiInteri *lista, int x) {
  while ((*lista != NULL) && x>0) {
    CancellaPrimo(lista);
    x--;
  }
}

/* versione ricorsiva */

void EliminaXElementiRic (ListaDiinteri *lista, int x) {
 if (x > 0) {
     CancellaPrimo(lista);
     EliminaXElementiRic(lista, x-1);
  }
}