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

// Struttura del Nodo con legame bidirezionale
typedef struct NodoDoppio {
  int dato;
  struct NodoDoppio *precedente; // Collegamento all'indietro (prev)
  struct NodoDoppio *prossimo;   // Collegamento in avanti (next)
} NodoDoppio;

// Struttura di Controllo professionale (Doppia Estremità)
typedef struct {
  NodoDoppio *head; // Primo nodo
  NodoDoppio *tail; // Ultimo nodo
} ListaDoppia;

// Inizializzazione della lista doppia
void inizializza_lista_doppia(ListaDoppia *l) {
  l->head = NULL;
  l->tail = NULL;
}

// Verifica stato della lista
bool is_empty_doppia(const ListaDoppia *l) { return l->head == NULL; }

// Allocazione e isolamento di un singolo NodoDoppio
NodoDoppio *crea_nodo_doppio(int valore) {
  NodoDoppio *nuovo = (NodoDoppio *)malloc(sizeof(NodoDoppio));
  if (nuovo == NULL) {
    fprintf(stderr, "Errore: RAM esaurita nell'allocazione del nodo doppio!\n");
    exit(1);
  }
  nuovo->dato = valore;
  nuovo->precedente = NULL;
  nuovo->prossimo = NULL;
  return nuovo;
}

// Inserimento in testa (Tempo Istantaneo)
void inserisci_testa_doppia(ListaDoppia *l, int valore) {
  NodoDoppio *nuovo = crea_nodo_doppio(valore);

  if (l->head == NULL) {
    // Se la lista era vuota, il nodo è sia testa che coda
    l->head = nuovo;
    l->tail = nuovo;
  } else {
    nuovo->prossimo = l->head; // Collegamento in avanti verso la vecchia testa
    l->head->precedente =
        nuovo; // Collegamento all'indietro della vecchia testa verso il nuovo
    l->head = nuovo; // Aggiornamento del marcatore di testa
  }
}

// Inserimento in coda (Tempo Istantaneo grazie al puntatore tail!)
void inserisci_coda_doppia(ListaDoppia *l, int valore) {
  NodoDoppio *nuovo = crea_nodo_doppio(valore);

  if (l->head == NULL) {
    l->head = nuovo;
    l->tail = nuovo;
  } else {
    nuovo->precedente =
        l->tail; // Collegamento all'indietro con il vecchio ultimo
    l->tail->prossimo =
        nuovo;       // Il vecchio ultimo si collega in avanti col nuovo
    l->tail = nuovo; // Aggiornamento del marcatore di coda
  }
}

// Scansione e ricerca sequenziale
NodoDoppio *cerca_nodo_doppio(const ListaDoppia *l, int valore) {
  NodoDoppio *corrente = l->head;
  while (corrente != NULL) {
    if (corrente->dato == valore) {
      return corrente; // Restituisce l'indirizzo esatto del nodo
    }
    corrente = corrente->prossimo;
  }
  return NULL;
}

// Rimozione mirata di un nodo specifico (Tempo Istantaneo - Chirurgia
// bilaterale pura!)
void rimuovi_nodo_doppio(ListaDoppia *l, NodoDoppio *da_eliminare) {
  if (l->head == NULL || da_eliminare == NULL) {
    return;
  }

  // CASO 1: Il nodo da eliminare è l'attuale testa
  if (l->head == da_eliminare) {
    l->head = da_eliminare->prossimo;
  }

  // CASO 2: Il nodo da eliminare è l'attuale coda
  if (l->tail == da_eliminare) {
    l->tail = da_eliminare->precedente;
  }

  // CASO 3: Ricucitura del nodo precedente (se esiste)
  if (da_eliminare->precedente != NULL) {
    da_eliminare->precedente->prossimo = da_eliminare->prossimo;
  }

  // CASO 4: Ricucitura del nodo successivo (se esiste)
  if (da_eliminare->prossimo != NULL) {
    da_eliminare->prossimo->precedente = da_eliminare->precedente;
  }

  // Deallocazione fisica del blocco orfano
  free(da_eliminare);
}

// Stampa in avanti (dalla testa alla coda)
void stampa_avanti(const ListaDoppia *l) {
  NodoDoppio *corrente = l->head;
  printf("Stampa in avanti: NULL <-> ");
  while (corrente != NULL) {
    printf("[%d] <-> ", corrente->dato);
    corrente = corrente->prossimo;
  }
  printf("NULL\n");
}

// Stampa all'indietro (dalla coda alla testa - Dimostra la bidirezionalità!)
void stampa_indietro(const ListaDoppia *l) {
  NodoDoppio *corrente = l->tail;
  printf("Stampa all'indietro: NULL <-> ");
  while (corrente != NULL) {
    printf("[%d] <-> ", corrente->dato);
    corrente = corrente->precedente; // Usiamo prev!
  }
  printf("NULL\n");
}

// Liberazione totale dello Heap
void libera_lista_doppia(ListaDoppia *l) {
  NodoDoppio *corrente = l->head;
  while (corrente != NULL) {
    NodoDoppio *succ = corrente->prossimo;
    free(corrente);
    corrente = succ;
  }
  l->head = NULL;
  l->tail = NULL;
}

// Programma di Test
int main(void) {
  ListaDoppia mia_lista;
  inizializza_lista_doppia(&mia_lista);

  printf("--- TEST INSERIMENTI BILATERALI ---\n");
  inserisci_testa_doppia(&mia_lista, 20);
  inserisci_testa_doppia(&mia_lista, 10); // Testa: 10 <-> 20
  inserisci_coda_doppia(&mia_lista, 30);  // Coda istantanea: 10 <-> 20 <-> 30
  inserisci_coda_doppia(&mia_lista,
                        40); // Lista finale: 10 <-> 20 <-> 30 <-> 40

  stampa_avanti(&mia_lista);
  stampa_indietro(&mia_lista); // Verifica del doppio collegamento

  printf("\n--- TEST RICERCA ED ELIMINAZIONE ISTANTANEA (CHIRURGIA BILATERALE) "
         "---\n");
  printf("Cerco il nodo con valore 30...\n");
  NodoDoppio *target = cerca_nodo_doppio(&mia_lista, 30);

  if (target != NULL) {
    printf("Nodo 30 rintracciato all'indirizzo %p. Procedo alla rimozione "
           "istantanea...\n",
           (void *)target);
    rimuovi_nodo_doppio(&mia_lista, target);

    printf("\nLista aggiornata dopo la rimozione:\n");
    stampa_avanti(&mia_lista);   // Atteso: 10 <-> 20 <-> 40
    stampa_indietro(&mia_lista); // Atteso: 40 <-> 20 <-> 10
  } else {
    printf("Nodo non trovato.\n");
  }

  // Cleanup completo della memoria
  libera_lista_doppia(&mia_lista);
  return 0;
}