successor_generator.cpp
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 /* NOTE on possible optimizations:
00013 
00014  * Sharing "GeneratorEmpty" instances might help quite a bit with
00015  reducing memory usage and possibly even speed, because there are
00016  bound to be many instance of those. However, it complicates
00017  deleting the successor generator, and memory doesn't seem to be
00018  an issue. Speed appears to be fine now, too. So this is probably
00019  an unnecessary complication.
00020 
00021  * Using slist instead of list led to a further 10% speedup on the
00022  largest Logistics instance, logistics-98/prob28.pddl. It would of
00023  course also reduce memory usage. However, it would make the code
00024  g++-specific, so it's probably not worth it.
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         //cout << "case "<<switch_var->get_name()<<" (Level " <<switch_var->get_level() <<
00103         //  ") has value " << i << ":" << endl;
00104         generator_for_value[i]->generate_cpp_input(outfile);
00105     }
00106     //cout << "always:" << endl;
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     //  cout << "variables:" << endl;
00138     //  for(int i=0; i< variables.size(); i++) {
00139     //    cout << variables[i]->get_name() << endl;
00140     //  }
00141     // We need the iterators to conditions to be stable:
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         // Test if no further switch is necessary (or possible).
00178         if(switch_var_no == varOrder.size())
00179             return new GeneratorLeaf(op_indices);
00180 
00181         //cout << "size:" << varOrder.size() << ", number: " << switch_var_no << endl;
00182         if(varOrder[switch_var_no]->is_functional()
00183                 || varOrder[switch_var_no]->is_module()) {
00184             // this switch var can be left out because variable is functional
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             // this switch var can be left out because no operator depends on it
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 }


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06