| 24 |
|
*/ |
| 25 |
|
|
| 26 |
|
/** |
| 27 |
< |
* @file GenerateCombination.hpp |
| 27 |
> |
* @file next_combination.hpp |
| 28 |
|
* @author tlin |
| 29 |
|
* @date 10/27/2004 |
| 30 |
|
* @version 1.0 |
| 39 |
|
namespace oopse { |
| 40 |
|
|
| 41 |
|
/** |
| 42 |
– |
* @fn bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, |
| 43 |
– |
* RandomAccessIterator first, RandomAccessIterator last) |
| 42 |
|
* @brief STL next_permuationtation like combination sequence generator. |
| 43 |
|
* Given the first and last iterator of a sequence, next_combination iteratively generates all |
| 44 |
< |
* possible combination. |
| 44 |
> |
* possible combinations. |
| 45 |
|
* @return if more combination is availiable, otherwise return false |
| 46 |
|
* @param iterContainer iterator container |
| 47 |
|
* @param first the first iterator |
| 64 |
|
* //1 |
| 65 |
|
* //8 |
| 66 |
|
* //1 8 |
| 67 |
+ |
* @endcode |
| 68 |
|
*/ |
| 69 |
|
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
| 70 |
|
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
| 80 |
|
iterContainer.insert(iterContainer.end(), first); |
| 81 |
|
return true; |
| 82 |
|
} else if (*(--i) != endIter){ |
| 83 |
< |
//if the last iterator in iterContainer does not reaches the end, just increment it |
| 83 |
> |
//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1 |
| 84 |
|
++(*i); |
| 85 |
|
return true; |
| 86 |
|
} else {// the last iterator in iterContainer does not reaches the end |
| 87 |
|
|
| 88 |
|
//starts at the end of the sequence and works its way towards the front, looking for two |
| 89 |
|
//consecutive members of the sequence where the difference between them is greater |
| 90 |
< |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin |
| 91 |
< |
//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while |
| 90 |
> |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0 |
| 91 |
> |
//and the last is 10 (due to STL's half open range)). At the end of while |
| 92 |
|
//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8. |
| 93 |
|
//If j is less than zero, it means it already reaches the last combination of current size. |
| 94 |
|
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
| 131 |
|
} //end next_combination |
| 132 |
|
|
| 133 |
|
/** |
| 135 |
– |
* @fn bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont, |
| 136 |
– |
* std::vector<std::string>& sequence, std::vector<std::string>& result, |
| 137 |
– |
* const std::string& wildCard) |
| 134 |
|
* @brief iteratively replace the sequence with wild cards |
| 135 |
|
* @return true if more combination sequence is avaliable, otherwise return true |
| 136 |
< |
* @param cont iterator container, if expect whole series of combination, just pass an empty iterator |
| 137 |
< |
* container. The user should not modify the iterator container |
| 136 |
> |
* @param cont iterator container, if expect the whole series of combinations, pass an empty iterator |
| 137 |
> |
* container. The user should not modify this iterator container |
| 138 |
|
* @param sequence the whole sequence used to generate combination |
| 139 |
|
* @param result a possible combination sequence which is set on return |
| 140 |
< |
* @wildCard the wild card string. Its value is "X" by default |
| 140 |
> |
* @param wildCard the wild card string. Its value is "X" by default |
| 141 |
|
* @note since next_combination never returns an empty sequence, replaceWildCard will not generate |
| 142 |
|
* one special combination, which is n identical wild cards (n is equal to the size of the passing sequence) |
| 143 |
|
* |
| 163 |
|
* //H X N |
| 164 |
|
* //X C N |
| 165 |
|
* //H C N |
| 166 |
< |
@endcode |
| 166 |
> |
* @endcode |
| 167 |
|
*/ |
| 168 |
|
bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont, |
| 169 |
|
std::vector<std::string>& sequence, std::vector<std::string>& result, |
| 184 |
|
|
| 185 |
|
return hasMoreCombination; |
| 186 |
|
|
| 187 |
< |
} |
| 187 |
> |
}//end replaceWildCard |
| 188 |
|
|
| 189 |
|
} //end namespace oopse |
| 190 |
|
#endif //UTILS_NEXT_COMBINATION_HPP |
