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

Comparing trunk/OOPSE-4/src/utils/next_combination.hpp (file contents):
Revision 2055 by tim, Mon Feb 21 15:22:56 2005 UTC vs.
Revision 2204 by gezelter, Fri Apr 15 22:04:00 2005 UTC

# Line 1 | Line 1
1 < /*
1 > /*
2   * Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3   *
4   * The University of Notre Dame grants you ("Licensee") a
# Line 54 | Line 54 | namespace oopse {
54   #include <iostream>
55   namespace oopse {
56  
57 < /**
58 < * @brief STL next_permuationtation like combination sequence generator.
59 < * Given the first and last iterator of a sequence, next_combination iteratively generates all
60 < * possible combinations.
61 < * @return if more combination is availiable, otherwise return false
62 < * @param iterContainer iterator container
63 < * @param first the first iterator
64 < * @param last the last iterator
65 < * @note first and last must be random access iterators and iterContainer must be the container of  
66 < * random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
67 < *
68 < * @code
69 < * std::vector<int> iv;
70 < * iv.push_back(1);
71 < * iv.push_back(8);
72 < * std::vector<std::vector<int>::iterator> ic;
73 < * while(next_combination(ic, iv.begin(), iv.end())) {
74 < *     for (i =  ic.begin(); i < ic.end(); ++i) {
75 < *         std::cout << **i << "\t";
76 < *     }
77 < *     std::cout << std::endl;
78 < * }
79 < * //output
80 < * //1
81 < * //8
82 < * //1  8
83 < * @endcode
84 < */
85 < template<class RandomAccessIterator>
86 < bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
57 >  /**
58 >   * @brief STL next_permuationtation like combination sequence generator.
59 >   * Given the first and last iterator of a sequence, next_combination iteratively generates all
60 >   * possible combinations.
61 >   * @return if more combination is availiable, otherwise return false
62 >   * @param iterContainer iterator container
63 >   * @param first the first iterator
64 >   * @param last the last iterator
65 >   * @note first and last must be random access iterators and iterContainer must be the container of  
66 >   * random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
67 >   *
68 >   * @code
69 >   * std::vector<int> iv;
70 >   * iv.push_back(1);
71 >   * iv.push_back(8);
72 >   * std::vector<std::vector<int>::iterator> ic;
73 >   * while(next_combination(ic, iv.begin(), iv.end())) {
74 >   *     for (i =  ic.begin(); i < ic.end(); ++i) {
75 >   *         std::cout << **i << "\t";
76 >   *     }
77 >   *     std::cout << std::endl;
78 >   * }
79 >   * //output
80 >   * //1
81 >   * //8
82 >   * //1  8
83 >   * @endcode
84 >   */
85 >  template<class RandomAccessIterator>
86 >  bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
87      if (first == last) {
88 <        return false;
88 >      return false;
89      }
90      
91      RandomAccessIterator endIter = --last;
92      typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end();
93      
94      if (iterContainer.empty()) {
95 <        //if sequence is empty, we insert the first iterator
96 <        iterContainer.insert(iterContainer.end(), first);
97 <        return true;
95 >      //if sequence is empty, we insert the first iterator
96 >      iterContainer.insert(iterContainer.end(), first);
97 >      return true;
98      } else if (*(--i) != endIter){
99 <        //if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
100 <        ++(*i);
101 <        return true;
99 >      //if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
100 >      ++(*i);
101 >      return true;
102      } else {// the last iterator in iterContainer does not reaches the end
103  
104 <        //starts at the end of the sequence and works its way towards the front, looking for two
105 <        //consecutive members of the sequence where the difference between them is greater
106 <        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0
107 <        //and the last is 10 (due to STL's half open range)). At the end of while
108 <        //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
109 <        //If j is less than zero, it means it already reaches the last combination of current size.
110 <        //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
111 <        // of combination to 5
112 <        typename std::vector<RandomAccessIterator>::iterator j = i;
113 <        j--;
114 <        while( j >= iterContainer.begin() && *i == *j + 1){
115 <            i--;
116 <            j--;
117 <        };
104 >      //starts at the end of the sequence and works its way towards the front, looking for two
105 >      //consecutive members of the sequence where the difference between them is greater
106 >      //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0
107 >      //and the last is 10 (due to STL's half open range)). At the end of while
108 >      //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
109 >      //If j is less than zero, it means it already reaches the last combination of current size.
110 >      //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
111 >      // of combination to 5
112 >      typename std::vector<RandomAccessIterator>::iterator j = i;
113 >      j--;
114 >      while( j >= iterContainer.begin() && *i == *j + 1){
115 >        i--;
116 >        j--;
117 >      };
118  
119 <        RandomAccessIterator raIter;
120 <        if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
121 <            //half open range
122 <            if (last  - first + 1  == iterContainer.size()) {
123 <                //if the current size equals to total number, done
124 <                return false;
125 <            } else {
119 >      RandomAccessIterator raIter;
120 >      if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
121 >        //half open range
122 >        if (last  - first + 1  == iterContainer.size()) {
123 >          //if the current size equals to total number, done
124 >          return false;
125 >        } else {
126  
127 <                //push the first currentSize+1 element into sequence
127 >          //push the first currentSize+1 element into sequence
128                  
129 <                for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
130 <                    *i = raIter;
131 <                }    
132 <                iterContainer.insert(iterContainer.end(), raIter);
129 >          for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
130 >            *i = raIter;
131 >          }    
132 >          iterContainer.insert(iterContainer.end(), raIter);
133                  
134 <                return true;
135 <            }
134 >          return true;
135 >        }
136              
137 <        } else {
138 <            ++(*j);
139 <            raIter = *j;
140 <            for(; i != iterContainer.end(); ++i) {
141 <                ++raIter;
142 <                *i = raIter;
143 <            }
144 <            return true;
145 <        }
137 >      } else {
138 >        ++(*j);
139 >        raIter = *j;
140 >        for(; i != iterContainer.end(); ++i) {
141 >          ++raIter;
142 >          *i = raIter;
143 >        }
144 >        return true;
145 >      }
146      }
147 < } //end next_combination
147 >  } //end next_combination
148  
149   } //end namespace oopse
150   #endif //UTILS_NEXT_COMBINATION_HPP

Diff Legend

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