32 |
|
|
33 |
|
#ifndef UTILS_REPLACEWILDCARD_HPP |
34 |
|
#define UTILS_REPLACEWILDCARD_HPP |
35 |
< |
|
35 |
> |
|
36 |
> |
#include <iostream> |
37 |
|
#include <vector> |
38 |
|
|
39 |
|
namespace oopse{ |
41 |
|
//use -1 to represent the wild card, it is easy and cheap to operate one integer (or index) instead of string |
42 |
|
const int WildCard = -1; |
43 |
|
|
44 |
+ |
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 |
|
/** |
48 |
|
* Driver function for replacing |
49 |
|
* @code |
65 |
|
|
66 |
|
for (int i = 0; i <= num; i++) { |
67 |
|
v = ReplaceWildCard(0, num -1, i); |
68 |
< |
results.insert(v.begin(), v.end(), results.end()); |
68 |
> |
results.insert(results.end(), v.begin(), v.end()); |
69 |
|
} |
70 |
|
return results; |
71 |
|
} |
72 |
|
|
73 |
|
/** Replace a sequence with n wildcards, returns all of the possible replacement*/ |
74 |
< |
std::vector<vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard) { |
74 |
> |
std::vector<std::vector<int> > ReplaceWildCard(int beginIndex, int endIndex, int nWildCard) { |
75 |
|
std::vector<std::vector<int> > results; |
76 |
|
|
77 |
|
int len = endIndex + 1 - beginIndex; |
81 |
|
//if the number of the wild card is zero, just return the whole sequence |
82 |
|
std::vector<int> singleResult; |
83 |
|
|
84 |
< |
for(int i = beginIdex; i <= endIndex; i++) |
84 |
> |
for(int i = beginIndex; i <= endIndex; i++) |
85 |
|
singleResult.push_back(i); |
86 |
|
|
87 |
|
results.push_back(singleResult); |
102 |
|
//we need to recursive calling ReplaceWildCard |
103 |
|
std::vector<int> firstPart; |
104 |
|
std::vector<std::vector<int> > secondPart; |
105 |
+ |
std::vector<std::vector<int> > sequences; |
106 |
|
|
107 |
|
for (int i = 0; i <=nRecursive; i ++) { |
108 |
|
firstPart.push_back( beginIndex + i); |
109 |
|
secondPart = ReplaceWildCard(beginIndex + i + 1, endIndex, nWildCard - 1); |
110 |
< |
results.push_back(adjoint(firstPart, secondPart)); |
110 |
> |
sequences = adjoint(firstPart, secondPart); |
111 |
> |
results.insert(results.end(), sequences.begin(), sequences.end()); |
112 |
|
} |
113 |
|
|
114 |
|
return results; |
115 |
|
} |
116 |
|
} |
117 |
|
|
118 |
< |
std::vector<std::vector<int> > adjoint( int firstPart, const std::vector<std::vector<int> >& secondPart){ |
118 |
> |
std::vector<std::vector<int> > adjoint( const std::vector<int>& firstPart, const std::vector<std::vector<int> >& secondPart){ |
119 |
|
std::vector<std::vector<int> > results(secondPart.size()); |
120 |
|
|
121 |
|
for (int i = 0; i < secondPart.size(); i++) { |
122 |
< |
results[i].insert(firstPart.being(), firstPart.end(), results[i].end()); |
123 |
< |
results[i].insert(secondPart[i].begin(), secondPart[i].end(), results[i].begin()); |
122 |
> |
results[i].insert(results[i].end(), firstPart.begin(), firstPart.end()); |
123 |
> |
results[i].insert(results[i].end(), secondPart[i].begin(), secondPart[i].end()); |
124 |
|
} |
125 |
|
|
126 |
|
return results; |
129 |
|
|
130 |
|
}//end namespace std |
131 |
|
|
132 |
< |
#endif //UTILS_REPLACEWILDCARD_HPP |
132 |
> |
#endif //UTILS_REPLACEWILDCARD_HPP |