Generated on Mon Nov 30 23:53:18 2009 for Gecode by doxygen 1.6.1

stress-extensional.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2005
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-04-02 20:58:46 +0200 (Thu, 02 Apr 2009) $ by $Author: schulte $
00011  *     $Revision: 8649 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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 // STATISTICS: example-any