stress-extensional.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040
00041 using namespace Gecode;
00042
00051 class StressExtensional : public Script {
00052 protected:
00054 IntVarArray x;
00055 public:
00057 typedef Support::DynamicArray<DFA::Transition,Heap> Transitions;
00059 void
00060 permute(int i_state, int i, int n, int p,
00061 Transitions& t, int& n_t, int& n_state) {
00062 if (i<n-1) {
00063 for (int j=n; j--; )
00064 if (!(p & (1 << j))) {
00065 t[n_t].i_state = i_state;
00066 t[n_t].symbol = j;
00067 t[n_t].o_state = ++n_state;
00068 n_t++;
00069 permute(n_state,i+1,n,p | (1 << j),
00070 t,n_t,n_state);
00071 }
00072 } else {
00073 for (int j=n; j--; )
00074 if (!(p & (1 << j))) {
00075 t[n_t].i_state = i_state;
00076 t[n_t].symbol = j;
00077 t[n_t].o_state = 1;
00078 n_t++;
00079 }
00080 }
00081 }
00083 DFA
00084 construct(int n) {
00085 Transitions t(heap);
00086 int n_t = 0;
00087 int n_state = 1;
00088 permute(0,0,n,0,t,n_t,n_state);
00089 t[n_t].i_state = -1;
00090 int f[] = {1,-1};
00091 DFA d(0,t,f);
00092 return d;
00093 }
00095 StressExtensional(const SizeOptions& opt)
00096 : x(*this,4*opt.size(),0,opt.size()) {
00097 DFA a = construct(opt.size());
00098 IntVarArgs y(opt.size());
00099 for (unsigned int i=0; i <= 3*opt.size(); i++) {
00100 for (int j = opt.size(); j--; )
00101 y[j] = x[i+j];
00102 extensional(*this, y, a);
00103 }
00104 for (int j=opt.size(); j--; )
00105 y[j] = x[j];
00106 branch(*this, y, INT_VAR_NONE, INT_VAL_MED);
00107 }
00109 StressExtensional(bool share, StressExtensional& s) : Script(share,s) {
00110 x.update(*this, share, s.x);
00111 }
00113 virtual Space*
00114 copy(bool share) {
00115 return new StressExtensional(share,*this);
00116 }
00118 virtual void
00119 print(std::ostream& os) const {
00120 os << "\tx[" << x.size() << "] = " << x << std::endl;
00121 }
00122 };
00123
00127 int
00128 main(int argc, char* argv[]) {
00129 SizeOptions opt("StressExtensional");
00130 opt.size(7);
00131 opt.parse(argc,argv);
00132 Script::run<StressExtensional,DFS,SizeOptions>(opt);
00133 return 0;
00134 }
00135
00136