Generated on Tue Jul 27 2010 21:59:11 for Gecode by doxygen 1.7.1

bool.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 
00042 namespace Test { namespace Int {
00043 
00045    namespace Bool {
00046 
00047      inline int
00048      check(int x0, Gecode::BoolOpType op, int x1) {
00049        switch (op) {
00050        case Gecode::BOT_AND: return x0 & x1;
00051        case Gecode::BOT_OR:  return x0 | x1;
00052        case Gecode::BOT_IMP: return !x0 | x1;
00053        case Gecode::BOT_EQV: return x0 == x1;
00054        case Gecode::BOT_XOR: return x0 != x1;
00055        default: GECODE_NEVER;
00056        }
00057        GECODE_NEVER;
00058        return 0;
00059      }
00060 
00066 
00067      class BinXYZ : public Test {
00068      protected:
00070        Gecode::BoolOpType op;
00071      public:
00073        BinXYZ(Gecode::BoolOpType op0)
00074          : Test("Bool::Bin::XYZ::"+str(op0),3,0,1), op(op0) {}
00076        virtual bool solution(const Assignment& x) const {
00077          return check(x[0],op,x[1]) == x[2];
00078        }
00080        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00081          using namespace Gecode;
00082          rel(home,
00083              channel(home,x[0]), op, channel(home,x[1]),
00084              channel(home,x[2]));
00085        }
00086      };
00087 
00089      class BinXXY : public Test {
00090      protected:
00092        Gecode::BoolOpType op;
00093      public:
00095        BinXXY(Gecode::BoolOpType op0)
00096          : Test("Bool::Bin::XXY::"+str(op0),2,0,1), op(op0) {}
00098        virtual bool solution(const Assignment& x) const {
00099          return check(x[0],op,x[0]) == x[1];
00100        }
00102        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00103          using namespace Gecode;
00104          BoolVar b = channel(home,x[0]);
00105          rel(home, b, op, b, channel(home,x[1]));
00106        }
00107      };
00108 
00110      class BinXYX : public Test {
00111      protected:
00113        Gecode::BoolOpType op;
00114      public:
00116        BinXYX(Gecode::BoolOpType op0)
00117          : Test("Bool::Bin::XYX::"+str(op0),2,0,1), op(op0) {}
00119        virtual bool solution(const Assignment& x) const {
00120          return check(x[0],op,x[1]) == x[0];
00121        }
00123        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00124          using namespace Gecode;
00125          BoolVar b = channel(home,x[0]);
00126          rel(home, b, op, channel(home,x[1]), b);
00127        }
00128      };
00129 
00131      class BinXYY : public Test {
00132      protected:
00134        Gecode::BoolOpType op;
00135      public:
00137        BinXYY(Gecode::BoolOpType op0)
00138          : Test("Bool::Bin::XYY::"+str(op0),2,0,1), op(op0) {}
00140        virtual bool solution(const Assignment& x) const {
00141          return check(x[0],op,x[1]) == x[1];
00142        }
00144        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00145          using namespace Gecode;
00146          BoolVar b = channel(home,x[1]);
00147          rel(home, channel(home,x[0]), op, b, b);
00148        }
00149      };
00150 
00152      class BinXXX : public Test {
00153      protected:
00155        Gecode::BoolOpType op;
00156      public:
00158        BinXXX(Gecode::BoolOpType op0)
00159          : Test("Bool::Bin::XXX::"+str(op0),1,0,1), op(op0) {}
00161        virtual bool solution(const Assignment& x) const {
00162          return check(x[0],op,x[0]) == x[0];
00163        }
00165        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00166          using namespace Gecode;
00167          BoolVar b = channel(home,x[0]);
00168          rel(home, b, op, b, b);
00169        }
00170      };
00171 
00173      class BinConstXY : public Test {
00174      protected:
00176        Gecode::BoolOpType op;
00178        int c;
00179      public:
00181        BinConstXY(Gecode::BoolOpType op0, int c0)
00182          : Test("Bool::Bin::XY::"+str(op0)+"::"+str(c0),2,0,1),
00183            op(op0), c(c0) {}
00185        virtual bool solution(const Assignment& x) const {
00186          return check(x[0],op,x[1]) == c;
00187        }
00189        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00190          using namespace Gecode;
00191          rel(home, channel(home,x[0]), op, channel(home,x[1]), c);
00192        }
00193      };
00194 
00196      class BinConstXX : public Test {
00197      protected:
00199        Gecode::BoolOpType op;
00201        int c;
00202      public:
00204        BinConstXX(Gecode::BoolOpType op0, int c0)
00205          : Test("Bool::Bin::XX::"+str(op0)+"::"+str(c0),1,0,1),
00206            op(op0), c(c0) {}
00208        virtual bool solution(const Assignment& x) const {
00209          return check(x[0],op,x[0]) == c;
00210        }
00212        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00213          using namespace Gecode;
00214          BoolVar b = channel(home,x[0]);
00215          rel(home, b, op, b, c);
00216        }
00217      };
00218 
00220      class Nary : public Test {
00221      protected:
00223        Gecode::BoolOpType op;
00224      public:
00226        Nary(Gecode::BoolOpType op0, int n)
00227          : Test("Bool::Nary::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
00229        virtual bool solution(const Assignment& x) const {
00230          int b = check(x[0],op,x[1]);
00231          for (int i=2; i<x.size()-1; i++)
00232            b = check(b,op,x[i]);
00233          return b == x[x.size()-1];
00234        }
00236        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00237          using namespace Gecode;
00238          BoolVarArgs b(x.size()-1);
00239          for (int i=x.size()-1; i--; )
00240            b[i]=channel(home,x[i]);
00241          rel(home, op, b, channel(home,x[x.size()-1]));
00242        }
00243      };
00244 
00246      class NaryShared : public Test {
00247      protected:
00249        Gecode::BoolOpType op;
00250      public:
00252        NaryShared(Gecode::BoolOpType op0, int n)
00253          : Test("Bool::Nary::Shared::"+str(op0)+"::"+str(n),n,0,1),
00254            op(op0) {}
00256        virtual bool solution(const Assignment& x) const {
00257          int b = check(x[0],op,x[1]);
00258          for (int i=2; i<x.size(); i++)
00259            b = check(b,op,x[i]);
00260          return b == x[x.size()-1];
00261        }
00263        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00264          using namespace Gecode;
00265          BoolVarArgs b(x.size());
00266          for (int i=x.size(); i--; )
00267            b[i]=channel(home,x[i]);
00268          rel(home, op, b, b[x.size()-1]);
00269        }
00270      };
00271 
00273      class NaryConst : public Test {
00274      protected:
00276        Gecode::BoolOpType op;
00278        int c;
00279      public:
00281        NaryConst(Gecode::BoolOpType op0, int n, int c0)
00282          : Test("Bool::Nary::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
00283            op(op0), c(c0) {}
00285        virtual bool solution(const Assignment& x) const {
00286          int b = check(x[0],op,x[1]);
00287          for (int i=2; i<x.size(); i++)
00288            b = check(b,op,x[i]);
00289          return b == c;
00290        }
00292        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00293          using namespace Gecode;
00294          BoolVarArgs b(x.size());
00295          for (int i=x.size(); i--; )
00296            b[i]=channel(home,x[i]);
00297          rel(home, op, b, c);
00298        }
00299      };
00300 
00301 
00303      class ClauseXYZ : public Test {
00304      protected:
00306        Gecode::BoolOpType op;
00307      public:
00309        ClauseXYZ(Gecode::BoolOpType op0, int n)
00310          : Test("Bool::Clause::XYZ::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
00312        virtual bool solution(const Assignment& x) const {
00313          int n = (x.size()-1) / 2;
00314          int b;
00315          if (n == 1) {
00316            b = check(x[0],op,!x[1]);
00317          } else {
00318            b = check(x[0],op,!x[n]);
00319            for (int i=1; i<n; i++)
00320              b = check(b,op,check(x[i],op,!x[n+i]));
00321          }
00322          return b == x[x.size()-1];
00323        }
00325        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00326          using namespace Gecode;
00327          int n = (x.size()-1) / 2;
00328          BoolVarArgs a(n), b(n);
00329          for (int i=n; i--; ) {
00330            a[i]=channel(home,x[i]);
00331            b[i]=channel(home,x[i+n]);
00332          }
00333          clause(home, op, a, b, channel(home,x[x.size()-1]));
00334        }
00335      };
00336 
00338      class ClauseXXYYX : public Test {
00339      protected:
00341        Gecode::BoolOpType op;
00342      public:
00344        ClauseXXYYX(Gecode::BoolOpType op0, int n)
00345          : Test("Bool::Clause::XXYYX::"+str(op0)+"::"+str(n),n,0,1),
00346            op(op0) {}
00348        virtual bool solution(const Assignment& x) const {
00349          int n = x.size() / 2;
00350          int b;
00351          if (n == 1) {
00352            b = check(x[0],op,!x[1]);
00353          } else {
00354            b = check(x[0],op,!x[n]);
00355            for (int i=1; i<n; i++)
00356              b = check(b,op,check(x[i],op,!x[n+i]));
00357          }
00358          return b == x[0];
00359        }
00361        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00362          using namespace Gecode;
00363          int n = x.size() / 2;
00364          BoolVarArgs a(2*n), b(2*n);
00365          for (int i=n; i--; ) {
00366            a[i]=a[i+n]=channel(home,x[i]);
00367            b[i]=b[i+n]=channel(home,x[i+n]);
00368          }
00369          clause(home, op, a, b, a[0]);
00370        }
00371      };
00372 
00374      class ClauseXXY : public Test {
00375      protected:
00377        Gecode::BoolOpType op;
00378      public:
00380        ClauseXXY(Gecode::BoolOpType op0, int n)
00381          : Test("Bool::Clause::XXY::"+str(op0)+"::"+str(n),n,0,1),
00382            op(op0) {}
00384        virtual bool solution(const Assignment& x) const {
00385          return (x[0] == 1) == (op == Gecode::BOT_OR);
00386        }
00388        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00389          using namespace Gecode;
00390          int n = x.size() / 2;
00391          BoolVarArgs a(2*n), b(2*n);
00392          for (int i=n; i--; ) {
00393            a[i]=b[i+n]=channel(home,x[i]);
00394            b[i]=a[i+n]=channel(home,x[i+n]);
00395          }
00396          clause(home, op, a, b, a[0]);
00397        }
00398      };
00399 
00401      class ClauseConst : public Test {
00402      protected:
00404        Gecode::BoolOpType op;
00406        int c;
00407      public:
00409        ClauseConst(Gecode::BoolOpType op0, int n, int c0)
00410          : Test("Bool::Clause::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
00411            op(op0), c(c0) {}
00413        virtual bool solution(const Assignment& x) const {
00414          int n = x.size() / 2;
00415          int b;
00416          if (n == 1) {
00417            b = check(x[0],op,!x[1]);
00418          } else {
00419            b = check(x[0],op,!x[n]);
00420            for (int i=1; i<n; i++)
00421              b = check(b,op,check(x[i],op,!x[n+i]));
00422          }
00423          return b == c;
00424        }
00426        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00427          using namespace Gecode;
00428          int n = x.size() / 2;
00429          BoolVarArgs a(n), b(n);
00430          for (int i=n; i--; ) {
00431            a[i]=channel(home,x[i]);
00432            b[i]=channel(home,x[i+n]);
00433          }
00434          clause(home, op, a, b, c);
00435        }
00436      };
00437 
00439      class Create {
00440      public:
00442        Create(void) {
00443          using namespace Gecode;
00444          for (BoolOpTypes bots; bots(); ++bots) {
00445            (void) new BinXYZ(bots.bot());
00446            (void) new BinXXY(bots.bot());
00447            (void) new BinXYX(bots.bot());
00448            (void) new BinXYY(bots.bot());
00449            (void) new BinXXX(bots.bot());
00450            (void) new BinConstXY(bots.bot(),0);
00451            (void) new BinConstXY(bots.bot(),1);
00452            (void) new BinConstXX(bots.bot(),0);
00453            (void) new BinConstXX(bots.bot(),1);
00454            (void) new Nary(bots.bot(),2);
00455            (void) new Nary(bots.bot(),6);
00456            (void) new Nary(bots.bot(),10);
00457            (void) new NaryShared(bots.bot(),2);
00458            (void) new NaryShared(bots.bot(),6);
00459            (void) new NaryShared(bots.bot(),10);
00460            (void) new NaryConst(bots.bot(),2,0);
00461            (void) new NaryConst(bots.bot(),6,0);
00462            (void) new NaryConst(bots.bot(),10,0);
00463            (void) new NaryConst(bots.bot(),2,1);
00464            (void) new NaryConst(bots.bot(),6,1);
00465            (void) new NaryConst(bots.bot(),10,1);
00466            if ((bots.bot() == BOT_AND) || (bots.bot() == BOT_OR)) {
00467              (void) new ClauseXYZ(bots.bot(),2);
00468              (void) new ClauseXYZ(bots.bot(),6);
00469              (void) new ClauseXYZ(bots.bot(),10);
00470              (void) new ClauseXXYYX(bots.bot(),2);
00471              (void) new ClauseXXYYX(bots.bot(),6);
00472              (void) new ClauseXXYYX(bots.bot(),10);
00473              (void) new ClauseXXY(bots.bot(),2);
00474              (void) new ClauseXXY(bots.bot(),6);
00475              (void) new ClauseXXY(bots.bot(),10);
00476              (void) new ClauseConst(bots.bot(),2,0);
00477              (void) new ClauseConst(bots.bot(),6,0);
00478              (void) new ClauseConst(bots.bot(),10,0);
00479              (void) new ClauseConst(bots.bot(),2,1);
00480              (void) new ClauseConst(bots.bot(),6,1);
00481              (void) new ClauseConst(bots.bot(),10,1);
00482            }
00483          }
00484        }
00485      };
00486 
00487      Create c;
00489 
00490    }
00491 }}
00492 
00493 // STATISTICS: test-int
00494