#include <iostream>  // cout, cin

using namespace std;

struct t_coord
{
    double valeur;
    int indice; // 1 ? Dimension
    t_coord *suiv;
};

struct t_vecteur
{
    int dimension;
    double defaut;
    t_coord *tete;
};

void initialiser(t_vecteur &v, int d, double dft)
{
    v.dimension = d;
    v.defaut = dft;
    v.tete = nullptr;
}

void vider(t_vecteur &v)
{
    t_coord *tmp;
    tmp = v.tete;

    while(tmp != nullptr)
    {
        t_coord *n = tmp->suiv;
        delete tmp;
        tmp = n;
    }

    delete tmp;
    v.tete = nullptr;
}

void modifier(t_vecteur &v, int i, double val)// on suppose l'indice <= dimension
(precondition)
{
    if(v.tete != nullptr)// il y a au moins une valeur significative
    {
        t_coord *svt = v.tete; // on stock le premier maillon
        t_coord *prv = nullptr;// et celui avant lui donc nullptr au debut
        while(svt != nullptr && svt->indice < i) // en gros ici on va chercher le
premier maillon dont l'indice est >= ? i
        {                                        //comme ca on ajoute le nouveau
maillon dans un ordre logique par rapport aux indices et pas en vrac
            prv = svt;
            svt = svt->suiv;
        }

        if(svt != nullptr) // Si indice >= i (en effet si != nullptr alors la boucle
s'est forcement arret?e a cause de la 2?me condition)
        {
            if(svt->indice == i)// Si indice = 1
            {
                if(val != v.defaut) // et que la valeur != defaut, on remplace
                {
                    svt->valeur = val;
                }
                else // sinon on supprime car le maillon n'est plus significatif
                {
                    if(prv == nullptr) // donc si il n'y avait que la tete
                        vider(v); // on vide car on a remplac? par une valeur par
defaut (cf le if/else au dessus)
                    else // si il y avait plus que 1 maillon
                    {
                        if(svt->suiv != nullptr) // et que ce n'est pas le dernier
du chainage
                        {
                            prv->suiv = svt->suiv; // on court circuite
                            delete svt; // on degage le 'flottant'
                            svt = nullptr; // peut etre pas obligatoire, par
securite on fais ca quand meme
                        }
                        else // si c'etait le dernier maillon du chainage
                        {
                            delete svt; // on le supprime
                            prv->suiv = nullptr; // on fait pointer celui d'avant
sur null et pas random zone memoire
                        }
                    }
                }
            }
            else // si l'indice est superieur ? i
            {
                if(val != v.defaut) // on ajoute avant svt si necessaire (donc si
pas valeur par defaut)
                {
                    t_coord *nouveau = new t_coord;
                    nouveau->indice = i;
                    nouveau->valeur = val;
                    nouveau->suiv = svt;
                    if(prv == nullptr)
                    {
                        v.tete = nouveau;
                    }
                    else
                        prv->suiv = nouveau;
                }
            }
        }
        else //si null alors ce la implique que prv a un indice < i donc on ajoute
apres prv
        {
            t_coord *nouveau = new t_coord;
            nouveau->indice = i;
            nouveau->valeur = val;
            prv->suiv = nouveau;
        }
    }
    else // il n'y a aucune coord significatives pour le moment
    {
        if(val != v.defaut) // on cr?e le premier maillon si necessaire
        {
            v.tete = new t_coord;
            v.tete->indice = i;
            v.tete->valeur = val;
            v.tete->suiv = nullptr;
        }
    }
}

void saisir(t_vecteur &v)
{
    int r = 0;
    cout << "###### Nouvelle Saisie ######\n" << endl;
    cout << "Avez vous une coordonn?e significative ? rajouter? (0 pour non, 1 pour
oui)" << endl;
    cin >> r;
    bool termine = r == 0? true:false;
    while(!termine)
    {
        int ind = 0;
        int val = 0;
        cout << "A quel indice voulez vous rajouter une valeur significative?" << endl;
        cin >> ind;
        cout << "Quelle valeur? (diffente de " << v.defaut << ")" << endl;
        cin >> val;
        modifier(v,ind,val);

        cout << "\n\n Bien recu, Avez vous une autre coordonn?e significative ?
rajouter? (0 pour non, 1 pour oui)" << endl;
        cin >> r;
        termine = r == 0? true:false;
    }
}


// pas tres efficace comme algo mais ?a fait le taff
void afficher(t_vecteur v, bool complet)
{
    cout << "[" ;
    if(complet)
    {
        for(int i = 1; i<=v.dimension;i++) // indice commence a 1
        {
            t_coord *tmp = v.tete;

            while(tmp != nullptr && tmp->indice < i)
            {
                tmp = tmp->suiv;
            }
            if(tmp != nullptr && tmp->indice == i)
            {
                cout << tmp->valeur << ",";
            }
            else
            {
                cout << v.defaut << ",";
            }
        }
        cout << "\b";
    }
    else
    {
        for(int i = 1; i<=v.dimension;i++) // indice commence a 1
        {
            t_coord *tmp = v.tete;

            while(tmp != nullptr && tmp->indice < i)
            {
                tmp = tmp->suiv;
            }
            if(tmp != nullptr && tmp->indice == i)
            {
                cout << "I"<< i << ":" <<tmp->valeur << ",";
            }
        }
        cout << "\b"; // on supprime la derniere virgule
    }

    cout << "]" << endl;
}

t_vecteur somme (t_vecteur v1, t_vecteur v2)
{
    t_vecteur res;
    initialiser(res,v1.dimension,v1.defaut+v2.defaut);

    t_coord *t1 = v1.tete;
    t_coord *t2 = v2.tete;

    while(t1 != nullptr || t2 != nullptr)
    {
        if(t1 != nullptr && t2 != nullptr)
        {
            if(t1->indice == t2->indice)
            {
                modifier(res,t1->indice,((t1->valeur)+(t2->valeur)));
                t1 = t1->suiv;
                t2 = t2->suiv;
            }
            else
            {
                if(t1->indice < t2->indice)
                {
                    modifier(res,t1->indice,t1->valeur + v2.defaut);
                    t1 = t1->suiv;
                }
                else
                {
                    modifier(res,t2->indice,t2->valeur + v1.defaut);
                    t2 = t2->suiv;
                }
            }
        }
        else if(t1 == nullptr)
        {
            modifier(res,t2->indice,t2->valeur+v1.defaut);
            t2 = t2->suiv;
        }
        else
        {
            modifier(res,t1->indice,t1->valeur+v2.defaut);
            t1 = t1->suiv;
        }
    }

    return res;
}

t_vecteur produit (t_vecteur v1, t_vecteur v2)
{
    t_vecteur res;
    initialiser(res,v1.dimension,v1.defaut*v2.defaut);

    t_coord *t1 = v1.tete;
    t_coord *t2 = v2.tete;

    while(t1 != nullptr || t2 != nullptr)
    {
        if(t1 != nullptr && t2 != nullptr)
        {
            if(t1->indice == t2->indice)
            {
                modifier(res,t1->indice,((t1->valeur)*(t2->valeur)));
                t1 = t1->suiv;
                t2 = t2->suiv;
            }
            else
            {
                if(t1->indice < t2->indice)
                {
                    modifier(res,t1->indice,t1->valeur * v2.defaut);
                    t1 = t1->suiv;
                }
                else
                {
                    modifier(res,t2->indice,t2->valeur * v1.defaut);
                    t2 = t2->suiv;
                }
            }
        }
        else if(t1 == nullptr)
        {
            modifier(res,t2->indice,t2->valeur*v1.defaut);
            t2 = t2->suiv;
        }
        else
        {
            modifier(res,t1->indice,t1->valeur*v2.defaut);
            t1 = t1->suiv;
        }
    }

    return res;
}


//question optionelle, pas super optimis? comme algo mais ca marche
t_vecteur conversion (double t[],int taille)
{
    double popVal = t[0];
    int occurMax = 0;

    for(int i = 0; i<taille;i++)
    {
        int compteur = 1;
        for(int j = i+1; j<taille;j++)
        {
            if(t[i] == t[j]) compteur++;
        }
        if(compteur > occurMax)
        {
            occurMax = compteur;
            popVal = t[i];
        }
    }

    t_vecteur res;
    res.dimension = taille;
    res.defaut = popVal;

    for(int i = 0; i<taille;i++)
    {
        if(t[i] != popVal)
        {
            modifier(res,i+1,t[i]);
        }
    }

    return res;
}

int main()
{
    /*t_vecteur vecteur;
    t_vecteur v2;
    initialiser(v2,10000000,1);
    initialiser(vecteur,10000000,0);
    saisir(v2);
    saisir(vecteur);
    //afficher(vecteur,false);
    //afficher(v2,false);

    t_vecteur som = somme(v2,vecteur);
    afficher(som,false);
    t_vecteur prod = produit(v2,vecteur);
    afficher(prod,false);

    vider(v2);
    vider(vecteur);
    vider(som);
    vider(prod);*/



    // ### test de la partie optionnelle ###
    double t[10] = {1,0,2,3,0,4,5,0,4,6};
    t_vecteur t2v = conversion(t,10);
    afficher(t2v,true);

    vider(t2v);



    return 0;
}