borderbasix: include/borderbasix/placemon.cc Source File

00001 //Requiers type mon to be defined somewhere else
00002 //on tache de rendre l'acces a int2mon et mon2int 
00003 //aussi rapide que possible meme si ca coute 
00004 //un peu, d'inserer puisque par hypothese on fait plus 
00005 //d'appel a int2mon mon2int 
00006 //que l'on insere ou enleve de monomes dedans!
00007 namespace{
00008   int sizeplace;
00009   mon *int2mon_;
00010   mon *mon2intmon;
00011   int *mon2intint;
00012   int (*ord)(const mon &m1,const mon &m2);
00013   int nbvars;
00014 #ifdef unimul
00015   int **multiple;
00016 
00017 #endif 
00018 #ifdef uninf
00019   void **nfmul;
00020 #endif
00021 }
00022 #ifdef unimul
00023 
00024 void displaymon()
00025 {
00026   cout<<"les mon"<<endl;
00027   for(int i=0;i<sizeplace;i++)
00028     cout<<int2mon_[i]<<" ";
00029   cout<<endl;
00030 }
00031 
00032 template<typename mon>
00033 void inline int2mon(const int &i,mon &res);
00034 
00035 template<typename mon>
00036 int inline mon2int(const mon &mm);
00037 
00038 inline void init_multiple(int n)
00039 {
00040   multiple=(int**)malloc(n*sizeof(int*));
00041   for(int i=0;i<n;i++)
00042     multiple[i]=NULL;
00043   nbvars=n;
00044 }
00045 void reinit_multiple()
00046 {
00047   for(int i=0;i<nbvars;i++)
00048     for(int j=0;j<sizeplace;j++)
00049       multiple[i][j]=-2;
00050 }
00051 
00052 template<typename typBase>
00053 inline int mulind(int indexbase, int var, const typBase &b)
00054 {
00055   if(multiple[var][indexbase]==-2)//||(multiple[var][indexbase]>=size))
00056     {
00057       mon tmpmon;
00058       int stock;
00059       int2mon(indexbase,tmpmon);
00060       tmpmon*=mon(var,1);
00061       if(IsinB(tmpmon,b))
00062         {
00063           stock=mon2int(tmpmon);
00064           multiple[var][indexbase]=stock;
00065         }
00066       else 
00067         multiple[var][indexbase]=-1;
00068     }
00069 //   if (multiple[var][indexbase]>=0)
00070 //     cout<<int2mon_[indexbase]<<"*"<<mon(var,1)<<" donne "<<int2mon_[multiple[var][indexbase]]<<endl;
00071   return multiple[var][indexbase];
00072 }
00073 #endif
00074 
00075 #ifdef uninf
00076 template<typename pol>
00077 inline void init_nf(int n)
00078 {
00079   nfmul=(void**)malloc(n*sizeof(pol*));
00080   for(int i=0;i<n;i++)
00081     *((pol**)nfmul+i)=NULL;
00082 }
00083 
00084 template<typename pol>
00085 void reinit_nf()
00086 {
00087   pol toto;
00088   toto.size=-1;
00089   for(int i=0;i<nbvars;i++)
00090     for(int j=0;j<sizeplace;j++)
00091       (*((pol**)nfmul+i))[j]=toto;
00092 }
00093 
00094 template<typename pol,typename typdump,typename Base>
00095 pol nf(int var ,int indmon,const typdump &dump,const Base & b)
00096 {
00097   //  cout<<"c moi c moi"<<endl;
00098   pol res;
00099   if(((*((pol**)nfmul+var)))[indmon].size==-1)
00100     {
00101       typedef typename typdump::value_type dumpstruct;
00102       typedef typename pol::monom_t mon;
00103       res.nf=NULL;
00104       res.size=-1;
00105       mon tmpmon;//=mon(1,var)*int2mon<mon>(indmon);
00106       int deg=0;//=tmpmon.GetDegree()+1;
00107       typename typdump::const_iterator iter;
00108       int2mon(indmon,tmpmon);
00109       deg=tmpmon.GetDegree()+1;
00110       tmpmon*=mon(var,1);
00111       for(iter=dump.begin();
00112           (iter!=dump.end()) && (iter->k!=deg);iter++);
00113       if(iter!=dump.end())//on cherche pas n'importe quoi qd meme
00114         {
00115           int i;
00116           for(i=0;i<iter->size;i++)
00117             {
00118               if(iter->nf[i].ind.rep==tmpmon.rep)
00119                 break;
00120             }
00121           if(i!=iter->size)
00122             res=(iter->nf[i]);
00123         }
00124       ((*((pol**)nfmul+var)))[indmon]=res;
00125     }
00126   return ((*((pol**)nfmul+var)))[indmon];
00127 }
00128 
00129 #endif
00130 
00131 template<typename ptrfun>
00132 void setorder(ptrfun tmpord)
00133 {
00134   ord=(int (*)(const mon &,const mon &))(tmpord);
00135 }
00136 int sizeplacemon()
00137 {
00138   return sizeplace;
00139 }
00140 template<typename mon>
00141 void putmon2(const mon & m,const int poscurrent)
00142 {
00143   int i;
00144   //si le monome est deja introduit on y touche pas
00145   //cout<<"putmon2 atteint"<<endl;
00146   //cout<<"poscurrent "<<poscurrent<<endl;
00147   //cout<<"mon2intmon==NULL?? "<<(mon2intmon==NULL)<<" m "<<m<<endl;
00148   //if (poscurrent<size)
00149   //  cout<<((mon2intmon==NULL)||(mon2intmon[poscurrent]==m))<<endl;
00150   if((mon2intmon==NULL)||(poscurrent==sizeplace)||
00151      (mon2intmon[poscurrent].rep!=m.rep))
00152     {
00153       //  cout<<"moncurent etc passe etc vaut "<<endl;
00154       sizeplace++;
00155 
00156 
00157       mon2intmon=(mon*)MAC_REV_REALLOC<mon>(mon2intmon,(sizeplace-1)*sizeof(mon)
00158                                             ,(sizeplace)*sizeof(mon));
00159       mon2intint=(int*)realloc(mon2intint,sizeplace*sizeof(int));
00160       
00161       //int2mon=(mon*)realloc(int2mon,size*sizeof(mon));
00162       //on vient d'agrandir les tableaux
00163       for(int k=sizeplace-1;k>poscurrent;k--)
00164         mon2intmon[k]=mon2intmon[k-1];
00165 
00166       //memmove((mon2intmon+poscurrent+1),(mon2intmon+poscurrent),
00167       //              (size-1-poscurrent)*sizeof(mon));
00168       memmove((mon2intint+poscurrent+1),(mon2intint+poscurrent),
00169               (sizeplace-1-poscurrent)*sizeof(int));
00170       //on cherche s'il y a un indice dans int2mon libre
00171       for(i=0;i<sizeplace-1;i++)
00172         if (int2mon_[i]==mon(-1)) break;
00173       if (i==sizeplace-1)
00174         {
00175           int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,(sizeplace-1)*sizeof(mon)
00176                                          ,sizeplace*sizeof(mon));
00177 #ifdef unimul
00178           for(int k=0;k<nbvars;k++)
00179             {
00180               //cout<<"j'ai fait un realloc "<<endl;
00181               multiple[k]=(int*)realloc(multiple[k],sizeplace*sizeof(int));
00182               multiple[k][sizeplace-1]=-2;
00183             }
00184 #endif 
00185 #ifdef uninf
00186           for(int k=0;k<nbvars;k++)
00187             {
00188               //cout<<"j'ai fait un realloc "<<endl;
00189               *((pol<mon,COEFF>**)nfmul+k)=(pol<mon,COEFF>*)
00190                                MAC_REV_REALLOC<pol<mon,COEFF> >
00191                 ((void*)*((pol<mon,COEFF>**)nfmul+k)
00192                  ,(sizeplace-1)*sizeof(pol<mon,COEFF>)
00193                  ,sizeplace*sizeof(pol<mon,COEFF>));
00194               ((pol<mon,COEFF>**)nfmul)[k][sizeplace-1].size=-1;
00195             }
00196 #endif 
00197         
00198         }
00199       int2mon_[i]=m;
00200       //cout<<"int2mon_["<<i<<"] vaut "<<m<<endl;
00201       mon2intint[poscurrent]=i;
00202       mon2intmon[poscurrent]=m;
00203       //cout<<"mon2intmon["<<poscurrent<<"] vaut"<<mon2intmon[poscurrent]
00204       //          <<" et est sense valoir "<<m<<endl;
00205     }
00206   return;
00207 }
00208 
00209 template<typename mon>
00210 void putmon(const mon & m)
00211 {
00212   int inf=0,sup=sizeplace,poscurrent=0;
00213   //on commence par localiser l'endroit dans mon2int*
00214   //ou on va rajouter le monom
00215   if(sizeplace!=0)
00216     for(poscurrent=sizeplace/2;ord(mon2intmon[poscurrent+1],
00217                               m)&&
00218           ord(m,mon2intmon[poscurrent-1]);)
00219       {
00220         if(ord(mon2intmon[poscurrent],m)>0)
00221           {
00222             sup=poscurrent;
00223             poscurrent=(inf+sup)/2;
00224           }
00225         else
00226           {
00227             inf=poscurrent;
00228             poscurrent=(inf+sup)/2;
00229           }
00230       }
00231   putmon2(m,poscurrent);
00232   return ;
00233 }
00234 
00235 
00236 template<typename mon>
00237 void removemon(const mon &m)
00238 {
00239   int inf=0,sup,poscurrent,i;
00240   //on commence par localiser l'endroit dans mon2int*
00241   //ou on va rajouter le monom
00242   for(poscurrent=sizeplace/2;ord(mon2intmon[poscurrent+1],
00243                                 m)&&
00244         ord(m,
00245             mon2intmon[poscurrent-1]);)
00246     {
00247       if(ord(mon2intmon[poscurrent],m)>0)
00248         {
00249           sup=poscurrent;
00250           poscurrent=(inf+sup)/2;
00251         }
00252       else
00253         {
00254           inf=poscurrent;
00255           poscurrent=(inf+sup)/2;
00256         }
00257     }
00258   //si le monome n'est PAS deja introduit on  touche a rien
00259   if(mon2intmon[poscurrent]!=m)
00260     {
00261       //on libere l'endroit ou se trouve ce monome
00262       int2mon_[poscurrent]=mon(-1);
00263       //on recopier apres dans les mon2int pour enlever le monome
00264       memmove((mon2intmon+poscurrent),(mon2intmon+poscurrent+1),
00265               (sizeplace-poscurrent-2)*sizeof(mon));
00266       memmove((mon2intint+poscurrent),(mon2intint+poscurrent+1),
00267               (sizeplace-poscurrent-2)*sizeof(int));
00268       //on retrecit les mon2int*
00269        sizeplace--;
00270        mon2intmon=(mon*)realloc(mon2intmon,sizeplace*sizeof(mon));
00271        mon2intint=(int*)realloc(mon2intint,sizeplace*sizeof(int));
00272     }
00273   return;
00274 }
00275 
00276 
00277 template<typename mon>
00278 void affplace(const mon &m,int p)
00279 {
00280   int2mon_[p]=m;
00281 }
00282 template<typename mon>
00283 void freeplace(int p)
00284 {
00285   int2mon_[p]=mon(-1);
00286 }
00287 template<typename mon>
00288 void inline int2mon(const int &i,mon &res)
00289 {
00290   res=mon(1,(int2mon_+i)->rep);
00291 }
00292 
00293 template<typename mon>
00294 int inline mon2int(const mon &mm)
00295 {
00296   typedef typename mon::coeff_t coeff;
00297   //mon2intmon et mon2intint doivent etre trie 
00298   //par aordre (ord) croissant
00299   //
00300   int inf=0,sup=sizeplace,poscurrent;
00301   mon m=mm;
00302   m.SetCoeff(1);
00303   // cout<<"rentre mon2int"<<endl;
00304   //cout<<"size "<<size<<endl;
00305   if(sizeplace==0) {mon2intmon=NULL;mon2intint=NULL;
00306   int2mon_=NULL;putmon(m);
00307   //cout<<"transition mon2int"<<endl;
00308   };
00309   //cout<<"sup "<<sup<<" inf "<<inf<<endl;
00310   for(poscurrent=sizeplace/2;(sup-inf>1)&&
00311         (mon2intmon[poscurrent].rep!=m.rep);)
00312     {
00313       //  cout<<"poscurrent "<<poscurrent<<endl;
00314       if(ord(mon2intmon[poscurrent],m)>0)
00315         {
00316           sup=poscurrent;
00317           poscurrent=(inf+sup)/2;
00318         }
00319       else
00320         {
00321           inf=poscurrent;
00322           poscurrent=(inf+sup)/2;
00323         }
00324     }
00325   //cout<<"sortie for mon2int "<<poscurrent<<endl;
00326   //cout<<"les monome "<<mon2intmon[poscurrent]<<" "<<m<<endl;
00327   if (mon2intmon[poscurrent].rep!=m.rep) 
00328     {
00329       if (ord(mon2intmon[poscurrent],m)<0) poscurrent++;
00330       //if(poscurrent<size)
00331         //cout<<"ord(mon2intmon[poscurrent],m) "
00332         //  <<ord(mon2intmon[poscurrent],m)<<endl;
00333       //cout<<"appel putmon2 "<<endl;
00334       putmon2(m,poscurrent);
00335     }
00336   //cout<<"sorti mon2int"<<endl;
00337   return mon2intint[poscurrent];
00338 }
00339 
00340 template<typename typPk, typename typdump>
00341 void swap_all(int i, int j, typPk & Pk ,typdump& dump)
00342 {
00343   typedef typename typPk::value_type::monom_t mon;
00344   typedef typename typdump::value_type dumpstruct;
00345   mon tmpmon;
00346   int deg,pos1,pos2;
00347   int2mon(j,tmpmon);
00348   deg=tmpmon.GetDegree();
00349   //  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00350   //  cout<<"swap "<<invconv<Poly>(*iter)<<endl;
00351   for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00352     if(j<iter->size&&!Iszero(iter->nf[j]))
00353       {
00354         //cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<iter->nf[j]<<endl;
00355         iter->nf[i]=iter->nf[j];
00356         iter->nf[j]=0;
00357       }
00358   for(typename typdump::iterator iter=dump.begin();iter!=dump.end();iter++)
00359     {
00360       //if(iter->k<=deg)
00361         {
00362           for(typename dumpstruct::pol_t *iterdump=iter->nf;
00363               iterdump!=iter->nf+iter->size;iterdump++)
00364             {
00365               if(j<iterdump->size&&!Iszero(iterdump->nf[j]))
00366                 {
00367                   iterdump->nf[i]=iterdump->nf[j];
00368                   iterdump->nf[j]=0;
00369                 }
00370             }
00371         }
00372     }
00373   tmpmon=int2mon_[i];
00374   int2mon_[i]=int2mon_[j];
00375   int2mon_[j]=tmpmon;
00376   for(pos1=0;mon2intint[pos1]!=j;pos1++);
00377   for(pos2=0;mon2intint[pos2]!=i;pos2++);
00378   mon2intint[pos1]=i;
00379   mon2intint[pos2]=j;
00380 
00381 #ifdef unimul
00382   for(int k=0;k<nbvars;k++)
00383     {
00384       for(int l=0;l<sizeplace;l++)
00385         {
00386           if(multiple[k][l]==i)
00387             multiple[k][l]=j;
00388           else if(multiple[k][l]==j)
00389             multiple[k][l]=i;
00390         }
00391       int stock=multiple[k][i];
00392       multiple[k][i]=multiple[k][j];
00393       multiple[k][j]=stock;
00394     }
00395 #endif
00396 #ifdef uninf
00397   for(int k=0;k<nbvars;k++)
00398     {
00399       pol<mon,COEFF> stock=(*((pol<mon,COEFF>**)nfmul+k))[i];
00400       (*((pol<mon,COEFF>**)nfmul+k))[i]=(*((pol<mon,COEFF>**)nfmul+k))[j];
00401       (*((pol<mon,COEFF>**)nfmul+k))[j]=stock;
00402     }
00403 #endif
00404 
00405 }
00406 
00407 void freeint2mon(int k)
00408 {
00409   //memmove(int2mon_+k,int2mon_+j+1,(size-j-1)*sizeof(mon));
00410   int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,sizeplace*sizeof(mon)
00411                                       ,(k)*sizeof(mon));
00412 #ifdef unimul
00413   for(int i=0;i<nbvars;i++)
00414     multiple[i]=(int *)realloc(multiple[i],k*sizeof(int));
00415 #endif 
00416 #ifdef uninf
00417   for(int i=0;i<nbvars;i++)
00418     ((pol<mon,COEFF>**)nfmul)[i]=(pol<mon,COEFF>*)
00419       MAC_REV_REALLOC<pol<mon,COEFF> >(
00420       ((pol<mon,COEFF>**)nfmul)[i],sizeplace*sizeof(pol<mon,COEFF>),
00421       k*sizeof(pol<mon,COEFF>));
00422 
00423 
00424 #endif
00425 }
00426 void freemon(int j)
00427 {
00428   int k;
00429   //memmove(int2mon_+j,int2mon_+j+1,(size-j-1)*sizeof(mon));
00430   //int2mon_=(mon*)MAC_REV_REALLOC<mon>(int2mon_,size*sizeof(mon)
00431   //                          ,(size-1)*sizeof(mon));
00432   for(k=0;mon2intint[k]!=j;k++);
00433   //cout<<"k "<<k<<" et size "<<size<<endl;
00434   memmove(mon2intint+k,mon2intint+k+1,(sizeplace-k-1)*sizeof(int));
00435   for(int i=k;i<sizeplace-1;i++)
00436     mon2intmon[i]=mon2intmon[i+1];
00437   mon2intmon[sizeplace-1]=mon(0);
00438   //memmove(mon2intmon+k,mon2intmon+k+1,(size-k-1)*sizeof(mon));
00439   mon2intint=(int*)MAC_REV_REALLOC<int>(mon2intint,sizeplace*sizeof(int)
00440                                    ,(sizeplace-1)*sizeof(int));
00441   mon2intmon=(mon*)MAC_REV_REALLOC<mon>(mon2intmon,sizeplace*sizeof(mon)
00442                                         ,(sizeplace-1)*sizeof(mon));
00443   sizeplace--;
00444 }  
00445 
00446 void serveurcompress(int i)
00447 {
00448   int tmpsize=sizeplace;
00449   freeint2mon(i+2);
00450   for(int k=i+2;k<tmpsize;k++)
00451     freemon(k);
00452   //for(int j=0;j<size;j++)
00453   //  cout<<j<<" les pos possibles "<<mon2intint[j]<<" "<<mon2intmon[j]<<" int2mon "<<int2mon_[mon2intint[j]]<<endl;
00454   // size=i+2;
00455 }
00456 
00457 template<typename typPk, typename typdump>
00458 void Docompress(int i, typPk & Pk, typdump& dump)
00459 {
00460   typedef typename typPk::value_type::monom_t mon;
00461   typedef typename typPk::value_type::coeff_t coeff;
00462   typedef typename typdump::value_type dumpstruct;
00463   mon tmpmon;
00464   
00465   for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00466     if(i<iter->size)
00467       {
00468         int k;
00469         for(k=i;k>=0&&Iszero(iter->nf[k]);k--);
00470         //      cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
00471         iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
00472                                                 ,iter->size*sizeof(coeff)
00473                                                 ,(k+1)*sizeof(coeff));
00474         //cout<<"I "<<i<<" et iter->size "<<iter->size<<endl;
00475         iter->size=k+1;
00476       }
00477   
00478   for(typename typdump::iterator iter=dump.begin();
00479       iter!=dump.end();iter++)
00480     //if(iter!=dump.rend())  
00481     {
00482       for(typename dumpstruct::pol_t *iterdump=iter->nf;
00483           iterdump!=iter->nf+iter->size;iterdump++)
00484         if(i<iterdump->size)
00485         {
00486           int k;
00487           for(k=i;k>=0&&Iszero(iterdump->nf[k]);k--);
00488           iterdump->nf=(coeff*)MAC_REV_REALLOC<coeff>(iterdump->nf
00489                                               ,iterdump->size*sizeof(coeff)
00490                                               ,(k+1)*sizeof(coeff));
00491           iterdump->size=k+1;
00492         }
00493     }
00494 }
00495 
00496 template<typename typdump, typename Base, typename typPk>
00497 void compress(typPk & Pk, typdump & dump, const Base  &b, int k)
00498 {
00499   //return;
00500   typedef typename typPk::value_type pol;
00501   typedef typename pol::monom_t mon;
00502   mon tmpmon;
00503   int i=0;int j=sizeplacemon()-1;
00504   //cout<<"Docompress"<<endl;
00505   for(i=0;i<j;i++)
00506     {
00507       int2mon(i,tmpmon);
00508       if(!IsinB(tmpmon,b))
00509         //On peut le virer
00510         {
00511           for(;j>i;j--)
00512             {
00513               int2mon(j,tmpmon);
00514               if(IsinB(tmpmon,b))
00515                 break;
00516             }
00517           if(i==j) break; //c fini on a plus rien a faire ici
00518           //      cout<<" swap "<<i<<" "<<int2mon_[i]<<" et "<<j<<" "<<int2mon_[j]<<endl;
00519           swap_all(i,j,Pk,dump);
00520         }
00521 
00522     }
00523   int2mon(i,tmpmon);
00524   for(;!IsinB(tmpmon,b);i--) 
00525     {
00526       int2mon(i,tmpmon);
00527       //cout<<"tmp mon "<<tmpmon<<endl;
00528     }
00529   Docompress(i+1,Pk,dump);
00530   serveurcompress(i);
00531 }
00532 
00533 
00534 
00535 template<typename typPk, typename typdump>
00536 void swap_all(int i, int j, typPk & Pk , typPk & redspol,typdump& dump)
00537 {
00538   typedef typename typPk::value_type::monom_t mon;
00539   typedef typename typdump::value_type dumpstruct;
00540   mon tmpmon;
00541   int deg,pos1,pos2;
00542   int2mon(j,tmpmon);
00543   deg=tmpmon.GetDegree();
00544   //  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00545   //  cout<<"swap "<<invconv<Poly>(*iter)<<endl;
00546   for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00547     if(j<iter->size&&!Iszero(iter->nf[j]))
00548       {
00549         //cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<iter->nf[j]<<endl;
00550         iter->nf[i]=iter->nf[j];
00551         iter->nf[j]=0;
00552       }
00553   for(typename typPk::iterator iter=redspol.begin();iter!=redspol.end();iter++)
00554     if(j<iter->size&&!Iszero(iter->nf[j]))
00555       {
00556         //cout<<"swapall "<<i<<" "<<j<<" iter->nf[j] "<<iter->nf[j]<<endl;
00557         iter->nf[i]=iter->nf[j];
00558         iter->nf[j]=0;
00559       }
00560   
00561   for(typename typdump::iterator iter=dump.begin();iter!=dump.end();iter++)
00562     {
00563       //if(iter->k<=deg)
00564         {
00565           for(typename dumpstruct::pol_t *iterdump=iter->nf;
00566               iterdump!=iter->nf+iter->size;iterdump++)
00567             {
00568               if(j<iterdump->size&&!Iszero(iterdump->nf[j]))
00569                 {
00570                   iterdump->nf[i]=iterdump->nf[j];
00571                   iterdump->nf[j]=0;
00572                 }
00573             }
00574         }
00575     }
00576   tmpmon=int2mon_[i];
00577   int2mon_[i]=int2mon_[j];
00578   int2mon_[j]=tmpmon;
00579   for(pos1=0;mon2intint[pos1]!=j;pos1++);
00580   for(pos2=0;mon2intint[pos2]!=i;pos2++);
00581   mon2intint[pos1]=i;
00582   mon2intint[pos2]=j;
00583 
00584 #ifdef unimul
00585   for(int k=0;k<nbvars;k++)
00586     {
00587       for(int l=0;l<sizeplace;l++)
00588         {
00589           if(multiple[k][l]==i)
00590             multiple[k][l]=j;
00591           else if(multiple[k][l]==j)
00592             multiple[k][l]=i;
00593         }
00594       int stock=multiple[k][i];
00595       multiple[k][i]=multiple[k][j];
00596       multiple[k][j]=stock;
00597     }
00598 #endif
00599 #ifdef uninf
00600   for(int k=0;k<nbvars;k++)
00601     {
00602       pol<mon,COEFF> stock=(*((pol<mon,COEFF>**)nfmul+k))[i];
00603       (*((pol<mon,COEFF>**)nfmul+k))[i]=(*((pol<mon,COEFF>**)nfmul+k))[j];
00604       (*((pol<mon,COEFF>**)nfmul+k))[j]=stock;
00605     }
00606 #endif
00607 
00608 }
00609 
00610 template<typename typPk, typename typdump>
00611 void Docompress(int i, typPk & Pk, typPk & redspol,typdump& dump)
00612 {
00613   typedef typename typPk::value_type::monom_t mon;
00614   typedef typename typPk::value_type::coeff_t coeff;
00615   typedef typename typdump::value_type dumpstruct;
00616   mon tmpmon;
00617   
00618   for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
00619     if(i<iter->size)
00620       {
00621         int k;
00622         for(k=i;k>=0&&Iszero(iter->nf[k]);k--);
00623         //      cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
00624         iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
00625                                                 ,iter->size*sizeof(coeff)
00626                                                 ,(k+1)*sizeof(coeff));
00627         //cout<<"I "<<i<<" et iter->size "<<iter->size<<endl;
00628         iter->size=k+1;
00629       }
00630   for(typename typPk::iterator iter=redspol.begin();iter!=redspol.end();iter++)
00631     if(i<iter->size)
00632       {
00633         int k;
00634         for(k=i;k>=0&&Iszero(iter->nf[k]);k--);
00635         //      cout<<" do compress K "<<k<<" "<<iter->nf[k]<<endl;
00636         iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
00637                                                 ,iter->size*sizeof(coeff)
00638                                                 ,(k+1)*sizeof(coeff));
00639         //cout<<"I "<<i<<" et iter->size "<<iter->size<<endl;
00640         iter->size=k+1;
00641       }
00642 
00643   for(typename typdump::iterator iter=dump.begin();
00644       iter!=dump.end();iter++)
00645     //if(iter!=dump.rend())  
00646     {
00647       for(typename dumpstruct::pol_t *iterdump=iter->nf;
00648           iterdump!=iter->nf+iter->size;iterdump++)
00649         if(i<iterdump->size)
00650         {
00651           int k;
00652           for(k=i;k>=0&&Iszero(iterdump->nf[k]);k--);
00653           iterdump->nf=(coeff*)MAC_REV_REALLOC<coeff>(iterdump->nf
00654                                               ,iterdump->size*sizeof(coeff)
00655                                               ,(k+1)*sizeof(coeff));
00656           iterdump->size=k+1;
00657         }
00658     }
00659 }
00660 
00661 template<typename typdump, typename Base, typename typPk>
00662 void compress(typPk & Pk, typPk &redspol,typdump & dump, const Base  &b, int k)
00663 {
00664   //return;
00665   typedef typename typPk::value_type pol;
00666   typedef typename pol::monom_t mon;
00667   mon tmpmon;
00668   int i=0;int j=sizeplacemon()-1;
00669   //cout<<"Docompress"<<endl;
00670   for(i=0;i<j;i++)
00671     {
00672       int2mon(i,tmpmon);
00673       if(!IsinB(tmpmon,b))
00674         //On peut le virer
00675         {
00676           for(;j>i;j--)
00677             {
00678               int2mon(j,tmpmon);
00679               if(IsinB(tmpmon,b))
00680                 break;
00681             }
00682           if(i==j) break; //c fini on a plus rien a faire ici
00683           //      cout<<" swap "<<i<<" "<<int2mon_[i]<<" et "<<j<<" "<<int2mon_[j]<<endl;
00684           swap_all(i,j,Pk,redspol,dump);
00685         }
00686 
00687     }
00688   int2mon(i,tmpmon);
00689   for(;!IsinB(tmpmon,b);i--) 
00690     {
00691       int2mon(i,tmpmon);
00692       //cout<<"tmp mon "<<tmpmon<<endl;
00693     }
00694   Docompress(i+1,Pk,redspol,dump);
00695   serveurcompress(i);
00696 }
00697 void freeplacemon()
00698 {
00699   MAC_REV_FREE<mon>(int2mon_,sizeplace*sizeof(mon));
00700   MAC_REV_FREE<mon>(mon2intmon,sizeplace*sizeof(mon));
00701   free(mon2intint);
00702   sizeplace=0;
00703 
00704 }