MyList.h

Go to the documentation of this file.

/* ***********************************************************************************
        Writer:         Sebastien Bloc
        Copyright:      2004
        eMail:          sebastien.bloc@free.fr
        URL:            http://mignonsoft.free.fr

        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.
        http://www.gnu.org/copyleft/gpl.html
*********************************************************************************** */

#ifndef INCLUDE_LISTE_GENERIQUE_H
#define INCLUDE_LISTE_GENERIQUE_H
/*
#ifndef BOOL // gestion des cross-platform
        #define BOOL    short
        #define TRUE    1
        #define FALSE   0
#endif
*/

#include <stdio.h>
#include <math.h>

typedef enum _ETypeStart
{
        list_current = 1,
        list_first,
        list_last,
        list_before,
        list_after
} ETypeStart; // pour le param1 de GoIndex

#include "MyException.h"

template <class T> class MyListItem
{
public:
        T *elem;                                          // element de la liste 
        MyListItem<T> *after,*before;   // sucesseur 
        BOOL selfUnAlloc;                         // le ptr doit il etre des alouées a la fin

        MyListItem()
        {
                elem=NULL;
                selfUnAlloc=FALSE;
                ZeroLink();
        }

        MyListItem(T *_elem,BOOL _selfAlloc,BOOL _selfUnAlloc)
        {
                New(_elem,_selfAlloc,_selfUnAlloc);
        }

        void ZeroLink()
        {
                after=NULL;
                before=NULL;
        }

        MyListItem(T *_elem) { New (_elem,FALSE,FALSE); }
        MyListItem(T &_elem) { New (&_elem,TRUE,TRUE); }

        ~MyListItem()
        {
                Delete();
        }

        void Delete()
        {
                if (elem&&selfUnAlloc) delete elem;
        }

        void New (T *_elem,BOOL _selfAlloc,BOOL _selfUnAlloc)
        {
                selfUnAlloc = _selfUnAlloc;
                if (_selfAlloc) 
                {
                        elem = new T;
                        *elem=*_elem; //operator=(T &source) de la class appelé, pourais etre aussi le contructeur de copie
                }
                else elem = _elem;
                if (!elem) throw MyExceptionMemory("MyList","NewElem",sizeof(T));
                after=NULL;
                before=NULL;
        }

        void New (T *elem) { New (elem,FALSE,FALSE); }
        void New (T &elem) { New (&elem,TRUE,TRUE); }


};

/*
MyList<int> list;
MyListIterator<int> i(&list);
i+=1;
i+=2;
for (i=0;i.More();i++)
{
        printf("%d",i.GetElem());
}
*/

template <class T> class MyList;

template <class T> class MyListIterator
{
private:
        MyListItem<T> *current;         
        MyList<T> *list;                        
        int     numCurrent;                             

public:
        MyListIterator()
        {
                Bind(NULL);
        }
        MyListIterator(MyList<T> *_list)
        {
                Bind(_list);
        }

        BOOL Bind(MyList<T> *_list)
        {
                list = _list;
                Zero();
                if (!_list) return FALSE;
                return TRUE;
        }

        void operator=(MyListIterator &src)
        {
                current =src.current;
                list = src.list;
                numCurrent = src.numCurrent;
        }

        void Zero()
        {
                current=NULL;
                numCurrent=-1;
        }

        MyListItem<T> * GetCurrent()
        {
                return current;
        }

        int GetIndex()
        {
                return numCurrent;
        }

        // Deplacement *********************************************************

        BOOL MoveFirst()
        {
                if (!current) return FALSE;
                Supr(current,FALSE);
                return AddFirst(current)?TRUE:FALSE;
        }

        BOOL MoveLast()
        {
                if (!current) return FALSE;
                Supr(current,FALSE);
                return AddLast(current)?TRUE:FALSE;;
        }

/*  a debuger
        BOOL MoveBefore()
        {
                if (!current) return FALSE;
                Supr(current,FALSE);
                return AddBefore(current)?TRUE:FALSE;
        }

        BOOL MoveAfter()
        {
                if (!current) return FALSE;
                Supr(current,FALSE);
                return AddAfter(current)?TRUE:FALSE;
        }
*/
        // Ajout *************************************************************

        MyListItem<T> * AddBefore (T *elem,BOOL selfAlloc,BOOL selfUnAlloc)
        {
                MyListItem<T> * item = new MyListItem<T>(elem,selfAlloc,selfUnAlloc);
                return AddBefore(item);
        }

        MyListItem<T> * AddBefore(MyListItem<T> * item)
        {       
                if (!item) return NULL;
                if (!current)  
                {
                        if (!list->first && !list->last) 
                        {
                                list->first=list->last=current=item;
                                numCurrent=0;
                        }
                        else return NULL; // pb d'intergrité
                }
                else 
                {
                        if (current==list->first)
                        {
                                list->first->before = item;
                                item->after =list->first;
                                list->first = current = item;
                        }
                        else
                        {
                                item->before = current->before;
                                current->before->after = item;
                                current->before = item;
                                item->after = current;
                                current = item;
                        }
                }
                list->nbElem ++;
                return current;
        }

        MyListItem<T> * AddFirst (T *elem,BOOL selfAlloc,BOOL selfUnAlloc)
        {
                MyListItem<T> * item = new MyListItem<T>(elem,selfAlloc,selfUnAlloc);
                return AddFirst(item);
        }

        MyListItem<T> * AddFirst (MyListItem<T> * item)
        {       
                if (!item) return NULL;
                if (!list->first) list->first=list->last=current=item;  
                else 
                {
                        list->first->before = item;
                        item->after = list->first;
                        list->first = current = item;
                }
                numCurrent=0;
                list->nbElem ++;
                return item;
        }

        MyListItem<T> * AddLast (T *elem,BOOL selfAlloc,BOOL selfUnAlloc)
        {
                MyListItem<T> * item = new MyListItem<T>(elem,selfAlloc,selfUnAlloc);
                return AddLast(item);
        }

        MyListItem<T> * AddLast (MyListItem<T> * item)
        {
                if (!item) return NULL;
                if (!list->last) current = list->first = list->last = item;  
                else 
                {
                        list->last->after = item;
                        item->before = list->last;
                        list->last = current = item;
                }
                numCurrent=list->nbElem;
                list->nbElem ++;
                return item;
        }

        MyListItem<T> * AddAfter (T *elem,BOOL selfAlloc,BOOL selfUnAlloc)
        {
                MyListItem<T> * item = new MyListItem<T>(elem,selfAlloc,selfUnAlloc);
                return AddAfter(item);
        }

        MyListItem<T> * AddAfter (MyListItem<T> * item)
        {
                if (!item) return FALSE;
                if (!current) 
                {
                        if (!list->first && !list->last) list->first=list->last=current=item;
                        else return FALSE;
                }
                else 
                {
                        if (current==list->last)
                        {
                                list->last->after = item;
                                item->before  = list->last;
                                list->last = current = item;
                        }
                        else
                        {
                                item->after = current->after;
                                current->after->before = current->after = item;
                                item->before = current;
                                current = item;
                        }
                }
                numCurrent++;
                list->nbElem ++;
                return item;
        }

        MyListItem<T> * AddFirst (T *elem) { return AddFirst(elem,FALSE,FALSE); }
        MyListItem<T> * AddFirst (T &elem) { return AddFirst(&elem,TRUE,TRUE); }
        T * AddNewFirst()
        {
                T *elem = new T;
                AddFirst(elem,FALSE,TRUE);
                return elem;
        }

        MyListItem<T> * AddLast (T *elem) { return AddLast(elem,FALSE,FALSE); }
        MyListItem<T> * AddLast (T &elem) { return AddLast(&elem,TRUE,TRUE); }
        T * AddNewLast()
        {
                T *elem = new T;
                AddLast(elem,FALSE,TRUE);
                return elem;
        }

        MyListItem<T> * AddBefore (T *elem) { return AddBefore(elem,FALSE,FALSE); }
        MyListItem<T> * AddBefore (T &elem) { return AddBefore(&elem,TRUE,TRUE); }
        T * AddNewBefore()
        {
                T *elem = new T;
                AddBefore(elem,FALSE,TRUE);
                return elem;
        }

        MyListItem<T> * AddAfter (T *elem) { return AddAfter(elem,FALSE,FALSE); }
        MyListItem<T> * AddAfter (T &elem) { return AddAfter(&elem,TRUE,TRUE); }
        T * AddNewAfter()
        {
                T *elem = new T;
                AddAfter(elem,FALSE,TRUE);
                return elem;
        }

        // Supression ***********************************************************

        BOOL SuprFirst (BOOL withItem=TRUE)
        {
                if (!list->first) return FALSE;
                MyListItem<T> * temp;

                temp = list->first->after;
                if (withItem) delete list->first;
                else list->first->ZeroLink();

                // la list a il un seul element ?
                if (!temp) 
                {
                        list->first = list->last = NULL;
                        Zero();
                }
                else
                {
                        if (current==list->first) current = temp;
                        else numCurrent--;
                        temp->before = NULL;
                        list->first = temp;
                }
                list->nbElem --;
                return TRUE;
        }

        BOOL SuprLast (BOOL withItem=TRUE)
        {
                if (!list->last) return FALSE;
                MyListItem<T> *temp;
                temp = list->last->before;
                if (withItem) delete list->last;
                else list->last->ZeroLink();

                // y a t'il plus d'un element dans la list
                if (!temp) 
                {
                        list->first = list->last = NULL;
                        Zero();
                }
                else
                {
                        if (list->last==current)
                        {
                                current = temp;
                                numCurrent--;
                        }
                        temp->after = NULL;
                        list->last = temp;
                }
                list->nbElem --;
                return TRUE;
        }

        void SuprAll()
        {
                GoFirst();
                while (More()) list->i.Supr();
                list->Zero();
                Zero();
        }

        BOOL Supr (MyListItem<T> *item,BOOL withItem=TRUE)
        {
                if (!item) return FALSE;

                MyListIterator<T> j=*this;
                for (j=0;j.More();j++)  
                {
                        if (j.GetCurrent()==item) return j.Supr(withItem);
                }
                return FALSE;
        }

        BOOL Supr(BOOL withItem=TRUE)
        {
                if (!current) return FALSE;
                MyListItem<T> * lAfter,*lBefore,*lOld;
                lAfter = current->after;
                lBefore = current->before;
                lOld = current;

                if (!lBefore && !lAfter)
                {
                        list->first = list->last = NULL;        
                        Zero();
                }
                else
                {
                        if (lBefore) 
                        {
                                lBefore->after=lAfter;
                                if (lAfter) 
                                {
                                        lAfter->before = lBefore;
                                        current = lAfter;
                                }
                                else 
                                {
                                        list->last = current = lBefore;
                                        numCurrent--;
                                }
                        }
                        else 
                        {
                                current = list->first = lAfter;
                                lAfter->before = NULL;
                                numCurrent--;
                        }
                }
                if (withItem) delete lOld;
                else lOld->ZeroLink();
                list->nbElem --;
                return TRUE;
        }

        BOOL SuprIndex(int index,BOOL withItem=TRUE)
        {
                if (!GoIndex(list->first,index)) return FALSE;
                return Supr(withItem);
        }

        // Deplacement *******************************************************

        BOOL GoTo(MyListItem<T> *item)
        {
                if (!item) return FALSE;
                for (GoFirst();More();GoAfter())        
                {
                        if (GetCurrent()==item) return TRUE;
                }
                return FALSE;
        }

        BOOL GoTo(T elem)
        {
                for (GoFirst();More();GoAfter())        
                {
                        if (GetElem()==elem) return TRUE;
                }
                return FALSE;
        }

        BOOL GoAfter()
        {
                if (current) current = current->after; 
                if (current)
                { 
                        numCurrent = numCurrent == -1 ? -1 : numCurrent+1;
                        return TRUE ;
                }
                else 
                {
                        numCurrent = -1;
                        return FALSE;
                }
        }

        BOOL GoBefore ()
        {
                if (current) current = current->before;
                if (current) 
                {
                        numCurrent = numCurrent == -1 ? -1 : numCurrent-1;
                        return TRUE;
                } 
                else 
                {
                        numCurrent = -1;
                        return FALSE;
                }
        }

        BOOL GoFirst ()
        {
                current = list->first;
                numCurrent = current? 0 : -1;
                return current? TRUE : FALSE;                           
        }

        BOOL GoIndex (ETypeStart start,int nb)
        {
                BOOL isUp;
                isUp = nb<0 ? FALSE : TRUE ; 
                nb = labs(nb);
                switch (start)
                {
                case list_current: break;
                case list_first: 
                        if (numCurrent != -1) 
                        {
                                nb = numCurrent-nb; 
                                isUp = nb<=0;
                                nb = labs(nb);
                        }
                        else 
                        {
                                isUp = TRUE;  
                                GoFirst(); 
                        }
                        break;
                case list_last:
                        if (numCurrent != -1) 
                        {
                                nb = list->nbElem-numCurrent-nb; 
                                isUp = nb>=0;
                                nb = labs(nb);
                        }
                        else 
                        {
                                isUp = FALSE;  
                                GoLast(); 
                        }
                        break;
                case list_before: isUp = FALSE; break;
                case list_after:  isUp = TRUE;  break;
                default:
                        return FALSE;
                }
                for (int i=0;i<nb;i++)
                {
                        if (More())
                        {
                                if (isUp) GoAfter();
                                else GoBefore();
                        } else return FALSE;
                }
                return TRUE;
        }

        BOOL GoLast ()
        {
                current = list->last;
                numCurrent = current? list->nbElem -1 : -1;
                return current? TRUE : FALSE;
        }

        // ********************************************************************************

        //inline operator T() const { return GetElem(); } marche pas
        //inline operator T *() const { return GetElemPtr(); }

        T & GetElem (int index=-1)
        {
                if (index!=-1) GoIndex(list_first,index);
                if (!current) return *list->elemNull;
                return *current->elem;
        }

        T * GetElemPtr ()
        {
                if (!current) return list->elemNull;
                return current->elem;
        }

        T * GetElemPtr (int index)
        {
                if (!GoIndex(list_first,index)) return list->elemNull;
                if (!current) return list->elemNull;
                return current->elem;
        }

        BOOL More ()
        {
                return current ? TRUE : FALSE;
        }               

        BOOL IsOnLast()
        {
                return (current==list->last)? TRUE : FALSE;
        }               

        BOOL IsOnFirst()
        {
                return (current==list->first)? TRUE : FALSE;
        }       

        MyListItem<T> * operator += (T *elem)
        {
                return AddLast(elem);
        }

        MyListItem<T> * operator += (T elem)
        {
                return AddLast(elem);
        }

        BOOL operator = (int index)
        {
                if (index>=0) return GoIndex(list_first,index);
                else return GoIndex(list_last,-index+1);
        }

        BOOL operator++ (int)
        {
                return GoAfter();
        }

        BOOL operator-- (int)
        {
                return GoBefore();
        }

        T * operator () (int num=-1)
        {
                return GetElemPtr(num);
        }

        T & operator [] (int num)
        {
                if (num<0)
                {
                        if (!GoIndex(list_last,-num)) return *list->elemNull;
                }
                else
                {                       
                        if (!GoIndex(list_first,num)) return *list->elemNull;
                }
                return GetElem();
        }               
};

template <class T> class MyList
{
        public:
                MyListIterator<T> i;                    
                T *     elemNull;                                       
                MyListItem<T> *first;                   
                MyListItem<T> *last;                    
                int     nbElem;                                         
                //              int             (* FoncCompare)(T elem1,T elem2);       // fonction de comparaison

                MyList ()
                {
                        Zero();
                        i.Bind(this);
                        //FoncCompare = DefaultFoncCompare;
                }

/*
                MyList (int(*_FoncCompare)(T,T))        // fonction de comparaison
                {
                        first = NULL;
                        current = NULL;
                        last = NULL;
                        nbElem = 0;
                        numCurrent = -1;

                        FoncNew = _FoncNew ? _FoncNew : DefaultFoncNew;
                }
*/
                ~MyList ()
                {
                        i.SuprAll();
                }

                void Zero()
                {
                        first = NULL;
                        last = NULL;
                        nbElem = 0;
                }

                int GetNbElem()
                {
                        return nbElem;
                }

                MyList<T> & operator = (MyList<T> &source)
                {
                        i.SuprAll();
                        *this+= source;
                        return *this;
                }

                MyList<T> & operator += (MyList<T> &source)
                {
                        for (source.i=0;source.i.More();source.i++) i+= source.i.GetElem();
                        return *this;
                }

                BOOL Save (FILE *fich)
                {
                        if (!fich) return FALSE;

                        fprintf(fich,"%d",nbElem);
                        MyListIterator<T> i(this);
                        T *item;

                        for (i=0;i.More();i++)
                        {
                                item = i.GetElemPtr();
                                if (item)
                                        if (!fwrite ((void *) item,sizeof(T),1,fich)) return FALSE;
                        }
                        return TRUE;
                }

                BOOL Load (FILE *fich)
                {
                        if (!fich) return FALSE;
                        
                        int nb;
                        fscanf(fich,"%d",&nb);
                        T elem;
                        MyListIterator<T> i(this);
                        for (int x=0;x<nb;x++)
                        {
                                if (!fread ((void *) &elem,sizeof(T),1,fich))return FALSE;
                                if (!i.AddAfter(elem)) return FALSE;
                        }
                        return TRUE;
                }

                void SetCompareFunction (int (* fonction)(T * elem1,T * elem2))
                {
                        FoncCompare = fonction;
                }
/*
                void SetNewFunction (T * (* fonction)(T * elem))
                {
                        FoncNew = fonction;
                }

                void SetDeleteFunction (BOOL (* fonction)(T *elem))
                {
                        FoncDelete = fonction;
                }
*/
                /* **********************************************************************************
                        list += elem;                   ==> AddLast
                        listDest = listSource;  ==> Copy d'une liste dans une autre
                        listDest += listSource; ==> Ajout d'une liste dans une autre
                        elem = list[12];                ==> Acced a l'elem 12 (13) vu que ca commance a 0
                        elem = list[-1];                ==> Acced au dernier elem
                        list = 0;                               ==> Se place a l'element indexé 0
                        list ++;                                ==> Se place a l'element suivant;
                        list --;                                ==> Se place a l'element d'avant;
                        lisr += 2;                              ==> Se place a 2 element plus loin
                        lisr -= 2;                              ==> Se place a 2 element avant
                ********************************************************************************** */
/*
                void operator += (T &elem)
                {
                        AddLast(elem);
                }
*/
};

template <class T> class MyStack : public MyList<T>
{
public:
        MyStack() : MyList<T>() {}

        BOOL Push(T elem)
        {
                return i.AddFirst(elem)?TRUE:FALSE;
        }

        T Pop()
        {
                if (i.GoFirst())
                {
                        T elem = i.GetElem();
                        i.SuprFirst();
                        return elem;
                }
                return *elemNull;
        }

        T Peek()
        {
                if (i.GoFirst()) return i.GetElem();
                return *elemNull;
        }

        BOOL FrontPush(T elem)
        {
                return i.AddLast(elem);
        }

        T FrontPop()
        {
                if (i.GoLast())
                {
                        T elem = i.GetElem();
                        i.SuprLast();
                        return elem;
                }
                return *elemNull;
        }

        T FrontPeek()
        {
                if (i.GoLast()) return i.GetElem();
                return *elemNull;
        }
};

// definition des fonctions d'allocation et des alloc par Default

template <class T> int DefaultFoncCompare (T elem1,T elem2)
{
        return memcmp((void *)elem1,(void *)elem2,sizeof(T));
}

/*
template <class T> T * DefaultFoncNew (T *elemSource)
{
        //T * elemDest = elemSource? new T(elemSource) : new T;
        T * elemDest = new T;
        *elemDest = elemSource;
        return elemDest;

        T * elemDest = new T;
        if (elemSource) memcpy((void *)elemDest,(void *)elemSource,sizeof(T));
        return elemDest;
}

template <class T> BOOL DefaultFoncDelete (T * elem)
{
        delete elem;
        return TRUE;
}

// definition des fonctions d'allocation et des alloc dans les MyString

#include "myString.h"

MyString * MyString_FoncNew (MyString *elemSource);
int MyString_FoncCompare (MyString * elem1,MyString * elem2);
#define MyListString(name) MyList<MyString> name(MyString_FoncCompare,MyString_FoncNew,NULL);
*/

#endif

---