placemon3sdp.hpp

Go to the documentation of this file.

#ifndef ALREADY_placemon3
#define ALREADY_placemon3
//Requiers type mon to be defined somewhere else
//on tache de rendre l'acces a int2mon et mon2int 
//aussi rapide que possible meme si ca coute 
//un peu, d'inserer puisque par hypothese on fait plus 
//d'appel a int2mon mon2int 
//que l'on insere ou enleve de monomes dedans!
template<class mon,typename pol>
struct monomial_server{
  typedef mon monom_t;
  typedef pol pol_t;
  int sizeplace;
  mon *int2mon_;
  mon *mon2intmon;
  int *mon2intint;
  int (*ord)(const mon &m1,const mon &m2);
  int nbvars;
#ifdef unimul
  int **multiple;
#endif 

#ifdef uninf
  void **nfmul;
#endif

#ifdef unimul

void displaymon()
{
  cout<<"les mon"<<endl;
  for(int i=0;i<sizeplace;i++)
    cout<<int2mon_[i]<<" ";
  cout<<endl;
}
 ~monomial_server() {
    MAC_REV_FREE<mon>(int2mon_,sizeplace*sizeof(mon));
    MAC_REV_FREE<mon>(mon2intmon,sizeplace*sizeof(mon));
    MAC_REV_FREE<int>(mon2intint,sizeplace*sizeof(int));
#ifdef unimul
  for(int i=0;i<nbvars;i++)
    free(multiple[i]);
  free(multiple);
#endif

#ifdef uninf
  for(int i=0;i<nbvars;i++)
    free(nfmul[i]);
  free(nfmul);
  
#endif
  }
  monomial_server() {
    sizeplace=0;int2mon_=NULL;mon2intmon=NULL;mon2intint=NULL;
    ord=NULL;
    }

  //template<typename mon>
  //void inline int2mon(const int &i,mon &res);

  //template<typename mon>
  //int inline mon2int(const mon &mm);

inline void init_multiple(int n)
{
  multiple=(int**)malloc(n*sizeof(int*));
  for(int i=0;i<n;i++)
    multiple[i]=NULL;
  nbvars=n;
}
void reinit_multiple()
{
  for(int i=0;i<nbvars;i++)
    for(int j=0;j<sizeplace;j++)
      multiple[i][j]=-2;
}

template<typename typBase>
inline int mulind(int indexbase, int var, const typBase &b)
{
  mon tmpdebug=mon(1,1)*mon(3,1);
  //cout<<"multiple[var][indexbase]"<<multiple[var][indexbase]<<endl;
  if(multiple[var][indexbase]==-2)//||(multiple[var][indexbase]>=size))
    {
      mon tmpmon;
      int stock;
      int2mon(indexbase,tmpmon);
      tmpmon*=mon(var,1);
      if(IsinB(tmpmon,b))
    {
      stock=mon2int(tmpmon);
      multiple[var][indexbase]=stock;
    }
      else 
    multiple[var][indexbase]=-1;
    }
//   if (multiple[var][indexbase]>=0)
//     cout<<int2mon_[indexbase]<<"*"<<mon(var,1)<<" donne "<<int2mon_[multiple[var][indexbase]]<<endl;
  return multiple[var][indexbase];
}
#endif

#ifdef uninf
//template<typename pol>
inline void init_nf(int n)
{
  nfmul=(void**)malloc(n*sizeof(pol*));
  for(int i=0;i<n;i++)
    *((pol**)nfmul+i)=NULL;
}

//template<typename pol>
void reinit_nf()
{
  pol toto;
  toto.size=-1;
  for(int i=0;i<nbvars;i++)
    for(int j=0;j<sizeplace;j++)
      (*((pol**)nfmul+i))[j]=toto;
}

template<typename typdump,typename Base>
pol nf(int var ,int indmon,const typdump &dump,const Base & b)
{
  //  cout<<"c moi c moi"<<endl;
  pol res;
  if(((*((pol**)nfmul+var)))[indmon].size==-1)
    {
      typedef typename typdump::value_type dumpstruct;
      //typedef typename pol::monom_t mon;
      res.nf=NULL;
      res.size=-1;
      mon tmpmon;//=mon(1,var)*int2mon<mon>(indmon);
      int deg=0;//=tmpmon.GetDegree()+1;
      typename typdump::const_iterator iter;
      int2mon(indmon,tmpmon);
      deg=tmpmon.GetDegree()+1;
      tmpmon*=mon(var,1);
      for(iter=dump.begin();
      (iter!=dump.end()) && (iter->k!=deg);iter++);
      if(iter!=dump.end())//on cherche pas n'importe quoi qd meme
    {
      int i;
      for(i=0;i<iter->size;i++)
        {
          if(iter->nf[i].ind.rep==tmpmon.rep)
        break;
        }
      if(i!=iter->size)
        res=(iter->nf[i]);
    }
      ((*((pol**)nfmul+var)))[indmon]=res;
    }
  return ((*((pol**)nfmul+var)))[indmon];
}

#endif

template<typename ptrfun>
void setorder(ptrfun tmpord)
{
  ord=(int (*)(const mon &,const mon &))(tmpord);
}
int sizeplacemon()
{
  return sizeplace;
}

  //template<typename mon>
void putmon2(const mon & m,const int poscurrent)
{
  int i;
  //si le monome est deja introduit on y touche pas
  //cout<<"putmon2 atteint"<<endl;
  //cout<<"poscurrent "<<poscurrent<<endl;
  //cout<<"mon2intmon==NULL?? "<<(mon2intmon==NULL)<<" m "<<m<<endl;
  //if (poscurrent<size)
  //  cout<<((mon2intmon==NULL)||(mon2intmon[poscurrent]==m))<<endl;
  if((mon2intmon==NULL)||(poscurrent==sizeplace)||
     (mon2intmon[poscurrent].rep!=m.rep))
    {
      //  cout<<"moncurent etc passe etc vaut "<<endl;
      sizeplace++;


      mon2intmon=(mon*)MAC_REV_REALLOC<mon>(mon2intmon,(sizeplace-1)*sizeof(mon)
                        ,(sizeplace)*sizeof(mon));
      mon2intint=(int*)realloc(mon2intint,sizeplace*sizeof(int));
      
      //int2mon=(mon*)realloc(int2mon,size*sizeof(mon));
      //on vient d'agrandir les tableaux
      for(int k=sizeplace-1;k>poscurrent;k--)
    mon2intmon[k]=mon2intmon[k-1];

      //memmove((mon2intmon+poscurrent+1),(mon2intmon+poscurrent),
      //          (size-1-poscurrent)*sizeof(mon));
      memmove((mon2intint+poscurrent+1),(mon2intint+poscurrent),
          (sizeplace-1-poscurrent)*sizeof(int));
      //on cherche s'il y a un indice dans int2mon libre
      for(i=0;i<sizeplace-1;i++)
    if (int2mon_[i]==mon(-1)) break;
      if (i==sizeplace-1)
    {
      int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,(sizeplace-1)*sizeof(mon)
                     ,sizeplace*sizeof(mon));
#ifdef unimul
      for(int k=0;k<nbvars;k++)
        {
          //cout<<"j'ai fait un realloc "<<endl;
          multiple[k]=(int*)realloc(multiple[k],sizeplace*sizeof(int));
          multiple[k][sizeplace-1]=-2;
        }
#endif 
#ifdef uninf
      for(int k=0;k<nbvars;k++)
        {
          //cout<<"j'ai fait un realloc "<<endl;
          *((pol**)nfmul+k)=(pol*)
                       MAC_REV_REALLOC<pol >
        ((void*)*((pol**)nfmul+k)
         ,(sizeplace-1)*sizeof(pol)
         ,sizeplace*sizeof(pol));
          ((pol**)nfmul)[k][sizeplace-1].size=-1;
        }
#endif 
    
    }
      int2mon_[i]=m;
      //cout<<"int2mon_["<<i<<"] vaut "<<m<<endl;
      mon2intint[poscurrent]=i;
      mon2intmon[poscurrent]=m;
      //cout<<"mon2intmon["<<poscurrent<<"] vaut"<<mon2intmon[poscurrent]
      //      <<" et est sense valoir "<<m<<endl;
    }
  return;
}

  //template<typename mon>
void putmon(const mon & m)
{
  int inf=0,sup=sizeplace,poscurrent=0;
  //on commence par localiser l'endroit dans mon2int*
  //ou on va rajouter le monom
  if(sizeplace!=0)
    for(poscurrent=sizeplace/2;ord(mon2intmon[poscurrent+1],
                  m)&&
      ord(m,mon2intmon[poscurrent-1]);)
      {
    if(ord(mon2intmon[poscurrent],m)>0)
      {
        sup=poscurrent;
        poscurrent=(inf+sup)/2;
      }
    else
      {
        inf=poscurrent;
        poscurrent=(inf+sup)/2;
      }
      }
  putmon2(m,poscurrent);
  return ;
}


  //template<typename mon>
void removemon(const mon &m)
{
  int inf=0,sup,poscurrent,i;
  //on commence par localiser l'endroit dans mon2int*
  //ou on va rajouter le monom
  for(poscurrent=sizeplace/2;ord(mon2intmon[poscurrent+1],
                m)&&
    ord(m,
        mon2intmon[poscurrent-1]);)
    {
      if(ord(mon2intmon[poscurrent],m)>0)
    {
      sup=poscurrent;
      poscurrent=(inf+sup)/2;
    }
      else
    {
      inf=poscurrent;
      poscurrent=(inf+sup)/2;
    }
    }
  //si le monome n'est PAS deja introduit on  touche a rien
  if(mon2intmon[poscurrent]!=m)
    {
      //on libere l'endroit ou se trouve ce monome
      int2mon_[poscurrent]=mon(-1);
      //on recopier apres dans les mon2int pour enlever le monome
      memmove((mon2intmon+poscurrent),(mon2intmon+poscurrent+1),
          (sizeplace-poscurrent-2)*sizeof(mon));
      memmove((mon2intint+poscurrent),(mon2intint+poscurrent+1),
          (sizeplace-poscurrent-2)*sizeof(int));
      //on retrecit les mon2int*
      //      cout<<"la"<<endl; 
      sizeplace--;
       mon2intmon=(mon*)realloc(mon2intmon,sizeplace*sizeof(mon));
       mon2intint=(int*)realloc(mon2intint,sizeplace*sizeof(int));
    }
  return;
}


  //template<typename mon>
void affplace(const mon &m,int p)
{
  int2mon_[p]=m;
}

  //template<typename mon>
void freeplace(int p)
{
  int2mon_[p]=mon(-1);
}

  //template<typename mon>
void inline int2mon(const int &i,mon &res)
{
  //  cout<<"sizeplace ici "<<sizeplace<<" et i "<<i<<endl;
  res=mon(1,(int2mon_+i)->rep);
}

  //template<typename mon>
int inline mon2int(const mon &mm)
{
  typedef typename mon::coeff_t coeff;
  //mon2intmon et mon2intint doivent etre trie 
  //par ordre (ord) croissant
  //
  int inf=0,sup=sizeplace,poscurrent;
  mon m=mm;
  m.SetCoeff(1);
  // cout<<"rentre mon2int"<<endl;
  //cout<<"size "<<size<<endl;
  if(sizeplace==0) {mon2intmon=NULL;mon2intint=NULL;
  int2mon_=NULL;putmon(m);
  //cout<<"transition mon2int"<<endl;
  };
  //cout<<"sup "<<sup<<" inf "<<inf<<endl;
  for(poscurrent=sizeplace/2;(sup-inf>1)&&
    (mon2intmon[poscurrent].rep!=m.rep);)
    {
      //  cout<<"poscurrent "<<poscurrent<<endl;
      if(ord(mon2intmon[poscurrent],m)>0)
    {
      sup=poscurrent;
      poscurrent=(inf+sup)/2;
    }
      else
    {
      inf=poscurrent;
      poscurrent=(inf+sup)/2;
    }
    }
  //cout<<"sortie for mon2int "<<poscurrent<<endl;
  //cout<<"les monome "<<mon2intmon[poscurrent]<<" "<<m<<endl;
  if (mon2intmon[poscurrent].rep!=m.rep) 
    {
      if (ord(mon2intmon[poscurrent],m)<0) poscurrent++;
      //if(poscurrent<size)
    //cout<<"ord(mon2intmon[poscurrent],m) "
    //  <<ord(mon2intmon[poscurrent],m)<<endl;
      //cout<<"appel putmon2 "<<endl;
      putmon2(m,poscurrent);
    }
  //cout<<"sorti mon2int"<<endl;
  return mon2intint[poscurrent];
}

template<typename typPk, typename typdump>
void swap_all(int i, int j, typPk & Pk ,typdump& dump)
{
  //hypothese i<j
  //
  typedef typename typPk::value_type::coeff_t coeff;
  //typedef typename typPk::value_type::monom_t mon;
  typedef typename typdump::value_type dumpstruct;
  mon tmpmon,tmpmon2;
  int deg,pos1,pos2;
  int2mon(j,tmpmon);
  int2mon(i,tmpmon2);
  deg=tmpmon.GetDegree();
#ifdef DEB
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    cout<<"swap "<<invconv<Poly>(*iter)<<endl;
  cout<<"je swap "<<tmpmon<<" et "<<tmpmon2<<endl;
#endif
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    if(j/8<iter->sizenf && ((iter->nfind[j/8]>>(j%8))&1))
      {
#ifdef DEB  
    cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<endl;
    //cout<<"x1*x3 a pour indice "<<mon2int(mon(1,1)*mon(3,1))<<endl;
#endif
    int nbentre=0;
    int indicej=0,indicei=0;
    coeff tmp;
    for(int k=i/8+1;k<=j/8;k++)
      nbentre+=nbbits[iter->nfind[k]];
    nbentre+=nbbits[iter->nfind[i/8]>>(i%8)];
    nbentre-=nbbits[iter->nfind[j/8]>>(j%8)];
    //nbentre--;
    //nbentre-=2;//on compt i et j dedans dans les formules precedentes
    
    for(int k=iter->sizenf-1;k>j/8;k--)
      indicej+=nbbits[iter->nfind[k]];
    indicej+=nbbits[iter->nfind[j/8]>>(j%8)];
    //  indicej--;
    for(int k=iter->sizenf-1;k>i/8;k--)
      indicei+=nbbits[iter->nfind[k]];
    indicei+=nbbits[iter->nfind[i/8]>>(i%8)];
#ifdef DEB
    cout<<iter->size<<endl<<indicej<<endl<<nbentre<<endl;
    cout<<"iter->size-indicej-nbentre+1 "<<iter->size-indicej-nbentre+1<<" et indice i "<<indicei<<" indicej "<<indicej<<endl;
    
    cout<<"iter->nf[iter-szie-indicej] "
        <<iter->nf[iter->size-indicej]<<endl;
    cout<<"iter->nf[iter-size-indicej-nbentre] "
        <<iter->nf[iter->size-indicej-nbentre]<<endl;
#endif
    tmp=iter->nf[iter->size-indicej];
    if((iter->nfind[i/8]>>(i%8))&1)
      {
        iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
                          ,iter->size*sizeof(coeff)
                          ,(iter->size-1)*sizeof(coeff));
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&=~(1<<(j%8));
        iter->size--;
      }
    else
      {
        for(int k=0;k<nbentre;k++)
          iter->nf[iter->size-indicej-k]=iter->nf[iter->size-indicej-k-1];
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&=~(1<<(j%8));
    
      }
    //  iter->nf[i]=iter->nf[j];
    //  iter->nf[j]=0;
#ifdef DEB
    if ((iter->sizenf*8>sizeplace) && ((iter->nfind[iter->sizenf-1]
                       >>(sizeplace%8))&1))
      {cout<<"swapall "<<iter->sizenf<<" "<<sizeplace<<endl;exit(10);}
#endif
      }
  for(typename typdump::iterator iter=dump.begin();iter!=dump.end();iter++)
    {
      
     //if(iter->k<=deg)
    {
      for(typename dumpstruct::pol_t *iterdump=iter->nf;
          iterdump!=iter->nf+iter->size;iterdump++)
        {
         
          if(j/8<iterdump->sizenf && (iterdump->nfind[j/8]>>(j%8))&1)
        {
          //cout<<"swapall "<<i<<" "<<j<<
          //" iter->nf[j] "<<iter->nf[j]<<endl;
          int nbentre=0;
          int indicej=0;
          coeff tmp;
          for(int k=i/8+1;k<=j/8;k++)
            nbentre+=nbbits[iterdump->nfind[k]];
          nbentre+=nbbits[iterdump->nfind[i/8]>>(i%8)];
          nbentre-=nbbits[iterdump->nfind[j/8]>>(j%8)];
          
          for(int k=iterdump->sizenf-1;k>j/8;k--)
            indicej+=nbbits[iterdump->nfind[k]];
          indicej+=nbbits[iterdump->nfind[j/8]>>(j%8)];

          tmp=iterdump->nf[iterdump->size-indicej];
          if((iterdump->nfind[i/8]>>(i%8))&1)
            {
              iterdump->nf=(coeff*)
            MAC_REV_REALLOC<coeff>(iterdump->nf
                       ,iterdump->size*sizeof(coeff)
                       ,(iterdump->size-1)*sizeof(coeff));
               iterdump->nf[iterdump->size-indicej-nbentre]=tmp;
               iterdump->nfind[i/8]|=1<<(i%8);
               iterdump->nfind[j/8]&=~(1<<(j%8));//^=1<<(j%8);
               iterdump->size--;

            }
          else
            {
              for(int k=0;k<nbentre;k++)
            iterdump->nf[iterdump->size-indicej-k]
              =iterdump->nf[iterdump->size-indicej-k-1];
              iterdump->nf[iterdump->size-indicej-nbentre]=tmp;
              iterdump->nfind[i/8]|=1<<(i%8);
              iterdump->nfind[j/8]&=~(1<<(j%8));//^=1<<(j%8);
            }
          //    iter->nf[i]=iter->nf[j];
          //    iter->nf[j]=0;
#ifdef DEB  
      if ((iterdump->sizenf*8>sizeplace) && ((iterdump->nfind[iterdump->sizenf-1]
                         >>(sizeplace%8))&1))
            {cout<<"swapall "<<iterdump->sizenf<<" "<<sizeplace<<endl;exit(10);}
#endif
        }
 
        }
    }
    }
  tmpmon=int2mon_[i];
  int2mon_[i]=int2mon_[j];
  int2mon_[j]=tmpmon;
  for(pos1=0;mon2intint[pos1]!=j;pos1++);
  for(pos2=0;mon2intint[pos2]!=i;pos2++);
  mon2intint[pos1]=i;
  mon2intint[pos2]=j;

#ifdef unimul
  for(int k=0;k<nbvars;k++)
    {
      for(int l=0;l<sizeplace;l++)
    {
      if(multiple[k][l]==i)
        multiple[k][l]=j;
      else if(multiple[k][l]==j)
        multiple[k][l]=i;
    }
      int stock=multiple[k][i];
      multiple[k][i]=multiple[k][j];
      multiple[k][j]=stock;
    }
#endif
#ifdef uninf
  for(int k=0;k<nbvars;k++)
    {
      pol stock=(*((pol**)nfmul+k))[i];
      (*((pol**)nfmul+k))[i]=(*((pol**)nfmul+k))[j];
      (*((pol**)nfmul+k))[j]=stock;
    }
#endif

}

void freeint2mon(int k)
{
  //memmove(int2mon_+k,int2mon_+j+1,(size-j-1)*sizeof(mon));
  int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,sizeplace*sizeof(mon)
                      ,(k)*sizeof(mon));
#ifdef unimul
  for(int i=0;i<nbvars;i++)
    multiple[i]=(int *)realloc(multiple[i],k*sizeof(int));
#endif 
#ifdef uninf
  for(int i=0;i<nbvars;i++)
    ((pol**)nfmul)[i]=(pol*)
      MAC_REV_REALLOC<pol >(
      ((pol**)nfmul)[i],sizeplace*sizeof(pol),k*sizeof(pol));


#endif
}
void freemon(int j)
{
  int k;
  //memmove(int2mon_+j,int2mon_+j+1,(size-j-1)*sizeof(mon));
  //int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,size*sizeof(mon)
  //                  ,(size-1)*sizeof(mon));
  for(k=0;mon2intint[k]!=j;k++);
  //cout<<"k "<<k<<" et size "<<size<<endl;
  memmove(mon2intint+k,mon2intint+k+1,(sizeplace-k-1)*sizeof(int));
  for(int i=k;i<sizeplace-1;i++)
    mon2intmon[i]=mon2intmon[i+1];
  mon2intmon[sizeplace-1]=mon(0);
  //memmove(mon2intmon+k,mon2intmon+k+1,(size-k-1)*sizeof(mon));
  mon2intint=(int*)MAC_REV_REALLOC<int>(mon2intint,sizeplace*sizeof(int)
                   ,(sizeplace-1)*sizeof(int));
  mon2intmon=(mon*)MAC_REV_REALLOC<mon>(mon2intmon,sizeplace*sizeof(mon)
                    ,(sizeplace-1)*sizeof(mon));
  //cout<<"ici "<<endl;
  sizeplace--;
}  

void serveurcompress(int i)
{
  int tmpsize=sizeplace;
  freeint2mon(i+2);
  for(int k=i+2;k<tmpsize;k++)
    freemon(k);
  //for(int j=0;j<size;j++)
  //  cout<<j<<" les pos possibles "<<mon2intint[j]<<" "<<mon2intmon[j]<<" int2mon "<<int2mon_[mon2intint[j]]<<endl;
  // size=i+2;
}

template<typename typPk, typename typdump>
void Docompress(int i, typPk & Pk, typdump& dump)
{
  //typedef typename typPk::value_type::monom_t mon;
  typedef typename typPk::value_type::coeff_t coeff;
  typedef typename typdump::value_type dumpstruct;
  mon tmpmon;
  
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    if(i<iter->sizenf*8)
      {
    int k;
    for(k=i/8;(k>=0) && !(iter->nfind[k]);k--);
    //  cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
    iter->nfind=(unsigned char*)MAC_REV_REALLOC<unsigned char>(iter->nfind
                        ,iter->sizenf
                        ,(k+1));
#ifdef DEB
    cout<<"I "<<i<<" et iter->sizenf "<<iter->sizenf<<endl;
#endif  
    iter->sizenf=k+1;
    
      }
  
  for(typename typdump::iterator iter=dump.begin();
      iter!=dump.end();iter++)
    //if(iter!=dump.rend())  
    {
      for(typename dumpstruct::pol_t *iterdump=iter->nf;
      iterdump!=iter->nf+iter->size;iterdump++)
    if(i<iterdump->sizenf*8)
    {
      int k;
      for(k=i/8;k>=0 && !(iterdump->nfind[k]);k--);
      iterdump->nfind=(unsigned char*)
        MAC_REV_REALLOC<unsigned char>(iterdump->nfind
                       ,iterdump->sizenf
                       ,(k+1));
      iterdump->sizenf=k+1;
    }
    }
}

template<typename typdump, typename Base, typename typPk>
void compress(typPk & Pk, typdump & dump, const Base  &b, int k)
{
  //  return;
  //typedef typename typPk::value_type pol;
  //typedef typename pol::monom_t mon;
  mon tmpmon;
  int i=0;int j=sizeplacemon()-1;
#ifdef DEBUG
  displaymon();
  //cout<<"sizeplacemon "<<sizeplacemon()<<endl;
  //cout<<"Docompress"<<endl;

  cout<<"poly avantcompress "<<Pk.size()<<endl;
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    cout<<invconv<Poly>(*iter)<<endl;       
#endif
  for(i=0;i<j;i++)
    {
      int2mon(i,tmpmon);
      if(!IsinB(tmpmon,b))
    //On peut le virer
    {
      for(;j>i;j--)
        {
          int2mon(j,tmpmon);
          if(IsinB(tmpmon,b))
        break;
          //  cout<<tmpmon<<" n'est pas dans B"<<endl;
        }
      if(i==j) break; //c fini on a plus rien a faire ici
      
      //cout<<" swap "<<i<<" "<<int2mon_[i]<<" et "<<j<<" "<<int2mon_[j]<<endl;
      swap_all(i,j,Pk,dump);
    }

    }
  cout<<"i ici place "<<i<<endl;
  int2mon(i,tmpmon);
  for(;!IsinB(tmpmon,b);i--) 
    {
      int2mon(i,tmpmon);
      //cout<<"tmp mon "<<tmpmon<<endl;
    }
  Docompress(i+1,Pk,dump);
  serveurcompress(i);
}

template<typename typPk, typename typdump>
void swap_all(int i, int j, typPk & Pk , typPk &res,typdump& dump)
{
  //hypothese i<j
  //
  typedef typename typPk::value_type::coeff_t coeff;
  //typedef typename typPk::value_type::monom_t mon;
  typedef typename typdump::value_type dumpstruct;
  mon tmpmon,tmpmon2;
  int deg,pos1,pos2;
  int2mon(j,tmpmon);
  int2mon(i,tmpmon2);
  deg=tmpmon.GetDegree();
#ifdef DEBUG
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    cout<<"swap "<<invconv<Poly>(*iter)<<endl;
  cout<<"je swap "<<tmpmon<<" et "<<tmpmon2<<endl;
#endif
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    if(j/8<iter->sizenf && ((iter->nfind[j/8]>>(j%8))&1))
      {
#ifdef DEBUG    
    cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<endl;
    //cout<<"x1*x3 a pour indice "<<mon2int(mon(1,1)*mon(3,1))<<endl;
#endif
    int nbentre=0;
    int indicej=0,indicei=0;
    coeff tmp;
    for(int k=i/8+1;k<=j/8;k++)
      nbentre+=nbbits[iter->nfind[k]];
    nbentre+=nbbits[iter->nfind[i/8]>>(i%8)];
    nbentre-=nbbits[iter->nfind[j/8]>>(j%8)];
    //nbentre--;
    //nbentre-=2;//on compt i et j dedans dans les formules precedentes
    
    for(int k=iter->sizenf-1;k>j/8;k--)
      indicej+=nbbits[iter->nfind[k]];
    indicej+=nbbits[iter->nfind[j/8]>>(j%8)];
    //  indicej--;
    for(int k=iter->sizenf-1;k>i/8;k--)
      indicei+=nbbits[iter->nfind[k]];
    indicei+=nbbits[iter->nfind[i/8]>>(i%8)];
#ifdef DEB
    cout<<iter->size<<endl<<indicej<<endl<<nbentre<<endl;
    cout<<"iter->size-indicej-nbentre+1 "<<iter->size-indicej-nbentre+1<<" et indice i "<<indicei<<" indicej "<<indicej<<endl;
    
    cout<<"iter->nf[iter-szie-indicej] "
        <<iter->nf[iter->size-indicej]<<endl;
    cout<<"iter->nf[iter-size-indicej-nbentre] "
        <<iter->nf[iter->size-indicej-nbentre]<<endl;
#endif
    tmp=iter->nf[iter->size-indicej];
    if((iter->nfind[i/8]>>(i%8))&1)
      {
        iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
                          ,iter->size*sizeof(coeff)
                          ,(iter->size-1)*sizeof(coeff));
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&= ~(1<<(j%8));
        iter->size--;
      }
    else
      {
        for(int k=0;k<nbentre;k++)
          iter->nf[iter->size-indicej-k]=iter->nf[iter->size-indicej-k-1];
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&= ~(1<<(j%8));
    
      }
    //  iter->nf[i]=iter->nf[j];
    //  iter->nf[j]=0;
#ifdef DEB
    if ((iter->sizenf*8>sizeplace) && ((iter->nfind[iter->sizenf-1]
                       >>(sizeplace%8))&1))
      {cout<<"swapall "<<iter->sizenf<<" "<<sizeplace<<endl;exit(10);}
#endif
      }
  //RES
  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
    if(j/8<iter->sizenf && ((iter->nfind[j/8]>>(j%8))&1))
      {
#ifdef DEB  
    cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<endl;
    //cout<<"x1*x3 a pour indice "<<mon2int(mon(1,1)*mon(3,1))<<endl;
#endif
    int nbentre=0;
    int indicej=0,indicei=0;
    coeff tmp;
    for(int k=i/8+1;k<=j/8;k++)
      nbentre+=nbbits[iter->nfind[k]];
    nbentre+=nbbits[iter->nfind[i/8]>>(i%8)];
    nbentre-=nbbits[iter->nfind[j/8]>>(j%8)];
    //nbentre--;
    //nbentre-=2;//on compt i et j dedans dans les formules precedentes
    
    for(int k=iter->sizenf-1;k>j/8;k--)
      indicej+=nbbits[iter->nfind[k]];
    indicej+=nbbits[iter->nfind[j/8]>>(j%8)];
    //  indicej--;
    for(int k=iter->sizenf-1;k>i/8;k--)
      indicei+=nbbits[iter->nfind[k]];
    indicei+=nbbits[iter->nfind[i/8]>>(i%8)];
#ifdef DEB
    cout<<iter->size<<endl<<indicej<<endl<<nbentre<<endl;
    cout<<"iter->size-indicej-nbentre+1 "<<iter->size-indicej-nbentre+1<<" et indice i "<<indicei<<" indicej "<<indicej<<endl;
    
    cout<<"iter->nf[iter-szie-indicej] "
        <<iter->nf[iter->size-indicej]<<endl;
    cout<<"iter->nf[iter-size-indicej-nbentre] "
        <<iter->nf[iter->size-indicej-nbentre]<<endl;
#endif
    tmp=iter->nf[iter->size-indicej];
    if((iter->nfind[i/8]>>(i%8))&1)
      {
        iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
                          ,iter->size*sizeof(coeff)
                          ,(iter->size-1)*sizeof(coeff));
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&= ~(1<<(j%8));
        iter->size--;
      }
    else
      {
        for(int k=0;k<nbentre;k++)
          iter->nf[iter->size-indicej-k]=iter->nf[iter->size-indicej-k-1];
        iter->nf[iter->size-indicej-nbentre]=tmp;
        iter->nfind[i/8]|=1<<(i%8);
        iter->nfind[j/8]&= ~(1<<(j%8));
    
      }
    //  iter->nf[i]=iter->nf[j];
    //  iter->nf[j]=0;
#ifdef DEB
    if ((iter->sizenf*8>sizeplace) && ((iter->nfind[iter->sizenf-1]
                       >>(sizeplace%8))&1))
      {cout<<"swapall "<<iter->sizenf<<" "<<sizeplace<<endl;exit(10);}
#endif
      }
  for(typename typdump::iterator iter=dump.begin();iter!=dump.end();iter++)
    {
      
     //if(iter->k<=deg)
    {
      for(typename dumpstruct::pol_t *iterdump=iter->nf;
          iterdump!=iter->nf+iter->size;iterdump++)
        {
         
          if(j/8<iterdump->sizenf && (iterdump->nfind[j/8]>>(j%8))&1)
        {
          //cout<<"swapall "<<i<<" "<<j<<
          //" iter->nf[j] "<<iter->nf[j]<<endl;
          int nbentre=0;
          int indicej=0;
          coeff tmp;
          for(int k=i/8+1;k<=j/8;k++)
            nbentre+=nbbits[iterdump->nfind[k]];
          nbentre+=nbbits[iterdump->nfind[i/8]>>(i%8)];
          nbentre-=nbbits[iterdump->nfind[j/8]>>(j%8)];
          
          for(int k=iterdump->sizenf-1;k>j/8;k--)
            indicej+=nbbits[iterdump->nfind[k]];
          indicej+=nbbits[iterdump->nfind[j/8]>>(j%8)];

          tmp=iterdump->nf[iterdump->size-indicej];
          if((iterdump->nfind[i/8]>>(i%8))&1)
            {
              iterdump->nf=(coeff*)
            MAC_REV_REALLOC<coeff>(iterdump->nf
                       ,iterdump->size*sizeof(coeff)
                       ,(iterdump->size-1)*sizeof(coeff));
               iterdump->nf[iterdump->size-indicej-nbentre]=tmp;
               iterdump->nfind[i/8]|=1<<(i%8);
               iterdump->nfind[j/8]&= ~(1<<(j%8));//^=1<<(j%8);
               iterdump->size--;

            }
          else
            {
              for(int k=0;k<nbentre;k++)
            iterdump->nf[iterdump->size-indicej-k]
              =iterdump->nf[iterdump->size-indicej-k-1];
              iterdump->nf[iterdump->size-indicej-nbentre]=tmp;
              iterdump->nfind[i/8]|=1<<(i%8);
              iterdump->nfind[j/8]&= ~(1<<(j%8));//^=1<<(j%8);
            }
          //    iter->nf[i]=iter->nf[j];
          //    iter->nf[j]=0;
#ifdef DEB  
      if ((iterdump->sizenf*8>sizeplace) && ((iterdump->nfind[iterdump->sizenf-1]
                         >>(sizeplace%8))&1))
            {cout<<"swapall "<<iterdump->sizenf<<" "<<sizeplace<<endl;exit(10);}
#endif
        }
 
        }
    }
    }
  tmpmon=int2mon_[i];
  int2mon_[i]=int2mon_[j];
  int2mon_[j]=tmpmon;
  for(pos1=0;mon2intint[pos1]!=j;pos1++);
  for(pos2=0;mon2intint[pos2]!=i;pos2++);
  mon2intint[pos1]=i;
  mon2intint[pos2]=j;

#ifdef unimul
  for(int k=0;k<nbvars;k++)
    {
      for(int l=0;l<sizeplace;l++)
    {
      if(multiple[k][l]==i)
        multiple[k][l]=j;
      else if(multiple[k][l]==j)
        multiple[k][l]=i;
    }
      int stock=multiple[k][i];
      multiple[k][i]=multiple[k][j];
      multiple[k][j]=stock;
    }
#endif
#ifdef uninf
  for(int k=0;k<nbvars;k++)
    {
      pol stock=(*((pol**)nfmul+k))[i];
      (*((pol**)nfmul+k))[i]=(*((pol**)nfmul+k))[j];
      (*((pol**)nfmul+k))[j]=stock;
    }
#endif

}

template<typename typPk, typename typdump>
void Docompress(int i, typPk & Pk, typPk &res,typdump& dump)
{
  //typedef typename typPk::value_type::monom_t mon;
  typedef typename typPk::value_type::coeff_t coeff;
  typedef typename typdump::value_type dumpstruct;
  mon tmpmon;
  
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    if(i<iter->size)
      {
    int k;
    for(k=i/8;(k>=0) && !(iter->nfind[k]);k--);
    //  cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
    iter->nfind=(unsigned char*)MAC_REV_REALLOC<unsigned char>(iter->nfind
                        ,iter->sizenf
                        ,(k+1));
    //cout<<"I "<<i<<" et iter->size "<<iter->size<<endl;
    iter->sizenf=k+1;
    
      }
  
  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
    if(i<iter->size)
      {
    int k;
    for(k=i/8;(k>=0) && !(iter->nfind[k]);k--);
    //  cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
    iter->nfind=(unsigned char*)MAC_REV_REALLOC<unsigned char>(iter->nfind
                        ,iter->sizenf
                        ,(k+1));
    //cout<<"I "<<i<<" et iter->size "<<iter->size<<endl;
    iter->sizenf=k+1;
    
      }
  
  for(typename typdump::iterator iter=dump.begin();
      iter!=dump.end();iter++)
    //if(iter!=dump.rend())  
    {
      for(typename dumpstruct::pol_t *iterdump=iter->nf;
      iterdump!=iter->nf+iter->size;iterdump++)
    if(i<iterdump->size)
    {
      int k;
      for(k=i/8;k>=0 && !(iterdump->nfind[k]);k--);
      iterdump->nfind=(unsigned char*)
        MAC_REV_REALLOC<unsigned char>(iterdump->nfind
                       ,iterdump->sizenf
                       ,(k+1));
      iterdump->sizenf=k+1;
    }
    }
}

template<typename typdump, typename Base, typename typPk>
void compress(typPk & Pk, typPk &res, typdump & dump, const Base  &b, int k)
{
  //  return;
  //typedef typename typPk::value_type pol;
  //typedef typename pol::monom_t mon;
  mon tmpmon;
  int i=0;int j=sizeplacemon()-1;
  //cout<<"sizeplacemon "<<sizeplacemon()<<endl;
  //cout<<"Docompress"<<endl;
  for(i=0;i<j;i++)
    {
      int2mon(i,tmpmon);
      if(!IsinB(tmpmon,b))
    //On peut le virer
    {
      for(;j>i;j--)
        {
          int2mon(j,tmpmon);
          if(IsinB(tmpmon,b))
        break;
        }
      if(i==j) break; //c fini on a plus rien a faire ici
      //      cout<<" swap "<<i<<" "<<int2mon_[i]<<" et "<<j<<" "<<int2mon_[j]<<endl;
      swap_all(i,j,Pk,res,dump);
    }

    }
  int2mon(i,tmpmon);
  for(;!IsinB(tmpmon,b);i--) 
    {
      int2mon(i,tmpmon);
      //cout<<"tmp mon "<<tmpmon<<endl;
    }
  Docompress(i+1,Pk,res,dump);
  serveurcompress(i);
}

void freeplacemon()
{
  MAC_REV_FREE<mon>(int2mon_,sizeplace*sizeof(mon));
  MAC_REV_FREE<mon>(mon2intmon,sizeplace*sizeof(mon));
  free(mon2intint);
  sizeplace=0;

}
};//struct monomial_server
#endif