| 35 |
|
|
| 36 |
|
#include <vector> |
| 37 |
|
#include <iterator> |
| 38 |
< |
|
| 38 |
> |
#include <iostream> |
| 39 |
|
namespace oopse { |
| 40 |
|
|
| 41 |
|
/** |
| 42 |
< |
* STL next_permuationtation like combination sequence generator |
| 43 |
< |
* |
| 44 |
< |
* <p> Preconditions: </p> |
| 45 |
< |
* |
| 42 |
> |
* @fn bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, |
| 43 |
> |
* RandomAccessIterator first, RandomAccessIterator last) |
| 44 |
> |
* @brief STL next_permuationtation like combination sequence generator. |
| 45 |
> |
* Given the first and last iterator of a sequence, next_combination iteratively generates all |
| 46 |
> |
* possible combination. |
| 47 |
> |
* @return if more combination is availiable, otherwise return false |
| 48 |
> |
* @param iterContainer iterator container |
| 49 |
> |
* @param first the first iterator |
| 50 |
> |
* @param last the last iterator |
| 51 |
> |
* @note first and last must be random access iterators and iterContainer must be the container of |
| 52 |
> |
* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last) |
| 53 |
> |
* |
| 54 |
> |
* @code |
| 55 |
> |
* std::vector<int> iv; |
| 56 |
> |
* iv.push_back(1); |
| 57 |
> |
* iv.push_back(8); |
| 58 |
> |
* std::vector<std::vector<int>::iterator> ic; |
| 59 |
> |
* while(next_combination(ic, iv.begin(), iv.end())) { |
| 60 |
> |
* for (i = ic.begin(); i < ic.end(); ++i) { |
| 61 |
> |
* std::cout << **i << "\t"; |
| 62 |
> |
* } |
| 63 |
> |
* std::cout << std::endl; |
| 64 |
> |
* } |
| 65 |
> |
* //output |
| 66 |
> |
* //1 |
| 67 |
> |
* //8 |
| 68 |
> |
* //1 8 |
| 69 |
|
*/ |
| 70 |
|
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
| 71 |
|
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
| 131 |
|
} |
| 132 |
|
} //end next_combination |
| 133 |
|
|
| 134 |
+ |
/** |
| 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) |
| 138 |
+ |
* @brief iteratively replace the sequence with wild cards |
| 139 |
+ |
* @return true if more combination sequence is avaliable, otherwise return true |
| 140 |
+ |
* @param cont iterator container, if expect whole series of combination, just pass an empty iterator |
| 141 |
+ |
* container. The user should not modify the iterator container |
| 142 |
+ |
* @param sequence the whole sequence used to generate combination |
| 143 |
+ |
* @param result a possible combination sequence which is set on return |
| 144 |
+ |
* @wildCard the wild card string. Its value is "X" by default |
| 145 |
+ |
* @note since next_combination never returns an empty sequence, replaceWildCard will not generate |
| 146 |
+ |
* one special combination, which is n identical wild cards (n is equal to the size of the passing sequence) |
| 147 |
+ |
* |
| 148 |
+ |
* @code |
| 149 |
+ |
* std::vector<std::string> sv; |
| 150 |
+ |
* std::vector<std::vector<std::string>::iterator> sic; |
| 151 |
+ |
* std::vector<std::string> resultString; |
| 152 |
+ |
* sv.push_back("H"); |
| 153 |
+ |
* sv.push_back("C"); |
| 154 |
+ |
* sv.push_back("N"); |
| 155 |
+ |
|
| 156 |
+ |
* while (replaceWildCard(sic, sv, resultString)) { |
| 157 |
+ |
* for(std::vector<std::string>::iterator i = resultString.begin(); i != resultString.end(); ++i) { |
| 158 |
+ |
* std::cout << *i << "\t"; |
| 159 |
+ |
* } |
| 160 |
+ |
* std::cout << std::endl; |
| 161 |
+ |
* } |
| 162 |
+ |
* //output |
| 163 |
+ |
* //H X X |
| 164 |
+ |
* //X C X |
| 165 |
+ |
* //X X N |
| 166 |
+ |
* //H C X |
| 167 |
+ |
* //H X N |
| 168 |
+ |
* //X C N |
| 169 |
+ |
* //H C N |
| 170 |
+ |
@endcode |
| 171 |
+ |
*/ |
| 172 |
+ |
bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont, |
| 173 |
+ |
std::vector<std::string>& sequence, std::vector<std::string>& result, |
| 174 |
+ |
const std::string& wildCard = "X") { |
| 175 |
+ |
if (cont.size() > sequence.size()) { |
| 176 |
+ |
std::cerr << "the size of iterator container is greater than the size of sequence"; |
| 177 |
+ |
} |
| 178 |
+ |
|
| 179 |
+ |
bool hasMoreCombination = next_combination(cont, sequence.begin(), sequence.end()); |
| 180 |
+ |
if (hasMoreCombination) { |
| 181 |
+ |
result.clear(); |
| 182 |
+ |
result.insert(result.begin(), sequence.size(), wildCard); |
| 183 |
+ |
std::vector<std::vector<std::string>::iterator>::iterator i; |
| 184 |
+ |
for ( i = cont.begin(); i != cont.end(); i++){ |
| 185 |
+ |
result[*i - sequence.begin()] = **i; |
| 186 |
+ |
} |
| 187 |
+ |
} |
| 188 |
+ |
|
| 189 |
+ |
return hasMoreCombination; |
| 190 |
+ |
|
| 191 |
+ |
} |
| 192 |
+ |
|
| 193 |
|
} //end namespace oopse |
| 194 |
|
#endif //UTILS_NEXT_COMBINATION_HPP |
| 195 |
|
|
