477 lines
11 KiB
C
477 lines
11 KiB
C
// Laboratorio 1 - Esercizio 4
|
|
// Matteo Schiff - s295565
|
|
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <stdbool.h>
|
|
#include <stdlib.h>
|
|
#include <ctype.h>
|
|
#define MAX_LEN 30
|
|
#define MAX_ROWS 1000
|
|
|
|
const int MAXL = 50;
|
|
|
|
typedef struct Time
|
|
{
|
|
unsigned int hours;
|
|
unsigned int minutes;
|
|
unsigned int seconds;
|
|
} time;
|
|
|
|
typedef struct Date
|
|
{
|
|
unsigned int year;
|
|
unsigned int month;
|
|
unsigned int day;
|
|
} date;
|
|
|
|
typedef struct Corsa
|
|
{
|
|
char codice_tratta[MAX_LEN];
|
|
char partenza[MAX_LEN];
|
|
char destinazione[MAX_LEN];
|
|
date data;
|
|
time ora_partenza;
|
|
time ora_arrivo;
|
|
unsigned int ritardo;
|
|
} corsa;
|
|
|
|
typedef struct Raccolta
|
|
{
|
|
corsa *corse_data[MAX_ROWS];
|
|
corsa *corse_codice[MAX_ROWS];
|
|
corsa *corse_partenza[MAX_ROWS];
|
|
corsa *corse_arrivo[MAX_ROWS];
|
|
} raccolta;
|
|
|
|
typedef enum
|
|
{
|
|
k_codice_tratta,
|
|
k_partenza,
|
|
k_destinazione,
|
|
k_data
|
|
} corsa_keys;
|
|
|
|
typedef enum
|
|
{
|
|
r_stampa,
|
|
r_ordina_data,
|
|
r_ordina_codice,
|
|
r_ordina_partenza,
|
|
r_ordina_destinazione,
|
|
r_ricerca_partenza,
|
|
r_fine
|
|
} t_comandi;
|
|
|
|
// Trasforma in lowercase tutti i caratteri di una stringa
|
|
char *toLower(char *s)
|
|
{
|
|
for (char *p = s; *p; p++)
|
|
*p = tolower(*p);
|
|
return s;
|
|
}
|
|
|
|
t_comandi leggiComando()
|
|
{
|
|
t_comandi c;
|
|
char cmd[MAXL];
|
|
char tabella[8][20] = {
|
|
"stampa", "ordina_data", "ordina_codice", "ordina_partenza", "ordina_destinazione", "ricerca", "fine"};
|
|
printf("comando (stampa/ordina_data/ordina_codice");
|
|
printf("/ordina_partenza/ordina_destinazione/ricerca/fine): ");
|
|
scanf("%s", cmd);
|
|
toLower(cmd);
|
|
c = r_stampa;
|
|
while (c < 8 && strcmp(cmd, tabella[c]) != 0)
|
|
c++;
|
|
return (c);
|
|
}
|
|
|
|
corsa_keys interpreta_tratta(char *tratta)
|
|
{
|
|
corsa_keys c;
|
|
char cmd[MAXL];
|
|
char tabella[8][20] = {
|
|
"codice\n", "partenza\n", "destinazione\n", "data\n"};
|
|
c = k_codice_tratta;
|
|
while (c < 8 && strcmp(tratta, tabella[c]) != 0)
|
|
c++;
|
|
return (c);
|
|
}
|
|
|
|
// restituisce true se la prima data è successiva o coincidente alla seconda
|
|
int confronta_data_ora(corsa *a, corsa *b)
|
|
{
|
|
if (a->data.year > b->data.year)
|
|
return true;
|
|
else if (a->data.year < b->data.year)
|
|
return false;
|
|
|
|
if (a->data.month > b->data.month)
|
|
return true;
|
|
else if (a->data.month < b->data.month)
|
|
return false;
|
|
|
|
if (a->data.day > b->data.day)
|
|
return true;
|
|
else if (a->data.day < b->data.day)
|
|
return false;
|
|
|
|
if (a->ora_partenza.hours > b->ora_partenza.hours)
|
|
return true;
|
|
else if (a->ora_partenza.hours < b->ora_partenza.hours)
|
|
return false;
|
|
|
|
if (a->ora_partenza.minutes > b->ora_partenza.minutes)
|
|
return true;
|
|
else if (a->ora_partenza.minutes < b->ora_partenza.minutes)
|
|
return false;
|
|
|
|
if (a->ora_partenza.seconds >= b->ora_partenza.seconds)
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
|
|
int confronta_codice(corsa *a, corsa *b)
|
|
{
|
|
return strcmp(a->codice_tratta, b->codice_tratta);
|
|
}
|
|
|
|
int confronta_partenza(corsa *a, corsa *b)
|
|
{
|
|
return strcmp(a->partenza, b->partenza) >= 0;
|
|
}
|
|
|
|
int confronta_arrivo(corsa *a, corsa *b)
|
|
{
|
|
return strcmp(a->destinazione, b->destinazione) >= 0;
|
|
}
|
|
|
|
int confronta_chiave(corsa *a, corsa *b, corsa_keys chiave)
|
|
{
|
|
switch (chiave)
|
|
{
|
|
case k_codice_tratta:
|
|
return confronta_codice(a, b);
|
|
case k_destinazione:
|
|
return confronta_arrivo(a, b);
|
|
case k_partenza:
|
|
return confronta_partenza(a, b);
|
|
case k_data:
|
|
return confronta_data_ora(a, b);
|
|
}
|
|
}
|
|
|
|
int min(int x, int y)
|
|
{
|
|
return (x < y) ? x : y;
|
|
}
|
|
|
|
void merge(corsa *A[MAX_ROWS], int low, int mid, int high, corsa_keys chiave)
|
|
{
|
|
int i, j, k;
|
|
corsa * temp[MAX_ROWS];
|
|
// Merge the temp arrays
|
|
i = low;
|
|
j = mid+1;
|
|
k = 0;
|
|
while (i <= mid && j <= high)
|
|
{
|
|
if (!confronta_chiave(A[i], A[j], chiave))
|
|
{
|
|
temp[k] = A[i];
|
|
i++;
|
|
}
|
|
else
|
|
{
|
|
temp[k] = A[j];
|
|
j++;
|
|
}
|
|
k++;
|
|
}
|
|
// Copy the remaining elements of L[]
|
|
while (i <= mid)
|
|
{
|
|
temp[k] = A[i];
|
|
i++;
|
|
k++;
|
|
}
|
|
// Copy the remaining elements of R[]
|
|
while (j <= high)
|
|
{
|
|
temp[k] = A[j];
|
|
j++;
|
|
k++;
|
|
}
|
|
|
|
for (i = 0; i <= high - low; i++) {
|
|
A[i+low] = temp[i];
|
|
}
|
|
}
|
|
|
|
void mergesort_by_key(corsa *A[MAX_ROWS], int low, int high, corsa_keys key)
|
|
{
|
|
if (low >= high)
|
|
return;
|
|
|
|
// Finding mid element
|
|
int mid = low + (high - low) / 2;
|
|
// Recursively sorting both the halves
|
|
mergesort_by_key(A, low, mid, key);
|
|
mergesort_by_key(A, mid + 1, high, key);
|
|
|
|
// Merge the array
|
|
merge(A, low, mid, high, key);
|
|
}
|
|
|
|
void stampa_corsa(corsa corsa)
|
|
{
|
|
printf(" - %s %s %s, data: %4u/%02u/%02u, ora di partenza: %02u:%02u:%02u, ora di arrivo: %02u:%02u:%02u, ritardo %d minuto\n",
|
|
corsa.codice_tratta, corsa.partenza, corsa.destinazione,
|
|
corsa.data.year, corsa.data.month, corsa.data.day,
|
|
corsa.ora_partenza.hours, corsa.ora_partenza.minutes, corsa.ora_partenza.seconds,
|
|
corsa.ora_arrivo.hours, corsa.ora_arrivo.minutes, corsa.ora_arrivo.seconds,
|
|
corsa.ritardo);
|
|
}
|
|
|
|
void stampa_corse_vettore(corsa **corse, int N)
|
|
{
|
|
for (int i = 0; i < N; i++)
|
|
{
|
|
stampa_corsa(*(corse[i]));
|
|
}
|
|
}
|
|
|
|
void stampa_corse_scelta(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
argomenti++; // salta lo spazio
|
|
switch (interpreta_tratta(argomenti))
|
|
{
|
|
case k_codice_tratta:
|
|
puts("Corse ordinate per codice:");
|
|
stampa_corse_vettore(rac->corse_codice, N);
|
|
break;
|
|
case k_data:
|
|
puts("Corse ordinate per data:");
|
|
stampa_corse_vettore(rac->corse_data, N);
|
|
break;
|
|
case k_destinazione:
|
|
puts("Corse ordinate per destinazione:");
|
|
stampa_corse_vettore(rac->corse_arrivo, N);
|
|
break;
|
|
case k_partenza:
|
|
puts("Corse ordinate per partenza:");
|
|
stampa_corse_vettore(rac->corse_partenza, N);
|
|
break;
|
|
|
|
default:
|
|
puts("Errore. La sintassi è 'stampa [codice/partenza/destinazione/data]'");
|
|
break;
|
|
}
|
|
}
|
|
|
|
void ordina_data(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
puts("Ordino le corse per data\n");
|
|
|
|
mergesort_by_key(rac->corse_data, 0, N - 1, k_data);
|
|
}
|
|
|
|
void ordina_codice(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
puts("Ordino le corse per codice tratta\n");
|
|
|
|
mergesort_by_key(rac->corse_codice, 0, N - 1, k_codice_tratta);
|
|
}
|
|
|
|
void ordina_partenza(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
puts("Ordino le corse per partenza\n");
|
|
|
|
mergesort_by_key(rac->corse_partenza, 0, N - 1, k_partenza);
|
|
}
|
|
|
|
void ordina_arrivo(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
puts("Ordino le corse per destinazione\n");
|
|
|
|
mergesort_by_key(rac->corse_arrivo, 0, N - 1, k_destinazione);
|
|
}
|
|
|
|
void ricerca_dicotomica(corsa *corse[MAX_ROWS], char *partenza, int partenza_len, int N)
|
|
{
|
|
int s = 0, e = N - 1, i = (e + s) / 2, res = strncmp(partenza, corse[i]->partenza, partenza_len);
|
|
while (res != 0)
|
|
{
|
|
if (e-s <= 0) { //nothing found
|
|
puts("Nessun risultato");
|
|
return;
|
|
}
|
|
|
|
if (res > 0)
|
|
{
|
|
s = i+1;
|
|
}
|
|
else
|
|
{
|
|
e = i-1;
|
|
}
|
|
i = (e + s) / 2;
|
|
res = strncmp(partenza, corse[i]->partenza, partenza_len);
|
|
}
|
|
|
|
s = i;
|
|
e = i;
|
|
while (s > 0 && !strncmp(partenza, corse[s - 1]->partenza, partenza_len))
|
|
s--;
|
|
|
|
while (e < (N - 1) && !strncmp(partenza, corse[e + 1]->partenza, partenza_len))
|
|
e++;
|
|
|
|
for (i = s; i <= e; i++)
|
|
{
|
|
stampa_corsa(*(corse[i]));
|
|
}
|
|
}
|
|
|
|
void ricerca_lineare(corsa *corse[MAX_ROWS], char *partenza, int partenza_len, int N)
|
|
{
|
|
for (int i = 0; i < N; i++) {
|
|
if (!strncmp(partenza, corse[i]->partenza, partenza_len))
|
|
stampa_corsa(*(corse[i]));
|
|
}
|
|
}
|
|
|
|
void ricerca_partenza(char *argomenti, raccolta *rac, int N)
|
|
{
|
|
char partenza[30], tipo[30], partenza_len;
|
|
if (sscanf(argomenti, " %30s %30s", tipo, partenza) != 2)
|
|
{
|
|
puts("Partenza non valida. La sintassi è 'partenza [dicotomica/lineare] <partenza>'");
|
|
return;
|
|
}
|
|
|
|
partenza_len = strlen(partenza);
|
|
|
|
puts("Risultati della ricerca per stazione di partenza:");
|
|
|
|
if (!strcmp(tipo, "dicotomica"))
|
|
{
|
|
ricerca_dicotomica(rac->corse_partenza, partenza, partenza_len, N);
|
|
}
|
|
else
|
|
{
|
|
ricerca_lineare(rac->corse_partenza, partenza, partenza_len, N);
|
|
}
|
|
}
|
|
|
|
void menuParola(raccolta *rac, int N)
|
|
{
|
|
t_comandi comando;
|
|
char argomenti[MAXL];
|
|
int i, continua = 1;
|
|
while (continua)
|
|
{
|
|
comando = leggiComando();
|
|
fgets(argomenti, MAXL, stdin); /* resto della riga */
|
|
switch (comando)
|
|
{
|
|
case r_stampa:
|
|
stampa_corse_scelta(argomenti, rac, N);
|
|
break;
|
|
case r_ordina_data:
|
|
ordina_data(argomenti, rac, N);
|
|
break;
|
|
case r_ordina_codice:
|
|
ordina_codice(argomenti, rac, N);
|
|
break;
|
|
case r_ordina_destinazione:
|
|
ordina_arrivo(argomenti, rac, N);
|
|
break;
|
|
case r_ordina_partenza:
|
|
ordina_partenza(argomenti, rac, N);
|
|
break;
|
|
case r_ricerca_partenza:
|
|
ricerca_partenza(argomenti, rac, N);
|
|
break;
|
|
case r_fine:
|
|
continua = 0;
|
|
break;
|
|
default:
|
|
puts("Comando non valido\n");
|
|
}
|
|
}
|
|
}
|
|
|
|
void fillArray(corsa corse[MAX_ROWS], corsa *corse_ptr[MAX_ROWS], int N)
|
|
{
|
|
for (int i = 0; i < N; i++)
|
|
{
|
|
corse_ptr[i] = &corse[i];
|
|
}
|
|
}
|
|
|
|
int loadFile(corsa corse[MAX_ROWS], int *N, char *filename)
|
|
{
|
|
FILE *fp_read;
|
|
unsigned int lines, i;
|
|
|
|
if ((fp_read = fopen(filename, "r")) == NULL)
|
|
{
|
|
puts("Impossibile aprire il file");
|
|
return 1;
|
|
}
|
|
|
|
fscanf(fp_read, "%u\n", &lines);
|
|
|
|
if (lines > MAX_ROWS)
|
|
{
|
|
fclose(fp_read);
|
|
return 1;
|
|
}
|
|
|
|
for (i = 0; i < lines; i++)
|
|
{
|
|
int num_read = fscanf(fp_read, "%30s %30s %30s %4u/%2u/%2u %2u:%2u:%2u %2u:%2u:%2u %u\n", corse[i].codice_tratta, corse[i].partenza, corse[i].destinazione, &corse[i].data.year, &corse[i].data.month, &corse[i].data.day, &corse[i].ora_partenza.hours, &corse[i].ora_partenza.minutes, &corse[i].ora_partenza.seconds, &corse[i].ora_arrivo.hours, &corse[i].ora_arrivo.minutes, &corse[i].ora_arrivo.seconds, &corse[i].ritardo);
|
|
if (num_read != 13)
|
|
{
|
|
// la stringa è mal formattata
|
|
printf("File non formattato correttamente. Errore a linea %d\n", i + 1);
|
|
fclose(fp_read);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
fclose(fp_read);
|
|
|
|
*N = i;
|
|
return 0;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
int N;
|
|
corsa corse[MAX_ROWS];
|
|
raccolta rac;
|
|
|
|
if (loadFile(corse, &N, "./corse.txt"))
|
|
{
|
|
return 1;
|
|
}
|
|
|
|
if (corse == NULL)
|
|
{
|
|
return 1;
|
|
}
|
|
|
|
fillArray(corse, rac.corse_data, N);
|
|
fillArray(corse, rac.corse_codice, N);
|
|
fillArray(corse, rac.corse_partenza, N);
|
|
fillArray(corse, rac.corse_arrivo, N);
|
|
|
|
menuParola(&rac, N);
|
|
|
|
return 0;
|
|
}
|