#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<cmath>

using namespace std;

/* Fonction gamma
Renvoi le numéro d'un couple d'entier
Entrée : 2 entiers correspondant au couple
Sortie : 1 entier, le numéro du couple
*/
int gamma(int,int);

/* Fonction degamma
A partir d'un entier renvoi le couple d'entier correspondant
Entrée : un entier, le numéro du couple recherché
Sortie : une file d'entiers contenant les 2 entiers du couple
*/
queue<int> degamma(int);

/* Fonction codage version récursive
Renvoi le numéro (un entier) d'un schéma et d'une liste d'entier associé à ce schéma
Entrée : une file de caractère contenant le schéma
                 une file d'entier contenant la liste d'entier
Sortie : un entier correspondant au numéro recherché
*/
int codageRecur(queue<char>,queue<int>);

/* Fonction codage version itérative
Renvoi le numéro (un entier) d'un schéma et d'une liste d'entier associé à ce schéma
Entrée : une pile de caractère contenant le schéma
                 une pile d'entier contenant la liste d'entier
Sortie : un entier correspondant au numéro recherché
*/
int codageIte(stack<char>,stack<int>);

/* Fonction décodage version itérative
Renvoi une liste d'entier à partir d'un schéma et d'un entier
Entrée : une file de caractère contenant le schéma
                 un entier correspondant à un numéro
Sortie : une file d'entier
*/
queue<int> decodageIte(int, queue<char>);

/* Fonction décodage version récursive
Renvoi une liste d'entier à partir d'un schéma et d'un entier
Entrée : une file de caractère contenant le schéma
                 un entier correspondant à un numéro
Sortie : une file d'entier
*/
queue<int> decodageRecur(int,queue<char>);

int main(){
        queue<char> schema,schemaDec;
        queue<int> liste,couple,resultdi,resultdr;
        stack<char> schemaIt;
        stack<int> listeIt;
        int i,j,tsch=0,nbrep=0,c=0,e,n;
        string sch,schd;


        //------------------------------------------------------------------------------
        /* Test de la fonction gamma */
        // Affection des valeurs des paramètres pour gamma
        cout << "GAMMA ET DEGAMMA" << endl << "Pour gamma : ";
        cout << "Donner i et j" << endl << "i = ";
        cin >> i;
        cout << "j = ";
        cin >> j;
        // Affichage du résultat
        cout << "Le couple ("<<i<<","<<j<<") a pour numéro : "<<gamma(i,j)<<endl;

        /* Test de la fonction degamma */
        // Affection de la valeur du paramètre de degamma
        cout << "Entrez un numéro n : ";
        cin >> n;
        couple = degamma(n);
        // Affichage du résultat
        cout << n << " est le numéro du couple (" << couple.front() <<","<< couple.back() <<")" << endl;
        cout << "----------------------------" << endl;

        //------------------------------------------------------------------------------
        /* Test des fonctions codage récursive et itérative */
        // Affection des valeurs des paramètres pour codage
        cout << "CODAGE ITERATIF ET RECURSIF" << endl;
        cout << "Entrez le schéma (ex : g.. ou gg...): ";
        cin >> sch;
        while(true){
                if(tsch == sch.size()) break;
                if(sch[tsch] == '.') nbrep++; //On compte le nombre de point pour controler le nombre d'entier présent dans la liste
                schema.push(sch[tsch]);
                schemaIt.push(sch[tsch]);
                tsch++;
        }

        cout << "Il y a dans votre schéma "<<nbrep<<" '.'. Vous pouvez donc entrer "<<nbrep<<" entiers dans votre liste :"<<endl;
        while(true){
                if(c==nbrep) break;
                cout << "Entrez un entier : ";
                cin >> e;
                liste.push(e);
                listeIt.push(e);
                c++;
        }
        // Affichage du résultat de codage récursif
        cout << "Version récursive : le numéro correspondant au schéma avec la liste d'entiers est = " << codageRecur(schema,liste)<< endl;

        // Affichage du résultat de codage récursif
        cout << "Version itératif : le numéro correspondant au schéma avec la liste d'entiers est = " << codageIte(schemaIt,listeIt)<< endl;
        cout << "----------------------------" << endl;

        //------------------------------------------------------------------------------
        /* Test des fonctions décodage récursive et itérative */
        // Affection de la valeur des paramètres
        cout << "DECODAGE ITERATIF ET RECURSIF" << endl;
        cout << "Entrez un numéro n : ";
        cin >> n;

        cout << "Entrez le schéma (ex : g.. ou gg...): ";
        cin >> schd;

        tsch = 0;
        while(true){
                if(tsch == schd.size()) break;
                schemaDec.push(schd[tsch]);
                tsch++;
        }

        // Affichage du résultat

        resultdi = decodageIte(n,schemaDec);
        resultdr = decodageRecur(n,schemaDec);

        cout << "Le resultat de decodage version itératif est l'ensemble d'entier: (" << resultdi.front();
        resultdi.pop();
        while(true){
                if(resultdi.empty()) break;
                cout << "," << resultdi.front();
                resultdi.pop();
        }
        cout << ")" << endl;

        cout << "Le resultat de decodage version récursif est l'ensemble d'entier: (" << resultdr.front();
        resultdr.pop();
        while(true){
                if(resultdr.empty()) break;
                cout << "," << resultdr.front();
                resultdr.pop();
        }
        cout << ")" << endl;

        system("pause");
}

//------------------------------- GAMMA - DEGAMMA --------------------------------------------------------------------

/* Fonction gamma */
int gamma(int i,int j){
        if(i<=j) return(j*j+i); // n = j²+i si i<=j
        if(i>j) return(i*i+(2*i-j)); // n = i²+2i-j si i > j
}

/* Fonction degamma */
/* Pour obtenir la racine carré on utilise la fonction sqrt de la librairie cmath
   La fonction sqrt prend en entrée un nombre de type double et retourne un double
   La fonction fmod() renvoie le reste de la division
*/
queue<int> degamma(int n){
        queue<int> couple;

        double nd = n; // On convertit en double l'entier n pour calculer la racine avec sqrt
        double racd = sqrt(nd);

        int rac = (int)(racd);// A partir de la racine de type double on obtient un entier sans la virgule pour calculer le modulo avec n
        double racvrg = (double)(rac+(0.5)); //On rajoute 0,5,racvrg permet de trouver la position de n


        if(fmod(nd,racd) ==0){ // si i = 0 alors j = racine(n)
                couple.push(0);
                couple.push(rac);
                return(couple);
        }else{
                if(racd < racvrg){
                        couple.push(n-(rac*rac)); // i = n - rac²
                        couple.push(rac); // j = racine(n)
                        return(couple);
                }else{
                        couple.push(rac); // i = rac
                        couple.push((rac*rac)+(2*rac)-n); // j = i²+2i-n
                        return(couple);
                }

        }
}

//------------------------------- CODAGE --------------------------------------------------------------------
/* Fonction codage version récursive */
int codageRecur(queue<char> sch,queue<int> lst){
        int nbrep=0,nbreg=0;
        queue<char> fg,fd;
        queue<int> lstg,lstd;

        if(sch.front() == '.') return(lst.front()); // Condition d'arret de la recursivité

        sch.pop(); // On supprime le 1er 'g'
        while(true){ // Calcul des fils droit et gauche, des listes d'entiers s1(lstg) et s2(lstd)
                if(sch.empty()) break;

// tant que le nombre de . est inférieur au nombre de g, on met les g et les . dans le fils gauche
                if(nbrep>nbreg){
                        fd.push(sch.front());
                        if(sch.front()=='.'){ // Si le caractère courant est . on rentre dans s2 le 1er entier de la liste
                                lstd.push(lst.front());
                                lst.pop();
                        }
                }else{
                        fg.push(sch.front());
                        if(sch.front()=='.'){ // Si le caractère courant est . on rentre dans s1 le 1er entier de la liste
                                lstg.push(lst.front());
                                lst.pop();
                        }
                        if(sch.front() == '.'){ // Calcul du nombre de . et de g
                                nbrep++;
                        }else{
                                nbreg++;
                        }
                }

                sch.pop();
        }

        int x = codageRecur(fg,lstg); // Récursivité
        int y = codageRecur(fd,lstd); // Récursivité

        return(gamma(x,y));
}

/* Fonction codage version itérative */
int codageIte(stack<char> sch,stack<int> lst){
        // La pile qui va contenir les résultats de la fonction gamma donc le résultat final
        stack<int> n;

        while(true){
                if(sch.empty()) break;

                if(sch.top() == '.'){
                        n.push(lst.top());
                        sch.pop();
                        lst.pop();
                }else{
                        int x = n.top();
                        n.pop();
                        int y = n.top();
                        n.pop();
                        n.push(gamma(x,y));
                        sch.pop();

                }
        }

        return n.top();
}

//------------------------------- DECODAGE --------------------------------------------------------------------

/* Fonction decodage version itérative */
queue<int> decodageIte(int n, queue<char> schema){
        queue<int> listentier,temp;
        stack<int> resultdg;

        resultdg.push(n);
        while(true){
                if(schema.empty()) break;

                if(schema.front() == '.'){
                        listentier.push(resultdg.top());
                        resultdg.pop();
                        schema.pop();
                }else{
                        temp = degamma(resultdg.top());
                        resultdg.pop();
                        resultdg.push(temp.back());
                        resultdg.push(temp.front());
                        temp.pop();
                        temp.pop();
                        schema.pop();
                }
        }

        return listentier;
}

/* Fonction decodage version récursive */
queue<int> decodageRecur(int n,queue<char> sch){
        queue<int> rdegamma,liste,temp;
        queue<char> fd,fg;
        int nbrep=0,nbreg=0;

        if(sch.front() == '.'){ // Condition d'arret de la récursivité
                queue<int> listentier;
                listentier.push(n);
                return listentier;
        }

        sch.pop(); // On supprime le 1er 'g'
        while(true){ // Calcul des fils droit et gauche, des listes d'entiers s1(lstg) et s2(lstd)
                if(sch.empty()) break;

// tant que le nombre de . est inférieur au nombre de g, on met les g et les . dans le fils gauche
                if(nbrep>nbreg){
                        fd.push(sch.front());
                }else{
                        fg.push(sch.front());
                        if(sch.front() == '.'){ // Calcul du nombre de . et de g
                                nbrep++;
                        }else{
                                nbreg++;
                        }
                }

                sch.pop();
        }

        rdegamma = degamma(n);

        temp = decodageRecur(rdegamma.front(),fg); // Récursivité
        // On récupére le contenu du résultat de la récursivité pour le fils gauche
        while(true){
                if(temp.empty()) break;
                liste.push(temp.front());
                temp.pop();
        }

        temp = decodageRecur(rdegamma.back(),fd); // Récursivité
        // On récupére le contenu du résultat de la récursivité pour le fils droit
        while(true){
                if(temp.empty()) break;
                liste.push(temp.front());
                temp.pop();
        }

        return liste;

}