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, RandomAccessIterator first, RandomAccessIterator last) |
43 |
> |
* @brief STL next_permuationtation like combination sequence generator. |
44 |
> |
* Given the first and last iterator of a sequence, next_combination iteratively generates all possible combination. |
45 |
> |
* @param iterContainer iterator container |
46 |
> |
* @param first the first iterator |
47 |
> |
* @param last the last iterator |
48 |
> |
* @note first and last must be random access iterators and iterContainer must be the container which |
49 |
> |
* element is iterator. And all of the iteratos in iterContainer must be within the range [first, last) |
50 |
> |
* |
51 |
> |
* @code |
52 |
> |
* std::vector<int> iv; |
53 |
> |
* iv.push_back(1); |
54 |
> |
* iv.push_back(8); |
55 |
> |
* std::vector<std::vector<int>::iterator> ic; |
56 |
> |
* while(next_combination(ic, iv.begin(), iv.end())) { |
57 |
> |
* for (i = ic.begin(); i < ic.end(); ++i) { |
58 |
> |
* std::cout << **i << "\t"; |
59 |
> |
* } |
60 |
> |
* std::cout << std::endl; |
61 |
> |
* } |
62 |
> |
* //output |
63 |
> |
* //1 |
64 |
> |
* //8 |
65 |
> |
* //1 8 |
66 |
|
*/ |
67 |
< |
template<class BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
68 |
< |
bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) { |
67 |
> |
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
68 |
> |
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
69 |
|
if (first == last) { |
70 |
|
return false; |
71 |
|
} |
72 |
|
|
73 |
< |
BidirectionalIterator endIter = --last; |
74 |
< |
typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end(); |
73 |
> |
RandomAccessIterator endIter = --last; |
74 |
> |
typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end(); |
75 |
|
|
76 |
|
if (iterContainer.empty()) { |
77 |
|
//if sequence is empty, we insert the first iterator |
91 |
|
//If j is less than zero, it means it already reaches the last combination of current size. |
92 |
|
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
93 |
|
// of combination to 5 |
94 |
< |
typename IteratorContainer<BidirectionalIterator>::iterator j = i; |
94 |
> |
typename IteratorContainer<RandomAccessIterator>::iterator j = i; |
95 |
|
j--; |
96 |
|
while( j >= iterContainer.begin() && *i == *j + 1){ |
97 |
|
i--; |
98 |
|
j--; |
99 |
|
}; |
100 |
|
|
101 |
< |
BidirectionalIterator biDirIter; |
101 |
> |
RandomAccessIterator raIter; |
102 |
|
if (j - iterContainer.begin() < 0) { //reaches the last combination of current size |
103 |
|
//half open range |
104 |
|
if (last - first + 1 == iterContainer.size()) { |
108 |
|
|
109 |
|
//push the first currentSize+1 element into sequence |
110 |
|
|
111 |
< |
for(i = iterContainer.begin(), biDirIter= first; i != iterContainer.end(); ++i, ++biDirIter) { |
112 |
< |
*i = biDirIter; |
111 |
> |
for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) { |
112 |
> |
*i = raIter; |
113 |
|
} |
114 |
< |
iterContainer.insert(iterContainer.end(), biDirIter); |
114 |
> |
iterContainer.insert(iterContainer.end(), raIter); |
115 |
|
|
116 |
|
return true; |
117 |
|
} |
118 |
|
|
119 |
|
} else { |
120 |
|
++(*j); |
121 |
< |
biDirIter = *j; |
121 |
> |
raIter = *j; |
122 |
|
for(; i != iterContainer.end(); ++i) { |
123 |
< |
++biDirIter; |
124 |
< |
*i = biDirIter; |
123 |
> |
++raIter; |
124 |
> |
*i = raIter; |
125 |
|
} |
126 |
|
return true; |
127 |
|
} |
128 |
|
} |
129 |
|
} //end next_combination |
130 |
|
|
131 |
+ |
bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont, |
132 |
+ |
std::vector<std::string> sequence, std::vector<std::string> result |
133 |
+ |
std::string& wildCard = "X") { |
134 |
+ |
if (cont.size() > sequnce.size()) { |
135 |
+ |
std::cerr << "the size of iterator container is greater than the size of sequence" |
136 |
+ |
} |
137 |
+ |
|
138 |
+ |
bool hasMoreCombination = next_combination(cont, sequence.begin(), sequence.end()); |
139 |
+ |
if (hasMoreCombination) { |
140 |
+ |
result.resize(sequence.size()); |
141 |
+ |
result.insert(result.end(), sequence.size(), wildCard); |
142 |
+ |
for ( i = cont.begin(); i != cont.end(); i++){ |
143 |
+ |
result[*i - sequence.begin()] = **i; |
144 |
+ |
} |
145 |
+ |
|
146 |
+ |
return hasMoreCombination; |
147 |
+ |
} |
148 |
+ |
|
149 |
|
} //end namespace oopse |
150 |
|
#endif //UTILS_NEXT_COMBINATION_HPP |
151 |
|
|