Generated on Thu Apr 11 13:59:07 2019 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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include "test/int.hh"
00035 
00036 #include <gecode/minimodel.hh>
00037 #include <climits>
00038 
00039 namespace Test { namespace Int {
00040 
00042    namespace Element {
00043 
00049 
00050      class IntIntVar : public Test {
00051      protected:
00053        Gecode::IntArgs c;
00054      public:
00056        IntIntVar(const std::string& s, const Gecode::IntArgs& c0,
00057                  int min, int max)
00058          : Test("Element::Int::Int::Var::"+s,2,min,max),
00059            c(c0) {}
00061        virtual bool solution(const Assignment& x) const {
00062          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
00063        }
00065        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00066          Gecode::element(home, c, x[0], x[1]);
00067        }
00068      };
00069 
00071      class IntIntInt : public Test {
00072      protected:
00074        Gecode::IntArgs c;
00076        int r;
00077      public:
00079        IntIntInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
00080          : Test("Element::Int::Int::Int::"+s+"::"+str(r0),1,-4,8),
00081            c(c0), r(r0) {}
00083        virtual bool solution(const Assignment& x) const {
00084          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
00085        }
00087        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00088          Gecode::element(home, c, x[0], r);
00089        }
00090      };
00091 
00093      class IntIntShared : public Test {
00094      protected:
00096        Gecode::IntArgs c;
00097      public:
00099        IntIntShared(const std::string& s, const Gecode::IntArgs& c0,
00100                     int minDomain=-4)
00101          : Test("Element::Int::Int::Shared::"+s,1,minDomain,8), c(c0) {}
00103        virtual bool solution(const Assignment& x) const {
00104          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[0];
00105        }
00107        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00108          Gecode::element(home, c, x[0], x[0]);
00109        }
00110      };
00111 
00113      class IntBoolVar : public Test {
00114      protected:
00116        Gecode::IntArgs c;
00117      public:
00119        IntBoolVar(const std::string& s, const Gecode::IntArgs& c0)
00120          : Test("Element::Int::Bool::Var::"+s,2,-4,8), c(c0) {}
00122        virtual bool solution(const Assignment& x) const {
00123          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
00124        }
00126        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00127          Gecode::element(home, c, x[0], Gecode::channel(home,x[1]));
00128        }
00129      };
00130 
00132      class IntBoolInt : public Test {
00133      protected:
00135        Gecode::IntArgs c;
00137        int r;
00138      public:
00140        IntBoolInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
00141          : Test("Element::Int::Bool::Int::"+s+"::"+str(r0),1,-4,8),
00142            c(c0), r(r0) {}
00144        virtual bool solution(const Assignment& x) const {
00145          return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
00146        }
00148        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00149          Gecode::element(home, c, x[0], r);
00150        }
00151      };
00152 
00154      class VarIntVar : public Test {
00155      public:
00157        VarIntVar(Gecode::IntPropLevel ipl)
00158          : Test("Element::Var::Int::Var::"+str(ipl),6,-1,3,false,ipl) {}
00160        virtual bool solution(const Assignment& x) const {
00161          return (x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1];
00162        }
00164        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00165          Gecode::IntVarArgs c(x.size()-2);
00166          for (int i=0; i<x.size()-2; i++)
00167            c[i]=x[2+i];
00168          Gecode::element(home, c, x[0], x[1], ipl);
00169        }
00170      };
00171 
00173      class VarIntInt : public Test {
00174      protected:
00176        int r;
00177      public:
00179        VarIntInt(Gecode::IntPropLevel ipl, int r0)
00180          : Test("Element::Var::Int::Int::"+str(ipl)+"::"+str(r0),
00181                 5,-1,3,false,ipl), r(r0) {
00182          contest = CTL_NONE;
00183        }
00185        virtual bool solution(const Assignment& x) const {
00186          return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r;
00187        }
00189        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00190          Gecode::IntVarArgs c(x.size()-1);
00191          for (int i=0; i<x.size()-1; i++)
00192            c[i]=x[1+i];
00193          Gecode::element(home, c, x[0], r, ipl);
00194        }
00195      };
00196 
00198      class VarIntShared : public Test {
00199      public:
00201        VarIntShared(Gecode::IntPropLevel ipl)
00202          : Test("Element::Var::Int::Shared::"+str(ipl),5,-1,3,false,ipl) {
00203          contest = CTL_NONE;
00204        }
00206        virtual bool solution(const Assignment& x) const {
00207          return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==x[0];
00208        }
00210        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00211          Gecode::IntVarArgs c(x.size()-1);
00212          for (int i=0; i<x.size()-1; i++)
00213            c[i]=x[1+i];
00214          Gecode::element(home, c, x[0], x[0], ipl);
00215        }
00216      };
00217 
00219      class VarBoolVar : public Test {
00220      public:
00222        VarBoolVar(void) : Test("Element::Var::Bool::Var",6,-1,3,false) {}
00224        virtual bool solution(const Assignment& x) const {
00225          for (int i=0; i<x.size()-2; i++)
00226            if ((x[2+i] < 0) || (x[2+i]>1))
00227              return false;
00228          return ((x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1]
00229                  && (x[1]>=0) && (x[1]<=1));
00230        }
00232        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00233          using namespace Gecode;
00234          BoolVarArgs c(x.size()-2);
00235          for (int i=0; i<x.size()-2; i++)
00236            c[i]=channel(home,x[2+i]);
00237          element(home, c, x[0], channel(home,x[1]));
00238        }
00239      };
00240 
00242      class VarBoolInt : public Test {
00243      protected:
00245        int r;
00246      public:
00248        VarBoolInt(int r0)
00249          : Test("Element::Var::Bool::Int::"+str(r0),5,-1,3,false), r(r0) {}
00251        virtual bool solution(const Assignment& x) const {
00252          for (int i=0; i<x.size()-1; i++)
00253            if ((x[1+i] < 0) || (x[1+i]>1))
00254              return false;
00255          return ((x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r);
00256        }
00258        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00259          using namespace Gecode;
00260          BoolVarArgs c(x.size()-1);
00261          for (int i=0; i<x.size()-1; i++)
00262            c[i]=channel(home,x[1+i]);
00263          if (r == 1) {
00264            switch (Base::rand(3)) {
00265            case 0:
00266              element(home, c, x[0], 1);
00267              break;
00268            case 1:
00269              {
00270                BoolVar one(home,1,1);
00271                rel(home, element(c,x[0]) == one);
00272              }
00273              break;
00274            case 2:
00275              rel(home, element(c,x[0]));
00276              break;
00277            default: GECODE_NEVER;
00278            }
00279          } else {
00280            element(home, c, x[0], r);
00281          }
00282        }
00283      };
00284 
00285 
00287      class MatrixIntIntVarXY : public Test {
00288      protected:
00290        Gecode::IntArgs tm;
00291      public:
00293        MatrixIntIntVarXY(void)
00294          : Test("Element::Matrix::Int::IntVar::XY",3,0,5,false),
00295            tm({0,1,2,3,4,5}) {}
00297        virtual bool solution(const Assignment& x) const {
00298          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00299          using namespace Gecode;
00300          if ((x[0] > 2) || (x[1] > 1))
00301            return false;
00302          Matrix<IntArgs> m(tm,3,2);
00303          return m(x[0],x[1]) == x[2];
00304        }
00306        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00307          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00308          using namespace Gecode;
00309          Matrix<IntArgs> m(tm,3,2);
00310          element(home, m, x[0], x[1], x[2]);
00311        }
00312      };
00313 
00315      class MatrixIntIntVarXX : public Test {
00316      protected:
00318        Gecode::IntArgs tm;
00319      public:
00321        MatrixIntIntVarXX(void)
00322          : Test("Element::Matrix::Int::IntVar::XX",2,0,3,false),
00323            tm({0,1,2,3}) {}
00325        virtual bool solution(const Assignment& x) const {
00326          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00327          using namespace Gecode;
00328          if (x[0] > 1)
00329            return false;
00330          Matrix<IntArgs> m(tm,2,2);
00331          return m(x[0],x[0]) == x[1];
00332        }
00334        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00335          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00336          using namespace Gecode;
00337          Matrix<IntArgs> m(tm,2,2);
00338          element(home, m, x[0], x[0], x[1]);
00339        }
00340      };
00341 
00343      class MatrixIntBoolVarXY : public Test {
00344      protected:
00346        Gecode::IntArgs tm;
00347      public:
00349        MatrixIntBoolVarXY(void)
00350          : Test("Element::Matrix::Int::BoolVar::XY",3,0,3,false),
00351            tm({0,1,1,0}) {}
00353        virtual bool solution(const Assignment& x) const {
00354          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00355          using namespace Gecode;
00356          if ((x[0] > 1) || (x[1] > 1))
00357            return false;
00358          Matrix<IntArgs> m(tm,2,2);
00359          return m(x[0],x[1]) == x[2];
00360        }
00362        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00363          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00364          using namespace Gecode;
00365          Matrix<IntArgs> m(tm,2,2);
00366          element(home, m, x[0], x[1], channel(home,x[2]));
00367        }
00368      };
00369 
00371      class MatrixIntBoolVarXX : public Test {
00372      protected:
00374        Gecode::IntArgs tm;
00375      public:
00377        MatrixIntBoolVarXX(void)
00378          : Test("Element::Matrix::Int::BoolVar::XX",2,0,3,false),
00379            tm({0,1,1,0}) {}
00381        virtual bool solution(const Assignment& x) const {
00382          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00383          using namespace Gecode;
00384          if (x[0] > 1)
00385            return false;
00386          Matrix<IntArgs> m(tm,2,2);
00387          return m(x[0],x[0]) == x[1];
00388        }
00390        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00391          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00392          using namespace Gecode;
00393          Matrix<IntArgs> m(tm,2,2);
00394          element(home, m, x[0], x[0], channel(home,x[1]));
00395        }
00396      };
00397 
00399      class MatrixIntVarIntVarXY : public Test {
00400      public:
00402        MatrixIntVarIntVarXY(void)
00403          : Test("Element::Matrix::IntVar::IntVar::XY",3+4,0,3,false) {}
00405        virtual bool solution(const Assignment& x) const {
00406          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00407          // remaining: matrix
00408          using namespace Gecode;
00409          if ((x[0] > 1) || (x[1] > 1))
00410            return false;
00411          IntArgs tm(4);
00412          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00413          Matrix<IntArgs> m(tm,2,2);
00414          return m(x[0],x[1]) == x[2];
00415        }
00417        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00418          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00419          using namespace Gecode;
00420          IntVarArgs tm(4);
00421          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00422          Matrix<IntVarArgs> m(tm,2,2);
00423          element(home, m, x[0], x[1], x[2]);
00424        }
00425      };
00426 
00428      class MatrixIntVarIntVarXX : public Test {
00429      public:
00431        MatrixIntVarIntVarXX(void)
00432          : Test("Element::Matrix::IntVar::IntVar::XX",2+4,0,3,false) {}
00434        virtual bool solution(const Assignment& x) const {
00435          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00436          // remaining: matrix
00437          using namespace Gecode;
00438          if (x[0] > 1)
00439            return false;
00440          IntArgs tm(4);
00441          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00442          Matrix<IntArgs> m(tm,2,2);
00443          return m(x[0],x[0]) == x[1];
00444        }
00446        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00447          // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
00448          using namespace Gecode;
00449          IntVarArgs tm(4);
00450          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00451          Matrix<IntVarArgs> m(tm,2,2);
00452          element(home, m, x[0], x[0], x[1]);
00453        }
00454      };
00455 
00457      class MatrixBoolVarBoolVarXY : public Test {
00458      public:
00460        MatrixBoolVarBoolVarXY(void)
00461          : Test("Element::Matrix::BoolVar::BoolVar::XY",3+4,0,1,false) {}
00463        virtual bool solution(const Assignment& x) const {
00464          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00465          // remaining: matrix
00466          using namespace Gecode;
00467          IntArgs tm(4);
00468          tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
00469          Matrix<IntArgs> m(tm,2,2);
00470          return m(x[0],x[1]) == x[2];
00471        }
00473        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00474          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00475          using namespace Gecode;
00476          BoolVarArgs tm(4);
00477          tm[0]=channel(home,x[3]); tm[1]=channel(home,x[4]);
00478          tm[2]=channel(home,x[5]); tm[3]=channel(home,x[6]);
00479          Matrix<BoolVarArgs> m(tm,2,2);
00480          element(home, m, x[0], x[1], channel(home,x[2]));
00481        }
00482      };
00483 
00485      class MatrixBoolVarBoolVarXX : public Test {
00486      public:
00488        MatrixBoolVarBoolVarXX(void)
00489          : Test("Element::Matrix::BoolVar::BoolVar::XX",2+4,0,1,false) {}
00491        virtual bool solution(const Assignment& x) const {
00492          // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
00493          // remaining: matrix
00494          using namespace Gecode;
00495          IntArgs tm(4);
00496          tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
00497          Matrix<IntArgs> m(tm,2,2);
00498          return m(x[0],x[0]) == x[1];
00499        }
00501        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00502          // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
00503          using namespace Gecode;
00504          BoolVarArgs tm(4);
00505          tm[0]=channel(home,x[2]); tm[1]=channel(home,x[3]);
00506          tm[2]=channel(home,x[4]); tm[3]=channel(home,x[5]);
00507          Matrix<BoolVarArgs> m(tm,2,2);
00508          element(home, m, x[0], x[0], channel(home,x[1]));
00509        }
00510      };
00511 
00512 
00513 
00514 
00516      class Create {
00517      public:
00519        void optimized(int idx, int val) {
00520          Gecode::IntArgs c(idx);
00521          for (int i=0; i<idx; i++)
00522            c[i]=std::max(val-i,0);
00523          (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::val",c,
00524                               val-8,val-1);
00525          if (idx != val)
00526            (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::idx",c,
00527                                 idx-8,idx-1);
00528        }
00530        Create(void) {
00531          using namespace Gecode;
00532          IntArgs ic1({-1,1,-3,3,-4});
00533          IntArgs ic2({-1,1,-1,1,-1,1,0,0});
00534          IntArgs ic3({-1});
00535          IntArgs ic4({0,-1,2,-2,4,-3,6});
00536          IntArgs ic5({0,0,1,2,3,4});
00537 
00538          IntArgs bc1({0,1,1,0,1});
00539          IntArgs bc2({1,1,0,1,0,1,0,0});
00540          IntArgs bc3({1});
00541 
00542          (void) new IntIntVar("A",ic1,-8,8);
00543          (void) new IntIntVar("B",ic2,-8,8);
00544          (void) new IntIntVar("C",ic3,-8,8);
00545          (void) new IntIntVar("D",ic4,-8,8);
00546 
00547          // Test optimizations
00548          {
00549            int ov[] = {
00550              SCHAR_MAX-1,SCHAR_MAX,
00551              SHRT_MAX-1,SHRT_MAX,
00552              0
00553            };
00554            for (int i=0; ov[i] != 0; i++)
00555              for (int j=0; ov[j] != 0; j++)
00556                optimized(ov[i],ov[j]);
00557          }
00558 
00559          for (int i=-4; i<=4; i++) {
00560            (void) new IntIntInt("A",ic1,i);
00561            (void) new IntIntInt("B",ic2,i);
00562            (void) new IntIntInt("C",ic3,i);
00563            (void) new IntIntInt("D",ic4,i);
00564          }
00565 
00566          (void) new IntIntShared("A",ic1);
00567          (void) new IntIntShared("B",ic2);
00568          (void) new IntIntShared("C",ic3);
00569          (void) new IntIntShared("D",ic4);
00570          (void) new IntIntShared("E",ic5,1);
00571 
00572          (void) new IntBoolVar("A",bc1);
00573          (void) new IntBoolVar("B",bc2);
00574          (void) new IntBoolVar("C",bc3);
00575 
00576          for (int i=0; i<=1; i++) {
00577            (void) new IntBoolInt("A",bc1,i);
00578            (void) new IntBoolInt("B",bc2,i);
00579            (void) new IntBoolInt("C",bc3,i);
00580          }
00581 
00582          (void) new VarIntVar(IPL_BND);
00583          (void) new VarIntVar(IPL_DOM);
00584 
00585          for (int i=-4; i<=4; i++) {
00586            (void) new VarIntInt(IPL_BND,i);
00587            (void) new VarIntInt(IPL_DOM,i);
00588          }
00589 
00590          (void) new VarIntShared(IPL_BND);
00591          (void) new VarIntShared(IPL_DOM);
00592 
00593          (void) new VarBoolVar();
00594          (void) new VarBoolInt(0);
00595          (void) new VarBoolInt(1);
00596 
00597          // Matrix tests
00598          (void) new MatrixIntIntVarXY();
00599          (void) new MatrixIntIntVarXX();
00600          (void) new MatrixIntBoolVarXY();
00601          (void) new MatrixIntBoolVarXX();
00602 
00603          (void) new MatrixIntVarIntVarXY();
00604          (void) new MatrixIntVarIntVarXX();
00605          (void) new MatrixBoolVarBoolVarXY();
00606          (void) new MatrixBoolVarBoolVarXX();
00607        }
00608      };
00609 
00610      Create c;
00612 
00613    }
00614 }}
00615 
00616 // STATISTICS: test-int