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

Comparing trunk/OOPSE-3.0/src/utils/next_combination.hpp (file contents):
Revision 1674 by tim, Thu Oct 28 19:06:59 2004 UTC vs.
Revision 1678 by tim, Thu Oct 28 21:11:12 2004 UTC

# Line 35 | Line 35
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 BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
71 < bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) {
70 > template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
71 > bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
72      if (first == last) {
73          return false;
74      }
75      
76 <    BidirectionalIterator endIter = --last;
77 <    typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end();
76 >    RandomAccessIterator endIter = --last;
77 >    typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end();
78      
79      if (iterContainer.empty()) {
80          //if sequence is empty, we insert the first iterator
# Line 71 | Line 94 | bool next_combination(IteratorContainer<BidirectionalI
94          //If j is less than zero, it means it already reaches the last combination of current size.
95          //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
96          // of combination to 5
97 <        typename IteratorContainer<BidirectionalIterator>::iterator j = i;
97 >        typename IteratorContainer<RandomAccessIterator>::iterator j = i;
98          j--;
99          while( j >= iterContainer.begin() && *i == *j + 1){
100              i--;
101              j--;
102          };
103  
104 <        BidirectionalIterator biDirIter;
104 >        RandomAccessIterator raIter;
105          if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
106              //half open range
107              if (last  - first + 1  == iterContainer.size()) {
# Line 88 | Line 111 | bool next_combination(IteratorContainer<BidirectionalI
111  
112                  //push the first currentSize+1 element into sequence
113                  
114 <                for(i = iterContainer.begin(), biDirIter= first; i  != iterContainer.end(); ++i, ++biDirIter) {
115 <                    *i = biDirIter;
114 >                for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
115 >                    *i = raIter;
116                  }    
117 <                iterContainer.insert(iterContainer.end(), biDirIter);
117 >                iterContainer.insert(iterContainer.end(), raIter);
118                  
119                  return true;
120              }
121              
122          } else {
123              ++(*j);
124 <            biDirIter = *j;
124 >            raIter = *j;
125              for(; i != iterContainer.end(); ++i) {
126 <                ++biDirIter;
127 <                *i = biDirIter;
126 >                ++raIter;
127 >                *i = raIter;
128              }
129              return true;
130          }
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  

Diff Legend

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