44 |
|
* <p> Preconditions: </p> |
45 |
|
* |
46 |
|
*/ |
47 |
< |
template<class BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
48 |
< |
bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) { |
47 |
> |
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
48 |
> |
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
49 |
|
if (first == last) { |
50 |
|
return false; |
51 |
|
} |
52 |
|
|
53 |
< |
BidirectionalIterator endIter = --last; |
54 |
< |
typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end(); |
53 |
> |
RandomAccessIterator endIter = --last; |
54 |
> |
typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end(); |
55 |
|
|
56 |
|
if (iterContainer.empty()) { |
57 |
|
//if sequence is empty, we insert the first iterator |
71 |
|
//If j is less than zero, it means it already reaches the last combination of current size. |
72 |
|
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
73 |
|
// of combination to 5 |
74 |
< |
typename IteratorContainer<BidirectionalIterator>::iterator j = i; |
74 |
> |
typename IteratorContainer<RandomAccessIterator>::iterator j = i; |
75 |
|
j--; |
76 |
|
while( j >= iterContainer.begin() && *i == *j + 1){ |
77 |
|
i--; |
78 |
|
j--; |
79 |
|
}; |
80 |
|
|
81 |
< |
BidirectionalIterator biDirIter; |
81 |
> |
RandomAccessIterator raIter; |
82 |
|
if (j - iterContainer.begin() < 0) { //reaches the last combination of current size |
83 |
|
//half open range |
84 |
|
if (last - first + 1 == iterContainer.size()) { |
88 |
|
|
89 |
|
//push the first currentSize+1 element into sequence |
90 |
|
|
91 |
< |
for(i = iterContainer.begin(), biDirIter= first; i != iterContainer.end(); ++i, ++biDirIter) { |
92 |
< |
*i = biDirIter; |
91 |
> |
for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) { |
92 |
> |
*i = raIter; |
93 |
|
} |
94 |
< |
iterContainer.insert(iterContainer.end(), biDirIter); |
94 |
> |
iterContainer.insert(iterContainer.end(), raIter); |
95 |
|
|
96 |
|
return true; |
97 |
|
} |
98 |
|
|
99 |
|
} else { |
100 |
|
++(*j); |
101 |
< |
biDirIter = *j; |
101 |
> |
raIter = *j; |
102 |
|
for(; i != iterContainer.end(); ++i) { |
103 |
< |
++biDirIter; |
104 |
< |
*i = biDirIter; |
103 |
> |
++raIter; |
104 |
> |
*i = raIter; |
105 |
|
} |
106 |
|
return true; |
107 |
|
} |