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

#ifndef UTILS_REPLACEWILDCARD_HPP
#define UTILS_REPLACEWILDCARD_HPP
 
#include <vector>

namespace oopse{

//use -1 to represent the wild card, it is easy and cheap to operate one integer (or index) instead of string
const int WildCard = -1;

/**
 * Driver function for replacing
 * @code
 * std::vector<std::vector<int> > result;
 * result = ReplaceAll(3);
 * /contents in result
 * //0, 1, 2
 * //-1, 1, 2
 * //0, -1, 2
 * //0, 1, -1
 * //-1, -1, 2
 * //0, -1, -1
 * //-1, -1, -1
 * @endcode
 */
std::vector<std::vector<int> > ReplaceAll(int num) {
    std::vector<std::vector<int> > results;
    std::vector<std::vector<int> > v;
    
    for (int i = 0; i <= num; i++) {
        v = ReplaceWildCard(0, num -1, i);
        results.insert(v.begin(), v.end(), results.end());
    }
    return results;
}

/** Replace a sequence with n wildcards, returns all of the possible replacement*/
std::vector<vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard) {
    std::vector<std::vector<int> > results;

    int len = endIndex + 1 - beginIndex;
    int nRecursive = len - nWildCard;

    if (nWildCard == 0) {
        //if the number of the wild card is zero, just return the whole sequence
        std::vector<int> singleResult;

        for(int i = beginIdex; i <= endIndex; i++)
            singleResult.push_back(i);

        results.push_back(singleResult);
        return results;
    }
        
    if (len < nWildCard) {
        //give warning message
        std::cerr << "Error" << std::endl;
        exit(1);
    } else if (len == nWildCard) {
        //if the lengths are the same, we only have one choice
        //replace all of the index with WildCard
        std::vector<int> singleResult(nWildCard, WildCard);
        results.push_back(singleResult);
        return results;
    } else {
        //we need to recursive calling ReplaceWildCard
        std::vector<int> firstPart;
        std::vector<std::vector<int> > secondPart;

        for (int i = 0; i <=nRecursive; i ++) {
            firstPart.push_back( beginIndex + i);
            secondPart = ReplaceWildCard(beginIndex + i + 1, endIndex, nWildCard - 1); 
            results.push_back(adjoint(firstPart, secondPart));
        }

        return results;
    }
}

std::vector<std::vector<int> > adjoint( int firstPart, const std::vector<std::vector<int> >& secondPart){
    std::vector<std::vector<int> > results(secondPart.size());

    for (int i = 0; i < secondPart.size(); i++) {
        results[i].insert(firstPart.being(), firstPart.end(), results[i].end());
        results[i].insert(secondPart[i].begin(), secondPart[i].end(), results[i].begin());
    }

    return results;
}


}//end namespace std

#endif //UTILS_REPLACEWILDCARD_HPP
Revision:	1659
Committed:	Wed Oct 27 23:17:19 2004 UTC (19 years, 8 months ago) by tim
File size:	3981 byte(s)
Log Message:	adding ReplaceWildCard.hpp, need test
#	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 ReplaceWildCard.hpp
28	* @author tlin
29	* @date 10/27/2004
30	* @version 1.0
31	*/
32
33	#ifndef UTILS_REPLACEWILDCARD_HPP
34	#define UTILS_REPLACEWILDCARD_HPP
35
36	#include <vector>
37
38	namespace oopse{
39
40	//use -1 to represent the wild card, it is easy and cheap to operate one integer (or index) instead of string
41	const int WildCard = -1;
42
43	/**
44	* Driver function for replacing
45	* @code
46	* std::vector<std::vector<int> > result;
47	* result = ReplaceAll(3);
48	* /contents in result
49	* //0, 1, 2
50	* //-1, 1, 2
51	* //0, -1, 2
52	* //0, 1, -1
53	* //-1, -1, 2
54	* //0, -1, -1
55	* //-1, -1, -1
56	* @endcode
57	*/
58	std::vector<std::vector<int> > ReplaceAll(int num) {
59	std::vector<std::vector<int> > results;
60	std::vector<std::vector<int> > v;
61
62	for (int i = 0; i <= num; i++) {
63	v = ReplaceWildCard(0, num -1, i);
64	results.insert(v.begin(), v.end(), results.end());
65	}
66	return results;
67	}
68
69	/** Replace a sequence with n wildcards, returns all of the possible replacement*/
70	std::vector<vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard) {
71	std::vector<std::vector<int> > results;
72
73	int len = endIndex + 1 - beginIndex;
74	int nRecursive = len - nWildCard;
75
76	if (nWildCard == 0) {
77	//if the number of the wild card is zero, just return the whole sequence
78	std::vector<int> singleResult;
79
80	for(int i = beginIdex; i <= endIndex; i++)
81	singleResult.push_back(i);
82
83	results.push_back(singleResult);
84	return results;
85	}
86
87	if (len < nWildCard) {
88	//give warning message
89	std::cerr << "Error" << std::endl;
90	exit(1);
91	} else if (len == nWildCard) {
92	//if the lengths are the same, we only have one choice
93	//replace all of the index with WildCard
94	std::vector<int> singleResult(nWildCard, WildCard);
95	results.push_back(singleResult);
96	return results;
97	} else {
98	//we need to recursive calling ReplaceWildCard
99	std::vector<int> firstPart;
100	std::vector<std::vector<int> > secondPart;
101
102	for (int i = 0; i <=nRecursive; i ++) {
103	firstPart.push_back( beginIndex + i);
104	secondPart = ReplaceWildCard(beginIndex + i + 1, endIndex, nWildCard - 1);
105	results.push_back(adjoint(firstPart, secondPart));
106	}
107
108	return results;
109	}
110	}
111
112	std::vector<std::vector<int> > adjoint( int firstPart, const std::vector<std::vector<int> >& secondPart){
113	std::vector<std::vector<int> > results(secondPart.size());
114
115	for (int i = 0; i < secondPart.size(); i++) {
116	results[i].insert(firstPart.being(), firstPart.end(), results[i].end());
117	results[i].insert(secondPart[i].begin(), secondPart[i].end(), results[i].begin());
118	}
119
120	return results;
121	}
122
123
124	}//end namespace std
125
126	#endif //UTILS_REPLACEWILDCARD_HPP