// --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// Copyright (C) 2007 Author: Fathi Elloumi.

// 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 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 LISTGEN_H
#define LISTGEN_H
#include <stdexcept>
using namespace std;

class Spacerror: public bad_alloc
{
public:
 const char * what() const { return "Full Memory in listgen "; }
};

class Emptyerror: public exception
{
public:
const char * what() const { return "Empty list";}
 };

template <class Tparam>
class Listgen
{
public:
        Listgen();                      // constructor
        ~Listgen();                     // destructor
        void deleteall() ;
        void insertafter(const Tparam & x) throw(Spacerror);        // insert after current and the new will the current
 		void next() throw(Emptyerror);
        void gofirst() throw(Emptyerror);
        bool isempty();
        bool szequal(const Listgen<Tparam> & liste);
        bool atend() throw(Emptyerror);
        const Tparam & value() throw(Emptyerror);
      //  void affich() throw(Emptyerror);
void intersect(const Listgen<Tparam> & lst,Listgen<Tparam> & lnouv,int & sup,int & tot,const Tparam & zero);
         void copy(Listgen<Tparam> & lst) ;
		      void copyspec(Listgen<Tparam> & lst) ;
private:
     struct Listnode
             {
                Tparam data;     
                Listnode *succ;
             } *head, *current ;

};
//-----------------------------------------------------
template <class Tparam>
Listgen<Tparam>::Listgen()
        {
        head=NULL;current=NULL;
        }

template <class Tparam>
Listgen<Tparam>::~Listgen()

        {
        Listnode *p;
        while (head!=NULL)
        {
        p=head->succ;
        delete head;
        head=p;
        };
        current=NULL;
        }

template <class Tparam>
bool Listgen<Tparam>::szequal(const Listgen<Tparam> & liste)
{   // we assume we have the same length and are sorted
  Listnode *p,*q;
  bool stop=false;
  p=head;
  q=liste.head;
  while ((p!=NULL) && (!stop))
  {
  if (p->data==q->data) {p=p->succ; q=q->succ;} else
  stop=true;

  };
  return (!stop);



}

template <class Tparam>
void Listgen<Tparam>::deleteall()

        {
        Listnode *p;
        while (head!=NULL)
        {
        p=head->succ;
        delete head;
        head=p;
        };
        current=NULL;
        }


template <class Tparam>
void Listgen<Tparam>::intersect(const Listgen<Tparam> & lst, Listgen<Tparam> & lnouv,int & sup,int & tot,const Tparam & zero)
{    // I assume that the listed are sorted.
        Listnode *p1,*p2;
   //     Listgen<Tparam> lnouv;
        int diff;
        sup=tot=0;
		lnouv.deleteall();
		//lnouv.head=lnouv.current=NULL;
        p1=head;
     //  throw Spacerror();
        p2=lst.head;
        if ((p1!=NULL) && (p2!=NULL))
        {
                while(p1!=NULL)

                { // printf("%i %i\n",p1->data,p2->data);

                  if (p1->data<p2->data) p1=p1->succ;
                    else
                    {
                      if (p1->data==p2->data)
                       {

                          if (lnouv.isempty()) sup++;
                          else
                          {
                          diff=p1->data-lnouv.value();
                          if (diff>1) sup++; else
                            if ((diff==1) && ((p1->data-zero)%2==0)) sup++;
                          };
                          lnouv.insertafter(p1->data);
                          tot++;

                          p1=p1->succ;p2=p2->succ;
                          if (p2==NULL) break;
                        }
                       else
                       {
                           while(p2!=NULL)
                           {
                             if (p2->data<p1->data) p2=p2->succ; else break;
                           };
                           if (p2==NULL) break;  
                       };


                    };

                };

        };
 //    printf("derner lnouv:%i ",lnouv.value()) ;
// return lnouv;
}

/////////////////
/*
template <class Tparam>
void Listgen<Tparam>::affich() throw(Emptyerror)
        {
        Listnode *p;
        if (head==NULL) throw(Emptyerror());
        p= head;
        while (p!=NULL)
        
        {
        cout <<p->data<<"\n" ;
        p=p->succ;
        };

        }
*/
//////////////////////
template <class Tparam>
void Listgen<Tparam>::insertafter(const Tparam & x) throw(Spacerror)
        {
        Listnode *p;
        p= new(nothrow)Listnode;
         //p=NULL;
       if (p==NULL) {Spacerror e; throw(e);};
        p->data=x; p->succ=NULL;
        if (head==NULL)
        head=current=p; else
        {current->succ=p;current=p;};
        }
 
template <class Tparam>
void Listgen<Tparam>::copy(Listgen<Tparam> & lst)
{
Listnode *p=head;
lst.head=NULL;lst.current=NULL;
  while (p!=NULL)
  {
     lst.insertafter(p->data);
        p=p->succ;
  }  ;


 }

template <class Tparam>
void Listgen<Tparam>::copyspec(Listgen<Tparam> & lst)
{
//Listnode *p=head;
lst.head=head;lst.current=head;
head=current=NULL;  
/*while (p!=NULL)
  {
     lst.insertafter(p->data);
        p=p->succ;
  }  ;
*/

 }

template <class Tparam>
void Listgen<Tparam>::next() throw(Emptyerror)
        {
			if (head==NULL) {Emptyerror e; throw(e);} else
        {
          if (current->succ!=NULL)  current=current->succ;
        };
        }
template <class Tparam>
void Listgen<Tparam>::gofirst() throw(Emptyerror)
        {

        if (head==NULL) {Emptyerror e; throw(e);} else
        
           current=head;
        

        }
template <class Tparam>
bool Listgen<Tparam>::isempty()
        {
        return (head==NULL);
        }
template <class Tparam>
bool Listgen<Tparam>::atend() throw(Emptyerror)
        {
        if (head==NULL) {Emptyerror e; throw(e);} else
       
          return (current->succ==NULL);
       
        
        }
template <class Tparam>
const Tparam & Listgen<Tparam>::value() throw(Emptyerror) 
        {
        if (head==NULL) {Emptyerror e; throw(e);}
        else
        return (current->data);
        }


#endif