/****************************************************************************/
/*                                LIBRARIES                                 */
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/****************************************************************************/
/*                                 MACRO                                    */
/****************************************************************************/
#define COMPARE(a,b) ( ( strcmp((char *)a , (char *)b) ) > 0 )

/****************************************************************************/
/*                           FORWARD DECLARATIONS                           */
/****************************************************************************/
void merge(void **s1,void **s2, int dim1,int dim2, int *contatore);
void mergesort(void **v,int dim, int *contatore);

/****************************************************************************/
/*                                   MAIN                                   */
/****************************************************************************/
int main(){
    char *buff,                   /* n buffer di 255 caratteri              */
    **sp;                         /* puntatore alle stringhe                */
    int n,                        /* numero di stringhe del file            */
        m,                        /* indica le posizioni stringhe in buff   */
        i,j,                      /* variabili di scorrimento               */
        contatore_1 = 0,          /* contatore "coppie inversione" n^2      */
        contatore_2 = 0;          /* contatore "coppie inversione" n log n  */
    FILE *f;                      /* puntatore a file                       */
   
    /* === LETTURA DA FILE ================================================ */
    f = fopen("input.txt","rt");
    fscanf(f,"%d",&n);
    buff = (char *)  malloc (n*255*sizeof(char));
    sp   = (char **) malloc (n*sizeof(char));
    m=0;
    i=0;
    /* legge una riga e la memorizza nel buffer buff[m] */
    while ( fscanf(f,"%s",&buff[m])!=EOF ){
        sp[i] = &buff[m];      /* s[i] punta alla parola i                  */
        m += strlen(sp[i])+1;  /* m indica la posizione lenght[parola(i)]+1 */
        i++;
    }
    fclose(f);
    /* =========================================== FINE LETTURA DA FILE === */
   
    printf("Parole nell'ordine di lettura:\n");
    for(m=0,i=0;i<n;i++){
        printf("%s ",&buff[m]); /* printf("%s ",sp[i]); */
               m+=strlen(&buff[m])+1;
    }printf("\n");

    /* Calcolo "coppie inversione" con n^2 confronti (n*(n-1)/2) */
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(COMPARE(sp[i],sp[j]))
                contatore_1++;

    /* Calcolo "coppie inversione" n log n confronti */
    mergesort(sp,n,&contatore_2);

    printf("Parole in ordine lessicografico:\n");
    for(i=0;i<n;i++)
        printf("%s ",sp[i]);
    printf("\n");

    printf("numero di coppie inversione n^2     = %d\n",contatore_1);
    printf("numero di coppie inversione n log n = %d\n",contatore_2);

    return 0;
}

/****************************************************************************/
/*                                MERGESORT                                 */
/****************************************************************************/
void merge(void **s1,void **s2, int dim1,int dim2, int *contatore){
    int k=0,i=0,j=0;
    void **S = (void **) malloc ( (dim1+dim2)*sizeof(void *) );
    while ( k < dim1+dim2 ){
        if ( i >= dim1 ){ S[k++] = s2[j++]; continue; }
        if ( j >= dim2 ){ S[k++] = s1[i++]; continue; }
        if (!(COMPARE (s1[i],s2[j])))
            S[k++] = s1[i++];
        else{
            /* quando prendiamo un elemento dalla stringa s2   *
             * questo costituirà "coppia inversione" con tutti *
             * gli elementi di s1 non ancora presenti in S     */
            (*contatore)+= dim1-i;    /* oppure j+dim1-k;      */
            S[k++] = s2[j++];
        }
    }
    for (k=0;k<(dim1+dim2);k++)
        s1[k] = S[k];
    free(S);
}

void mergesort(void **v,int dim, int *contatore)
{
    void **s1,**s2;
    if (dim>1){
        s1 = &v[0];
        s2 = &v[dim/2];
        mergesort(s1,dim/2,contatore);
        mergesort(s2,dim-(dim/2),contatore);
        merge(s1,s2,dim/2,dim-(dim/2),contatore);
    }
}