/**

 BINOME :
 <NOM1> <Prenom1>
 <NOM2> <Prenom2>

 FONCTIONS NON TRAITEES :
 <
 Lister ici les fonctions non developpees et/ou non testees. Exemple :
 - occurrences : non developpee
 - occurrences_rec : non testee

 >

 SOURCES UTILISEES :
 <
 Lister ici les sources utilisees pour faire ce TP : Internet, livres, autres
 élèves, etc. à l'exclusion du cours et des TD. Indiquer "Aucune" si aucune
 source n'a été utilisée.
 >

 */

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

/******************************************************************************
 1- DEFINITIONS COMMUNES AUX TYPES PILE ET FILE
 ******************************************************************************/

// Cette directive selectionne l'implementation "tableau" des piles et files. La
// commenter pour selectionner l'implementation "liste chaînée".
//#define IMPL_TABL

#ifdef IMPL_TABL

// Nombre maximal d'éléments géré par une pile ou une file
#define MAX_ELEM 10

#else

// Définition d'un maillon et d'une liste
typedef struct maillon {
	int info;
	struct maillon* suiv;
} maillon;

typedef maillon* liste;

#endif


/******************************************************************************
 2- DEFINITION DES TYPES PILE ET FILE
 ******************************************************************************/

//
// DEFINITION d'une pile
//
  typedef struct pile {
#ifdef IMPL_TABL
    int elements[MAX_ELEM];
    int sommet;
#else
    liste elements;
    unsigned int taille;
#endif
 } pile;

//
// DEFINITION d'une file
//
  typedef struct file {
#ifdef IMPL_TABL
     int elements[MAX_ELEM + 1];
     int debut;
     int fin;
#else
    maillon* debut;
    maillon* fin;
    unsigned int taille;
#endif
 } file;

// Note : il faut laisser un élément du tableau inutilisé pour
// distinguer les cas :
// - file vide : fin == debut
// - file pleine : SUCC(fin) == debut
// Le tableau fait donc (MAX_ELEM + 1) éléments pour faire que
// la file puisse contenir jusqu'à MAX_ELEM éléments.


/******************************************************************************
 3- FONCTIONS DE MANIPULATION D'UNE PILE
 ******************************************************************************/

/**
 * Sert à initialiser une variable de type pile à "pile vide".
 *
 * Retourne : la valeur d'initialisation d'une pile vide.
 */
pile initPile() {
    pile p;
    #ifdef IMPL_TABL
        p.sommet = 0;
    #else
        p.taille = 0;
    #endif
    return p;
}

/**
 * Détermine la taille d'une pile.
 *
 * Paramètre p : pile à examiner.
 *
 * Retourne : la taille de p.
 */
int taillePile(pile p) {
    int taille;
    #ifdef IMPL_TABL
        taille = p.sommet;
    #else
        taille = p.taille;
    #endif
    return taille;
}

/**
 * Détermine si une pile est vide.
 *
 * Paramètre p : pile à tester.
 *
 * Retourne : 1 si p est vide et 0 sinon.
 */
int estPileVide(pile p) {
#ifdef IMPL_TABL
    if(p.sommet == 0)
        return 1;
    else
        return 0;
#else
    if(p.taille == 0)
        return 1;
    else
        return 0;
#endif
}

/**
 * Détermine l'élément au sommet d'une pile.
 *
 * Paramètre p : pile à examiner.
 * Paramètre e : sommet de la pile retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int sommet(pile p, int* e) {
#ifdef IMPL_TABL
    for(int i = 0; i < p.sommet; i++)
        *e = p.elements[i];
#else
    int cpt = 0;
    if(p.elements == NULL)
        *e = 0;
    else
        *e = p.elements->info;
    return 1;
#endif
}

/**
 * Empile un élément sur une pile.
 *
 * Paramètre p : pile sur laquelle empiler.
 * Paramètre e : élément à empiler.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int empiler(pile* p, int e) {
#ifdef IMPL_TABL
    if(p->sommet >= MAX_ELEM)
        return 0;
    else
    {
        p->elements[p->sommet] = e;
        p->sommet = p->sommet + 1;
        return 1;
    }
#else
    maillon* m;
    m = new maillon;
    m->info = e;
    m->suiv = p->elements;

    p->elements = m;

    p->taille += 1;
#endif
}

/**
 * Dépile un élément d'une pile.
 *
 * Paramètre p : pile de laquelle dépiler.
 * Paramètre e : élément dépilé.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int depiler(pile* p, int* e) {
#ifdef IMPL_TABL
    int cpt = 0;
    if(p->sommet == 0)
        return 0;

    while(cpt < p->sommet)
    {
        cpt++;
    }
    *e = p->elements[p->sommet];
    p->sommet -= 1;
    return 1;
#else
    if(p->elements == NULL) return 0;

    *e = p->elements->info;
    maillon* maille = p->elements;

    p->elements = p->elements->suiv;
    p->taille--;

    delete maille;
    return 1;

#endif
}


/******************************************************************************
 4- FONCTION DE MANIPULATION D'UNE FILE
 ******************************************************************************/

/**
 * Sert à initialiser une variable de type file à "file vide".
 *
 * Retourne +: la valeur d'initialisation d'une file vide.
 */
file initFile() {
    file f;
#ifdef IMPL_TABL
    f.debut = 0;
    f.fin = 0;
#else
    f.debut = 0;
    f.fin = 0;
    f.taille = 0;
#endif
return f;
}

/**
 * Détermine la taille d'une file.
 *
 * Paramètre f : file à examiner.
 *
 * Retourne : la taille de f.
 */
int tailleFile(file f) {
    int taille = 0;
#ifdef IMPL_TABL
    taille = f.fin - f.debut;
#else
    taille = f.taille;
#endif
    return taille;
}

/**
 * Détermine si une file est vide.
 *
 * Paramètre f : file à tester.
 *
 * Retourne : 1 si f est vide et 0 sinon.
 */
int estFileVide(file f) {
#ifdef IMPL_TABL
    if(f.debut == f.fin)
        return 1;
    else
        return 0;
#else
    if(f.taille == 0)
        return 1;
    else
        return 0;
#endif
}

/**
 * Détermine l'élément au début d'une file.
 *
 * Paramètre f : file à examiner.
 * Paramètre e : début de la file retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int debut(file f, int* e) {
#ifdef IMPL_TABL
    *e = f.debut;
#else
    if(f.debut == NULL)
        *e = 0;
    else
        *e = f.debut->info;
#endif
return 1;
}

/**
 * Détermine l'élément à la fin d'une file.
 *
 * Paramètre f : file à examiner.
 * Paramètre e : fin de la file retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int fin(file f, int* e) {
#ifdef IMPL_TABL
    *e = f.fin;
#else
    if(f.fin == NULL)
        *e = 0;
    else
        *e = f.fin->info;
#endif
return 1;
}

/**
 * Enfile un élément dans une pile.
 *
 * Paramètre f : file dans laquelle enfiler.
 * Paramètre e : élément à enfiler.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int enfiler(file* f, int e) {
#ifdef IMPL_TABL
    throw "non traité";
#else
    maillon* m = new maillon;
    m->info = e;
    m->suiv = NULL;

    if(f->debut == NULL)
        f->debut = m;
    else
        f->fin->suiv = m;
    f->fin = m;
    f->taille++;
    return 1;
#endif
}

/**
 * Défile un élément d'une file.
 *
 * Paramètre f : file de laquelle défiler.
 * Paramètre e : élément défilé.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int defiler(file* f, int* e) {
#ifdef IMPL_TABL
    throw "non traité";
#else
    if(f->debut == f->fin) return 0;
    *e = f->debut->info;
    maillon* maille = f->debut;
    f->debut = f->debut->suiv;
    f->taille--;
    delete maille;

    return 1;
#endif
}


/******************************************************************************
 5- EXERCICES D'APPLICATION
 ******************************************************************************/

/**
 * Inverse l'ordre des éléments d'une file.
 *
 * Paramètre f : file à inverser.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int inverser(file* f) {
    throw "non traité";
}

/**
 * Fusionne une collection de files d'entrées triées par ordre décroissant de
 * leurs éléments en une unique file de sortie triéee par ordre décroissant de
 * ses éléments. Les doublons éventuels ne sont pas supprimés. Après exécution,
 * toutes les files d'entrée sont vides.
 *
 * Exemple d'exécution :
 * - files en entrée : <11, 5, 4< ; <7< ; <10, 5, 5, 1<
 * - file en sortie : <11, 10, 7, 5, 5, 5, 4, 1<
 *
 * Paramètre fe : tableau des files d'entrées.
 * Paramètre nfe : nombre de files dans fe.
 * Paramètre fs : file de sortie.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int fusionner(file* fe, int nfe, file* fs) {
    throw "non traité";
}

/**
 * Décompose une file d'entrée en une collection de file de sorties triées par
 * ordre décroissant de leurs éléments. Les doublons éventuels ne sont pas
 * supprimés. Après exécution, la file d'entrée est vide.
 *
 * Exemple d'exécution :
 * - file en entrée : <1, 7, 7, 2, 4, 5, 0<
 * - files en sortie : <1, 0< ; <7, 7, 2< ; <4< ; <5<
 *
 * Paramètre fe : file d'entrée à décomposer.
 * Paramètre fs : tabeau des files de sortie.
 * Paramètre nfs : nombre de files dans fs.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int decomposer(file* fe, file** fs, int* nfs) {
    throw "non traité";
}

/**
 * Trie une file dans l'ordre décroissante de ses éléments.
 *
 * Paramètre f : file à trier.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int trier(file* f) {
    throw "non traité";
}

/**
 * Evalue une expression booléenne post-fixée. Les opérateurs sont '+' (ou),
 * '*' (et), '^' (ou exclusif) et '!' (négation) ; les opérandes sont les
 * constantes 0 (faux) et 1 (vrai).
 *
 * Exemple d'exécution :
 * - évaluation de "1 0 + !" : 0
 * - évaluation de  "0 1 ! * 1 +" : 1
 * - évaluation de "0 1" ou "1 + 0" ou "" : -1 (expressions incorrectes)
 *
 * Paramètre e : expression à évaluer.
 *
 * Retourne : l'évaluation de e ou -1 si échec.
 */
int evaluer(const char* e) {
    throw "non traité";
}


/******************************************************************************
 FONCTIONS UTILITAIRES - Construction et affichage de piles et files
 ******************************************************************************/

/**
 * Convertit un tableau d'entiers en une pile. Le premier élément correspond au
 * sommet de la pile, le dernier au fond.
 *
 * Parametre n : le nombre d'éléments de t.
 * Parametre t : tableau d'entiers à convertir.
 *
 * Retourne : la pile équivalente à t.
 */
pile pilet(int n, const int t[]) {
    pile r = initPile();
    for (int i = 0; i < n; i++) {
        empiler(&r, t[n - 1 - i]);
    }
    return r;
}

/**
 * Représente une pile sous la forme d'une chaine de caractères. Le premier élément
 * listé est le sommet de la pile, le dernier le fond.
 *
 * Parametre p : pile à représenter.
 *
 * Retourne : la chaîne représentant p.
 */
string chainep(pile* p) {
    if (estPileVide(*p)) {
        return "<|";
    }
    ostringstream s;
    pile t = initPile();
    s << "<";
    // parcours DESTRUCTIF de la pile
    while (!estPileVide(*p)) {
        int e;
        depiler(p, &e);
        empiler(&t, e);
        s << e << ", ";
    }
    // pile à RECONSTRUIRE juste apres
    while (!estPileVide(t)) {
        int e;
        depiler(&t, &e);
        empiler(p, e);
    }
    // remplacer le dernier ", " par "|" (fond de pile)
    string r = s.str();
    return r.replace(r.size() - 2, r.size(), "|");
}

/**
 * Convertit un tableau d'entiers en une file. Le premier élément correspond au
 * debut de la file, le dernier à la fin.
 *
 * Parametre n : le nombre d'éléments de t.
 * Parametre t : tableau d'entiers à convertir.
 *
 * Retourne : la file équivalente à t.
 */
file filet(int n, const int t[]) {
    file r = initFile();
    for (int i = 0; i < n; i++) {
        enfiler(&r, t[i]);
    }
    return r;
}

/**
 * Représente une file sous la forme d'une chaine de caractères. Le premier élément
 * listé est le début de la file, le dernier la fin.
 *
 * Parametre f : file à représenter.
 *
 * Retourne : la chaîne représentant f.
 */
string chainef(file* f) {
    if (estFileVide(*f)) {
        return "<<";
    }
    ostringstream s;
    int t = tailleFile(*f);
    s << "<";
    // parcours reconstructif de la file
    for (int i = 0; i < t; i++) {
        int e;
        defiler(f, &e);
        enfiler(f, e);
        s << e << ", ";
    }
    // remplacer le dernier ", " par "<" (fin de file)
    string r = s.str();
    return r.replace(r.size() - 2, r.size(), "<");
}


/******************************************************************************
 PROGRAMME DE TEST - Tester ici chaque fonction developpee
 ******************************************************************************/



int main() {

    pile p;
    file f;
    int e;
    int g;
    int s = 0;
    int first;
    int last;
    string test;

    #ifdef IMPL_TABL
    cout << "-------------- Par tableaux --------------" << endl << endl;
    #else
    cout << "-------------- Par liste chainee --------------" << endl << endl;
    #endif

    //
    // TESTS D'UNE PILE
    //

    cout << "-------- Test Pile (vide) --------" << endl;
    p = initPile();
    sommet(p, &s);
    #ifdef IMPL_TABL
    for(int i = p.sommet - 1; i >= 0; i--)
        cout << p.elements[i] << endl;
    #else
    test = chainep(&p);
    cout << "[" << test << "]" << endl << endl;
    #endif

    cout << "Taille pile : " << taillePile(p) << " | ";
    cout << "Pile vide : " << estPileVide(p) << " | ";
    cout << "Sommet pile : " << s << endl << endl;

    cout << "-------- Test Empilement (2, 1, 5, 3, 7 puis 8) --------" << endl;

    empiler(&p, 2);
    empiler(&p, 1);
    empiler(&p, 5);
    empiler(&p, 3);
    empiler(&p, 7);
    empiler(&p, 8);

    sommet(p, &s);

    cout << "Affichage de la pile : " << endl;
    #ifdef IMPL_TABL
    for(int i = p.sommet - 1; i >= 0; i--)
        cout << p.elements[i] << endl;
    #else
    test = chainep(&p);
    cout << "[" << test << "]" << endl << endl;
    #endif

    cout << "Taille pile : " << taillePile(p) << " | ";
    cout << "Pile vide : " << estPileVide(p) << " | ";
    cout << "Sommet pile : " << s << endl << endl;

    cout << "-------- Test Depilement (3 depilements) --------" << endl;

    depiler(&p, &e);
    depiler(&p, &e);
    depiler(&p, &e);

    sommet(p, &s);

    #ifdef IMPL_TABL
    for(int i = p.sommet - 1; i >= 0; i--)
        cout << p.elements[i] << endl;
    #else
    test = chainep(&p);
    cout << "[" << test << "]" << endl << endl;
    #endif

    cout << "Taille pile : " << taillePile(p) << " | ";
    cout << "Pile vide : " << estPileVide(p) << " | ";
    cout << "Sommet pile : " << s << endl << endl;

    //
    // TESTS D'UNE FILE
    //

    cout << "-------- Test File (vide) --------" << endl;
    f = initFile();
    debut(f, &first);
    fin(f, &last);

    cout << "Taille file : " << tailleFile(f) << " | ";
    cout << "File vide : " << estFileVide(f) << " | ";
    cout << "Debut file : " << first << " | ";
    cout << "Fin file : " << last << endl;

    enfiler(&f, 1);
    enfiler(&f, 2);
    enfiler(&f, 3);
    enfiler(&f, 4);
    enfiler(&f, 5);
    enfiler(&f, 6);

    debut(f, &first);
    fin(f, &last);

    cout << "Taille file : " << tailleFile(f) << " | ";
    cout << "File vide : " << estFileVide(f) << " | ";
    cout << "Debut file : " << first << " | ";
    cout << "Fin file : " << last << endl;

    test = chainef(&f);
    cout << "[" << test << "]" << endl << endl;

    defiler(&f, &g);
    defiler(&f, &g);
    defiler(&f, &g);
    defiler(&f, &g);

    debut(f, &first);
    fin(f, &last);

    cout << "Taille file : " << tailleFile(f) << " | ";
    cout << "File vide : " << estFileVide(f) << " | ";
    cout << "Debut file : " << first << " | ";
    cout << "Fin file : " << last << endl;

    test = chainef(&f);
    cout << "[" << test << "]" << endl << endl;
    //
    // TESTS inverser()
    //

    //
    // TESTS fusionner()
    //

    //
    // TESTS decomposer()
    //

    //
    // TESTS trier()
    //

    //
    // TESTS evaluer()
    //

	return 0;
}