Generated on Mon May 5 05:53:55 2008 for Gecode by doxygen 1.5.5

extensional.cc

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Mikael Lagerkvist, 2007
00009  *     Christian Schulte, 2005
00010  *
00011  *  Last modified:
00012  *     $Date: 2008-02-28 10:25:14 +0100 (Thu, 28 Feb 2008) $ by $Author: zayenz $
00013  *     $Revision: 6341 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include "test/int.hh"
00041 
00042 #include "gecode/minimodel.hh"
00043 
00044 namespace Test { namespace Int {
00045 
00047    namespace Extensional {
00048    
00054 
00055      class RegSimpleA : public Test {
00056      public:
00058        RegSimpleA(void) : Test("Extensional::Reg::Simple::A",4,2,2) {}
00060        virtual bool solution(const Assignment& x) const {
00061          return (((x[0] == 0) || (x[0] == 2)) &&
00062                  ((x[1] == -1) || (x[1] == 1)) &&
00063                  ((x[2] == 0) || (x[2] == 1)) &&
00064                  ((x[3] == 0) || (x[3] == 1)));
00065        }
00067        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00068          using namespace Gecode;
00069          extensional(home, x,
00070                      (REG(0) | REG(2)) +
00071                      (REG(-1) | REG(1)) +
00072                      (REG(7) | REG(0) | REG(1)) +
00073                      (REG(0) | REG(1)));
00074        }
00075      };
00076      
00078      class RegSimpleB : public Test {
00079      public:
00081        RegSimpleB(void) : Test("Extensional::Reg::Simple::B",4,2,2) {}
00083        virtual bool solution(const Assignment& x) const {
00084          return (x[0]<x[1]) && (x[1]<x[2]) && (x[2]<x[3]);
00085        }
00087        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00088          using namespace Gecode;
00089          extensional(home, x,
00090                      (REG(-2) + REG(-1) + REG(0) + REG(1)) |
00091                      (REG(-2) + REG(-1) + REG(0) + REG(2)) |
00092                      (REG(-2) + REG(-1) + REG(1) + REG(2)) |
00093                      (REG(-2) + REG(0) + REG(1) + REG(2)) |
00094                      (REG(-1) + REG(0) + REG(1) + REG(2)));
00095          }
00096      };
00097      
00099      class RegDistinct : public Test {
00100      public:
00102        RegDistinct(void) : Test("Extensional::Reg::Distinct",4,-1,4) {}
00104        virtual bool solution(const Assignment& x) const {
00105          for (int i=0; i<x.size(); i++) {
00106            if ((x[i] < 0) || (x[i] > 3))
00107              return false;
00108            for (int j=i+1; j<x.size(); j++)
00109              if (x[i]==x[j])
00110                return false;
00111          }
00112          return true;
00113        }
00115        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00116          using namespace Gecode;
00117          extensional(home, x,
00118                      (REG(0)+REG(1)+REG(2)+REG(3)) |
00119                      (REG(0)+REG(1)+REG(3)+REG(2)) |
00120                      (REG(0)+REG(2)+REG(1)+REG(3)) |
00121                      (REG(0)+REG(2)+REG(3)+REG(1)) |
00122                      (REG(0)+REG(3)+REG(1)+REG(2)) |
00123                      (REG(0)+REG(3)+REG(2)+REG(1)) |
00124                      (REG(1)+REG(0)+REG(2)+REG(3)) |
00125                      (REG(1)+REG(0)+REG(3)+REG(2)) |
00126                      (REG(1)+REG(2)+REG(0)+REG(3)) |
00127                      (REG(1)+REG(2)+REG(3)+REG(0)) |
00128                      (REG(1)+REG(3)+REG(0)+REG(2)) |
00129                      (REG(1)+REG(3)+REG(2)+REG(0)) |
00130                      (REG(2)+REG(0)+REG(1)+REG(3)) |
00131                      (REG(2)+REG(0)+REG(3)+REG(1)) |
00132                      (REG(2)+REG(1)+REG(0)+REG(3)) |
00133                      (REG(2)+REG(1)+REG(3)+REG(0)) |
00134                      (REG(2)+REG(3)+REG(0)+REG(1)) |
00135                      (REG(2)+REG(3)+REG(1)+REG(0)) |
00136                      (REG(3)+REG(0)+REG(1)+REG(2)) |
00137                      (REG(3)+REG(0)+REG(2)+REG(1)) |
00138                      (REG(3)+REG(1)+REG(0)+REG(2)) |
00139                      (REG(3)+REG(1)+REG(2)+REG(0)) |
00140                      (REG(3)+REG(2)+REG(0)+REG(1)) |
00141                      (REG(3)+REG(2)+REG(1)+REG(0)));
00142        }
00143      };
00144      
00146      class RegSharedA : public Test {
00147      public:
00149        RegSharedA(void) : Test("Extensional::Reg::Shared::A",4,2,2) {}
00151        virtual bool solution(const Assignment& x) const {
00152          return (((x[0] == 0) || (x[0] == 2)) &&
00153                  ((x[1] == -1) || (x[1] == 1)) &&
00154                  ((x[2] == 0) || (x[2] == 1)) &&
00155                  ((x[3] == 0) || (x[3] == 1)));
00156        }
00158        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00159          using namespace Gecode;
00160          IntVarArgs y(8);
00161          for (int i=0; i<4; i++)
00162            y[i]=y[i+4]=x[i];
00163          unshare(home,y);
00164          extensional(home, y,
00165                      ((REG(0) | REG(2)) +
00166                       (REG(-1) | REG(1)) +
00167                       (REG(7) | REG(0) | REG(1)) +
00168                       (REG(0) | REG(1)))(2,2));
00169        }
00170      };
00171    
00173      class RegSharedB : public Test {
00174      public:
00176        RegSharedB(void) : Test("Extensional::Reg::Shared::B",4,2,2) {}
00178        virtual bool solution(const Assignment& x) const {
00179          return (((x[0] == 0) || (x[0] == 2)) &&
00180                  ((x[1] == -1) || (x[1] == 1)) &&
00181                  ((x[2] == 0) || (x[2] == 1)) &&
00182                  ((x[3] == 0) || (x[3] == 1)));
00183        }
00185        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00186          using namespace Gecode;
00187          IntVarArgs y(12);
00188          for (int i=0; i<4; i++)
00189            y[i]=y[i+4]=y[i+8]=x[i];
00190          unshare(home,y);
00191          extensional(home, y,
00192                      ((REG(0) | REG(2)) +
00193                       (REG(-1) | REG(1)) +
00194                       (REG(7) | REG(0) | REG(1)) +
00195                       (REG(0) | REG(1)))(3,3));
00196        }
00197      };
00198    
00200      class RegSharedC : public Test {
00201      public:
00203        RegSharedC(void) : Test("Extensional::Reg::Shared::C",4,0,1) {}
00205        virtual bool solution(const Assignment& x) const {
00206          return (x[1]==1) && (x[2]==0) && (x[3]==1);
00207        }
00209        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00210          using namespace Gecode;
00211          Gecode::BoolVarArgs y(8);
00212          for (int i=0; i<4; i++)
00213            y[i]=y[i+4]=channel(home,x[i]);
00214          unshare(home,y);
00215          extensional(home,y,
00216                      ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(2,2));
00217        }
00218      };
00219    
00221      class RegSharedD : public Test {
00222      public:
00224        RegSharedD(void) : Test("Extensional::Reg::Shared::D",4,0,1) {}
00226        virtual bool solution(const Assignment& x) const {
00227          return (x[1]==1) && (x[2]==0) && (x[3]==1);
00228        }
00230        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00231          using namespace Gecode;
00232          Gecode::BoolVarArgs y(12);
00233          for (int i=0; i<4; i++)
00234            y[i]=y[i+4]=y[i+8]=channel(home,x[i]);
00235          unshare(home, y);
00236          extensional(home, y,
00237                      ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(3,3));
00238        }
00239      };
00240    
00242      class RegEmptyDFA : public Test {
00243      public:
00245        RegEmptyDFA(void) : Test("Extensional::Reg::Empty::DFA",1,0,0) {
00246          testsearch = false;
00247        }
00249        virtual bool solution(const Assignment& x) const {
00250          (void)x;
00251          return false;
00252        }
00254        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00255          Gecode::DFA d;
00256          Gecode::extensional(home, x, d);
00257        }
00258      };
00259    
00261      class RegEmptyREG : public Test {
00262      public:
00264        RegEmptyREG(void) : Test("Extensional::Reg::Empty::REG",1,0,0) {
00265          testsearch = false;
00266        }
00268        virtual bool solution(const Assignment& x) const {
00269          (void)x;
00270          return false;
00271        }
00273        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00274          Gecode::REG r;
00275          Gecode::extensional(home, x, r);
00276        }
00277      };
00278    
00280      class TupleSetA : public Test {
00281      public:
00283        TupleSetA(Gecode::PropKind pk)
00284          : Test("Extensional::TupleSet::A::"+str(pk),
00285                 4,1,5,false,Gecode::ICL_DOM,pk) {}
00287        virtual bool solution(const Assignment& x) const {
00288          return ((x[0] == 1 && x[1] == 3 && x[2] == 2 && x[3] == 3) ||
00289                  (x[0] == 2 && x[1] == 1 && x[2] == 2 && x[3] == 4) ||
00290                  (x[0] == 2 && x[1] == 2 && x[2] == 1 && x[3] == 4) ||
00291                  (x[0] == 3 && x[1] == 3 && x[2] == 3 && x[3] == 2) ||
00292                  (x[0] == 4 && x[1] == 3 && x[2] == 4 && x[3] == 1)
00293                  );
00294        }
00296        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00297          using namespace Gecode;
00298          TupleSet t;
00299          IntArgs t1(4,  2, 1, 2, 4);
00300          IntArgs t2(4,  2, 2, 1, 4);
00301          IntArgs t3(4,  4, 3, 4, 1);
00302          IntArgs t4(4,  1, 3, 2, 3);
00303          IntArgs t5(4,  3, 3, 3, 2);
00304          t.add(t1);
00305          t.add(t2);
00306          t.add(t3);
00307          t.add(t4);
00308          t.add(t5);
00309          t.finalize();
00310 
00311          extensional(home, x, t, ICL_DEF, pk);
00312        }
00313      };
00314 
00316      class TupleSetB : public Test {
00317        mutable Gecode::TupleSet t;
00318      public:
00320        TupleSetB(Gecode::PropKind pk)
00321          : Test("Extensional::TupleSet::B::"+str(pk),
00322                 4,1,5,false,Gecode::ICL_DOM,pk) {
00323          using namespace Gecode;
00324          IntArgs t1 (4,  2, 1, 2, 4);
00325          IntArgs t2 (4,  2, 2, 1, 4);
00326          IntArgs t3 (4,  4, 3, 4, 1);
00327          IntArgs t4 (4,  1, 3, 2, 3);
00328          IntArgs t5 (4,  3, 3, 3, 2);
00329          IntArgs t6 (4,  5, 1, 4, 4);
00330          IntArgs t7 (4,  2, 5, 1, 5);
00331          IntArgs t8 (4,  4, 3, 5, 1);
00332          IntArgs t9 (4,  1, 5, 2, 5);
00333          IntArgs t10(4,  5, 3, 3, 2);
00334          t.add(t1);
00335          t.add(t2);
00336          t.add(t3);
00337          t.add(t4);
00338          t.add(t5);
00339          t.add(t6);
00340          t.add(t7);
00341          t.add(t8);
00342          t.add(t9);
00343          t.add(t10);
00344        }
00346        virtual bool solution(const Assignment& x) const {
00347          using namespace Gecode;
00348          for (int i = 0; i < t.tuples(); ++i) {
00349            TupleSet::Tuple l = t[i];
00350            bool same = true;
00351            for (int j = 0; j < t.arity() && same; ++j)
00352              if (l[j] != x[j]) same = false;
00353            if (same) return true;
00354          }
00355          return false;
00356        }
00358        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00359          using namespace Gecode;
00360          extensional(home, x, t, ICL_DEF, pk);
00361        }
00362      };
00363 
00364 
00365 
00367      class TupleSetBool : public Test {
00368        mutable Gecode::TupleSet t;
00369      public:
00371        TupleSetBool(Gecode::PropKind pk, double prob)
00372          : Test("Extensional::TupleSet::Bool::"+str(pk),
00373                 5,0,1,false,Gecode::ICL_DOM,pk) {
00374          using namespace Gecode;
00375          
00376          CpltAssignment ass(5, IntSet(0, 1));
00377          while (ass()) {
00378            if (Base::rand(100) <= prob*100) {
00379              IntArgs tuple(5);
00380              for (int i = 5; i--; ) tuple[i] = ass[i];
00381              t.add(tuple);
00382            }   
00383            ++ass;
00384          }
00385          t.finalize();
00386        }
00388        virtual bool solution(const Assignment& x) const {
00389          using namespace Gecode;
00390          for (int i = 0; i < t.tuples(); ++i) {
00391            TupleSet::Tuple l = t[i];
00392            bool same = true;
00393            for (int j = 0; j < t.arity() && same; ++j)
00394              if (l[j] != x[j]) same = false;
00395            if (same) return true;
00396          }
00397          return false;
00398        }
00400        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00401          using namespace Gecode;
00402          BoolVarArgs y(x.size());
00403          for (int i = x.size(); i--; ) y[i] = channel(home, x[i]);
00404          extensional(home, y, t, ICL_DEF, pk);
00405        }
00406      };
00407 
00408 
00409      RegSimpleA ra;
00410      RegSimpleB rb;
00411    
00412      RegDistinct rd;
00413    
00414      RegSharedA rsa;
00415      RegSharedB rsb;
00416      RegSharedC rsc;
00417      RegSharedD rsd;
00418 
00419      RegEmptyDFA redfa;
00420      RegEmptyREG rereg;
00421 
00422 
00423      TupleSetA tsam(Gecode::PK_MEMORY);
00424      TupleSetA tsas(Gecode::PK_SPEED);
00425 
00426      TupleSetB tsbm(Gecode::PK_MEMORY);
00427      TupleSetB tsbs(Gecode::PK_SPEED);
00428 
00429      TupleSetBool tsboolm(Gecode::PK_MEMORY, 0.3);
00430      TupleSetBool tsbools(Gecode::PK_SPEED, 0.3);
00432 
00433    }
00434 }}
00435 
00436 
00437 // STATISTICS: test-int
00438