ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/group/trunk/OOPSE-2.0/src/utils/next_combination.hpp
(Generate patch)

Comparing trunk/OOPSE-2.0/src/utils/next_combination.hpp (file contents):
Revision 1674 by tim, Thu Oct 28 19:06:59 2004 UTC vs.
Revision 1676 by tim, Thu Oct 28 20:01:39 2004 UTC

# Line 39 | Line 39 | namespace oopse {
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
# Line 71 | Line 91 | bool next_combination(IteratorContainer<BidirectionalI
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()) {
# Line 88 | Line 108 | bool next_combination(IteratorContainer<BidirectionalI
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  

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines