Pillole video 7

#include <iostream>
#include <chrono>
#include <vector>


using namespace std;

struct Nodo {
  string dato = "";

  Nodo *next = nullptr;
};



void ins_testa(Nodo *&il, Nodo *nuovo)
{
    nuovo->next = il;
    il = nuovo;
}



void ins_coda(Nodo *&il, Nodo *nuovo)
{
  if (il == nullptr) //lista vuota ?
  {
    nuovo->next = il;
    il = nuovo;
  }
  else
  {
    Nodo *ultimo = il;

    //otteniamo un puntatore all'ultimo nodo attuale
    while(ultimo->next != nullptr) ultimo = ultimo->next;

    ultimo->next = nuovo;
    nuovo->next = nullptr;
  }
}

void stampa_dalla_coda(Nodo *p, int profondita, int &massima)
{
  massima = max(profondita, massima);

  if (p!=nullptr)
    stampa_dalla_coda(p->next, profondita+1, massima);
}


//Equazione di ricorrenza temporale: T(n) = 2*T(n/2) + O(n)
//Equazione di ricorrenza spaziale: T(n) = T(n/2) + O(1)
//Complessità temporale: O(nlog(n))
//Complessità spaziale: O(log(n))
void stampaInvertita(Nodo *testa,int  dim){

    //Casi base
    //Lista vuota
    if (testa == nullptr)
        return;
    //Lista con un solo elemento
    if (testa->next == nullptr)
        ;//cout << testa->dato << endl;
        //Passo ricorsivo
    else{
        Nodo* attuale = testa;
        //Suddivido in due metà la lista
        for (int i = 0; i < dim/2 - 1; ++i) {
            attuale = attuale->next;
        }
        //Mi fermo all'ultimo elemento della prima metà
        //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
        Nodo* temp = attuale;
        attuale = attuale->next;
        temp->next = nullptr;

        //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
        stampaInvertita(attuale, dim/2);
        stampaInvertita(testa, dim - dim/2);

        //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
        temp->next = attuale;
    }
}

//credits Alex-qk5ei (youtube)
int stampaInvertitaMisuraStack(Nodo *testa, int dim){

    //Casi base
    //Lista vuota
    if (testa == nullptr)
        return 1;
    //Lista con un solo elemento
    if (testa->next == nullptr) {
        ;//cout << testa->dato << endl;
        return 1;
    }
    //Passo ricorsivo
    else{
        Nodo* attuale = testa;

        //Suddivido in due metà la lista
        for (int i = 0; i < (dim>>1) - 1; ++i) {
            attuale = attuale->next;
        }

        //Mi fermo all'ultimo elemento della prima metà
        //ed imposto il puntatore al successivo a nullptr, così da avere due liste fisicamente separate
        Nodo* temp = attuale;
        attuale = attuale->next;
        temp->next = nullptr;

        /*La profondità massima dello stack P(n) può essere definita ricorsivamente come: P(n) = max(P(n/2), P(n-n/2)) + 1
        L'addendo 1 equivale alla presenza sullo stack del record di attivazione corrente
        Inoltre, considerando che n-n/2 >= n/2 in ogni caso, max(P(n/2), P(n-n/2)) = P(n-n/2) e, conseguentemente
        P(n) = P(n-n/2) + 1
        L'istruzione sottostante rappresenta dunque la profondità massima che andrà restituita al metodo chiamante
        */
        //Ora richiedo la stampa della seconda metà seguita dalla prima; l'ordine delle chiamate è fondamentale
        int profondita = stampaInvertitaMisuraStack(attuale, dim - (dim>>1)) + 1;
        stampaInvertitaMisuraStack(testa, dim>>1);
        //Dopo la stampa non resta che ricongiungere le due liste precedentemente divise
        temp->next = attuale;

        return profondita;
    }
}

int fattoriale(int n)
{
   if (n == 0)
    return 1;
   else
     return n * fattoriale(n - 1);
}


int fattoriale_tail(int n, int accumulatore=1)
{
   if (n == 0)
    return accumulatore;
   else
    return fattoriale_tail(n - 1, n * accumulatore);
}


enum Comando {START, STOP};
auto Cronometro(Comando comando = Comando::START)
{
  static std::chrono::time_point<std::chrono::system_clock> inizio;
  static std::chrono::time_point<std::chrono::system_clock> fine;

  if (comando == Comando::START)
  {
    inizio = chrono::high_resolution_clock::now();
    fine = inizio;
  }
  else
    fine = chrono::high_resolution_clock::now();


  return chrono::duration_cast<std::chrono::milliseconds>(fine - inizio).count();
}








void stampaInvertitaVector(Nodo *il)
{
  vector<Nodo*> v;

  while(il!=nullptr)
  {
    v.push_back(il);
    il = il-> next;
  }

  for (int i=v.size()-1; i>=0; i--);
    //cout << v[i] -> dato << " ";
}








void InvertiLista(Nodo *&il)
{

  Nodo * precedente = nullptr;
  Nodo * corrente=il;
  Nodo * successivo = nullptr;

  while(corrente!=nullptr)
  {
    successivo = corrente->next;
    corrente->next =  precedente;

    precedente = corrente;
    corrente = successivo;
  }

  il=precedente;
}





void stampa(Nodo *p)
{
  while (p!=nullptr)
  {
    //cout << p->dato << " ";

    //al prossimo nodo
    p = p->next;
  }
}

// Struttura per rappresentare una "mossa"
struct HanoiMove {
    int n;          // Numero di dischi
    char from;      // Piolo di partenza (A, B, C)
    char to;        // Piolo di destinazione
    char aux;       // Piolo ausiliario
};

// Versione iterativa senza STL (stack manuale)
void hanoi_iterative_no_stl(int n, char from = 'A', char to = 'C', char aux = 'B') {
    const int MAX_STACK_SIZE = 1000; // Dimensione massima dello stack
    HanoiMove stack[MAX_STACK_SIZE];
    int top = -1; // Inizializza lo stack vuoto

    // Simula la prima chiamata ricorsiva
    stack[++top] = {n, from, to, aux};

    while (top >= 0) { // Finché lo stack non è vuoto
        HanoiMove current = stack[top--]; // Pop

        if (current.n == 1) {
            // Caso base: sposta il disco
            cout << "Muovi disco 1 da " << current.from << " a " << current.to << endl;
        } else {
            // Simula le chiamate ricorsive in ordine inverso (LIFO)
            // 1. hanoi(n-1, aux, to, from)
            stack[++top] = {current.n - 1, current.aux, current.to, current.from};
            // 2. Sposta il disco n da from a to (caso base fittizio)
            stack[++top] = {1, current.from, current.to, current.aux};
            // 3. hanoi(n-1, from, aux, to)
            stack[++top] = {current.n - 1, current.from, current.aux, current.to};
        }
    }
}


void hanoi(int n, char from = 'A', char to = 'C', char aux = 'B') {
    if (n == 1) {
        cout << "Muovi disco 1 da " << from << " a " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);  // Sposta n-1 dischi da 'from' a 'aux'
    cout << "Muovi disco " << n << " da " << from << " a " << to << endl;
    hanoi(n - 1, aux, to, from);  // Sposta n-1 dischi da 'aux' a 'to'
}

int main()
{
    //cout << fattoriale_tail(60001) << endl;
    //hanoi_iterative_no_stl(3);

    string dati_prova[] = {"abaco", "amo", "bicicletta", "cane", "canguro", "mare", "sale", "zebra"};

    Nodo *il = nullptr;

    int quante_run=10000;
    int num_ele = 20000;

    for (int i=0; i<num_ele; i++)
      ins_testa(il, new Nodo{dati_prova[i%8]});

    //stampaInvertitaVector(il);

//    stampa(il);
//    InvertiLista(il);
//    stampa(il);
//    InvertiLista(il);
//    stampa(il);



    //CON RICORSIONE E DIVIDE ET IMPERA
    Cronometro(Comando::START);
    for (int run=0; run<quante_run; run++)
          stampaInvertita(il,num_ele);
    cout << "Ricorsione con divide/impera: " << Cronometro(Comando::STOP) << endl;

    //CON VECTOR DI APPOGGIO
    Cronometro(Comando::START);
    for (int run=0; run<quante_run; run++)
          stampaInvertitaVector(il);
    cout << "Iterativa con vector di puntatori: " << Cronometro(Comando::STOP) << endl;


    //CON INVERSIONE PUNTATORI
    Cronometro(Comando::START);
    for (int run=0; run<quante_run; run++)
    {
      InvertiLista(il);
      stampa(il);
      InvertiLista(il);
    }
    cout << "Iterativa con inversione fisica lista: " << Cronometro(Comando::STOP) << endl;



    return 0;
}