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

#define     N_NODI      20
#define     TAB_SIZE    7919

//-----------------------------------------------------------------------------
// Definizione della struttura dati per la memorizzazione del grafo mediante
// matrice di adiacenze.
//
int     mtx[N_NODI][N_NODI];

typedef struct TAG_HASH {
char    *key;
int     num;
} HASH;

//-----------------------------------------------------------------------------
// Definizione della tabella di hash usata per memorizzare l'associazione
// nome del nodo, nodo del grafo
//
HASH    tab[TAB_SIZE];


//-----------------------------------------------------------------------------
// Definizione della struttura dati per memorizzare il risultato
//
typedef struct T_RESULT {
int source;
int end;
int dim;
} RESULT;

RESULT vett[N_NODI*N_NODI];
int n_vett;

//-----------------------------------------------------------------------------
// Prototipi delle funzioni
//
int     hash( char *k );// Funzione di hash
int     hash_init( void );// Inizializza la tabella
void    hash_add( char *k, int n);// Aggiunge un dato alla tabella
int     hash_lookup( char *k );// Cerca una chiave nella tabella
char    *hash_getkey( int n );// Cerca la chiave associata al dato
void    hash_dispose( void );// Canella il contenuto della tabella

void    read_file( char *s );// Legge il file

static int compare( const void *p1, const void *p2 );// Confronto

//-----------------------------------------------------------------------------
// Implementazione delle funzioni
//
int hash( char *k )
{
char    *p;
int     h;

h = 0;
for( p = k; *p; p++ )
    h += (char)*p;

h = h % TAB_SIZE;

return( h );
}

int    hash_init( void )
{
int     i;

for( i = 0; i < TAB_SIZE; i++ )
{
    tab[i].key = NULL;
    tab[i].num = -1;
}
}

void    hash_add( char *k, int n)
{
int     h;

h = hash( k );

// Gestisce le collisioni con open addressing e linear probing
while( tab[h].key != NULL )
h = (h+1) % TAB_SIZE;

tab[h].key = (char *)strdup( k );
tab[h].num = n;
}

int    hash_lookup( char *k )
{
int     h;
int     p;

h = hash( k );

while( tab[h].key != NULL && strcmp( tab[h].key, k ) != 0 )
{
h = (h+1) % TAB_SIZE;
}

if( tab[h].key == NULL )
return( -1 );// La chiave non esiste
return( h );// La chiave esiste
}

char    *hash_getkey( int n )
{
int i;

for( i = 0; i < TAB_SIZE; i++ )
if( tab[i].num == n )
return( tab[i].key );
return( NULL );
}

void    hash_dispose( void )
{
int     i;

for( i = 0; i < TAB_SIZE; i++ )
if( tab[i].key != NULL )
free( tab[i].key );
}

void    read_file(char *s )
{
FILE    *fp;
char    tmp[256];
int     dim;
int     n_nodi;
char    nome[11];
int     i, pos;
char    *p, *q;
int     start, end;
int     node_ctr;

fp = fopen( s, "r" );
if( fp == NULL )
{
	printf( "Impossibile aprire %s\n", s );
	return;
}

node_ctr = 0;
while( fgets( tmp, 256, fp ) != NULL )
{
// Legge dimensione e numero di nodi
sscanf( tmp, "%d %d", &dim, &n_nodi );

// Scarta dimensione e numero di nodi e punta
// al primo carattere del nodo mittente
p = tmp;
while( (*p >= '0' && *p <= '9') || *p == ' ' )
p++;

// Identifica il nome di ogni nodo

for( i = 0; i < n_nodi; i++ )
{
q = strstr( p, " " );
sscanf( p, "%s", nome );
if( q != NULL )
p = q+1;

if( i == 0 )
{
// Se e' il primo nodo della sequenza lo
// metto in start
pos = hash_lookup( nome );
if( pos == -1 )
{
// Se il nodo non e' ancora stato
// trovato lo aggiungo alla hash table
hash_add( nome, node_ctr );
start = node_ctr;
node_ctr++;
}
else
start = tab[pos].num;
}
else
{
// Il nodo non e' il primo della sequenza
pos = hash_lookup( nome );
if( pos == -1 )
{
// Se il nodo non e' ancora stato
// trovato lo aggiungo alla hash table
hash_add( nome, node_ctr );
end = node_ctr;
node_ctr++;
}
else
end = tab[pos].num;
// Aggiorna la matrice
mtx[start][end] += dim;

// La prossima tratta inizia dal nodo corrente
start = end;
}
}
}

fclose( fp );
}

static int compare( const void *p1, const void *p2 )
{
RESULT i;
RESULT j;

i = *((RESULT *)p1);
j = *((RESULT *)p2);

if( i.dim > j.dim )
return( 1 );
if( i.dim < j.dim )
return( -1 );

return( 0 );
}

int main(int argc, char *argv[])
{
int   i, j;

hash_init();
read_file( "esame20030911.txt" );

n_vett = 0;

for( i = 0; i < N_NODI; i++ )
{
for( j = 0; j < N_NODI; j++ )
if( mtx[i][j] != 0 )
{
vett[n_vett].source = i;
vett[n_vett].end = j;
vett[n_vett].dim = mtx[i][j];
n_vett++;
}
}

qsort( vett, n_vett, sizeof( RESULT ), compare );

for( i = 0; i < n_vett; i++ )
  printf( "%-11s %-11s %d\n", hash_getkey( vett[i].source ),
    hash_getkey( vett[i].end ),
    vett[i].dim );

hash_dispose();

return 0;
}