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 1930 by gezelter, Wed Jan 12 22:41:40 2005 UTC

# Line 1 | Line 1
1 < /*
2 < * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
3 < *
4 < * Contact: oopse@oopse.org
5 < *
6 < * This program is free software; you can redistribute it and/or
7 < * modify it under the terms of the GNU Lesser General Public License
8 < * as published by the Free Software Foundation; either version 2.1
9 < * of the License, or (at your option) any later version.
10 < * All we ask is that proper credit is given for our work, which includes
11 < * - but is not limited to - adding the above copyright notice to the beginning
12 < * of your source code files, and to any copyright notice that you may distribute
13 < * with programs based on this work.
14 < *
15 < * This program is distributed in the hope that it will be useful,
16 < * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 < * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 < * GNU Lesser General Public License for more details.
19 < *
20 < * You should have received a copy of the GNU Lesser General Public License
21 < * along with this program; if not, write to the Free Software
22 < * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
1 > /*
2 > * Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3   *
4 + * The University of Notre Dame grants you ("Licensee") a
5 + * non-exclusive, royalty free, license to use, modify and
6 + * redistribute this software in source and binary code form, provided
7 + * that the following conditions are met:
8 + *
9 + * 1. Acknowledgement of the program authors must be made in any
10 + *    publication of scientific results based in part on use of the
11 + *    program.  An acceptable form of acknowledgement is citation of
12 + *    the article in which the program was described (Matthew
13 + *    A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
14 + *    J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
15 + *    Parallel Simulation Engine for Molecular Dynamics,"
16 + *    J. Comput. Chem. 26, pp. 252-271 (2005))
17 + *
18 + * 2. Redistributions of source code must retain the above copyright
19 + *    notice, this list of conditions and the following disclaimer.
20 + *
21 + * 3. Redistributions in binary form must reproduce the above copyright
22 + *    notice, this list of conditions and the following disclaimer in the
23 + *    documentation and/or other materials provided with the
24 + *    distribution.
25 + *
26 + * This software is provided "AS IS," without a warranty of any
27 + * kind. All express or implied conditions, representations and
28 + * warranties, including any implied warranty of merchantability,
29 + * fitness for a particular purpose or non-infringement, are hereby
30 + * excluded.  The University of Notre Dame and its licensors shall not
31 + * be liable for any damages suffered by licensee as a result of
32 + * using, modifying or distributing the software or its
33 + * derivatives. In no event will the University of Notre Dame or its
34 + * licensors be liable for any lost revenue, profit or data, or for
35 + * direct, indirect, special, consequential, incidental or punitive
36 + * damages, however caused and regardless of the theory of liability,
37 + * arising out of the use of or inability to use software, even if the
38 + * University of Notre Dame has been advised of the possibility of
39 + * such damages.
40   */
41 <
41 >
42   /**
43 < * @file GenerateCombination.hpp
43 > * @file next_combination.hpp
44   * @author    tlin
45   * @date  10/27/2004
46   * @version 1.0
# Line 35 | Line 51
51  
52   #include <vector>
53   #include <iterator>
54 <
54 > #include <iostream>
55   namespace oopse {
56  
57   /**
58 < * STL next_permuationtation like combination sequence generator
59 < *
60 < * <p> Preconditions: </p>
61 < *
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 BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
86 < bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) {
85 > template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
86 > bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
87      if (first == last) {
88          return false;
89      }
90      
91 <    BidirectionalIterator endIter = --last;
92 <    typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end();
91 >    RandomAccessIterator endIter = --last;
92 >    typename IteratorContainer<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;
98      } else if (*(--i) != endIter){
99 <        //if the last iterator in iterContainer does not reaches the end, just increment it
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, begin
107 <        //index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
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 IteratorContainer<BidirectionalIterator>::iterator j = i;
112 >        typename IteratorContainer<RandomAccessIterator>::iterator j = i;
113          j--;
114          while( j >= iterContainer.begin() && *i == *j + 1){
115              i--;
116              j--;
117          };
118  
119 <        BidirectionalIterator biDirIter;
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()) {
# Line 88 | Line 126 | bool next_combination(IteratorContainer<BidirectionalI
126  
127                  //push the first currentSize+1 element into sequence
128                  
129 <                for(i = iterContainer.begin(), biDirIter= first; i  != iterContainer.end(); ++i, ++biDirIter) {
130 <                    *i = biDirIter;
129 >                for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
130 >                    *i = raIter;
131                  }    
132 <                iterContainer.insert(iterContainer.end(), biDirIter);
132 >                iterContainer.insert(iterContainer.end(), raIter);
133                  
134                  return true;
135              }
136              
137          } else {
138              ++(*j);
139 <            biDirIter = *j;
139 >            raIter = *j;
140              for(; i != iterContainer.end(); ++i) {
141 <                ++biDirIter;
142 <                *i = biDirIter;
141 >                ++raIter;
142 >                *i = raIter;
143              }
144              return true;
145          }

Diff Legend

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