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 <iostream>
#include <vector>

namespace oopse{

//use -1 to represent the wild card, it is easy and cheap to handle integer
const int WildCard = -1;

std::vector<std::vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard);
std::vector<std::vector<int> > adjoint( const std::vector<int>& firstPart, const std::vector<std::vector<int> >& secondPart);

/**
 * 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
 * //-1, 1, -1 
 * //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(results.end(), v.begin(), v.end());
    }
    return results;
}

/** Replace a sequence with n wildcards, returns all of the possible replacement*/
std::vector<std::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 = beginIndex; 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;
        std::vector<std::vector<int> > sequences;

        for (int i = 0; i <=nRecursive; i ++) {
          firstPart.clear();
          for(int j = 0; j < i; ++j) {
              firstPart.push_back(beginIndex + j);
            }       
            firstPart.push_back(WildCard);
            secondPart = ReplaceWildCard(beginIndex + i + 1, endIndex, nWildCard - 1); 
            sequences = adjoint(firstPart, secondPart);
            results.insert(results.end(), sequences.begin(), sequences.end());                      
        }

        return results;
    }
}

std::vector<std::vector<int> > adjoint( const std::vector<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(results[i].end(), firstPart.begin(), firstPart.end());
        results[i].insert(results[i].end(), secondPart[i].begin(), secondPart[i].end());
    }

    return results;
}


}//end namespace std

#endif //UTILS_REPLACEWILDCARD_HPP
Revision:	1662
Committed:	Thu Oct 28 03:14:11 2004 UTC (19 years, 8 months ago) by tim
File size:	4469 byte(s)
Log Message:	ReplaceWildCard(recursive version) is working, need refactoring. An iterative version is on the way
#	User	Rev	Content
1	tim	1659	/*
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	tim	1661
36			#include <iostream>
37	tim	1659	#include <vector>
38
39			namespace oopse{
40
41	tim	1662	//use -1 to represent the wild card, it is easy and cheap to handle integer
42	tim	1659	const int WildCard = -1;
43
44	tim	1661	std::vector<std::vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard);
45			std::vector<std::vector<int> > adjoint( const std::vector<int>& firstPart, const std::vector<std::vector<int> >& secondPart);
46
47	tim	1659	/**
48			* Driver function for replacing
49			* @code
50			* std::vector<std::vector<int> > result;
51			* result = ReplaceAll(3);
52			* /contents in result
53			* //0, 1, 2
54			* //-1, 1, 2
55			* //0, -1, 2
56			* //0, 1, -1
57			* //-1, -1, 2
58	tim	1662	* //-1, 1, -1
59	tim	1659	* //0, -1, -1
60			* //-1, -1, -1
61			* @endcode
62			*/
63			std::vector<std::vector<int> > ReplaceAll(int num) {
64			std::vector<std::vector<int> > results;
65			std::vector<std::vector<int> > v;
66
67			for (int i = 0; i <= num; i++) {
68			v = ReplaceWildCard(0, num -1, i);
69	tim	1661	results.insert(results.end(), v.begin(), v.end());
70	tim	1659	}
71			return results;
72			}
73
74			/** Replace a sequence with n wildcards, returns all of the possible replacement*/
75	tim	1661	std::vector<std::vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard) {
76	tim	1659	std::vector<std::vector<int> > results;
77
78			int len = endIndex + 1 - beginIndex;
79			int nRecursive = len - nWildCard;
80
81			if (nWildCard == 0) {
82			//if the number of the wild card is zero, just return the whole sequence
83			std::vector<int> singleResult;
84
85	tim	1661	for(int i = beginIndex; i <= endIndex; i++)
86	tim	1659	singleResult.push_back(i);
87
88			results.push_back(singleResult);
89			return results;
90			}
91
92			if (len < nWildCard) {
93			//give warning message
94			std::cerr << "Error" << std::endl;
95			exit(1);
96			} else if (len == nWildCard) {
97			//if the lengths are the same, we only have one choice
98			//replace all of the index with WildCard
99			std::vector<int> singleResult(nWildCard, WildCard);
100			results.push_back(singleResult);
101			return results;
102			} else {
103			//we need to recursive calling ReplaceWildCard
104			std::vector<int> firstPart;
105			std::vector<std::vector<int> > secondPart;
106	tim	1661	std::vector<std::vector<int> > sequences;
107	tim	1659
108			for (int i = 0; i <=nRecursive; i ++) {
109	tim	1662	firstPart.clear();
110			for(int j = 0; j < i; ++j) {
111			firstPart.push_back(beginIndex + j);
112			}
113			firstPart.push_back(WildCard);
114	tim	1659	secondPart = ReplaceWildCard(beginIndex + i + 1, endIndex, nWildCard - 1);
115	tim	1661	sequences = adjoint(firstPart, secondPart);
116			results.insert(results.end(), sequences.begin(), sequences.end());
117	tim	1659	}
118
119			return results;
120			}
121			}
122
123	tim	1661	std::vector<std::vector<int> > adjoint( const std::vector<int>& firstPart, const std::vector<std::vector<int> >& secondPart){
124	tim	1659	std::vector<std::vector<int> > results(secondPart.size());
125
126			for (int i = 0; i < secondPart.size(); i++) {
127	tim	1661	results[i].insert(results[i].end(), firstPart.begin(), firstPart.end());
128			results[i].insert(results[i].end(), secondPart[i].begin(), secondPart[i].end());
129	tim	1659	}
130
131			return results;
132			}
133
134
135			}//end namespace std
136
137	tim	1661	#endif //UTILS_REPLACEWILDCARD_HPP