JetMCUtils/interface/combination.h

0001 //=======================================================
0002 // combination.h
0003 // Description : Template class to find combinations
0004 //=======================================================
0005 // Copyright 2003 - 2006 Wong Shao Voon
0006 // No warranty, implied or expressed, is included.
0007 // Author is not liable for any type of loss through
0008 // the use of this source code. Use it at your own risk!
0009 //=======================================================
0010
0011 #ifndef __COMBINATION_H__
0012 #define __COMBINATION_H__
0013
0014 namespace stdcomb {
0015
0016   // Non recursive template function
0017   template <class BidIt>
0018
0019   inline bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {
0020     bool boolmarked = false;
0021     BidIt r_marked;
0022
0023     BidIt n_it1 = n_end;
0024     --n_it1;
0025
0026     BidIt tmp_r_end = r_end;
0027     --tmp_r_end;
0028
0029     for (BidIt r_it1 = tmp_r_end; r_it1 != r_begin || r_it1 == r_begin; --r_it1, --n_it1) {
0030       if (*r_it1 == *n_it1) {
0031         if (r_it1 != r_begin)  //to ensure not at the start of r sequence
0032         {
0033           boolmarked = true;
0034           r_marked = (--r_it1);
0035           ++r_it1;  //add it back again
0036           continue;
0037         } else  // it means it is at the start the sequence, so return false
0038           return false;
0039       } else  //if(*r_it1!=*n_it1 )
0040       {
0041         //marked code
0042         if (boolmarked == true) {
0043           //for loop to find which marked is in the first sequence
0044           BidIt n_marked;  //mark in first sequence
0045           for (BidIt n_it2 = n_begin; n_it2 != n_end; ++n_it2)
0046             if (*r_marked == *n_it2) {
0047               n_marked = n_it2;
0048               break;
0049             }
0050
0051           BidIt n_it3 = ++n_marked;
0052           for (BidIt r_it2 = r_marked; r_it2 != r_end; ++r_it2, ++n_it3) {
0053             *r_it2 = *n_it3;
0054           }
0055           return true;
0056         }
0057         for (BidIt n_it4 = n_begin; n_it4 != n_end; ++n_it4)
0058           if (*r_it1 == *n_it4) {
0059             *r_it1 = *(++n_it4);
0060             return true;
0061           }
0062       }
0063     }
0064
0065     return true;  //will never reach here
0066   }
0067
0068   // Non recursive template function with Pred
0069   template <class BidIt, class Prediate>
0070
0071   inline bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) {
0072     bool boolmarked = false;
0073     BidIt r_marked;
0074
0075     BidIt n_it1 = n_end;
0076     --n_it1;
0077
0078     BidIt tmp_r_end = r_end;
0079     --tmp_r_end;
0080
0081     for (BidIt r_it1 = tmp_r_end; r_it1 != r_begin || r_it1 == r_begin; --r_it1, --n_it1) {
0082       if (Equal(*r_it1, *n_it1)) {
0083         if (r_it1 != r_begin)  //to ensure not at the start of r sequence
0084         {
0085           boolmarked = true;
0086           r_marked = (--r_it1);
0087           ++r_it1;  //add it back again
0088           continue;
0089         } else  // it means it is at the start the sequence, so return false
0090           return false;
0091       } else  //if(*r_it1!=*n_it1 )
0092       {
0093         //marked code
0094         if (boolmarked == true) {
0095           //for loop to find which marked is in the first sequence
0096           BidIt n_marked;  //mark in first sequence
0097           for (BidIt n_it2 = n_begin; n_it2 != n_end; ++n_it2)
0098             if (Equal(*r_marked, *n_it2)) {
0099               n_marked = n_it2;
0100               break;
0101             }
0102
0103           BidIt n_it3 = ++n_marked;
0104           for (BidIt r_it2 = r_marked; r_it2 != r_end; ++r_it2, ++n_it3) {
0105             *r_it2 = *n_it3;
0106           }
0107           return true;
0108         }
0109         for (BidIt n_it4 = n_begin; n_it4 != n_end; ++n_it4)
0110           if (Equal(*r_it1, *n_it4)) {
0111             *r_it1 = *(++n_it4);
0112             return true;
0113           }
0114       }
0115     }
0116
0117     return true;  //will never reach here
0118   }
0119
0120   // Non recursive template function
0121   template <class BidIt>
0122
0123   inline bool prev_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {
0124     BidIt marked;  //for r
0125     BidIt r_marked;
0126     BidIt n_marked;
0127
0128     BidIt tmp_n_end = n_end;
0129     --tmp_n_end;
0130
0131     BidIt r_it1 = r_end;
0132     --r_it1;
0133
0134     for (BidIt n_it1 = tmp_n_end; n_it1 != n_begin || n_it1 == n_begin; --n_it1) {
0135       if (*r_it1 == *n_it1) {
0136         r_marked = r_it1;
0137         n_marked = n_it1;
0138         break;
0139       }
0140     }
0141
0142     BidIt n_it2 = n_marked;
0143
0144     BidIt tmp_r_end = r_end;
0145     --tmp_r_end;
0146
0147     for (BidIt r_it2 = r_marked; r_it2 != r_begin || r_it2 == r_begin; --r_it2, --n_it2) {
0148       if (*r_it2 == *n_it2) {
0149         if (r_it2 == r_begin && !(*r_it2 == *n_begin)) {
0150           for (BidIt n_it3 = n_begin; n_it3 != n_end; ++n_it3) {
0151             if (*r_it2 == *n_it3) {
0152               marked = r_it2;
0153               *r_it2 = *(--n_it3);
0154
0155               BidIt n_it4 = n_end;
0156               --n_it4;
0157               for (BidIt r_it3 = tmp_r_end; (r_it3 != r_begin || r_it3 == r_begin) && r_it3 != marked;
0158                    --r_it3, --n_it4) {
0159                 *r_it3 = *n_it4;
0160               }
0161               return true;
0162             }
0163           }
0164         } else if (r_it2 == r_begin && *r_it2 == *n_begin) {
0165           return false;  //no more previous combination;
0166         }
0167       } else  //if(*r_it2!=*n_it2 )
0168       {
0169         ++r_it2;
0170         marked = r_it2;
0171         for (BidIt n_it5 = n_begin; n_it5 != n_end; ++n_it5) {
0172           if (*r_it2 == *n_it5) {
0173             *r_it2 = *(--n_it5);
0174
0175             BidIt n_it6 = n_end;
0176             --n_it6;
0177             for (BidIt r_it4 = tmp_r_end; (r_it4 != r_begin || r_it4 == r_begin) && r_it4 != marked; --r_it4, --n_it6) {
0178               *r_it4 = *n_it6;
0179             }
0180             return true;
0181           }
0182         }
0183       }
0184     }
0185     return false;  //Will never reach here, unless error
0186   }
0187
0188   // Non recursive template function with Pred
0189   template <class BidIt, class Prediate>
0190
0191   inline bool prev_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) {
0192     BidIt marked;  //for r
0193     BidIt r_marked;
0194     BidIt n_marked;
0195
0196     BidIt tmp_n_end = n_end;
0197     --tmp_n_end;
0198
0199     BidIt r_it1 = r_end;
0200     --r_it1;
0201
0202     for (BidIt n_it1 = tmp_n_end; n_it1 != n_begin || n_it1 == n_begin; --n_it1) {
0203       if (Equal(*r_it1, *n_it1)) {
0204         r_marked = r_it1;
0205         n_marked = n_it1;
0206         break;
0207       }
0208     }
0209
0210     BidIt n_it2 = n_marked;
0211
0212     BidIt tmp_r_end = r_end;
0213     --tmp_r_end;
0214
0215     for (BidIt r_it2 = r_marked; r_it2 != r_begin || r_it2 == r_begin; --r_it2, --n_it2) {
0216       if (Equal(*r_it2, *n_it2)) {
0217         if (r_it2 == r_begin && !Equal(*r_it2, *n_begin)) {
0218           for (BidIt n_it3 = n_begin; n_it3 != n_end; ++n_it3) {
0219             if (Equal(*r_it2, *n_it3)) {
0220               marked = r_it2;
0221               *r_it2 = *(--n_it3);
0222
0223               BidIt n_it4 = n_end;
0224               --n_it4;
0225               for (BidIt r_it3 = tmp_r_end; (r_it3 != r_begin || r_it3 == r_begin) && r_it3 != marked;
0226                    --r_it3, --n_it4) {
0227                 *r_it3 = *n_it4;
0228               }
0229               return true;
0230             }
0231           }
0232         } else if (r_it2 == r_begin && Equal(*r_it2, *n_begin)) {
0233           return false;  //no more previous combination;
0234         }
0235       } else  //if(*r_it2!=*n_it2 )
0236       {
0237         ++r_it2;
0238         marked = r_it2;
0239         for (BidIt n_it5 = n_begin; n_it5 != n_end; ++n_it5) {
0240           if (Equal(*r_it2, *n_it5)) {
0241             *r_it2 = *(--n_it5);
0242
0243             BidIt n_it6 = n_end;
0244             --n_it6;
0245             for (BidIt r_it4 = tmp_r_end; (r_it4 != r_begin || r_it4 == r_begin) && r_it4 != marked; --r_it4, --n_it6) {
0246               *r_it4 = *n_it6;
0247             }
0248             return true;
0249           }
0250         }
0251       }
0252     }
0253     return false;  //Will never reach here, unless error
0254   }
0255
0256   // Recursive template function
0257   template <class RanIt, class Func>
0258
0259   void recursive_combination(
0260       RanIt nbegin, RanIt nend, int n_column, RanIt rbegin, RanIt rend, int r_column, int loop, Func func) {
0261     int r_size = rend - rbegin;
0262
0263     int localloop = loop;
0264     int local_n_column = n_column;
0265
0266     //A different combination is out
0267     if (r_column > (r_size - 1)) {
0268       func(rbegin, rend);
0269       return;
0270     }
0271     /////////////////////////////////
0272
0273     for (int i = 0; i <= loop; ++i) {
0274       RanIt it1 = rbegin;
0275       for (int cnt = 0; cnt < r_column; ++cnt) {
0276         ++it1;
0277       }
0278
0279       RanIt it2 = nbegin;
0280       for (int cnt2 = 0; cnt2 < n_column + i; ++cnt2) {
0281         ++it2;
0282       }
0283
0284       *it1 = *it2;
0285
0286       ++local_n_column;
0287
0288       recursive_combination(nbegin, nend, local_n_column, rbegin, rend, r_column + 1, localloop, func);
0289       --localloop;
0290     }
0291   }
0292
0293 }  // namespace stdcomb
0294
0295 #endif