/*
\file drop.c
  \authors Framba Luca & Amato Lorenzo Gaetano informatica (CDS Fisica) 2016/17
  \brief assegnamento 2: intestazione delle funzioni da implementare
 */

/* protezione inclusioni multiple */
#ifndef __DROP__H
#define __DROP__H

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "drop.h"
#include <stdbool.h>

/* ATTENZIONE: l'area di caduta e' rappresentata con una matrice di puntatori
   a righe e NON e' globale come era nel primo assegnamento */

/** tipo delle 4 adiacenze
    con cui stiamo lavorando (nessuna, croce, diagonale, entrambe) */
typedef enum {NONE, CROSS, DIAGONAL, BOTH} adj_t;

/** valori possibili per la matrice che rappresenta l'area di caduta, EMPTY contraddistingue un'area vuota, FULL un'area un cui si e' gia' sedimentata una
particella e OSTACLE rappresenta un'area occupata da un ostacolo. FULL ed OBSTACLE non sono attraversabili*/
#define EMPTY '.'
#define FULL '*'
#define OBSTACLE '@'

/** ogni ostacolo e' quadrato o rettangolare e definito dalle coordinate dell'estremo in alto a sinistra e in basso a destra all'interno della matrice che rappresenta l'area di caduta. s_i deve sempre essere minore o uguale di d_i e s_j mionre uguale di d_j */
typedef struct {
  unsigned s_i, s_j; /* coordinate dell'angolo in alto a sinistra */
  unsigned d_i, d_j; /* coordinate dell'angolo in basso a destra */
} obstacle_t;

/** Lista degli ostacoli, sempre ordinata in senso crescente. L'ordinamento
e' definito come segue:

L'ostacolo [(x1,y1),(t1,q1)] precede [(x2,y2),(t2,q2)] se vale che
se x1!= x2 e x1 < x2 oppure
se x1 == x2 e y1!= y2 e y1 < y2 oppure
se x1 == x2 e y1 == y2 e t1!= t2 e t1 < t2 oppure
se x1 == x2 e y1 == y2 e t1 == t2 e q1!= q2 e q1 < q2
*/
typedef struct list  {
  obstacle_t * pobj; /* puntatore all'ostacolo */
  struct list * next; /* puntatore al prossimo elemento della lista */
} lista_t;

/* prototipi di tutte le funzioni */

void init_matrix (char** mat, unsigned n, unsigned m);
void free_matrix (char*** pmat, unsigned n);
int step (int* next_i, int* next_j, adj_t ad, char** mat, int n, int m);
obstacle_t * string_to_obstacle (char * s);
char * obstacle_to_string (obstacle_t * po, char* s, int n);
int put_obstacle_in_matrix (obstacle_t * s,char ** mat, unsigned n, unsigned m);
lista_t * put_obstacle_in_list (obstacle_t* p,lista_t* l);
void free_list (lista_t ** plist);

/** (FORNITA DAI DOCENTI)
    alloca una nuova matrice che rappresenta l'area di caduta utilizzando
    la rappresentazione con array di puntatori a righe
    (senza inizializzarla)

   \param n numero di righe
   \param m numero di colonne

   \retval NULL se si e' verificato un errore (setta errno)
   \retval p il puntatore alla matrice allocata
*/
char** new_matrix (unsigned n, unsigned m);


/** (FORNITA DAI DOCENTI)
   stampa la matrice mat sul file "f" (gia' aperto) usando
   -- il carattere '.' (EMPTY) per le posizioni vuote
   -- il carattere '*' (FULL) per le posizioni piene
   -- il carattere '@' (OBJECT) per le posizioni occupate dagli ostacoli
(i caratteri utilizzati nelle macro che li definiscono)

   \param f il file in cui stampare (gia' aperto in scrittura)
   \param mat il puntatore alla matrice
   \param n numero di righe
   \param n numero di colonne
*/


void fprint_matrix (FILE * f, char ** a, unsigned n, unsigned m);


/** inizializza la matrice mat settando tutti i valori a EMPTY

   \param mat puntatore alla matrice
   \param n numero di righe
   \param m numero di colonne
*/
void init_matrix (char** mat, unsigned n, unsigned m){

    int i,j;

    if((mat == NULL) || (n == 0) || (m == 0)){ /* matrice vuota */
        printf("Matrice vuota.\n");

    }
    else{
        for(i=0;i<n;i++){ /* i scorre sulle righe */
            for(j=0;j<m;j++) /* j scorre sulle colonne */
                mat[i][j] = EMPTY; /* assegna ad ogni valore di riga e colonna il valore EMPTY */

        }
    }
    return;
}

/** libera la memoria occupata dalla matrice e mette a NULL il puntatore pmat

    \param pmat puntatore al puntatore alla matrice da liberare
    \param n numero di righe
 */
void free_matrix (char*** pmat, unsigned n){
    int i; /* variabile per muoversi nel ciclo for */
    char **s;
    s = *pmat; /* s diventa il puntatore alla matrice da liberare */

    for(i=0;i<n;i++)
        free(s[i]); /* dealloca la memoria di tutte le colonne della matrice */
    free(s); /* dealloca  la memoria dell'array di puntatori alle righe */
    *pmat = NULL; /* mette il puntatore alla matrice a NULL */
    return;
}

/** calcola la caduta della prossima particella restituendo le coordinate (i,j) del prossimo elemento dell'area da mettere a FULL

   \param next_i l'indirizzo della variabile dove scrivere il valore della coordinata i
   \param next_j l'indirizzo della variabile dove scrivere il valore della coordinata j
   \param ad tipo di adiacenza con cui stiamo lavorando (croce, diagonale o entrambe)
   \param mat puntatore alla matrice
   \param n numero di righe della matrice
   \param m numero di colonne della matrice

   \SPECIFICA
   il prossimo elemento da riempire viene calcolato simulando la caduta di una particella
   a partire dalla posizione P0 di coordinate ( 0, M/2 ),
   ad ogni passo, se mi trovo nella posizione Pi = (i,j) considero l'insieme U delle celle non ancora piene fra la tre celle
              (i+1,j-1) (i+1,j) (i+1,j-1)
   e scelgo in modo equiprobabile fra le celle in U, ad esempio nel caso in cui le tre celle contengano rispettivamente
              EMPTY EMPTY FULL
   U = { (i+1,j-1), (i+1,j) }
   e scelgo fra i due elementi di U con probabilità 1/2.

   La caduta della particella si arresta quando di verifica uno dei due seguenti casi:
   1) sono arrivato all'ultima riga (la N-1) (quindi mi sedimento sul fondo)
   2) U e' vuoto
   3) ho almeno una cella piena nell'intorno di (i,j) definito da dall'adiacenza "ad" ovvero
      a) nessuno (NONE): in questo caso mi fermo solo se (i+1,j), (i+1,j-1) e (i+1,j+1) sono gia' piene (U e' vuoto)
      b) croce (CROSS):
                (i-1,j)
     (i,j-1)     <i,j>    (i,j+1)
                (i+1,j)
      c) diagonale (DIAGONAL)
     (i-1,j-1)            (i-1,j+1)
                 <i,j>
     (i+1,j-1)            (i+1,j+1)
     d) croce e diagonale insieme (BOTH)
     (i-1,j-1)   (i-1,j)        (i-1,j+1)
      (i,j-1)     <i,j>          (i,j+1)
     (i+1,j-1)   (i+1,j)        (i+1,j+1)

   In tutti i casi --> restituisco in *next_i
   il valore di i e in *next_j il valore di j

   \retval 0 se le coordinate sono state calcolate correttamente
   \retval -1 se il punto di caduta iniziale P0
    al centro della prima riga è già FULL
    in questo caso non viene modificato il valore di *next_i *next_j

*/

int step (int * next_i, int * next_j, adj_t ad, char ** mat, int n, int m){
  /* i e j servono per muoversi all'interno della variabile e p assumerà un valore casuale tra 0 e 2 per scegliere in modo pseudocasuale il
  prossimo passo */
  int i=0,j,p;
  /* j diventa la parte intera di m/2 in caso di m dispari, avendolo definito come int è un passaggio superfluo ma rassicurante */
  j = (int) m/2;

  bool check = true; /* variabile che controlla se la particella sedimenta */

  /* la prima posizione della matrice è occupata oppure la matrice ha dimensioni sulle quali applicare la funzione ritorna errore */
  if((mat[i][j] != EMPTY) || (m <= 1) || (n <= 1))
    return -1;


  switch(ad){ /* controlla il tipo di adiacenza */
    case BOTH:{ /* adiacenza BOTH */
    while(check){

        /* condizioni che fan sedimentare la particella */

        if(i == n-1) /* la particella è sul fondo */
            {check = false; *next_i = i; *next_j = j;}

        else if(i == 0){ /* la particella è nella prima riga */
            /* la particella non sedimenta nella posizione attuale quindi prosegue */
            if( (mat[1][j-1] == EMPTY)&&(mat[1][j]== EMPTY)&&(mat[1][j+1] == EMPTY) ){
                i++;
                p = my_rand()%3;
                switch(p){
                    case 0: j--; break;/* la particella prosegue a sinistra */
                    case 1:; break; /* la particella prosegue dritta */
                    case 2: j++; break;/* la particella prosegue a destra */
                }
            }
            /* la particella sedimenta nella posizione attuale */
            else {check = false; *next_i = i; *next_j = j;}
        }

        /* la particella è sul bordo sinistro e una delle posizioni attorno alla particella è FULL o OBSTACLE la particella sedimenta */
        else if( (j == 0) &&
        ( (mat[i-1][j] != EMPTY)||(mat[i-1][j+1] != EMPTY)||(mat[i][j+1] != EMPTY)||(mat[i+1][j] != EMPTY)||(mat[i+1][j+1] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella è sul bordo destro e una delle posizioni attorno alla particella è FULL o OBSTACLE la particella sedimenta */
        else if( (j == (m-1)) &&
        ( (mat[i-1][j] != EMPTY)||(mat[i-1][j-1] != EMPTY)||(mat[i][j-1] != EMPTY)||(mat[i+1][j] != EMPTY)||(mat[i+1][j-1] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella non è lungo i bordi e una delle posizioni attorno alla particella è FULL o OBSTACLE la particella sedimenta */
        else if( (mat[i-1][j-1] != EMPTY)||(mat[i-1][j] != EMPTY)||(mat[i-1][j+1] != EMPTY)||(mat[i][j-1] != EMPTY)||(mat[i][j+1] != EMPTY)||
        (mat[i+1][j-1] != EMPTY)||(mat[i+1][j] != EMPTY)||(mat[i+1][j+1] != EMPTY) )
            {check = false; *next_i = i; *next_j = j;}

        else{ /* la particella non sedimenta nella posizione attuale e quindi procede */
            i++;
            if(j == 0){ /* la particella è sul bordo sinistro */
                p = my_rand()%2;
                switch(p){
                    case 0:; break; /* la particella prosegue in linea retta */
                    case 1: j++; break; /* la particella prosegue a destra */
                }
            }
            else if(j == (m-1)){ /* la particella è sul bordo destro */
                p = my_rand()%2;
                switch(p){
                    case 0:; break; /* la particella prosegue in linea retta */
                    case 1: j--;  break;/* la particella prosegue a sinistra */
                }

            }
            else{ /* la particella non è lungo i bordi e procede in una delle 3 posizioni sottostanti */
                p = my_rand()%3;
                switch(p){
                    case 0:; break; /* la particella prosegue in linea retta */
                    case 1: j--; break; /* la particella prosegue a sinistra */
                    case 2: j++; break; /* la particella prosegue a destra */
                }
            }
        } /* else */
    }  /* while */
    }
    case DIAGONAL:{
    while(check){
        /* condizioni che fan sedimentare la particella */
        if(i == n-1) /* la particella è sul fondo */
            {check = false; *next_i = i; *next_j = j;}

        else if(i == 0){ /* la particella è nella prima riga */
            /* la particella non sedimenta nella posizione attuale quindi prosegue */
            if( (mat[1][j-1] == EMPTY)&&(mat[1][j+1] == EMPTY) ){
                i++;
                if(mat[1][j] != EMPTY){ /* la particella non può proseguire dritta */
                    p = my_rand()%2;
                    switch(p){
                        case 0: j--; break;/* la particella prosegue a sinistra */
                        case 1: j++; break;/* la particella prosegue a destra */
                    }
                }
                else{ /* la particella può proseguire in tutte le direzioni */
                    p = my_rand()%3;
                    switch(p){
                        case 0: j--; break;/* la particella prosegue a sinistra */
                        case 1: break;
                        case 2: j++; break;/* la particella prosegue a destra */
                    }
                }
            }
            /* la particella sedimenta nella posizione attuale */
            else {check = false; *next_i = i; *next_j = j;}
        }


        /* la particella è sul bordo sinistro, una delle posizioni diagonali alla particella è occupata e la particella sedimenta */
        else if( (j == 0) &&
        ( (mat[i-1][j+1] != EMPTY)||(mat[i+1][j+1] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella è sul bordo destro, una delle posizioni diagonali alla particella è occupata e la particella sedimenta */
        else if( (j == (m-1)) &&
        ( (mat[i-1][j-1] != EMPTY)||(mat[i+1][j-1] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella non è lungo i bordi, una delle posizioni attorno alla particella è occupata e la particella sedimenta */
        else if( (mat[i-1][j-1] != EMPTY)||(mat[i-1][j+1] != EMPTY)||(mat[i+1][j-1] != EMPTY)||(mat[i+1][j+1] != EMPTY) )
            {check = false; *next_i = i; *next_j = j;}

        else{ /* la particella non sedimenta nella posizione attuale e quindi procede */
            i++;
            if(j == 0){ /* la particella è sul bordo sinistro */
                if( mat[i][j] != EMPTY ) /*la posizione sottostante la particella è occupata */
                    j++; /* la particella può solo proseguire a destra */
                else{ /* la particella può proseguire in entrambe le direzioni */
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break; /* la particella prosegue in linea retta */
                        case 1: j++; break; /* la particella prosegue a destra */
                    }
                }
            }
            else if(j == (m-1)){ /* la particella è sul bordo destro */
                if( mat[i][j] != EMPTY) /*la posizione sottostante la particella è occupata */
                    j--; /* la particella può solo proseguire a sinistra */
                else{ /* la particella può proseguire in entrambe le direzioni */
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break; /* la particella prosegue in linea retta */
                        case 1: j--; break; /* la particella prosegue a sinistra */
                    }
                }
            }
            else if( mat[i][j] != EMPTY ){ /* la particella non è lungo i bordi e la posizione sotto la particella è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j++; break;/* la particella prosegue a destra */
                    case 1: j--; break;/* la particella prosegue a sinistra */
                }
            }
            else{ /* la particella non è lungo i bordi, la posizione sottostante non è occupata e procede in una delle 3 posizioni                sottostanti in modo pseudocasuale */
                p = my_rand()%3;
                switch(p){
                    case 0:; break;/* la particella prosegue in linea retta */
                    case 1: j--; break;/* la particella prosegue a sinistra */
                    case 2: j++; break;/* la particella prosegue a destra */
                }
            }
        }/* else */
    } /* while */
    break;}


    case CROSS:{ /* adiacenza CROSS */
    while(check){
        /* condizioni che fanno sedimentare la particella */
        if(i == (n-1)) /* la particella è sul fondo */
            {check = false; *next_i = i; *next_j = j;}

        else if(i == 0){ /* la particella è nella prima riga */
            /* la particella non sedimenta nella posizione attuale quindi prosegue */
            if( mat[1][j] == EMPTY ){
                i++;
                if((mat[1][j-1] != EMPTY) && (mat[1][j+1] != EMPTY)) /* la particella non può proseguire lateralmente */
                    {j = j;} /* la particella prosegue dritta */
                else if(mat[1][j-1] != EMPTY){ /* la particella non può proseguire a sinistra */
                    p = my_rand()%2;
                    switch(p){
                        case 0: break;/* la particella prosegue dritta */
                        case 1: j++; break;/* la particella prosegue a destra */
                    }
                }
                else if(mat[1][j+1] != EMPTY){ /* la particella non può proseguire a destra */
                    p = my_rand()%2;
                    switch(p){
                        case 0: break;/* la particella prosegue dritta */
                        case 1: j--; break;/* la particella prosegue a sinistra */
                    }
                }
                else{ /* la particella può proseguire in tutte le direzioni */
                    p = my_rand()%3;
                    switch(p){
                        case 0: j--; break;/* la particella prosegue a sinistra */
                        case 1: break;
                        case 2: j++; break;/* la particella prosegue a destra */
                    }
                }
            }
            /* la particella sedimenta nella posizione attuale */
            else {check = false; *next_i = i; *next_j = j;}
        }

        /* la particella è sul bordo sinistro e una delle posizioni attorno alla particella è occupata e la particella sedimenta */
        else if( (j == 0) &&
        ( (mat[i-1][j] != EMPTY)||(mat[i][j+1] != EMPTY)||(mat[i+1][j] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella è sul bordo destro e una delle posizioni attorno alla particella è occupata e la particella sedimenta */
        else if( (j == (m-1)) &&
        ( (mat[i-1][j] != EMPTY)||(mat[i][j-1] != EMPTY)||(mat[i+1][j] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella non è lungo i bordi e una delle posizioni attorno alla particella è occupata e la particella sedimenta */
        else if( (mat[i-1][j] != EMPTY)||(mat[i][j-1] != EMPTY)||(mat[i][j+1] != EMPTY)||
        (mat[i+1][j] != EMPTY) )
            {check = false; *next_i = i; *next_j = j;}

        else{ /* la particella non sedimenta nella posizione attuale e quindi procede */
            i++;
            if(j == 0){ /* la particella è sul bordo sinistro */
                if( mat[i][j+1] != EMPTY ) /*la posizione a destra della particella è occupata */
                    {} /* la particella può solo proseguire in linea retta */
                else{
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break;/* la particella prosegue in linea retta */
                        case 1: j++; break;/* la particella prosegue a destra */
                    }
                }
            }
            else if(j == (m-1)){ /* la particella è sul bordo destro */
                if( mat[i][j-1] != EMPTY ) /* la posizione a sinistra della particella è occupata */
                    {} /* la particella può solo proseguire in linea retta */
                else{
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break; /* la particella prosegue in linea retta */
                        case 1: j--; break; /* la particella prosegue a destra */
                    }
                }
            }
            else if( (mat[i][j-1] != EMPTY) && (mat[i][j+1] != EMPTY) ) /* la posizione laterali sotto la particella sono occupate */
                {} /* la particella può solo proseguire in linea retta */
            else if( mat[i][j-1] != EMPTY ){ /* solo la posizione laterale sinistra è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j++; break; /* la particella prosegue a destra */
                    case 1: ; break; /* la particella prosegue in linea retta */
                }
            }
            else if( mat[i][j+1] != EMPTY ){ /* solo la posizione laterale destra è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j--; break; /* la particella prosegue a sinistra */
                    case 1: ; break; /* la particella prosegue in linea retta */
                }
            }
            else{ /* la particella non è lungo i bordi, la posizioni laterali sottostanti non sono occupate quindi la particella procede               in una delle 3 posizioni sottostanti in modo pseudocasuale */
                p = my_rand()%3;
                switch(p){
                    case 0:; break; /* la particella prosegue in linea retta */
                    case 1: j--; break; /* la particella prosegue a sinistra */
                    case 2: j++; break; /* la particella prosegue a destra */
                }
            }
        } /* else */
    } /* while */
    break;}

    case NONE:{ /* adiacenza NONE */
    while(check){
        /* condizioni che fan sedimentare la particella */
        if(i == (n-1)) /* la particella è sul fondo */
            {check = false; *next_i = i; *next_j = j;}

        /* la particella è sul bordo sinistro, le posizioni sotto la particella sono occupate e la particella sedimenta */
        else if( (j == 0) && ( (mat[i+1][j+1] != EMPTY)||(mat[i+1][j] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella è sul bordo destro, le posizioni sotto la particella sono occupate e la particella sedimenta */
        else if( (j == (m-1)) && ( (mat[i+1][j] != EMPTY)&&(mat[i+1][j-1] != EMPTY) ) )
            {check = false; *next_i = i; *next_j = j;}

        /* la particella non è lungo i bordi, le posizioni sotto alla particella sono occupate e la particella sedimenta */
        else if( (mat[i+1][j] != EMPTY)&&(mat[i+1][j-1] != EMPTY)&&(mat[i+1][j+1] != EMPTY) )
            {check = false; *next_i = i; *next_j = j;}

        else{ /* la particella non sedimenta nella posizione attuale e quindi procede */
            i++;
            if(j == 0){ /* la particella è sul bordo sinistro */
                if( mat[i][j+1] != EMPTY ) /*la posizione laterale destra è occupata */
                    {j=j;} /* la particella può solo proseguire in linea retta */
                else if (mat[i][j] != EMPTY) /* la posizione sotto la particella è occupata */
                    j++; /* la particella può proseguire solo a destra */
                else{ /* nessuna delle posizioni sottostanti è occupata */
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break; /* la particella prosegue in linea retta */
                        case 1: j++;break;  /* la particella prosegue a destra */
                    }
                }
            }
            else if(j == (m-1)){ /* la particella è sul bordo destro */
                if( mat[i][j-1] != EMPTY ) /* la posizione laterale sinistra è occupata */
                    {} /* la particella può solo proseguire in linea retta */
                else if (mat[i][j] != EMPTY) /* la posizione sotto la particella è occupata */
                    j--; /* la particella può proseguire solo a sinistra */
                else{ /* nessuna delle posizioni sottostanti è occupata */
                    p = my_rand()%2;
                    switch(p){
                        case 0:; break;  /* la particella prosegue in linea retta */
                        case 1: j--; break; /* la particella prosegue a sinistra */
                    }
                }
            }
            else if( (mat[i][j-1] != EMPTY) && (mat[i][j+1] != EMPTY) ) /* la posizione laterali sotto la particella sono occupate */
                {} /* la particella può solo proseguire in linea retta */

            /* solo la posizione laterale sinistra e quella sottostante sono occupate */
            else if( (mat[i][j-1] != EMPTY) && (mat[i][j] != EMPTY) )
                j++; /* la particella può proseguire solo a destra */

            /* solo la posizione laterale destra e quella sottostante sono occupate */
            else if( (mat[i][j+1] != EMPTY) && (mat[i][j] != EMPTY) )
                j--; /* la particella può proseguire solo a sinistra */

            else if( mat[i][j+1] != EMPTY ){ /* solo la posizione laterale destra è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j--; break; /* la particella prosegue a sinistra */
                    case 1: ; break; /* la particella prosegue in linea retta */
                }
            }

            else if( mat[i][j] != EMPTY ){ /* solo la posizione sottostante è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j--; break; /* la particella prosegue a sinistra */
                    case 1: j++; break; /* la particella prosegue a destra */
                }
            }

            else if( mat[i][j-1] != EMPTY ){ /* solo la posizione laterale sinistra è occupata */
                p = my_rand()%2;
                switch(p){
                    case 0: j++; break; /* la particella prosegue a destra */
                    case 1: ; break; /* la particella prosegue in linea retta */
                }
            }
            else{ /* la particella non è lungo i bordi, la posizioni laterali sottostanti non sono occupate quindi la particella procede               in una delle 3 posizioni sottostanti in modo pseudocasuale */
                p = my_rand()%3;
                switch(p){
                    case 0:; break; /* la particella prosegue in linea retta */
                    case 1: j--; break; /* la particella prosegue a sinistra */
                    case 2: j++; break; /* la particella prosegue a destra */
                }
            }
        } /* else */
    }  /* while */
    break;} /* case */

  }  /* switch */
return 0;
}



/** legge la rappresentazione di un ostacolo come stringa di 4 estremi interi
    (es. "0 0 3 4" rapresenta i due estremi (0,0) superiore sinistro e (3,4) inferiore destro)
    e crea sullo heap la corrispondente struttura obstacle_t
    controllando anche che le due coordinate siano consistenti ovvero detta (si,sj) la coordinata in alto a sinistra e (di,dj)
    quella in basso a destra deve essere vero che
    si <= di && sj <= dj

    \param s la stringa contenente gli estremi (es. "0 0 3 4")

    \retval p il puntatore alla nuova struttura obstacle_t creata (se la conversione ha avuto successo)
    \retval NULL altrimenti
*/



obstacle_t * string_to_obstacle (char * s){
    int i = 0;  /* variabile per spostarsi all'interno della stringa */
    obstacle_t *p;  /*creo il puntatore all'ostacolo e l'ostacolo */

    p = calloc(1,sizeof(obstacle_t)); /* alloco l'ostacolo in memoria con i valori inizializzati a 0 */

        /* ciclo che si ferma quando il valore della stringa è ' ', cioè cambia la coordinata */
    while(s[i] != ' '){

        /** assegno a s_i il valore della stringa prima dello spazio facendo sì che s_i contenga il valore del precedente (s_i*10), così          viene spostato nella cifra successiva e sommandogli il valore attuale della stringa convertito da char a int (questo procedimento           viene effettuato su tutte le coordinate) */
        p -> s_i = (p -> s_i)*10 + ((unsigned) s[i] -'0');
        i++; /* avanza di posizione nella stringa */
    }

    i++; /* avanza di posizione nella stringa per superare il primo ' ' */
    while(s[i] != ' '){
        p -> s_j = (p -> s_j)*10 + ((unsigned) s[i] -'0'); /* assegno a s_j il secondo valore della stringa prima dello spazio */
        i++;
    }

    i++; /* avanza di posizione nella stringa per superare il secondo ' ' */
    while(s[i] != ' '){
        p -> d_i = (p -> d_i)*10 + ((unsigned) s[i] -'0'); /* assegno a s_i il terzo valore della stringa prima dello spazio */
        i++;
    }

    i++; /* avanza di posizione nella stringa per superare il terzo ' ' e il ciclo che segue avanza fino al carattere terminatore della stringa*/

    while(s[i] != '\0'){
        p -> d_j = (p -> d_j)*10 + ((unsigned) s[i] -'0'); /* assegno a s_i il qarto valore della stringa prima del carattere terminatore */
        i++;
    }

    /* se le coordinate inserite sono insensate ritorna NULL */
    if ( (p->s_i > p->d_i) || (p->s_j > p->d_j) )
        return NULL;
    /* altrimenti ritorna il puntatore all'ostacolo creato */
    return p;
}





/** crea la rappresentazione di un ostacolo come stringa con i 4 estremi (es. "0 0 3 4" rapresenta i due estremi (0,0) superiore sinistro e (3,4) inferiore destro)
    \param po puntatore all'ostacolo
    \param s puntatore all'array di caratteri dove scrivere la stringa risultato della conversione
    \param n lunghezza dell'array s

    \retval s il puntatore al primo carattere della stringa (se la conversione ha avuto successo)
    \retval NULL altrimenti
*/


char * obstacle_to_string (obstacle_t * po, char * s, int n){

    /* definizione variabili */
    unsigned i=0,j=0,prec=0,count=0,hold,check, s_i, s_j, d_i, d_j;

    if(n <= 8)  /* se l'array non è abbastanza lungo ritorna NULL */
        return NULL;

    /** variabili contenenti i valori dell'ostacolo per non modificare i valori delle coordinate effettive durante la funzione */
    s_i = po->s_i;
    s_j = po->s_j;
    d_i = po->d_i;
    d_j = po->d_j;


    /* i procedimenti nello specifico vengono spiegati solo per il primo valore */
    if(s_i == 0){ /* nel caso s_i sia 0 viene attribuito al primo valore della stringa 0 */
        s[j] = '0';
        j++; /* j tiene conto dell'avanzamento nella scrittura della stringa */
    }


    while( (s_i/1) >= 1 ){ /* ciclo che conta le cifre di s_i in count, quando s_i = 0 viene interrotto */
        count++;
        /* per ogni cifra si avanza nella stringa di una posizione e successivamente la stringa verrà riempita con i char corrispondenti */
        j++;

        /* s_i perde una cifra ad ogni ciclo fino ad arrivare a 0 */
        s_i = (int) (s_i/10);
    }

    /* s_i torna al suo valore originale */
    s_i = po->s_i;

    /* prec contiene il valore 0 per s_i ma successivamente conterrà la posizione sucessiva all'ultimo ' ' riempito
    il ciclo fa andare i dall'ultima posizione riempita e avanza per il numero di cifre di s_i */
    for(i=prec;i<j;i++){
        count--;

        /* hold contiene il valore della cifra corrente di s_i, in quanto divide il valore di s_i per 10^count, dove count è il numero di          cifre rimanenti -1 */
        hold = (int) (s_i/(pow(10,count)));

        /* il valore precedentemente calcolato di hold viene convertito in char da int e inserito nella posizione corrente della            stringa */
        s[i] = (char) hold +'0';

        /* s_i diventa il resto della divisione tra se stesso e 10^(n° delle sue cifre -1), quindi è come se perdesse la sua prima cifra,             nel caso in cui questa cifr fosse 0 s_i non cambia */
        s_i = (s_i%( (int) ((pow(10,count))) ));

    }

    /* alla posizione j viene assegnato ' ' */
    s[j] = ' ';

    /* j aumenta */
    j++;

    if(s_j == 0){
        s[j] = '0';
        j++;
    }
    /* prec indica la posizione successiva all'ultimo ' ' riempito */
    prec = j;

    while( (s_j/1) >= 1 ){ /*ciclo che conta le cifre di s_j in count */
        count++;
        j++;
        s_j = s_j/10;
    }
    s_j = po->s_j;
    for(i=prec;i<j;i++){
        count--;
        hold = (int) (s_j/(pow(10,count)));

        s[i] = (char) hold +'0' ;

        s_j = (s_j%( (int) ((pow(10,count))) ));

    }
    s[j] = ' ';
    j++;


    if(d_i == 0){
        s[j] = '0';
        j++;
    }

    prec = j;

    while( (d_i/1) >= 1 ){ /*ciclo che conta le cifre di d_i in count */
        count++;
        j++;
        d_i = d_i/10;
    }
    d_i = po->d_i;
    for(i=prec;i<j;i++){
        count--;
        hold = (int) (d_i/(pow(10,count)));

        s[i] = (char) hold +'0' ;

        d_i = (d_i%( (int) ((pow(10,count))) ));

    }
    s[j] = ' ';
    j++;


    if(d_j == 0){
        s[j] = '0';
        j++;
    }
    prec = j;

    while( (d_j/1) >= 1 ){ /*ciclo che conta le cifre di d_j in count */
        count++;
        j++;
        d_j = d_j/10;
    }
    d_j = po->d_j;
    for(i=prec;i<j;i++){
        count--;
        hold = (int) (d_j/(pow(10,count)));

        s[i] = (char) hold +'0' ;

        d_j = (d_j%( (int) ((pow(10,count))) ));

    }

    /* la posizione seguente a quella contenente l'ultima cifra di d_j assume quella del carattere terminatore della stringa */
    s[j] = '\0';

    /* ritorna il puntatore alla stringa */
    return s;
}



/** inserisce nella matrice di caduta l'ostacolo s marcando gli elementi corrispondenti all'ostacolo con OBSTACLE
  \param s puntatore all'ostacolo da inserire
   \param mat puntatore alla matrice
   \param n numero di righe
   \param m numero di colonne

  \retval 0 se tutto è andato bene
  \retval -1 se l'ostacolo è incompatibile con l'area di caduta (es. le coordinate sono maggiori del numero di righe/colonne)
*/
int put_obstacle_in_matrix (obstacle_t * s,char ** mat, unsigned n, unsigned m){

    int i,j; /*variabili per muoversi all'interno della matrice */

    if( ( (*s).s_i > (*s).d_i ) || ( s->s_j > s->d_j ) ) /* controllo che le coordinate abbiano senso */
        return -1;

    if( (s->s_i >= n) || (s->d_i >= n) || (s->s_j >= m) || (s->d_j >= m) ) /* le coordinate sono troppo grandi per la matrice */
        return -1;

    for(i = (s->s_i); i <= (s->d_i); i++)       /* i parte da s_i e termina in d_i */
        for(j = (s->s_j); j <= (s->d_j); j++)   /* j parte da s_j e finisce in d_j */
            mat[i][j] = OBSTACLE; /* assegna al valore corrispondente della matrice il valore OBSTACLE */
    return 0;

}

/** inserisce un ostacolo nella lista mantenendo l'ordinamento crescente
  \param p l'ostacolo da inserire (viene inserito direttamente senza effettuare copie)
  \param l il puntatore alla testa della lista

  \retval l il puntatore alla nuova testa della lista (dopo l'inserimento)

*/
lista_t * put_obstacle_in_list (obstacle_t* p,lista_t * l){

    lista_t *elem, *succ, *prec; /* creo il puntatore al nuovo elemento della lista e due per scorrere la lista  */

    elem = malloc(sizeof(lista_t)); /* creo il nuovo elemento della lista */

    bool check = true; /* variabile booleana messa a FALSE quando l'ostacolo trova il suo posto nella lista */

    if(l == NULL){ /* lista vuota */
        elem->next = NULL; /* metto il puntatore del primo elemento della lista a NULL */
        l = elem;   /* metto l come puntatore al primo elemento della lista */
        elem -> pobj = p; /* assegno al nuovo elemento l'ostacolo dato in input */
        return l; /* chiudo la funzione */
    }

    elem -> pobj = p; /* assegno al nuovo elemento l'ostacolo dato in input */
    succ = l;  /* s punta alla testa della lista */
    prec = succ;

    /* l'elemento nuovo va disposto in testa alla lista non vuota */
    if( ((p->s_i) < (succ->pobj->s_i)) || ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) < (succ->pobj->s_j)) ) ||
    ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) < (succ->pobj->d_i)) ) ||
    ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
    ((p->d_j) < (succ->pobj->d_j)) ) ){

    check = false; /* salta il while */
    l = elem; /* l punta al nuovo elemento */
    elem->next = succ; /* il nuovo elemento punta al successivo */
    }


    while(check){

        if((succ->next) == NULL){ /* fine lista */

            /* l'elemento è già presente nella lista ed è l'ultimo */
            if( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
            ((p->d_j) == (succ->pobj->d_j)) ){
            return l; /* chiudo la funzione */
            }

            /* l'elemento nuovo va disposto prima dell'ultimo */
            if( ((p->s_i) < (succ->pobj->s_i)) || ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) < (succ->pobj->s_j)) ) ||
            ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) < (succ->pobj->d_i)) ) ||
            ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
            ((p->d_j) < (succ->pobj->d_j)) ) ){

                prec->next = elem;
                elem->next = succ;
                return l;
            }
            else{
            succ->next = elem;  /* l'ultimo elemento della lista punta a quello creato */
            elem->next = NULL; /* pongo il nuovo elemento come ultimo elemento della lista */
            return l;
            }
        }

        /* l'elemento è già presente nella lista */
        if( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
        ((p->d_j) == (succ->pobj->d_j)) ){
        return l; /* chiudo la funzione */
        }

        /* il nuovo elemento va disposto prima di quello attuale */
        if( ((p->s_i) < (succ->pobj->s_i)) || ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) < (succ->pobj->s_j)) ) ||
        ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) < (succ->pobj->d_i)) ) ||
        ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
        ((p->d_j) < (succ->pobj->d_j)) ) ){
            check = false;
            prec->next = elem; /* l'elemento precedente punta a quello nuovo */
            elem->next = succ; /* l'elemento nuovo punta a quello successivo */

        }
        /* il nuovo elemento non va disposto prima di quello attuale */
        else if( ((p->s_i) > (succ->pobj->s_i)) || ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) > (succ->pobj->s_j)) ) ||
        ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) > (succ->pobj->d_i)) ) ||
        ( ((p->s_i) == (succ->pobj->s_i)) && ((p->s_j) == (succ->pobj->s_j)) && ((p->d_i) == (succ->pobj->d_i)) &&
        ((p->d_j) > (succ->pobj->d_j)) ) ){

        /* prec e succ avanzano nella lista facendo sempre si che prec punti sempre all'elemento precedente a succ e succ a quello successivo*/
        prec = succ;
        succ = succ->next;
        }






    }
    return l;
}


/** libera la memoria occupata dalla lista mettendo a NULL il puntatore alla lista
   \param plist puntatore al puntatore della lista da deallocare
*/

void free_list (lista_t ** plist){
    lista_t *f;
    f = *plist; /* f punta alla testa della lista */

    /* se siamo all'ultimo elemento della lista */
    if(f->next == NULL){
        free(f->pobj); /* libera la memoria dell'oggetto a cui punta l'oggetto pobj della lista */
        free(f); /* libera la memoria dell'ultimo elemento della lista */
        *plist = NULL; /* mette il puntatore all'ultimo elemento della lista (ormai deallocato) a NULL */
        return;
    }

    /* se l'elemento della lista esaminato non è l'ultimo procede */
    free_list(&(f->next)); /* richiama la funzione sul prossimo elemento della lista */
    free(f->pobj); /* libera la memoria dell'oggetto a cui punta l'oggetto pobj della lista */
    free(f); /* libera la memoria dell' elemento attuale della lista */
    *plist = NULL; /* mette il puntatore all'elemento attuale della lista a NULL */
    return;
}


#endif