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 |
|
|