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.
branches/new_design/OOPSE-3.0/src/utils/next_combination.hpp (file contents), Revision 1823 by tim, Thu Dec 2 02:23:45 2004 UTC

# Line 24 | Line 24
24   */
25  
26   /**
27 < * @file GenerateCombination.hpp
27 > * @file next_combination.hpp
28   * @author    tlin
29   * @date  10/27/2004
30   * @version 1.0
# 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 > * @brief STL next_permuationtation like combination sequence generator.
43 > * Given the first and last iterator of a sequence, next_combination iteratively generates all
44 > * possible combinations.
45 > * @return if more combination is availiable, otherwise return false
46 > * @param iterContainer iterator container
47 > * @param first the first iterator
48 > * @param last the last iterator
49 > * @note first and last must be random access iterators and iterContainer must be the container of  
50 > * random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
51 > *
52 > * @code
53 > * std::vector<int> iv;
54 > * iv.push_back(1);
55 > * iv.push_back(8);
56 > * std::vector<std::vector<int>::iterator> ic;
57 > * while(next_combination(ic, iv.begin(), iv.end())) {
58 > *     for (i =  ic.begin(); i < ic.end(); ++i) {
59 > *         std::cout << **i << "\t";
60 > *     }
61 > *     std::cout << std::endl;
62 > * }
63 > * //output
64 > * //1
65 > * //8
66 > * //1  8
67 > * @endcode
68   */
69 < template<class BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
70 < bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) {
69 > template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
70 > bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
71      if (first == last) {
72          return false;
73      }
74      
75 <    BidirectionalIterator endIter = --last;
76 <    typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end();
75 >    RandomAccessIterator endIter = --last;
76 >    typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end();
77      
78      if (iterContainer.empty()) {
79          //if sequence is empty, we insert the first iterator
80          iterContainer.insert(iterContainer.end(), first);
81          return true;
82      } else if (*(--i) != endIter){
83 <        //if the last iterator in iterContainer does not reaches the end, just increment it
83 >        //if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
84          ++(*i);
85          return true;
86      } else {// the last iterator in iterContainer does not reaches the end
87  
88          //starts at the end of the sequence and works its way towards the front, looking for two
89          //consecutive members of the sequence where the difference between them is greater
90 <        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
91 <        //index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
90 >        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0
91 >        //and the last is 10 (due to STL's half open range)). At the end of while
92          //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
93          //If j is less than zero, it means it already reaches the last combination of current size.
94          //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
95          // of combination to 5
96 <        typename IteratorContainer<BidirectionalIterator>::iterator j = i;
96 >        typename IteratorContainer<RandomAccessIterator>::iterator j = i;
97          j--;
98          while( j >= iterContainer.begin() && *i == *j + 1){
99              i--;
100              j--;
101          };
102  
103 <        BidirectionalIterator biDirIter;
103 >        RandomAccessIterator raIter;
104          if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
105              //half open range
106              if (last  - first + 1  == iterContainer.size()) {
# Line 88 | Line 110 | bool next_combination(IteratorContainer<BidirectionalI
110  
111                  //push the first currentSize+1 element into sequence
112                  
113 <                for(i = iterContainer.begin(), biDirIter= first; i  != iterContainer.end(); ++i, ++biDirIter) {
114 <                    *i = biDirIter;
113 >                for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
114 >                    *i = raIter;
115                  }    
116 <                iterContainer.insert(iterContainer.end(), biDirIter);
116 >                iterContainer.insert(iterContainer.end(), raIter);
117                  
118                  return true;
119              }
120              
121          } else {
122              ++(*j);
123 <            biDirIter = *j;
123 >            raIter = *j;
124              for(; i != iterContainer.end(); ++i) {
125 <                ++biDirIter;
126 <                *i = biDirIter;
125 >                ++raIter;
126 >                *i = raIter;
127              }
128              return true;
129          }

Diff Legend

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