--- Informatica 448 II - 1 luglio 2015 - soluzioni ----

TESTO IN C++ (SOLO PER STUDENTI IMMATRICOLATI AL 2' ANNO E SUCCESSIVI CHE HANNO SCELTO
DI PORTARE IL PROGRAMMA VECCHIO)

Un negozio di alimentari conserva i prodotti in scatole che contengono zero
o piu` prodotti dello stesso tipo. I prodotti in ogni scatola hanno lo stesso
prezzo e data di scadenza, e sono rappresentati mediante le seguenti definizioni:

    #include <iostream>
    #include <fstream>
    #include <cstring>
    using namespace std;

    const int MAX_N = 60; /* lunghezza nome prodotto */ 
    const int MAX_BOX = 9999; /* numero massimo scatole */

    struct Data { int mese; int anno; int giorno; };

    struct Box {
	int codice;	/* codice unico scatola */
	Data scade;	/* data di scadenza */
	float buy;	/* prezzo di acquisto di un oggetto */
	float sell;	/* prezzo di vendita di un oggetto */
	unsigned int numero; /* numero oggetti nella scatola */
	char prodotto[MAX_N];	/* nome prodotto */
    }

    struct store {	/* magazzino */
	int numero_scatole;	/* numero totale di scatole */
	Box scatole [MAX_BOX];
    }

La struttura store contiene tutte le scatole con almeno 1 oggetto
nel vettore scatole, nelle posizioni da 0 a numero_scatole-1

REALIZZARE LE SEGUENTI FUNZIONI:

    void scadono(store *s, Data xx)
	stampa il numero totale di oggetti che scadono entro la data xx
	e il loro prezzo totale di acquisto
	SUGGERIMENTO: definire una funzione per il confronto di date

    void elimina(store *s)
	elimina dal magazzino tutte le scatole per cui numero == 0,
	compattando gli elementi in scatole

    float vendi(store *s, const char xxx[], unsigned int nn)
	Se nel magazzino sono disponibili almeno nn oggetti di nome xxx,
	restituisce il prezzo totale di vendita degli stessi eliminando
	gli oggetti dalle relative scatole (ed eliminando le scatole dal magazzino).
	IN CASO CONTRARIO, LASCIA IL MAGAZZINO INALTERATO E RITORNA -1
	NOTA: la quantita` desiderata puo` essere in piu` scatole

    void ordina(store *s)
	ordina l'elenco delle scatole in modo crescente secondo il campo
	prodotto e, a parita` di quel campo, secondo la quantita` (sell-buy)* numero

	Descrivere la funzione di ordinamento utilizzata e mostrarne l'implementazione.
	NOTA: Non e` accettabile l'uso di funzioni di libreria per l'ordinamento;
	si consiglia di usare un algoritmo semplice anche se inefficiente.
	SUGGERIMENTO: definire una funzione per il confronto di due oggetti
	secondo il criterio di ordinamento sopra definito.

    void compatta(store *s)
	supponendo lo schedario ordinato mediante la funzione precedente,
	compatta il magazzino inserendo tutti i prodotti con lo stesso prodotto
	in una sola scatola, assegnando alla data di scadenza il minore dei valori
	delle scatole da cui provengono gli oggetti, e ai prezzi di acquisto e vendita
	le medie pesate dei prezzi delle scatole di provenienza.

    int migliori_quattro(store *s)
	Stampa prodotto, sell e buy dei quattro Box che hanno la maggiore differenza
	(sell - buy)
	NOTA: se ci sono meno di quattro Box nella struttura si ferma prima.

=======================--- POSSIBILE SOLUZIONE ----===================

Innanzitutto realizziamo una funzione che confronta due date e
ritorna -1, 0 o +1 a seconda che la prima sia minore, uguale o
maggiore alla seconda

    int date_cmp(Data a, Data b) {
	if (a.anno < b.anno) {
	    return -1;
	} else if (a.anno > b.anno) {
	    return 1;
	} else if (a.mese < b.mese) {
	    return -1;
	} else if (a.mese > b.mese) {
	    return 1;
	} else if (a.giorno < b.giorno) {
	    return -1;
	} else if (a.giorno > b.giorno) {
	    return 1;
	} else {
	    return 0;
	}
    }

La funzione scadono() deve scandire l'intero magazzino e accumulare
le informazioni delle entrate che scadono entro la data specificata.
Utilizziamo due variabili per accumulare numero di oggetti e prezzi

    void scadono(store *s, Data xx) {
	int i, oggetti = 0; /* numero totale oggetti scelti */
	float prezzo = 0.0; /* prezzo totale oggetti scelti */

	for (i = 0; i < s->numero_scatole; i++) {
	    Box *b = &(s->scatole[i]); // abbreviazione
	    if (date_cmp(b->scade, xx) <= 0) { /* scade entro xx */
		oggetti += b->numero;
		prezzo += b->numero * b->buy;
	    }
	}
	cout << "Ci sono " << oggetti << " oggetti scaduti " <<
	   " per un prezzo totale " << prezzo << "\n";
    }
	
La funzione elimina() sostituisce ogni scatola con contenuto 0 con
l'ultima del vettore, aggiornando la lunghezza

    void elimina(store *s) {
	int i;
	for (i = 0; i < s->numero_scatole; i++) {
	    if (s->scatole[i].numero == 0) {
		s->scatole[i] = s->scatole[s->numero_scatole - 1];
		s->numero_scatole--;
	    }
	}
    }


La funzione vendi() deve operare in due passate, nella prima determina
se ci sono abbastanza oggetti disponibili, nella seconda rimuove
gli oggetti venduti.

    float vendi(store *s, const char xxx[], unsigned int nn) {
	int i, mancano = nn, prendi;
	float prezzo = 0;

	/* prima passata */
	for (i = 0; mancano > 0 && i < s->numero_scatole; i++) {
	    if (strcmp(xxx, s->scatole[i].prodotto) == 0) { /* trovato oggetto */
		mancano -= s->scatole[i].numero;
	    }
	}
	if (mancano > 0) {
	    return -1; /* non ci sono abbastanza oggetti disponibili */
	}
	/* seconda passata, estrae oggetti e calcola prezzo */
	mancano = nn; /* oggetti ancora mancanti */
	for (i = 0; mancano > 0 && i < s->numero_scatole; i++) {
	    if (strcmp(xxx, s->scatole[i].prodotto) == 0) { /* trovato oggetto */
		prendi = s->scatole[i].numero;
		if (mancano < prendi) {
		    prendi = mancano; /* prendi solo quelli mancanti */
		}
		s->scatole[i].numero -= prendi;
		mancano -= prendi;
		prezzo += prendi * s->scatole[i].sell; /* prezzo di vendita */
	    }
	}
	return prezzo;
    }

La funziona ordina() implementa un normale algoritmo di ordinamento con una opportuna
funzione per il confronto

    int my_cmp(Box *a, Box *b) {  
	int x = strcmp(a->prodotto, b->prodotto);
	if (x != 0) {
	    return x;
	} else {
	    float pa = (a->sell - a->buy ) * a->numero;
	    float pb = (b->sell - b->buy ) * b->numero;
	    if (pa < pb) {
	        return -1;
	    } else if (pa > pb) {
		return 1;
	    } else {
		return 0;
	    }
	}
    }

    fatto questo possiamo usare un semplice algoritmo quadratico es. selection sort

    void ordina(store *s) {
        Box *b = s->scatole; /* abbreviazione */
	int i, j, x /* candidato per lo scambio */;

	for (i = 0; i < s->numero_scatole - 1; i++) {
	    for (x = i, j = i + 1; j < s->numero_scatole; j++) {
		if (my_cmp( &b[j], &b[x]) < 0) { /* b[j] < b[x] */
		    x = j;
		}
	    }
	    /* ora b[x] e` il minimo, scambio b[x] e b[i] */
	    Box tmp = b[i];
	    b[i] = b[x];
	    b[x] = tmp;
	}
    }

Per la funzione compatta(), visto che i prodotti sono ordinati, gli oggetti
con lo stesso nome sono adiacenti quindi possiamo limitare l'analisi alle sole
scatole adiacenti. Le medie pesate sono definite come
	sum_i ( p[i] * n[i] ) / sum_i ( n[i] )
pertanto accumuliamo i valori buy*numero, sell*numero e numero e alla fine calcoliamo
il quoziente.

    void compatta(store *s) {
	Box *b = &s->scatole; /* abbreviazione */
	int i, j; /* indici per la scansione */

	for (i = 0; i < s->numero_scatole; i = j) {
	    /* inizio accumulo */
	    int n_tot = 0;
	    float buy = 0, sell = 0;
	    for (j = i; j < s->numero_scatole && strcmp(b[i].prodotto, b[j].prodotto); j++) {
		int n = b[j].numero; /* numero oggetti correnti */

		b[j].numero = 0; /* vuoto la scatola */
		n_tot += n;
		buy += n * b[j].buy;
		sell += n * b[j].sell;
	    }
	    if (n_tot == 0) {
		continue; /* caso speciale, scatole vuote */
	    }
	    /* qui b[j] e` diverso da b[i], accumulo tutto in b[i] */
	    b[i].numero = n_tot;
	    b[i].buy = buy/n_tot; /* media pesata */
	    b[i].sell = sell/n_tot; /* media pesata */
	}
    }

Infine per la funzione migliori_quattro() si esegue una versione semplificata dell'ordinamento

    int migliori_quattro(store *s) {
        Box *b = s->scatole; /* abbreviazione */
	int i, j, x /* candidato per lo scambio */;
	int lim = 4; /* quanti ne dobbiamo selezionare */

	if (s->numero_scatole <lim) {
	    lim = s->numero_scatole;
	}

	for (i = 0; i < lim; i++) {
	    for (x = i, j = i + 1; j < s->numero_scatole; j++) {
		if ( b[j].sell - b[j].buy > b[x].sell - b[x].buy]) { /* b[j] meglio di b[x] */
		    x = j;
		}
	    }
	    /* ora b[x] e` il migliore, scambio b[x] e b[i] */
	    Box tmp = b[i];
	    b[i] = b[x];
	    cout << "Posizione " << i + 1 << " prodotto " << b[i].prodotto " <<
		<< " differenza " << (b[i].sell - b[i].buy]) "\n";
	}
	return 0;
    }

------------------ fine soluzioni -------