Generated on Thu Mar 22 10:39:36 2012 for Gecode by doxygen 1.6.3

element.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: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
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 "test/int.hh"
00039 
00040 #include <gecode/minimodel.hh>
00041 #include <climits>
00042 
00043 namespace Test { namespace Int {
00044 
00046    namespace Element {
00047 
00053 
00054      class IntIntVar : public Test {
00055      protected:
00057        Gecode::IntArgs c;
00058      public:
00060        IntIntVar(const std::string& s, const Gecode::IntArgs& c0,
00061                  int min, int max)
00062          : Test("Element::Int::Int::Var::"+s,2,min,max), 
00063            c(c0) {}
00065        virtual bool solution(const Assignment& x) const {
00066          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
00067        }
00069        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00070          Gecode::element(home, c, x[0], x[1]);
00071        }
00072      };
00073 
00075      class IntIntInt : public Test {
00076      protected:
00078        Gecode::IntArgs c;
00080        int r;
00081      public:
00083        IntIntInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
00084          : Test("Element::Int::Int::Int::"+s+"::"+str(r0),1,-4,8),
00085            c(c0), r(r0) {}
00087        virtual bool solution(const Assignment& x) const {
00088          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
00089        }
00091        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00092          Gecode::element(home, c, x[0], r);
00093        }
00094      };
00095 
00097      class IntIntShared : public Test {
00098      protected:
00100        Gecode::IntArgs c;
00101      public:
00103        IntIntShared(const std::string& s, const Gecode::IntArgs& c0,
00104                     int minDomain=-4)
00105          : Test("Element::Int::Int::Shared::"+s,1,minDomain,8), c(c0) {}
00107        virtual bool solution(const Assignment& x) const {
00108          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[0];
00109        }
00111        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00112          Gecode::element(home, c, x[0], x[0]);
00113        }
00114      };
00115 
00117      class IntBoolVar : public Test {
00118      protected:
00120        Gecode::IntArgs c;
00121      public:
00123        IntBoolVar(const std::string& s, const Gecode::IntArgs& c0)
00124          : Test("Element::Int::Bool::Var::"+s,2,-4,8), c(c0) {}
00126        virtual bool solution(const Assignment& x) const {
00127          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
00128        }
00130        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00131          Gecode::element(home, c, x[0], Gecode::channel(home,x[1]));
00132        }
00133      };
00134 
00136      class IntBoolInt : public Test {
00137      protected:
00139        Gecode::IntArgs c;
00141        int r;
00142      public:
00144        IntBoolInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
00145          : Test("Element::Int::Bool::Int::"+s+"::"+str(r0),1,-4,8),
00146            c(c0), r(r0) {}
00148        virtual bool solution(const Assignment& x) const {
00149          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
00150        }
00152        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00153          Gecode::element(home, c, x[0], r);
00154        }
00155      };
00156 
00158      class VarIntVar : public Test {
00159      public:
00161        VarIntVar(Gecode::IntConLevel icl)
00162          : Test("Element::Var::Int::Var::"+str(icl),6,-1,3,false,icl) {}
00164        virtual bool solution(const Assignment& x) const {
00165          return (x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1];
00166        }
00168        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00169          Gecode::IntVarArgs c(x.size()-2);
00170          for (int i=0; i<x.size()-2; i++)
00171            c[i]=x[2+i];
00172          Gecode::element(home, c, x[0], x[1], icl);
00173        }
00174      };
00175 
00177      class VarIntInt : public Test {
00178      protected:
00180        int r;
00181      public:
00183        VarIntInt(Gecode::IntConLevel icl, int r0)
00184          : Test("Element::Var::Int::Int::"+str(icl)+"::"+str(r0),
00185                 5,-1,3,false,icl), r(r0) {
00186          contest = CTL_NONE;
00187        }
00189        virtual bool solution(const Assignment& x) const {
00190          return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r;
00191        }
00193        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00194          Gecode::IntVarArgs c(x.size()-1);
00195          for (int i=0; i<x.size()-1; i++)
00196            c[i]=x[1+i];
00197          Gecode::element(home, c, x[0], r, icl);
00198        }
00199      };
00200 
00202      class VarIntShared : public Test {
00203      public:
00205        VarIntShared(Gecode::IntConLevel icl)
00206          : Test("Element::Var::Int::Shared::"+str(icl),5,-1,3,false,icl) {
00207          contest = CTL_NONE;
00208        }
00210        virtual bool solution(const Assignment& x) const {
00211          return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==x[0];
00212        }
00214        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00215          Gecode::IntVarArgs c(x.size()-1);
00216          for (int i=0; i<x.size()-1; i++)
00217            c[i]=x[1+i];
00218          Gecode::element(home, c, x[0], x[0], icl);
00219        }
00220      };
00221 
00223      class VarBoolVar : public Test {
00224      public:
00226        VarBoolVar(void) : Test("Element::Var::Bool::Var",6,-1,3,false) {}
00228        virtual bool solution(const Assignment& x) const {
00229          for (int i=0; i<x.size()-2; i++)
00230            if ((x[2+i] < 0) || (x[2+i]>1))
00231              return false;
00232          return ((x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1]
00233                  && (x[1]>=0) && (x[1]<=1));
00234        }
00236        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00237          using namespace Gecode;
00238          BoolVarArgs c(x.size()-2);
00239          for (int i=0; i<x.size()-2; i++)
00240            c[i]=channel(home,x[2+i]);
00241          element(home, c, x[0], channel(home,x[1]));
00242        }
00243      };
00244 
00246      class VarBoolInt : public Test {
00247      protected:
00249        int r;
00250      public:
00252        VarBoolInt(int r0)
00253          : Test("Element::Var::Bool::Int::"+str(r0),5,-1,3,false), r(r0) {}
00255        virtual bool solution(const Assignment& x) const {
00256          for (int i=0; i<x.size()-1; i++)
00257            if ((x[1+i] < 0) || (x[1+i]>1))
00258              return false;
00259          return ((x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r);
00260        }
00262        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00263          using namespace Gecode;
00264          BoolVarArgs c(x.size()-1);
00265          for (int i=0; i<x.size()-1; i++)
00266            c[i]=channel(home,x[1+i]);
00267          element(home, c, x[0], r);
00268        }
00269      };
00270 
00271 
00273      class MatrixIntIntVarXY : public Test {
00274      protected:
00276        Gecode::IntArgs tm;
00277      public:
00279        MatrixIntIntVarXY(void)
00280          : Test("Element::Matrix::Int::IntVar::XY",3,0,5,false), 
00281            tm(6, 0,1,2,3,4,5) {}
00283        virtual bool solution(const Assignment& x) const {
00284          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00285          using namespace Gecode;
00286          if ((x[0] > 2) || (x[1] > 1))
00287            return false;
00288          Matrix<IntArgs> m(tm,3,2);
00289          return m(x[0],x[1]) == x[2];
00290        }
00292        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00293          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00294          using namespace Gecode;
00295          Matrix<IntArgs> m(tm,3,2);
00296          element(home, m, x[0], x[1], x[2]);
00297        }
00298      };
00299 
00301      class MatrixIntIntVarXX : public Test {
00302      protected:
00304        Gecode::IntArgs tm;
00305      public:
00307        MatrixIntIntVarXX(void)
00308          : Test("Element::Matrix::Int::IntVar::XX",2,0,3,false), 
00309            tm(4, 0,1,2,3) {}
00311        virtual bool solution(const Assignment& x) const {
00312          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00313          using namespace Gecode;
00314          if (x[0] > 1)
00315            return false;
00316          Matrix<IntArgs> m(tm,2,2);
00317          return m(x[0],x[0]) == x[1];
00318        }
00320        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00321          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00322          using namespace Gecode;
00323          Matrix<IntArgs> m(tm,2,2);
00324          element(home, m, x[0], x[0], x[1]);
00325        }
00326      };
00327 
00329      class MatrixIntBoolVarXY : public Test {
00330      protected:
00332        Gecode::IntArgs tm;
00333      public:
00335        MatrixIntBoolVarXY(void)
00336          : Test("Element::Matrix::Int::BoolVar::XY",3,0,3,false), 
00337            tm(4, 0,1,1,0) {}
00339        virtual bool solution(const Assignment& x) const {
00340          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00341          using namespace Gecode;
00342          if ((x[0] > 1) || (x[1] > 1))
00343            return false;
00344          Matrix<IntArgs> m(tm,2,2);
00345          return m(x[0],x[1]) == x[2];
00346        }
00348        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00349          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00350          using namespace Gecode;
00351          Matrix<IntArgs> m(tm,2,2);
00352          element(home, m, x[0], x[1], channel(home,x[2]));
00353        }
00354      };
00355 
00357      class MatrixIntBoolVarXX : public Test {
00358      protected:
00360        Gecode::IntArgs tm;
00361      public:
00363        MatrixIntBoolVarXX(void)
00364          : Test("Element::Matrix::Int::BoolVar::XX",2,0,3,false), 
00365            tm(4, 0,1,1,0) {}
00367        virtual bool solution(const Assignment& x) const {
00368          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00369          using namespace Gecode;
00370          if (x[0] > 1)
00371            return false;
00372          Matrix<IntArgs> m(tm,2,2);
00373          return m(x[0],x[0]) == x[1];
00374        }
00376        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00377          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00378          using namespace Gecode;
00379          Matrix<IntArgs> m(tm,2,2);
00380          element(home, m, x[0], x[0], channel(home,x[1]));
00381        }
00382      };
00383 
00385      class MatrixIntVarIntVarXY : public Test {
00386      public:
00388        MatrixIntVarIntVarXY(void)
00389          : Test("Element::Matrix::IntVar::IntVar::XY",3+4,0,3,false) {}
00391        virtual bool solution(const Assignment& x) const {
00392          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00393          // remaining: matrix
00394          using namespace Gecode;
00395          if ((x[0] > 1) || (x[1] > 1))
00396            return false;
00397          IntArgs tm(4);
00398          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00399          Matrix<IntArgs> m(tm,2,2);
00400          return m(x[0],x[1]) == x[2];
00401        }
00403        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00404          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00405          using namespace Gecode;
00406          IntVarArgs tm(4);
00407          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00408          Matrix<IntVarArgs> m(tm,2,2);
00409          element(home, m, x[0], x[1], x[2]);
00410        }
00411      };
00412 
00414      class MatrixIntVarIntVarXX : public Test {
00415      public:
00417        MatrixIntVarIntVarXX(void)
00418          : Test("Element::Matrix::IntVar::IntVar::XX",2+4,0,3,false) {}
00420        virtual bool solution(const Assignment& x) const {
00421          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00422          // remaining: matrix
00423          using namespace Gecode;
00424          if (x[0] > 1)
00425            return false;
00426          IntArgs tm(4);
00427          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00428          Matrix<IntArgs> m(tm,2,2);
00429          return m(x[0],x[0]) == x[1];
00430        }
00432        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00433          // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
00434          using namespace Gecode;
00435          IntVarArgs tm(4);
00436          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00437          Matrix<IntVarArgs> m(tm,2,2);
00438          element(home, m, x[0], x[0], x[1]);
00439        }
00440      };
00441 
00443      class MatrixBoolVarBoolVarXY : public Test {
00444      public:
00446        MatrixBoolVarBoolVarXY(void)
00447          : Test("Element::Matrix::BoolVar::BoolVar::XY",3+4,0,1,false) {}
00449        virtual bool solution(const Assignment& x) const {
00450          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00451          // remaining: matrix
00452          using namespace Gecode;
00453          IntArgs tm(4);
00454          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00455          Matrix<IntArgs> m(tm,2,2);
00456          return m(x[0],x[1]) == x[2];
00457        }
00459        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00460          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00461          using namespace Gecode;
00462          BoolVarArgs tm(4);
00463          tm[0]=channel(home,x[3]); tm[1]=channel(home,x[4]); 
00464          tm[2]=channel(home,x[5]); tm[3]=channel(home,x[6]);
00465          Matrix<BoolVarArgs> m(tm,2,2);
00466          element(home, m, x[0], x[1], channel(home,x[2]));
00467        }
00468      };
00469 
00471      class MatrixBoolVarBoolVarXX : public Test {
00472      public:
00474        MatrixBoolVarBoolVarXX(void)
00475          : Test("Element::Matrix::BoolVar::BoolVar::XX",2+4,0,1,false) {}
00477        virtual bool solution(const Assignment& x) const {
00478          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00479          // remaining: matrix
00480          using namespace Gecode;
00481          IntArgs tm(4);
00482          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00483          Matrix<IntArgs> m(tm,2,2);
00484          return m(x[0],x[0]) == x[1];
00485        }
00487        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00488          // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
00489          using namespace Gecode;
00490          BoolVarArgs tm(4);
00491          tm[0]=channel(home,x[2]); tm[1]=channel(home,x[3]); 
00492          tm[2]=channel(home,x[4]); tm[3]=channel(home,x[5]);
00493          Matrix<BoolVarArgs> m(tm,2,2);
00494          element(home, m, x[0], x[0], channel(home,x[1]));
00495        }
00496      };
00497 
00498 
00499 
00500 
00502      class Create {
00503      public:
00505        void optimized(int idx, int val) {
00506          Gecode::IntArgs c(idx);
00507          for (int i=0; i<idx; i++)
00508            c[i]=std::max(val-i,0);
00509          (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::val",c,
00510                               val-8,val-1);
00511          if (idx != val)
00512            (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::idx",c,
00513                                 idx-8,idx-1);
00514        }
00516        Create(void) {
00517          using namespace Gecode;
00518          IntArgs ic1(5, -1,1,-3,3,-4);
00519          IntArgs ic2(8, -1,1,-1,1,-1,1,0,0);
00520          IntArgs ic3(1, -1);
00521          IntArgs ic4(7, 0,-1,2,-2,4,-3,6);
00522          IntArgs ic5(6, 0,0,1,2,3,4);
00523 
00524          IntArgs bc1(5, 0,1,1,0,1);
00525          IntArgs bc2(8, 1,1,0,1,0,1,0,0);
00526          IntArgs bc3(1, 1);
00527 
00528          (void) new IntIntVar("A",ic1,-8,8);
00529          (void) new IntIntVar("B",ic2,-8,8);
00530          (void) new IntIntVar("C",ic3,-8,8);
00531          (void) new IntIntVar("D",ic4,-8,8);
00532 
00533          // Test optimizations
00534          {
00535            int ov[] = {
00536              SCHAR_MAX-1,SCHAR_MAX,
00537              SHRT_MAX-1,SHRT_MAX,
00538              0
00539            };
00540            for (int i=0; ov[i] != 0; i++)
00541              for (int j=0; ov[j] != 0; j++)
00542                optimized(ov[i],ov[j]);
00543          }
00544 
00545          for (int i=-4; i<=4; i++) {
00546            (void) new IntIntInt("A",ic1,i);
00547            (void) new IntIntInt("B",ic2,i);
00548            (void) new IntIntInt("C",ic3,i);
00549            (void) new IntIntInt("D",ic4,i);
00550          }
00551 
00552          (void) new IntIntShared("A",ic1);
00553          (void) new IntIntShared("B",ic2);
00554          (void) new IntIntShared("C",ic3);
00555          (void) new IntIntShared("D",ic4);
00556          (void) new IntIntShared("E",ic5,1);
00557 
00558          (void) new IntBoolVar("A",bc1);
00559          (void) new IntBoolVar("B",bc2);
00560          (void) new IntBoolVar("C",bc3);
00561 
00562          for (int i=0; i<=1; i++) {
00563            (void) new IntBoolInt("A",bc1,i);
00564            (void) new IntBoolInt("B",bc2,i);
00565            (void) new IntBoolInt("C",bc3,i);
00566          }
00567 
00568          (void) new VarIntVar(ICL_BND);
00569          (void) new VarIntVar(ICL_DOM);
00570 
00571          for (int i=-4; i<=4; i++) {
00572            (void) new VarIntInt(ICL_BND,i);
00573            (void) new VarIntInt(ICL_DOM,i);
00574          }
00575 
00576          (void) new VarIntShared(ICL_BND);
00577          (void) new VarIntShared(ICL_DOM);
00578 
00579          (void) new VarBoolVar();
00580          (void) new VarBoolInt(0);
00581          (void) new VarBoolInt(1);
00582 
00583          // Matrix tests
00584          (void) new MatrixIntIntVarXY();
00585          (void) new MatrixIntIntVarXX();
00586          (void) new MatrixIntBoolVarXY();
00587          (void) new MatrixIntBoolVarXX();
00588 
00589          (void) new MatrixIntVarIntVarXY();
00590          (void) new MatrixIntVarIntVarXX();
00591          (void) new MatrixBoolVarBoolVarXY();
00592          (void) new MatrixBoolVarBoolVarXX();
00593        }
00594      };
00595 
00596      Create c;
00598 
00599    }
00600 }}
00601 
00602 // STATISTICS: test-int