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 next_combination.hpp
 * @author    tlin
 * @date  10/27/2004
 * @version 1.0
 */ 

#ifndef UTILS_NEXT_COMBINATION_HPP
#define UTILS_NEXT_COMBINATION_HPP

#include <vector>
#include <iterator>
#include <iostream>
namespace oopse {

/**
 * @brief STL next_permuationtation like combination sequence generator.
 * Given the first and last iterator of a sequence, next_combination iteratively generates all 
 * possible combinations.
 * @return if more combination is availiable, otherwise return false
 * @param iterContainer iterator container
 * @param first the first iterator
 * @param last the last iterator
 * @note first and last must be random access iterators and iterContainer must be the container of  
 * random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
 *
 * @code
 * std::vector<int> iv;
 * iv.push_back(1);
 * iv.push_back(8);
 * std::vector<std::vector<int>::iterator> ic;
 * while(next_combination(ic, iv.begin(), iv.end())) {
 *     for (i =  ic.begin(); i < ic.end(); ++i) {
 *         std::cout << **i << "\t";
 *     }
 *     std::cout << std::endl;
 * }
 * //output
 * //1
 * //8
 * //1  8
 * @endcode
 */
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) {
        return false;
    }
    
    RandomAccessIterator endIter = --last;
    typename IteratorContainer<RandomAccessIterator>::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 increase its iterator by 1 
        ++(*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, first is 0
        //and the last is 10 (due to STL's half open range)). 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<RandomAccessIterator>::iterator j = i;
        j--;
        while( j >= iterContainer.begin() && *i == *j + 1){
            i--;
            j--;
        };

        RandomAccessIterator raIter;
        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(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
                    *i = raIter;
                }    
                iterContainer.insert(iterContainer.end(), raIter);
                
                return true; 
            }
            
        } else {
            ++(*j);
            raIter = *j;
            for(; i != iterContainer.end(); ++i) {
                ++raIter;
                *i = raIter;
            }
            return true;
        }
    }
} //end next_combination

} //end namespace oopse
#endif //UTILS_NEXT_COMBINATION_HPP

Revision:	1823
Committed:	Thu Dec 2 02:23:45 2004 UTC (19 years, 7 months ago) by tim
File size:	5152 byte(s)
Log Message:	begin to fix linking problem
#	Content
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.
23	*
24	*/
25
26	/**
27	* @file next_combination.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	#include <iostream>
39	namespace oopse {
40
41	/**
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 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	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 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, 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<RandomAccessIterator>::iterator j = i;
97	j--;
98	while( j >= iterContainer.begin() && i == j + 1){
99	i--;
100	j--;
101	};
102
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()) {
107	//if the current size equals to total number, done
108	return false;
109	} else {
110
111	//push the first currentSize+1 element into sequence
112
113	for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) {
114	*i = raIter;
115	}
116	iterContainer.insert(iterContainer.end(), raIter);
117
118	return true;
119	}
120
121	} else {
122	++(*j);
123	raIter = *j;
124	for(; i != iterContainer.end(); ++i) {
125	++raIter;
126	*i = raIter;
127	}
128	return true;
129	}
130	}
131	} //end next_combination
132
133	} //end namespace oopse
134	#endif //UTILS_NEXT_COMBINATION_HPP
135