/*
* list.h
*
* Copyright
* (C) 2005 VANDERBRUGGEN Thomas <tvanderbruggen@yahoo.fr>
*
* Created on 22/05/2005
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#ifndef __LIST__
#define __LIST__
#include <stdlib.h>
namespace list
{
template<typename _Tp> class list;
template<> class list<int>;
template<> class list<float>;
template<> class list<double>;
template<> class list<long double>;
//retourne la longueur d'une liste :
template<typename _Tp> unsigned int Longueur(const list<_Tp>&);
/*
* On utilise la définition inductive suivante pour les listes :
* Soient E un ensemble non vide
* L l'ensemble des listes d'éléments de E
* On pose L = {{}} u E X L
* où {} désigne l'ensemble vide.
*/
template<typename _Tp>
struct _node
{
_Tp _L_Contenu; //le premier élement
_node<_Tp> *_L_Suivant;//le reste de la liste
};
template<typename _Tp>
class list
{
private:
_node<_Tp> *_L_Noeud;
public:
//le constructeur par défaut
list(_node<_Tp> * const);
//le constructeur de copies
list(const list&);
//retourne le noeud
_node<_Tp> * Node();
const _node<_Tp> * Node() const;
//retourne le premier élément
_Tp Tete();
const _Tp Tete() const;
//retoune le reste de la liste
list<_Tp> * Suivant();
const list<_Tp> * Suivant() const;
//operator :
//assigne une liste à une autre liste :
list<_Tp> operator=(const list<_Tp>&);
//teste si deux listes sont égales
bool operator==(const list<_Tp>&);
//teste si deux listes sont différentes
bool operator!=(const list<_Tp>&);
};
//retourne le noeud
template<typename _Tp>
inline _node<_Tp>*
list<_Tp>::Node(){return _L_Noeud;}
template<typename _Tp>
inline const _node<_Tp>*
list<_Tp>::Node() const{return _L_Noeud;}
//retourne le premier élément
template<typename _Tp>
inline _Tp
list<_Tp>::Tete() {return _L_Noeud._L_Contenu;}
template<typename _Tp>
inline const _Tp
list<_Tp>::Tete() const {return _L_Noeud._L_Contenu;}
//retoune le reste de la liste
template<typename _Tp>
inline list<_Tp>*
list<_Tp>::Suivant()
{
_L_Noeud = _L_Noeud->_L_Suivant;
return *this;
}
template<typename _Tp>
inline const list<_Tp>*
list<_Tp>::Suivant() const
{
_L_Noeud = _L_Noeud->_L_Suivant;
return *this;
}
//le constructeur par défaut
template<typename _Tp>
inline
list<_Tp>::list(_node<_Tp> * const __noeud)
:_L_Noeud(*__noeud){ }
//le constructeur de copies
template<typename _Tp>
inline
list<_Tp>::list(const list &__list)
:_L_Noeud(__list.Node()){ }
//operators :
//assigne une liste à une autre liste :
template<typename _Tp>
inline list<_Tp>
list<_Tp>::operator=(const list<_Tp>& __list)
{
_L_Noeud._L_Contenu = __list.Tete();
_L_Noeud._L_Suivant = __list.Suivant();
return *this;
}
//teste si deux listes sont égales
//cette fonction est récursive.
template<typename _Tp>
bool
list<_Tp>::operator==(const list<_Tp>& __list)
{
if(__list._L_Noeud == NULL && _L_Noeud == NULL)
return true;
else if(__list._L_Noeud != NULL && _L_Noeud == NULL)
return false;
else if(__list._L_Noeud == NULL && _L_Noeud != NULL)
return false;
else
{
if(__list.Tete() == _L_Noeud._L_Contenu &&
__list.Suivant() == _L_Noeud._L_Suivant)
return true;
else return false;
}
}
//teste si deux listes sont différentes
template<typename _Tp>
bool
list<_Tp>::operator!=(const list<_Tp>& __list)
{
list<_Tp> __lst = list(_L_Noeud);
return !(__lst == __list);
}
//retourne la longueur d'une liste :
//Cette fonction est récursive.
template<typename _Tp>
unsigned int
Longueur(const list<_Tp>& __list)
{
if(__list._L_Noeud == NULL) return 0;
else return 1 + Longueur(__list.Suivant());
}
}//namespace list
#endif /*__LIST__*/