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

// Definizione del tipo Nodo
typedef struct Nodo {
  int dato;
  struct Nodo *prossimo;
} Nodo;

// Alloca e inizializza un nodo isolato
Nodo *crea_nodo(int valore) {
  Nodo *nuovo = (Nodo *)malloc(sizeof(Nodo));
  if (nuovo == NULL) {
    fprintf(stderr, "Errore: RAM esaurita nell'allocazione del nodo!\n");
    exit(1);
  }
  nuovo->dato = valore;
  nuovo->prossimo = NULL;
  return nuovo;
}

// Verifica se la lista è vuota
bool is_empty(Nodo *testa) { return testa == NULL; }

// Stampa sequenziale della lista
void stampa_lista(Nodo *testa) {
  Nodo *corrente = testa;
  printf("Lista: ");
  while (corrente != NULL) {
    printf("[%d] -> ", corrente->dato);
    corrente = corrente->prossimo;
  }
  printf("NULL\n");
}

// Ricerca di un elemento con ritorno del flag e del puntatore al nodo
bool cerca_elemento(Nodo *testa, int chiave, Nodo **risultato) {
  Nodo *corrente = testa;
  while (corrente != NULL) {
    if (corrente->dato == chiave) {
      if (risultato != NULL) {
        *risultato = corrente;
      }
      return true;
    }
    corrente = corrente->prossimo;
  }
  if (risultato != NULL) {
    *risultato = NULL;
  }
  return false;
}

// Inserimento in testa (Tempo istantaneo)
Nodo *inserisci_testa(Nodo *testa, int valore) {
  Nodo *nuovo = crea_nodo(valore);
  nuovo->prossimo = testa;
  return nuovo;
}

// Inserimento in coda (Tempo proporzionale alla lunghezza)
Nodo *inserisci_coda(Nodo *testa, int valore) {
  Nodo *nuovo = crea_nodo(valore);
  if (testa == NULL) {
    return nuovo;
  }
  Nodo *corrente = testa;
  while (corrente->prossimo != NULL) {
    corrente = corrente->prossimo;
  }
  corrente->prossimo = nuovo;
  return testa;
}

// Inserimento ordinato (Mantenimento dell'ordine crescente)
Nodo *inserisci_ordinato(Nodo *testa, int valore) {
  Nodo *nuovo = crea_nodo(valore);

  // Caso 1: Lista vuota o inserimento in testa
  if (testa == NULL || valore < testa->dato) {
    nuovo->prossimo = testa;
    return nuovo;
  }

  // Caso 2: Inserimento in mezzo o in coda (con due puntatori)
  Nodo *precedente = testa;
  Nodo *corrente = testa->prossimo;

  while (corrente != NULL && corrente->dato < valore) {
    precedente = corrente;
    corrente = corrente->prossimo;
  }

  precedente->prossimo = nuovo;
  nuovo->prossimo = corrente;

  return testa;
}

// Cancellazione in testa
Nodo *rimuovi_testa(Nodo *testa) {
  if (testa == NULL)
    return NULL;

  Nodo *da_eliminare = testa;
  testa = testa->prossimo;
  free(da_eliminare);

  return testa;
}

// Cancellazione in coda
Nodo *rimuovi_coda(Nodo *testa) {
  if (testa == NULL)
    return NULL;

  if (testa->prossimo == NULL) {
    free(testa);
    return NULL;
  }

  Nodo *corrente = testa;
  while (corrente->prossimo->prossimo != NULL) {
    corrente = corrente->prossimo;
  }

  free(corrente->prossimo);
  corrente->prossimo = NULL;

  return testa;
}

// Cancellazione di un valore specifico (con scavalcamento)
Nodo *rimuovi_valore(Nodo *testa, int valore) {
  if (testa == NULL)
    return NULL;

  if (testa->dato == valore) {
    Nodo *temp = testa->prossimo;
    free(testa);
    return temp;
  }

  Nodo *precedente = testa;
  Nodo *corrente = testa->prossimo;

  while (corrente != NULL && corrente->dato != valore) {
    precedente = corrente;
    corrente = corrente->prossimo;
  }

  if (corrente != NULL) {
    precedente->prossimo = corrente->prossimo;
    free(corrente);
  }

  return testa;
}

// --- ALGORITMISTICA: BUBBLE SORT CON SWAP FISICO DEI NODI ---

// Funzione helper per scambiare due nodi consecutivi A e B
Nodo *scambia_adiacenti(Nodo *testa, Nodo *prev, Nodo *A, Nodo *B) {
  A->prossimo = B->prossimo;
  B->prossimo = A;
  if (prev == NULL) {
    testa = B;
  } else {
    prev->prossimo = B;
  }
  return testa;
}

// Bubble sort in-place ad alta efficienza (scambio dei link di memoria)
Nodo *ordina_lista(Nodo *testa) {
  if (testa == NULL || testa->prossimo == NULL) {
    return testa;
  }

  bool scambiato;
  Nodo *limite = NULL;

  do {
    scambiato = false;
    Nodo *corrente = testa;
    Nodo *precedente = NULL;

    while (corrente->prossimo != limite) {
      Nodo *successivo = corrente->prossimo;

      if (corrente->dato > successivo->dato) {
        testa = scambia_adiacenti(testa, precedente, corrente, successivo);
        precedente = successivo;
        scambiato = true;
      } else {
        precedente = corrente;
        corrente = corrente->prossimo;
      }
    }
    limite = corrente;

  } while (scambiato);

  return testa;
}

// Rilascio ricorsivo o iterativo di tutta la memoria nello Heap
void libera_lista(Nodo *testa) {
  Nodo *corrente = testa;
  while (corrente != NULL) {
    Nodo *successivo = corrente->prossimo;
    free(corrente);
    corrente = successivo;
  }
}

// Programma di Test
int main(void) {
  Nodo *lista = NULL;

  printf("--- TEST INSERIMENTI ---\n");
  lista = inserisci_testa(lista, 30);
  lista = inserisci_testa(lista, 10);
  lista = inserisci_coda(lista, 40);
  lista = inserisci_ordinato(lista, 20); // Inserimento centrale ordinato
  stampa_lista(lista);                   // Atteso: 10 -> 20 -> 30 -> 40

  printf("\n--- TEST RICERCA ---\n");
  Nodo *nodo_trovato = NULL;
  if (cerca_elemento(lista, 30, &nodo_trovato)) {
    printf("Trovato valore 30 all'indirizzo di memoria: %p\n",
           (void *)nodo_trovato);
  } else {
    printf("Valore 30 non trovato.\n");
  }

  printf("\n--- TEST CANCELLAZIONI ---\n");
  lista = rimuovi_testa(lista); // Rimuove 10
  stampa_lista(lista);          // Atteso: 20 -> 30 -> 40

  lista = rimuovi_coda(lista); // Rimuove 40
  stampa_lista(lista);         // Atteso: 20 -> 30

  lista = inserisci_coda(lista, 50);
  stampa_lista(lista);               // Atteso: 20 -> 30 -> 50
  lista = rimuovi_valore(lista, 30); // Rimuove il valore intermedio
  stampa_lista(lista);               // Atteso: 20 -> 50

  printf("\n--- TEST ORDINAMENTO SU DISORDINATA ---\n");
  libera_lista(lista);
  lista = NULL;

  lista = inserisci_testa(lista, 5);
  lista = inserisci_testa(lista, 25);
  lista = inserisci_testa(lista, 12);
  lista = inserisci_testa(lista, 1);
  lista = inserisci_testa(lista, 18);
  printf("Prima del sort: ");
  stampa_lista(lista);

  lista = ordina_lista(lista);
  printf("Dopo il sort (swap nodi): ");
  stampa_lista(lista); // Atteso: 1 -> 5 -> 12 -> 18 -> 25

  // Cleanup finale dello Heap
  libera_lista(lista);
  lista = NULL;
  return 0;
}