/*---------------------------------------------------------
pile
par Martin Robinson

-----------------------------------------------------------
preprocesseur
---------------------------------------------------------*/

#pragma once
#ifndef _PILE
#define _PILE

#include <assert.h>


/*---------------------------------------------------------
classe
---------------------------------------------------------*/
template <class TYPE>		
struct cellule{
	TYPE element;
	cellule * next;
	cellule (const TYPE& e, cellule * n)
	{
		element = e;
		next = n;
	}
};

template <class TYPE>
class pile{
		cellule<TYPE> * _top;	            // 1er élément de la pile
        cellule<TYPE>* stCopyR(cellule<TYPE> * , cellule<TYPE> * );
		void cellClear(cellule<TYPE>*);
                                    //copieur recursif
	public:
		pile();		                //constructeurr & destructeurr
		~pile();
		
		void push(const TYPE& e);	//ajoute un nouveau dessus
        void pop();					//enlève le dessus

        const TYPE& top() const;	//retourne le dessus, mais dépile pas
        int size()const;			//retourne le nb d’élément

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

        const pile<TYPE>& operator=(const pile<TYPE>& s);
                                    //affectateur
        bool operator==(const pile<TYPE>& s)const;
                                    //comparaison de 2 piles

};

/*--------------------------------------------
methode
--------------------------------------------*/

//constructeur
template <class TYPE>
pile<TYPE>::pile()
{
    _top = 0;
}

//destructeur
template <class TYPE>
pile<TYPE>::~pile()
{
    clear();
}

//ajouté un élément au sommet de la pile
template <class TYPE>
void pile<TYPE>::push(const TYPE& e)
{
    _top = new cellule<TYPE>(e,_top);
}

//enlevé la cellule du sommet de la pile
template <class TYPE>
void pile<TYPE>::pop()
{
    if(empty())
        return;
    cellule<TYPE> * tmp = _top->next;
    delete[] _top;
    _top = tmp;
}

//acquérir l'élément au sommet de la pile
template <class TYPE>
const TYPE& pile<TYPE>::top()const
{
    assert(_top);
    return _top->element;
}

//acquérir la taille de la pile
template <class TYPE>
int pile<TYPE>::size()const
{
    cellule<TYPE> * tmp = _top;
    int n=0;
    while (tmp)
    {
        tmp = tmp->next;
        n++;
    }
    return n;
}

//tester la videsse de la pile
template <class TYPE>
bool pile<TYPE>::empty()const
{
    return size()==0;
}

//vidé la pile
template <class TYPE>
void pile<TYPE>::clear()
{
    while(_top)
        pop();
}

//copieur
//privee
template <class TYPE>
void pile<TYPE>::cellClear(cellule<TYPE>* cell)
{
	if(cell->next)
		cellClear(cell->next);
	delete cell;
}

template <class TYPE>
cellule<TYPE> * pile<TYPE>::stCopyR(cellule<TYPE> * to, cellule<TYPE> * from)
{
	if (!to)
		to = new cellule<TYPE>(from->element,0);
	else
		to->element = from->element;
	if (from->next)
		to->next = stCopyR(to->next, from->next);
	else if (to->next)
	{
		cellClear(to->next);
		to->next = 0;
	}
	return to;
}

//publique
template <class TYPE>
const pile<TYPE>& pile<TYPE>::operator=(const pile<TYPE>& s)
{
	if (this != &s)
	{
		if (s._top)
			_top = stCopyR(_top, s._top);
		else
			clear();
    }

    return *this;
}

//comparateur
template <class TYPE>
bool pile<TYPE>::operator==(const pile<TYPE>& s)const
{
    //initialisation
    cellule<TYPE> * a = _top,
                  * b = s._top;
    //meme taille
    if(size() != s.size())
        return false;
    //toutes les valeurs pareilles
    while(a && b)
    {
        if (a->element != b->element)
            return false;
        a = a->next;
        b = b->next;
    }
    return true;
}


#endif