src/utils/next_combination.hpp

/*
 * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
 * 
 * Contact: oopse@oopse.org
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 * All we ask is that proper credit is given for our work, which includes
 * - but is not limited to - adding the above copyright notice to the beginning
 * of your source code files, and to any copyright notice that you may distribute
 * with programs based on this work.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

/**
 * @file GenerateCombination.hpp
 * @author    tlin
 * @date  10/27/2004
 * @version 1.0
 */ 

#ifndef UTILS_NEXT_COMBINATION_HPP
#define UTILS_NEXT_COMBINATION_HPP

#include <vector>
#include <iterator>

namespace oopse {

/**
 * STL next_permuationtation like combination sequence generator 
 * 
 * <p> Preconditions: </p>
 * 
 */
template<class BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) {
        return false;
    }
    
    BidirectionalIterator endIter = --last;
    typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end();
    
    if (iterContainer.empty()) {
        //if sequence is empty, we insert the first iterator
        iterContainer.insert(iterContainer.end(), first);
        return true;
    } else if (*(--i) != endIter){
        //if the last iterator in iterContainer does not reaches the end, just increment it 
        ++(*i);
        return true;
    } else {// the last iterator in iterContainer does not reaches the end

        //starts at the end of the sequence and works its way towards the front, looking for two 
        //consecutive members of the sequence where the difference between them is greater 
        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
        //index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
        //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
        //If j is less than zero, it means it already reaches the last combination of current size.
        //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
        // of combination to 5
        typename IteratorContainer<BidirectionalIterator>::iterator j = i;
        j--;
        while( j >= iterContainer.begin() && *i == *j + 1){
            i--;
            j--;
        };

        BidirectionalIterator biDirIter;
        if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
            //half open range
            if (last  - first + 1  == iterContainer.size()) {
                //if the current size equals to total number, done
                return false;
            } else {

                //push the first currentSize+1 element into sequence 
                
                for(i = iterContainer.begin(), biDirIter= first; i  != iterContainer.end(); ++i, ++biDirIter) {
                    *i = biDirIter;
                }    
                iterContainer.insert(iterContainer.end(), biDirIter);
                
                return true; 
            }
            
        } else {
            ++(*j);
            biDirIter = *j;
            for(; i != iterContainer.end(); ++i) {
                ++biDirIter;
                *i = biDirIter;
            }
            return true;
        }
    }
} //end next_combination

} //end namespace oopse
#endif //UTILS_NEXT_COMBINATION_HPP

Revision:	181
Committed:	Thu Oct 28 19:06:59 2004 UTC (21 years ago) by tim
File size:	4325 byte(s)
Log Message:	STL next_permutation like next_combination is working
#	User	Rev	Content
1	tim	181	/*
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.
23			*
24			*/
25
26			/**
27			* @file GenerateCombination.hpp
28			* @author tlin
29			* @date 10/27/2004
30			* @version 1.0
31			*/
32
33			#ifndef UTILS_NEXT_COMBINATION_HPP
34			#define UTILS_NEXT_COMBINATION_HPP
35
36			#include <vector>
37			#include <iterator>
38
39			namespace oopse {
40
41			/**
42			* STL next_permuationtation like combination sequence generator
43			*
44			* <p> Preconditions: </p>
45			*
46			*/
47			template<class BidirectionalIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
48			bool next_combination(IteratorContainer<BidirectionalIterator>& iterContainer, BidirectionalIterator first, BidirectionalIterator last) {
49			if (first == last) {
50			return false;
51			}
52
53			BidirectionalIterator endIter = --last;
54			typename IteratorContainer<BidirectionalIterator>::iterator i = iterContainer.end();
55
56			if (iterContainer.empty()) {
57			//if sequence is empty, we insert the first iterator
58			iterContainer.insert(iterContainer.end(), first);
59			return true;
60			} else if (*(--i) != endIter){
61			//if the last iterator in iterContainer does not reaches the end, just increment it
62			++(*i);
63			return true;
64			} else {// the last iterator in iterContainer does not reaches the end
65
66			//starts at the end of the sequence and works its way towards the front, looking for two
67			//consecutive members of the sequence where the difference between them is greater
68			//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
69			//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
70			//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
71			//If j is less than zero, it means it already reaches the last combination of current size.
72			//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
73			// of combination to 5
74			typename IteratorContainer<BidirectionalIterator>::iterator j = i;
75			j--;
76			while( j >= iterContainer.begin() && i == j + 1){
77			i--;
78			j--;
79			};
80
81			BidirectionalIterator biDirIter;
82			if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
83			//half open range
84			if (last - first + 1 == iterContainer.size()) {
85			//if the current size equals to total number, done
86			return false;
87			} else {
88
89			//push the first currentSize+1 element into sequence
90
91			for(i = iterContainer.begin(), biDirIter= first; i != iterContainer.end(); ++i, ++biDirIter) {
92			*i = biDirIter;
93			}
94			iterContainer.insert(iterContainer.end(), biDirIter);
95
96			return true;
97			}
98
99			} else {
100			++(*j);
101			biDirIter = *j;
102			for(; i != iterContainer.end(); ++i) {
103			++biDirIter;
104			*i = biDirIter;
105			}
106			return true;
107			}
108			}
109			} //end next_combination
110
111			} //end namespace oopse
112			#endif //UTILS_NEXT_COMBINATION_HPP
113