A
Andy
Hello, everyone,
I am writing a segment of code for listing the permutation of some
event sequences.
I tried to use template to make the code more general. When I
commented the
code as shown below, the code works okay. Otherwise, it will goes to
seg fault.
I am puzzled on this. Can anybody give me any hints?
Thank you very much!
- Andy
The following is the code:
#include <vector>
using std::vector;
template<typename T>
class Scheduler
{
struct ChoicePoint
{
public:
// ChoicePoint() {
// event_counters.clear();
// pid = event_index = -1;
// }
// ChoicePoint(const ChoicePoint& cp){
// event_counters = cp.event_counters;
// pid = cp.pid;
// event_index = cp.event_index;
// }
// ChoicePoint operator = (const ChoicePoint& rhs){
// event_counters = rhs.event_counters;
// pid = rhs.pid;
// event_index = rhs.event_index;
// }
// bool operator == (const ChoicePoint& rhs){
// return (event_counters == rhs.event_counters &&
// pid == rhs.pid && event_index == rhs.event_index);
// }
public:
vector<int> event_counters; // progress of each process
int pid;
int event_index;
};
public:
Scheduler(vector<vector<T> >& _events)
{
events = _events;
num_procs = events.size();
ChoicePoint cp;
cp.event_counters.clear();
cp.event_counters.resize(num_procs, 0);
cp.pid = -1;
cp.event_index = -1;
choice_stack.clear();
choice_stack.push_back(cp);
}
bool has_other_choices(ChoicePoint cp){
int i;
for (i = cp.pid + 1; i < num_procs; i++)
if (cp.event_counters < events.size() - 1) break;
return (i < num_procs);
}
ChoicePoint next_choice(ChoicePoint cp){
int i;
assert( has_other_choices(cp) );
for (i = cp.pid + 1; i < num_procs; i++)
if (cp.event_counters < events.size() - 1) break;
ChoicePoint newcp = cp;
newcp.event_counters[cp.pid]--;
newcp.pid = i;
newcp.event_index = cp.event_counters;
newcp.event_counters++;
return newcp;
}
bool has_next_level_choice(ChoicePoint cp){
int i;
for (i = 0; i < num_procs; i++)
if (cp.event_counters < events.size()) return true;
return false;
}
ChoicePoint next_level_choice(ChoicePoint cp){
int i;
assert( has_next_level_choice(cp) );
for (i = 0; i < num_procs; i++)
if (cp.event_counters < events.size()) break;
ChoicePoint newcp;
newcp = cp;
newcp.pid = i;
newcp.event_index = cp.event_counters;
newcp.event_counters++;
return newcp;
}
bool next_permutation(vector<T>& result){
choice = choice_stack[ choice_stack.size() - 1];
choice_stack.pop_back();
while ( !has_other_choices(choice) && !choice_stack.empty() ){
choice = *(choice_stack.rbegin());
choice_stack.pop_back();
}
if (!has_other_choices(choice)) return false;
ChoicePoint newcp;
int i, len;
choice = next_choice(choice);
while ( has_next_level_choice(choice) ){
choice_stack.push_back(choice);
choice = next_level_choice(choice);
}
choice_stack.push_back(choice);
T val;
int pid, eidx;
result.clear();
len = choice_stack.size();
for (i = 0; i < len; i++){
pid = choice_stack.pid;
eidx= choice_stack.event_index;
val = events[pid][eidx];
result.push_back(val);
}
return true;
}
void set_input(vector<vector<T> > &val);
private:
void get_trace_from_choice_stack(vector<T>& trace);
private:
vector<vector<T> > events;
int num_procs;
vector<ChoicePoint> choice_stack;
ChoicePoint choice;
};
#include <iostream>
using namespace std;
int main()
{
vector<vector<int> > a;
vector<int> a1, a2;
a1.push_back(1);
a1.push_back(3);
a2.push_back(4);
a2.push_back(6);
a.push_back(a1);
a.push_back(a2);
Scheduler<int> sched(a);
vector<int> result;
while ( sched.next_permutation(result) ){
int i;
for (i = 0; i < result.size(); i++)
cout<< result <<" ";
cout<<endl;
}
return 0;
}
I am writing a segment of code for listing the permutation of some
event sequences.
I tried to use template to make the code more general. When I
commented the
code as shown below, the code works okay. Otherwise, it will goes to
seg fault.
I am puzzled on this. Can anybody give me any hints?
Thank you very much!
- Andy
The following is the code:
#include <vector>
using std::vector;
template<typename T>
class Scheduler
{
struct ChoicePoint
{
public:
// ChoicePoint() {
// event_counters.clear();
// pid = event_index = -1;
// }
// ChoicePoint(const ChoicePoint& cp){
// event_counters = cp.event_counters;
// pid = cp.pid;
// event_index = cp.event_index;
// }
// ChoicePoint operator = (const ChoicePoint& rhs){
// event_counters = rhs.event_counters;
// pid = rhs.pid;
// event_index = rhs.event_index;
// }
// bool operator == (const ChoicePoint& rhs){
// return (event_counters == rhs.event_counters &&
// pid == rhs.pid && event_index == rhs.event_index);
// }
public:
vector<int> event_counters; // progress of each process
int pid;
int event_index;
};
public:
Scheduler(vector<vector<T> >& _events)
{
events = _events;
num_procs = events.size();
ChoicePoint cp;
cp.event_counters.clear();
cp.event_counters.resize(num_procs, 0);
cp.pid = -1;
cp.event_index = -1;
choice_stack.clear();
choice_stack.push_back(cp);
}
bool has_other_choices(ChoicePoint cp){
int i;
for (i = cp.pid + 1; i < num_procs; i++)
if (cp.event_counters < events.size() - 1) break;
return (i < num_procs);
}
ChoicePoint next_choice(ChoicePoint cp){
int i;
assert( has_other_choices(cp) );
for (i = cp.pid + 1; i < num_procs; i++)
if (cp.event_counters < events.size() - 1) break;
ChoicePoint newcp = cp;
newcp.event_counters[cp.pid]--;
newcp.pid = i;
newcp.event_index = cp.event_counters;
newcp.event_counters++;
return newcp;
}
bool has_next_level_choice(ChoicePoint cp){
int i;
for (i = 0; i < num_procs; i++)
if (cp.event_counters < events.size()) return true;
return false;
}
ChoicePoint next_level_choice(ChoicePoint cp){
int i;
assert( has_next_level_choice(cp) );
for (i = 0; i < num_procs; i++)
if (cp.event_counters < events.size()) break;
ChoicePoint newcp;
newcp = cp;
newcp.pid = i;
newcp.event_index = cp.event_counters;
newcp.event_counters++;
return newcp;
}
bool next_permutation(vector<T>& result){
choice = choice_stack[ choice_stack.size() - 1];
choice_stack.pop_back();
while ( !has_other_choices(choice) && !choice_stack.empty() ){
choice = *(choice_stack.rbegin());
choice_stack.pop_back();
}
if (!has_other_choices(choice)) return false;
ChoicePoint newcp;
int i, len;
choice = next_choice(choice);
while ( has_next_level_choice(choice) ){
choice_stack.push_back(choice);
choice = next_level_choice(choice);
}
choice_stack.push_back(choice);
T val;
int pid, eidx;
result.clear();
len = choice_stack.size();
for (i = 0; i < len; i++){
pid = choice_stack.pid;
eidx= choice_stack.event_index;
val = events[pid][eidx];
result.push_back(val);
}
return true;
}
void set_input(vector<vector<T> > &val);
private:
void get_trace_from_choice_stack(vector<T>& trace);
private:
vector<vector<T> > events;
int num_procs;
vector<ChoicePoint> choice_stack;
ChoicePoint choice;
};
#include <iostream>
using namespace std;
int main()
{
vector<vector<int> > a;
vector<int> a1, a2;
a1.push_back(1);
a1.push_back(3);
a2.push_back(4);
a2.push_back(6);
a.push_back(a1);
a.push_back(a2);
Scheduler<int> sched(a);
vector<int> result;
while ( sched.next_permutation(result) ){
int i;
for (i = 0; i < result.size(); i++)
cout<< result <<" ";
cout<<endl;
}
return 0;
}