/*---------------------------------------------------------------
Nom Du Programme: pile.h
Auteur: Thibault Podevin
Date: 25 Octobre 2012
But: Objet qui reecrit la librairie stack afin de constituer des piles
-----------------------------------------------------------------*/

#ifndef PILE_H
#define PILE_H

#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

template <class T>
class pile
{
private:
        //Structure compossant les cases de la pile
        struct cellule
        {
            T element;                        //ellement en memoire
            cellule * suivant;                //poiteur vers la case suivante

            cellule(const T &e, cellule * s)  //constructeur de case
            {
                element = e;                  //ellement en memoire
                suivant = s;                  //poiteur vers la case suivante
            }
        };
        cellule * _premier;                   //poiteur vers la premiere case
        int _size;                            //taille de la pile
public:
    pile();                                   //constructeur
    ~pile();                                  //destructeur

    void push(const T & e);                   //ajoute une case au debut de la pile
    void pop();                               //suprime la derniere case ajouter

    const T & top() const;                    //renvoie l'element de la derniere case
    int size() const;                         //renvoie la taille de la pile

    bool empty() const;                       //verifie si la pile est vide
    void clear();                             //detruit la pile

    pile<T>& operator=(const pile<T>& p);     //surcharge de l'operateur =
    bool operator==(const pile<T>& p);        //surcharge de l'operateur ==
protected:
    cellule * copie (cellule * temp);         //methode proteger qui copie une pile dans une autre

};

//constructeur de la pile
template <class T>
pile<T>::pile()
{
    _premier = NULL;                          //initialise la premiere cellule a NULL
    _size = 0;                                //et la taille a 0

}

//destructeur de la pile
template <class T>
pile<T>::~pile()
{
    clear();                                  //detruit la pile
    delete _premier;                          //detruit le pointeur en memoire
}

//ajoute une case au debut de la pile
template <class T>
void pile<T>::push(const T & e)
{
    if(empty())                               //si la pile est vide
    {
        _premier = new cellule (e, NULL);     //initialise la premiere cellule
    }
    else
    {
        _premier = new cellule (e, _premier); //sinon creer en une autre avec la premiere cellule
    }
    _size++;                                  //augmente la taille
}

//suprime la derniere case ajouter
template <class T>
void pile<T>::pop()
{
    assert(!empty());                         //empeche le pop si la pile est deja vide
    _size--;                                  //reduit la taille de 1
    cellule * toDelete = _premier;            //creer une cellule temporaire qui contient la cellule a suprimer
    T e=_premier->element;                    //associe la valeur du suivant a la premiere cellule
    _premier = _premier->suivant;             //associe l'adresse du suivant a la premiere cellule
    delete toDelete;                          //supprime <<l'ancienne premiere>> cellule
}

//renvoie l'element de la derniere case
template <class T>
const T & pile<T>::top() const
{
    assert(_premier != NULL);                 //assertion si la cellule est vide
    return _premier->element;                 //retourne l'element
}

//renvoie l'element de la taille
template <class T>
int pile<T>::size() const
{
    return _size;
}

//verifie si la pile est vide
template <class T>
bool pile<T>::empty() const
{
    return !_size;                             //retourne false si la taille est 0
}

//detruit la pile
template <class T>
void pile<T>::clear()
{
    while(!empty())                            //tan que la pile est pleine,
        pop();                                 //supprime la derniere cellule
}

//methode proteger qui copie une pile de facons recursive dans une autre pile
template <class T>
typename pile<T>::cellule * pile<T>::copie(pile<T>::cellule * temp)
{
    if(temp!=NULL)                             //si la pile contien quelque chose
        return new cellule(temp->element, copie(temp->suivant));//creer une nouvelle cellule avec celle de la temporaire
    else
        return NULL;                           //tan que la fin de cette derniere n'est pas atteinte
}

//surcharge de l'operateur =
template <class T>
pile<T>& pile<T>::operator=(const pile<T>& p)
{
    if (this == &p) return *this;              //si c'est la meme pile qui est associer, renvois juste celle-ci
	clear();                                   //supprime la

	cellule *tempImplicite=NULL,               //creer une nouvelle cellule pour la pile implicite
			*tempExplicite=p._premier;         //creer une cellule temporaire pour la pile explicite
    _size=p._size;                             //associe la taille de la pile explicite pour que cette derniere soit pareil
	if(tempExplicite != NULL)                  //si la pile explicite est vide
	{
		_premier = copie(p._premier);          //apelle la methode de copie recursive
	}
    return *this;                              //renvoie la pile
}

//surcharge de l'operateur ==
template <class T>
bool pile<T>::operator==(const pile<T>& p)
{
    if (this == &p) return true;               //si c'est la meme pile qui est comparer, elle est forcement pareil
    if (_size != p._size) return false;        //mais si les tailles sont diferentes, elle sont differentes

	cellule *tempImplicite=_premier,           //creer une cellule temporaire pour la pile implicite
			*tempExplicite=p._premier;         //creer une cellule temporaire pour la pile explicite
    if(!p.empty())                             //si la pile n'est pas vide
    {
        while(tempImplicite == NULL)           //tan que la pile n'est pas fini d'etre parcourue
        {
            if(tempImplicite->element != tempExplicite->element)
                return false;                  //si les elements aux cellules pret ne sont pas egaux, renvois faux
            tempImplicite = tempImplicite -> suivant;//avance les cellules
            tempExplicite = tempExplicite -> suivant;
        }
    }
    else
        return false;

    return true;
}


#endif // PILE_H