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

typedef unsigned short int boolean;
#define TRUE 1
#define FALSE 0

struct list{
    float value;
    struct list * next;
};

struct list_times{
    float value;
    int times;
    struct list_times * next;
};

boolean isequal(float a, float b);


void init(struct list ** ptr);
void visit(struct list * ptr);
boolean suf_insert(struct list **ptr, float value);
boolean pre_insert(struct list **ptrptr, float value);

void init_times(struct list_times ** ptr);
void visit_times(struct list_times * ptr);
boolean search_times(struct list ** ptr,  float *V, int n, struct list_times ** new );
boolean suf_insert_times(struct list_times ** ptrptr, float value, int times);
boolean pre_insert_times(struct list_times ** ptrptr, float value, int times);

int main() {

    char answer; float value; struct list * ptr; struct list_times * new; float * V; int n;

    printf("Programma che riceve in input i valori (float) di una lista e di un array, e li inserisce in una nuova lista nella quale verrà indicata la loro occorrenza nel vettore"
           "Durante l'inserimento dei valori nella nuova lista l'altra sarà cancellata\n");

    init(&ptr);
    init_times(&new);


    do{
       printf("Inserisci un valore della lista:\n");
        scanf("%f", &value);

        suf_insert(&ptr,value);

        printf("Se vuoi inserire un altro valore digita ""y""\n");
        scanf("%s", &answer);

    } while(answer=='y'||answer=='Y');


    do {
        printf("Inserisci la dimensione dell'array:\n");
        scanf("%d", &n);

        if (n <= 0)
            printf("La dimensine deve essere maggiore di 0!");

    } while(n<=0);

    if((V=(float *)malloc(sizeof(float)*n))) {

        for (int i = 0; i < n; i++) {
            printf("Inserisci un valore dell'array:\n");
            scanf("%f", &V[i]);
        }

        printf("Lista inserita:\n");
        visit(ptr);

        printf("\nVettore inserito:\n");
        for(int i=0;i<n;i++)
            printf("Valore %d: " "%f\n",i+1,V[i]);


        printf("Nuova lista:\n");
        search_times(&ptr, V, n, &new);
        visit_times(new);


    }//if
    else
        printf("Non è stato possibile allocare lo spazio di memoria per l'array\n");

    return 0;
}

boolean search_times(struct list ** ptr, float *V, int n, struct list_times ** new ){

struct list * tmp_ptr;

    if( V!=NULL && n>=0 ){

        while((*ptr)!=NULL) {

            int times=0;

            for (int i = 0; i < n; i++) {
                if (isequal((*ptr)->value, V[i]))
                    times++;
            }

             if((suf_insert_times(new, (*ptr)->value, times))==FALSE)
                 return FALSE;

        tmp_ptr=*ptr;
        ptr=&((*ptr)->next);
        free(tmp_ptr);
        }
return TRUE;
    }

else
    return FALSE;

}


boolean suf_insert_times(struct list_times ** ptrptr, float value, int times)
{
    while( *ptrptr != NULL )
        ptrptr = &((*ptrptr)->next);
    if ( pre_insert_times(ptrptr,value,times) )
        return TRUE;
    else
        return FALSE;
}

boolean pre_insert_times(struct list_times ** ptrptr, float value, int times){

struct list_times * tmp_new;
    tmp_new = (struct list_times *)malloc(sizeof(struct list_times));
    if(tmp_new!=NULL) {
        tmp_new->value = value;
        tmp_new->times=times;
        tmp_new->next = *ptrptr;
        *ptrptr = tmp_new;
        return TRUE;
    }
    else
        return FALSE;

}

void init_times(struct list_times ** ptr)
{
    *ptr = NULL;
}

void init(struct list ** ptr)
{
    *ptr = NULL;
}

boolean pre_insert(struct list **ptrptr, float value)
{
    struct list * tmp_ptr;
    tmp_ptr = (struct list *)malloc(sizeof(struct list));
    if ( tmp_ptr != NULL ) {
        tmp_ptr->value = value;
        tmp_ptr->next = *ptrptr;
        *ptrptr = tmp_ptr;
        return TRUE;
    }
    else
        return FALSE;

}

boolean suf_insert(struct list **ptrptr, float value)
{
    while( *ptrptr != NULL )
        ptrptr = &((*ptrptr)->next);
    if ( pre_insert(ptrptr,value) )
        return TRUE;
    else
        return FALSE;
}

void visit(struct list * ptr)
{

    while ( ptr != NULL ) {
        printf("%f ", ptr->value);
        ptr = ptr->next;
    }
}

void visit_times(struct list_times * ptr)
{

    while ( ptr != NULL ) {
        printf("%f ", ptr->value);
        printf("%d ", ptr->times);
        ptr = ptr->next;
    }
}

boolean isequal(float a, float b) {
    float diff, max;
    diff = fabs(a-b);
    a = fabs(a);
    b = fabs(b);
    max = a > b ? a : b;
    if ( diff < FLT_EPSILON*max) return TRUE;
    else return FALSE;
}