Algoritmi e strutture dati

/*
 * Una struttura ospedaliera deve riorganizzare alcuni elenchi di pazienti 
 * tra cui elenco1 (un Binary Search Tree) ed elenco2 (una Hash Table).
 * In ciascuna struttura, un paziente
 * e' rappresentato da un ID (campo chiave di tipo TKey, ossia un intero),
 * dal nome e dal cognome (di tipo TValue, ossia due stringhe).
 * In tutte le strutture coinvolte, i pazienti con esenzione dal ticket
 * vengono indicati con uno 0 finale nel loro ID.
 * 
 * Si dovra' realizzare un programma che sposti tutti i pazienti con esenzione
 * (ID la cui ultima cifra sia 0) da elenco2 ad elenco1, rimuovendo gli
 * eventuali duplicati in conseguenza del travaso. Inoltre, si dovranno copiare in elenco3
 * (una lista ordinata) tutti i pazienti di elenco1, eseguendo anche una stampa
 * dei soli pazienti con esenzione considerando gli ID in ordine decrescente.
 * Bisogna, infine, rimuovere da elenco1 il paziente con ID piu' alto.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 *    
 * 1) HTtoBST_exemption(ht, bst): funzione ITERATIVA che copia da ht a bst tutti
 *    i pazienti con ID la cui ultima cifra sia 0, rimuovendoli da ht.
 *    Nel caso in cui un paziente di ht gia' esiste in bst,
 *    esso non verra' duplicato (ma verra' comunque rimosso da ht).
 * 2) BSTtoList(bst, list): funzione RICORSIVA che copia da bst a list tutti
 *    i pazienti di bst in ordine crescente di ID.
 * 3) listPrintReverse_exemption(list): funzione RICORSIVA che stampa gli elementi di 
 *    list in ordine inverso (in termini di ID).
 * 4) BSTremoveLast(bst): funzione RICORSIVA che rimuove da bst l'ultimo 
 *    elemento in ordine di ID (ossia il paziente con l'ID piu' alto). 
 *    Restituisce il bst aggiornato.
 * 
 */

#include <stdio.h>
#include "THT.h"
#include "TBST.h"
#include "TList.h"
#include "TInfo.h"
#include "TArray.h"

TBST HTtoBST_exemption(THT* ht, TBST bst) {
    for(int i = 0; i < ht->n_bucket; i++)
    for(TNode *node = ht->bucket[i]; node != NULL; node = node->link)
    if(HTtoBST_exemption(ht, bst->info.key)){
        if(BSTsearch(bst, node->info) == NULL)
        bst = BSTinsert(bst, node->info);
        HTdelete(ht, node->info.key);
    }
    
    return bst;
}

TList BSTtoList(TBST bst, TList list) {
    // Caso base: l'albero è vuoto, niente da aggiungere
    if(bst != NULL){
        //Divide e combina: aggiungo il sotto-albero sinistro (elementi minori)
        list = BSTtoList(bst->left, list);
        
        // Aggiungo l'elemento
        list = listInsert(list, bst->info);
        
        // Aggiungo il sotto-albero destro (elementi maggiori)
        list = BSTtoList(bst->right, list);
        
        return list;
    }

}

void listPrintReverse_exemption(TList list) {
    // Caso base
    if(list == NULL)
    return;
    
    // Divide et Impera
    listPrintReverse_exemption(list->link);
    printf("%d\n",list->info);

}

TBST BSTremoveLast(TBST bst) {
    TInfo min, max;
    
    // Caso base
    if(bst == NULL)
    return 0;
    
    // Divide et Impera (+ combina)
    if(!infoGreater(min, bst->info))
    BSTprint(bst->left);
    if (!infoGreater(min, bst->info) && !infoLess(max, bst->info))
        infoPrint(bst->info);
    if (!infoLess(max, bst->info))
        BSTprint(bst->right);
        
    bst = BSTdelete(bst, bst->info);
    
    return bst;
}

/* Logica applicativa */

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1320, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2370, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4443, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4230, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2644, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1110, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(3);
    HTinsert(elenco2, 3351, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4260, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 4443, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 6320, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1110, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 5430, (TValue) {"Lucio", "Rossetti"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});
    HTinsert(elenco2, 3450, (TValue) {"Biagio", "Verdini"});

    printf("Pazienti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nPazienti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBST_exemption(elenco2, elenco1);

    printf("\nPazienti in elenco1 (BST) dopo lo spostamento:\n");
    BSTprint(elenco1);
    printf("\nPazienti in elenco2 (HT) dopo lo spostamento:\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    printf("\nRiverso in elenco3 i pazienti di elenco1...");
    printf("\nPazienti in elenco3 (Lista):\n");
    elenco3 = BSTtoList(elenco1, elenco3);
    listPrint(elenco3);
    
    printf("\nPazienti con esenzione presenti in elenco3 (Lista)\n(in ordine decrescente)\n");
    listPrintReverse_exemption(elenco3);
    
    printf("\nPazienti in elenco1 (BST dopo aver rimosso l'elemento con ID massimo):\n");
    elenco1 = BSTremoveLast(elenco1);
    BSTprint(elenco1);
    

    BSTdestroy(elenco1);
    HTdestroy(elenco2);
    listDestroy(elenco3);

    return 0;
}