Algoritmi lezione 30 - liste concatenate VS array

//LINK a utility_vettori.h (le funzioni di supporto usate spesso nel sorgente principale)
// https://pastebin.com/jxsd1vSt (è la parte all'inizio)



#include <iostream>
#include <memory>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;
#include "../../vettori/min_max/utility_vettori.h"


template <typename T>
class ListaConcatenata {
private:
    // Nodo della lista_numeri
    class Nodo {
    public:
        T dati;

        std::unique_ptr<Nodo> successivo = nullptr;

      //Nodo(T i_dati) { dati = i_dati;}
        Nodo(T i_dati) : dati(i_dati) {}
    };

    std::unique_ptr<Nodo> testa = nullptr;
    Nodo* coda = nullptr;

public:
    ListaConcatenata() {}

    // Aggiunge un elemento all'inizio della lista
    void inserisci_in_testa(T i_dati) {
        auto nuovo = std::make_unique<Nodo>(i_dati);
        if (!testa) {
            coda = nuovo.get();
        }

        //std::cout << "testa PRIMA: " << testa.get() << std::endl;
        nuovo->successivo = std::move(testa);
        //std::cout << "testa DOPO: " << testa.get() << std::endl;

        testa = std::move(nuovo);
    }

    // Aggiunge un elemento alla fine della lista
    void inserisci_in_coda(T i_dati) {
        auto nuovo = std::make_unique<Nodo>(i_dati);
        if (!coda) {
            testa = std::move(nuovo);
            coda = testa.get();
        } else {
            coda->successivo = std::move(nuovo);
            coda = coda->successivo.get();
        }
    }

    // Stampa gli elementi della lista
    void stampa() const {
        Nodo* temp = testa.get();
        while (temp) {
            std::cout << temp->dati << " -> ";
            temp = temp->successivo.get();
        }
        std::cout << "nullptr" << std::endl;
    }

    // Stampa gli elementi della lista
    int conta() const {
        int cont = 0;

        Nodo* temp = testa.get();
        while (temp) {
            cont++;
            temp = temp->successivo.get();
        }
        return cont;
    }


    // Rimuove il primo elemento con il i_dati specificati
    void elimina(T i_dati) {
        Nodo* temp = testa.get();
        Nodo* precedente = nullptr;

        // Se il nodo da rimuovere è la testa
        if (temp && temp->dati == i_dati) {
            testa = std::move(testa->successivo);
            if (!testa) {
                coda = nullptr;
            }
            return;
        }

        // Cerca il nodo da rimuovere
        while (temp && temp->dati != i_dati) {
            precedente = temp;
            temp = temp->successivo.get();
        }

        // Se il nodo non è stato trovato
        if (!temp) return;

        // Rimuove il nodo
        precedente->successivo = std::move(temp->successivo);
        if (!precedente->successivo) {
            coda = precedente;
        }
    }

    // Controlla se la lista è vuota
    bool vuota() const {
        return !testa;
    }

    bool inserisci_alla_posizione(int posizione, T i_dati)
    {
      int conta_nodi = 0;
      Nodo *temp = testa.get();

      if (posizione<0) return false;

      if (posizione == 0)
      {
        inserisci_in_testa(i_dati);
        return true;
      }
      else
      {
        while (temp && conta_nodi < posizione-1)
        {
          conta_nodi++;
          temp = temp->successivo.get();
        }

        if (temp)
        {
          auto nuovo = std::make_unique<Nodo>(i_dati);
          nuovo->successivo = std::move(temp->successivo);
          temp->successivo = std::move(nuovo);
          return true;
        }
        else
          return false;
      }

    }

};

//   struct Dati {
//      double * v;
//
//      Dati() { v = new double[50000];}
//   };

//   struct Dati {
//      double v[100];
//   };


    const long NUM_ELEMENTI = 1000;
    unsigned long v[NUM_ELEMENTI*2];

    //Dati vDati[NUM_ELEMENTI * 2];




int main() {
    ListaConcatenata<unsigned long> lista_numeri;

//    lista_numeri.inserisci_in_coda(1);
//    lista_numeri.inserisci_in_coda(2);
//    lista_numeri.inserisci_in_coda(3);
//    lista_numeri.inserisci_in_coda(4);
////
//    std::cout << "lista_numeri: ";
//
//    lista_numeri.elimina(1);
//    lista_numeri.elimina(4);
//    lista_numeri.elimina(4);
//    lista_numeri.elimina(2);
//    lista_numeri.elimina(3);
//
//
//
//
//    lista_numeri.inserisci_alla_posizione(-9, 999);
//    lista_numeri.stampa(); return 0;
//



    //carico metà vettore
    carica_vettore_interi(v, NUM_ELEMENTI);
    long inseriti = NUM_ELEMENTI;


    //creo una lista con gli stessi elementi
    for (int i=0; i<NUM_ELEMENTI; i++)
       lista_numeri.inserisci_in_coda(v[i]);

      //stampa_vettore_interi(v, inseriti);
      //cout << endl;
      //lista_numeri.stampa();
      //cout << endl << endl;

    int punto_inserimento = 0;
//    Dati da_inserire;
//    da_inserire.v[0] = 999;

    srand(5);

    Cronometro(Stato::START);
    for (int i=0; i<NUM_ELEMENTI; i++)
    {
      punto_inserimento = rand()%inseriti;
      //shift per inserire in punto_inserimento
      for (int j = inseriti; j>punto_inserimento; j--)
        v[j] = v[j-1];

      v[punto_inserimento] = 999; //da_inserire;  //999;
      inseriti ++;
    }
    //stampa_vettore_interi(v, inseriti);
    cout << endl;


    cout << "Tempo impiegato con vettore: " << Cronometro(Stato::STOP) << endl;

    //stesse operazioni con lista
    srand(5);
    inseriti = NUM_ELEMENTI;

    Cronometro(Stato::START);
    for (int i=0; i<NUM_ELEMENTI; i++)
    {
      punto_inserimento = rand()%inseriti;
      lista_numeri.inserisci_alla_posizione(punto_inserimento, 999);
      inseriti++;
    }

    cout << "Tempo impiegato con lista: " << Cronometro(Stato::STOP) << endl;

    //lista_numeri.stampa();

    return 0;
}