CMS 3D CMS Logo

/data/refman/pasoursint/CMSSW_5_3_3/src/PhysicsTools/JetMCUtils/interface/combination.h

Go to the documentation of this file.
00001 //=======================================================
00002 // combination.h
00003 // Description : Template class to find combinations
00004 //=======================================================
00005 // Copyright 2003 - 2006 Wong Shao Voon
00006 // No warranty, implied or expressed, is included.
00007 // Author is not liable for any type of loss through 
00008 // the use of this source code. Use it at your own risk!
00009 //=======================================================
00010 
00011 
00012 #ifndef __COMBINATION_H__
00013 #define __COMBINATION_H__
00014 
00015 
00016 namespace stdcomb
00017 {
00018 
00019 // Non recursive template function
00020 template <class BidIt>
00021 
00022 inline bool next_combination(BidIt n_begin, BidIt n_end,
00023 BidIt r_begin, BidIt r_end)
00024 {
00025   
00026   bool boolmarked=false;
00027   BidIt r_marked;
00028   
00029   BidIt n_it1=n_end;
00030   --n_it1;
00031   
00032   
00033   BidIt tmp_r_end=r_end;
00034   --tmp_r_end;
00035   
00036   for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
00037   {
00038     if(*r_it1==*n_it1 )
00039     {
00040       if(r_it1!=r_begin) //to ensure not at the start of r sequence
00041       {
00042         boolmarked=true;
00043         r_marked=(--r_it1);
00044         ++r_it1;//add it back again 
00045         continue;
00046       }
00047       else // it means it is at the start the sequence, so return false
00048         return false;      
00049     }
00050     else //if(*r_it1!=*n_it1 )
00051     {
00052       //marked code
00053       if(boolmarked==true)
00054       {
00055         //for loop to find which marked is in the first sequence
00056         BidIt n_marked;//mark in first sequence
00057         for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
00058           if(*r_marked==*n_it2) {n_marked=n_it2;break;}
00059       
00060     
00061         BidIt n_it3=++n_marked;    
00062         for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
00063         {
00064           *r_it2=*n_it3;
00065         }
00066         return true;
00067       }
00068       for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
00069         if(*r_it1==*n_it4)
00070         {
00071           *r_it1=*(++n_it4);
00072           return true;           
00073         }
00074     }
00075   }  
00076 
00077   return true;//will never reach here    
00078 }
00079 
00080 // Non recursive template function with Pred
00081 template <class BidIt, class Prediate>
00082 
00083 inline bool next_combination(
00084         BidIt n_begin, 
00085         BidIt n_end,
00086         BidIt r_begin, 
00087         BidIt r_end,
00088         Prediate Equal)
00089 {
00090   
00091   bool boolmarked=false;
00092   BidIt r_marked;
00093   
00094   BidIt n_it1=n_end;
00095   --n_it1;
00096   
00097   
00098   BidIt tmp_r_end=r_end;
00099   --tmp_r_end;
00100   
00101   for(BidIt r_it1=tmp_r_end; r_it1!=r_begin || r_it1==r_begin; --r_it1,--n_it1)
00102   {
00103     if( Equal( *r_it1, *n_it1) )
00104     {
00105       if(r_it1!=r_begin) //to ensure not at the start of r sequence
00106       {
00107         boolmarked=true;
00108         r_marked=(--r_it1);
00109         ++r_it1;//add it back again 
00110         continue;
00111       }
00112       else // it means it is at the start the sequence, so return false
00113         return false;      
00114     }
00115     else //if(*r_it1!=*n_it1 )
00116     {
00117       //marked code
00118       if(boolmarked==true)
00119       {
00120         //for loop to find which marked is in the first sequence
00121         BidIt n_marked;//mark in first sequence
00122         for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
00123           if( Equal( *r_marked, *n_it2) ) {n_marked=n_it2;break;}
00124       
00125     
00126         BidIt n_it3=++n_marked;    
00127         for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
00128         {
00129           *r_it2=*n_it3;
00130         }
00131         return true;
00132       }
00133       for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
00134         if( Equal(*r_it1, *n_it4) )
00135         {
00136           *r_it1=*(++n_it4);
00137           return true;           
00138         }
00139     }
00140   }  
00141 
00142   return true;//will never reach here    
00143 }
00144 
00145 
00146 // Non recursive template function
00147 template <class BidIt>
00148 
00149 inline bool prev_combination(BidIt n_begin, BidIt n_end,
00150 BidIt r_begin, BidIt r_end)
00151 {
00152   
00153   bool boolsame=false;
00154   BidIt marked;//for r
00155   BidIt r_marked;
00156   BidIt n_marked;
00157   
00158 
00159   BidIt tmp_n_end=n_end;
00160   --tmp_n_end;
00161   
00162   BidIt r_it1=r_end;
00163   --r_it1;
00164   
00165   for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
00166   {
00167     if(*r_it1==*n_it1)
00168     {
00169       r_marked=r_it1;
00170       n_marked=n_it1;
00171       break;
00172     }
00173   }  
00174   
00175   BidIt n_it2=n_marked;
00176 
00177 
00178   BidIt tmp_r_end=r_end;
00179   --tmp_r_end;
00180   
00181   for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
00182   {
00183     if(*r_it2==*n_it2 )
00184     {
00185       if(r_it2==r_begin&& !(*r_it2==*n_begin) )
00186       {
00187         for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
00188         {
00189           if(*r_it2==*n_it3)
00190           {
00191             marked=r_it2;
00192             *r_it2=*(--n_it3);
00193             
00194             BidIt n_it4=n_end;
00195             --n_it4;
00196             for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
00197             {
00198               *r_it3=*n_it4;              
00199             }
00200             return true;
00201           }
00202         }
00203       }
00204       else if(r_it2==r_begin&&*r_it2==*n_begin)
00205       {
00206         return false;//no more previous combination; 
00207       }
00208     }
00209     else //if(*r_it2!=*n_it2 )
00210     {
00211       ++r_it2;
00212       marked=r_it2;
00213       for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
00214       {
00215         if(*r_it2==*n_it5)
00216         {
00217           *r_it2=*(--n_it5);
00218 
00219           BidIt n_it6=n_end;
00220           --n_it6;
00221           for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
00222           {
00223             *r_it4=*n_it6;              
00224           }
00225           return true;
00226         }
00227       }
00228     }
00229   }  
00230   return false;//Will never reach here, unless error    
00231 }
00232 
00233 
00234 // Non recursive template function with Pred
00235 template <class BidIt, class Prediate>
00236 
00237 inline bool prev_combination(
00238         BidIt n_begin, 
00239         BidIt n_end,
00240         BidIt r_begin, 
00241         BidIt r_end,
00242         Prediate Equal)
00243 {
00244   
00245   bool boolsame=false;
00246   BidIt marked;//for r
00247   BidIt r_marked;
00248   BidIt n_marked;
00249   
00250 
00251   BidIt tmp_n_end=n_end;
00252   --tmp_n_end;
00253   
00254   BidIt r_it1=r_end;
00255   --r_it1;
00256   
00257   for(BidIt n_it1=tmp_n_end; n_it1!=n_begin || n_it1==n_begin ; --n_it1)
00258   {
00259     if( Equal(*r_it1, *n_it1) )
00260     {
00261       r_marked=r_it1;
00262       n_marked=n_it1;
00263       break;
00264     }
00265   }  
00266   
00267   BidIt n_it2=n_marked;
00268 
00269 
00270   BidIt tmp_r_end=r_end;
00271   --tmp_r_end;
00272   
00273   for(BidIt r_it2=r_marked; r_it2!=r_begin || r_it2==r_begin; --r_it2,--n_it2)
00274   {
00275     if( Equal(*r_it2, *n_it2) )
00276     {
00277       if(r_it2==r_begin&& !Equal(*r_it2, *n_begin) )
00278       {
00279         for(BidIt n_it3=n_begin;n_it3!=n_end;++n_it3)
00280         {
00281           if(Equal(*r_it2, *n_it3))
00282           {
00283             marked=r_it2;
00284             *r_it2=*(--n_it3);
00285             
00286             BidIt n_it4=n_end;
00287             --n_it4;
00288             for(BidIt r_it3=tmp_r_end; (r_it3!=r_begin || r_it3==r_begin) &&r_it3!=marked; --r_it3,--n_it4)
00289             {
00290               *r_it3=*n_it4;              
00291             }
00292             return true;
00293           }
00294         }
00295       }
00296       else if(r_it2==r_begin&&Equal(*r_it2, *n_begin))
00297       {
00298         return false;//no more previous combination; 
00299       }
00300     }
00301     else //if(*r_it2!=*n_it2 )
00302     {
00303       ++r_it2;
00304       marked=r_it2;
00305       for(BidIt n_it5=n_begin;n_it5!=n_end;++n_it5)
00306       {
00307         if(Equal(*r_it2, *n_it5))
00308         {
00309           *r_it2=*(--n_it5);
00310 
00311           BidIt n_it6=n_end;
00312           --n_it6;
00313           for(BidIt r_it4=tmp_r_end; (r_it4!=r_begin || r_it4==r_begin) &&r_it4!=marked; --r_it4,--n_it6)
00314           {
00315             *r_it4=*n_it6;              
00316           }
00317           return true;
00318         }
00319       }
00320     }
00321   }  
00322   return false;//Will never reach here, unless error    
00323 }
00324 
00325 
00326 // Recursive template function
00327 template <class RanIt, class Func>
00328 
00329 void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
00330                       RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
00331 {
00332         
00333         int r_size=rend-rbegin;
00334         
00335         
00336         int localloop=loop;
00337         int local_n_column=n_column;
00338         
00339         //A different combination is out
00340         if(r_column>(r_size-1))
00341         {
00342     func(rbegin,rend);
00343     return;
00344         }
00346         
00347         for(int i=0;i<=loop;++i)
00348         {
00349                                 
00350                 RanIt it1=rbegin;
00351                 for(int cnt=0;cnt<r_column;++cnt)
00352                 {
00353                   ++it1;
00354                 } 
00355                 
00356                 RanIt it2=nbegin;
00357                 for(int cnt2=0;cnt2<n_column+i;++cnt2)
00358                 {
00359                   ++it2;
00360                 } 
00361                 
00362                 *it1=*it2;
00363                 
00364                 ++local_n_column;
00365                 
00366                 recursive_combination(nbegin,nend,local_n_column,
00367                         rbegin,rend,r_column+1,localloop,func);
00368                 --localloop;
00369         }
00370         
00371 }
00372 
00373 }
00374 
00375 #endif