Go to the documentation of this file.00001 #include "operator.h"
00002 #include "successor_generator.h"
00003 #include "variable.h"
00004
00005 #include <functional>
00006 #include <iostream>
00007 #include <fstream>
00008 #include <vector>
00009 #include <cassert>
00010 using namespace std;
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 class GeneratorBase {
00029 public:
00030 virtual ~GeneratorBase() {
00031 }
00032 virtual void dump(string indent) const = 0;
00033 virtual void generate_cpp_input(ostream &outfile) const = 0;
00034 };
00035
00036 class GeneratorSwitch : public GeneratorBase {
00037 private:
00038 Variable *switch_var;
00039 list<int> immediate_ops_indices;
00040 vector<GeneratorBase *> generator_for_value;
00041 GeneratorBase *default_generator;
00042 public:
00043 ~GeneratorSwitch();
00044 GeneratorSwitch(Variable *switch_variable, list<int> &operators,
00045 const vector<GeneratorBase *> &gen_for_val, GeneratorBase *default_gen);
00046 virtual void dump(string indent) const;
00047 virtual void generate_cpp_input(ostream &outfile) const;
00048 };
00049
00050 class GeneratorLeaf : public GeneratorBase {
00051 private:
00052 list<int> applicable_ops_indices;
00053 public:
00054 GeneratorLeaf(list<int> &operators);
00055 virtual void dump(string indent) const;
00056 virtual void generate_cpp_input(ostream &outfile) const;
00057 };
00058
00059 class GeneratorEmpty : public GeneratorBase {
00060 public:
00061 virtual void dump(string indent) const;
00062 virtual void generate_cpp_input(ostream &outfile) const;
00063 };
00064
00065 GeneratorSwitch::GeneratorSwitch(Variable *switch_variable,
00066 list<int> &operators, const vector<GeneratorBase *> &gen_for_val,
00067 GeneratorBase *default_gen) :
00068 switch_var(switch_variable), generator_for_value(gen_for_val),
00069 default_generator(default_gen) {
00070 immediate_ops_indices.swap(operators);
00071 }
00072
00073 GeneratorSwitch::~GeneratorSwitch() {
00074 for(int i = 0; i < generator_for_value.size(); i++)
00075 delete generator_for_value[i];
00076 delete default_generator;
00077 }
00078
00079 void GeneratorSwitch::dump(string indent) const {
00080 cout << indent << "switch on " << switch_var->get_level() << endl;
00081 cout << indent << "immediately:" << endl;
00082 for(list<int>::const_iterator op_iter = immediate_ops_indices.begin(); op_iter
00083 != immediate_ops_indices.end(); ++op_iter)
00084 cout << indent << *op_iter << endl;
00085 for(int i = 0; i < switch_var->get_range(); i++) {
00086 cout << indent << "case " << i << ":" << endl;
00087 generator_for_value[i]->dump(indent + " ");
00088 }
00089 cout << indent << "always:" << endl;
00090 default_generator->dump(indent + " ");
00091 }
00092
00093 void GeneratorSwitch::generate_cpp_input(ostream &outfile) const {
00094 int level = switch_var->get_level();
00095 assert(level != -1);
00096 outfile << "switch " << level << endl;
00097 outfile << "check " << immediate_ops_indices.size() << endl;
00098 for(list<int>::const_iterator op_iter = immediate_ops_indices.begin(); op_iter
00099 != immediate_ops_indices.end(); ++op_iter)
00100 outfile << *op_iter << endl;
00101 for(int i = 0; i < switch_var->get_range(); i++) {
00102
00103
00104 generator_for_value[i]->generate_cpp_input(outfile);
00105 }
00106
00107 default_generator->generate_cpp_input(outfile);
00108 }
00109
00110 GeneratorLeaf::GeneratorLeaf(list<int> &ops) {
00111 applicable_ops_indices.swap(ops);
00112 }
00113
00114 void GeneratorLeaf::dump(string indent) const {
00115 for(list<int>::const_iterator op_iter = applicable_ops_indices.begin(); op_iter
00116 != applicable_ops_indices.end(); ++op_iter)
00117 cout << indent << *op_iter << endl;
00118 }
00119
00120 void GeneratorLeaf::generate_cpp_input(ostream &outfile) const {
00121 outfile << "check " << applicable_ops_indices.size() << endl;
00122 for(list<int>::const_iterator op_iter = applicable_ops_indices.begin(); op_iter
00123 != applicable_ops_indices.end(); ++op_iter)
00124 outfile << *op_iter << endl;
00125 }
00126
00127 void GeneratorEmpty::dump(string indent) const {
00128 cout << indent << "<empty>" << endl;
00129 }
00130
00131 void GeneratorEmpty::generate_cpp_input(ostream &outfile) const {
00132 outfile << "check 0" << endl;
00133 }
00134
00135 SuccessorGenerator::SuccessorGenerator(const vector<Variable *> &variables,
00136 const vector<Operator> &operators) {
00137
00138
00139
00140
00141
00142 conditions.reserve(operators.size());
00143 list<int> all_operator_indices;
00144 for(int i = 0; i < operators.size(); i++) {
00145 const Operator *op = &operators[i];
00146 Condition cond;
00147 for(int j = 0; j < op->get_prevail_start().size(); j++) {
00148 Operator::Prevail prev = op->get_prevail_start()[j];
00149 cond.push_back(make_pair(prev.var, prev.prev));
00150 }
00151 for(int j = 0; j < op->get_pre_post_start().size(); j++) {
00152 Operator::PrePost pre_post = op->get_pre_post_start()[j];
00153 if(pre_post.pre != -1)
00154 cond.push_back(make_pair(pre_post.var, pre_post.pre));
00155 }
00156 sort(cond.begin(), cond.end());
00157 all_operator_indices.push_back(i);
00158 conditions.push_back(cond);
00159 next_condition_by_op.push_back(conditions.back().begin());
00160 }
00161
00162 cout << "all_operator_indices.size(): " << all_operator_indices.size() << endl;
00163
00164 varOrder = variables;
00165 sort(varOrder.begin(), varOrder.end());
00166
00167 root = construct_recursive(0, all_operator_indices);
00168 }
00169
00170 GeneratorBase *SuccessorGenerator::construct_recursive(int switch_var_no,
00171 list<int> &op_indices) {
00172 if(op_indices.empty())
00173 return new GeneratorEmpty;
00174
00175 while(true) {
00176
00177
00178 if(switch_var_no == varOrder.size())
00179 return new GeneratorLeaf(op_indices);
00180
00181
00182 if(varOrder[switch_var_no]->is_functional()
00183 || varOrder[switch_var_no]->is_module()) {
00184
00185 ++switch_var_no;
00186 continue;
00187 }
00188
00189 Variable *switch_var = varOrder[switch_var_no];
00190 int number_of_children = switch_var->get_range();
00191
00192 vector<list<int> > ops_for_val_indices(number_of_children);
00193 list<int> default_ops_indices;
00194 list<int> applicable_ops_indices;
00195
00196 bool all_ops_are_immediate = true;
00197 bool var_is_interesting = false;
00198
00199 while(!op_indices.empty()) {
00200 int op_index = op_indices.front();
00201 op_indices.pop_front();
00202 assert(op_index >= 0 && op_index < next_condition_by_op.size());
00203 Condition::const_iterator &cond_iter = next_condition_by_op[op_index];
00204 assert(cond_iter - conditions[op_index].begin() >= 0);
00205 assert(cond_iter - conditions[op_index].begin() <= conditions[op_index].size());
00206 if(cond_iter == conditions[op_index].end()) {
00207 var_is_interesting = true;
00208 applicable_ops_indices.push_back(op_index);
00209 } else {
00210 all_ops_are_immediate = false;
00211 Variable *var = cond_iter->first;
00212 int val = cond_iter->second;
00213 if(var == switch_var) {
00214 var_is_interesting = true;
00215 ++cond_iter;
00216 ops_for_val_indices[val].push_back(op_index);
00217 } else {
00218 default_ops_indices.push_back(op_index);
00219 }
00220 }
00221 }
00222
00223 if(all_ops_are_immediate) {
00224 return new GeneratorLeaf(applicable_ops_indices);
00225 } else if(var_is_interesting) {
00226 vector<GeneratorBase *> gen_for_val;
00227 for(int j = 0; j < number_of_children; j++) {
00228 gen_for_val.push_back(construct_recursive(switch_var_no + 1,
00229 ops_for_val_indices[j]));
00230 }
00231 GeneratorBase *default_sg = construct_recursive(switch_var_no + 1,
00232 default_ops_indices);
00233 return new GeneratorSwitch(switch_var, applicable_ops_indices, gen_for_val, default_sg);
00234 } else {
00235
00236 ++switch_var_no;
00237 default_ops_indices.swap(op_indices);
00238 }
00239 }
00240 }
00241
00242 SuccessorGenerator::SuccessorGenerator() {
00243 root = 0;
00244 }
00245
00246 SuccessorGenerator::~SuccessorGenerator() {
00247 delete root;
00248 }
00249
00250 void SuccessorGenerator::dump() const {
00251 cout << "Successor Generator:" << endl;
00252 root->dump(" ");
00253 }
00254 void SuccessorGenerator::generate_cpp_input(ostream &outfile) const {
00255 root->generate_cpp_input(outfile);
00256 }