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

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  *     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: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00013  *     $Revision: 10684 $
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 #include <climits>
00044 
00045 namespace Test { namespace Int {
00046 
00048    namespace Extensional {
00049 
00055 
00056      class RegSimpleA : public Test {
00057      public:
00059        RegSimpleA(void) : Test("Extensional::Reg::Simple::A",4,2,2) {}
00061        virtual bool solution(const Assignment& x) const {
00062          return (((x[0] == 0) || (x[0] == 2)) &&
00063                  ((x[1] == -1) || (x[1] == 1)) &&
00064                  ((x[2] == 0) || (x[2] == 1)) &&
00065                  ((x[3] == 0) || (x[3] == 1)));
00066        }
00068        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00069          using namespace Gecode;
00070          extensional(home, x,
00071                      (REG(0) | REG(2)) +
00072                      (REG(-1) | REG(1)) +
00073                      (REG(7) | REG(0) | REG(1)) +
00074                      (REG(0) | REG(1)));
00075        }
00076      };
00077 
00079      class RegSimpleB : public Test {
00080      public:
00082        RegSimpleB(void) : Test("Extensional::Reg::Simple::B",4,2,2) {}
00084        virtual bool solution(const Assignment& x) const {
00085          return (x[0]<x[1]) && (x[1]<x[2]) && (x[2]<x[3]);
00086        }
00088        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00089          using namespace Gecode;
00090          extensional(home, x,
00091                      (REG(-2) + REG(-1) + REG(0) + REG(1)) |
00092                      (REG(-2) + REG(-1) + REG(0) + REG(2)) |
00093                      (REG(-2) + REG(-1) + REG(1) + REG(2)) |
00094                      (REG(-2) + REG(0) + REG(1) + REG(2)) |
00095                      (REG(-1) + REG(0) + REG(1) + REG(2)));
00096          }
00097      };
00098 
00100      class RegSimpleC : public Test {
00101      public:
00103        RegSimpleC(void) : Test("Extensional::Reg::Simple::C",6,0,1) {}
00105        virtual bool solution(const Assignment& x) const {
00106          int pos = 0;
00107          int s = x.size();
00108 
00109          while (pos < s && x[pos] == 0) ++pos;
00110          if (pos + 4 > s) return false;
00111 
00112          for (int i = 0; i < 2; ++i, ++pos)
00113            if (x[pos] != 1) return false;
00114          if (pos + 2 > s) return false;
00115 
00116          for (int i = 0; i < 1; ++i, ++pos)
00117            if (x[pos] != 0) return false;
00118          while (pos < s && x[pos] == 0) ++pos;
00119          if (pos + 1 > s) return false;
00120 
00121          for (int i = 0; i < 1; ++i, ++pos)
00122            if (x[pos] != 1) return false;
00123          while (pos < s) if (x[pos++] != 0) return false;
00124          return true;
00125 
00126        }
00128        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00129          using namespace Gecode;
00130          extensional(home, x,
00131                      *REG(0) + REG(1)(2,2) + +REG(0) + REG(1)(1,1) + *REG(0));
00132        }
00133      };
00134 
00136      class RegDistinct : public Test {
00137      public:
00139        RegDistinct(void) : Test("Extensional::Reg::Distinct",4,-1,4) {}
00141        virtual bool solution(const Assignment& x) const {
00142          for (int i=0; i<x.size(); i++) {
00143            if ((x[i] < 0) || (x[i] > 3))
00144              return false;
00145            for (int j=i+1; j<x.size(); j++)
00146              if (x[i]==x[j])
00147                return false;
00148          }
00149          return true;
00150        }
00152        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00153          using namespace Gecode;
00154          extensional(home, x,
00155                      (REG(0)+REG(1)+REG(2)+REG(3)) |
00156                      (REG(0)+REG(1)+REG(3)+REG(2)) |
00157                      (REG(0)+REG(2)+REG(1)+REG(3)) |
00158                      (REG(0)+REG(2)+REG(3)+REG(1)) |
00159                      (REG(0)+REG(3)+REG(1)+REG(2)) |
00160                      (REG(0)+REG(3)+REG(2)+REG(1)) |
00161                      (REG(1)+REG(0)+REG(2)+REG(3)) |
00162                      (REG(1)+REG(0)+REG(3)+REG(2)) |
00163                      (REG(1)+REG(2)+REG(0)+REG(3)) |
00164                      (REG(1)+REG(2)+REG(3)+REG(0)) |
00165                      (REG(1)+REG(3)+REG(0)+REG(2)) |
00166                      (REG(1)+REG(3)+REG(2)+REG(0)) |
00167                      (REG(2)+REG(0)+REG(1)+REG(3)) |
00168                      (REG(2)+REG(0)+REG(3)+REG(1)) |
00169                      (REG(2)+REG(1)+REG(0)+REG(3)) |
00170                      (REG(2)+REG(1)+REG(3)+REG(0)) |
00171                      (REG(2)+REG(3)+REG(0)+REG(1)) |
00172                      (REG(2)+REG(3)+REG(1)+REG(0)) |
00173                      (REG(3)+REG(0)+REG(1)+REG(2)) |
00174                      (REG(3)+REG(0)+REG(2)+REG(1)) |
00175                      (REG(3)+REG(1)+REG(0)+REG(2)) |
00176                      (REG(3)+REG(1)+REG(2)+REG(0)) |
00177                      (REG(3)+REG(2)+REG(0)+REG(1)) |
00178                      (REG(3)+REG(2)+REG(1)+REG(0)));
00179        }
00180      };
00181 
00183      class RegRoland : public Test {
00184      public:
00186        RegRoland(int n)
00187          : Test("Extensional::Reg::Roland::"+str(n),n,0,1) {}
00189        virtual bool solution(const Assignment& x) const {
00190          int n = x.size();
00191          return
00192            ((n > 1) && (x[n-2] == 0)) ||
00193            ((n > 0) && (x[n-1] == 0));
00194        }
00196        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00197          using namespace Gecode;
00198          REG r0(0), r1(1);
00199          REG r01 = r0 | r1;
00200          extensional(home, x, *r01 + r0 + r01(0,1));
00201        }
00202      };
00203 
00205      class RegSharedA : public Test {
00206      public:
00208        RegSharedA(void) : Test("Extensional::Reg::Shared::A",4,2,2) {}
00210        virtual bool solution(const Assignment& x) const {
00211          return (((x[0] == 0) || (x[0] == 2)) &&
00212                  ((x[1] == -1) || (x[1] == 1)) &&
00213                  ((x[2] == 0) || (x[2] == 1)) &&
00214                  ((x[3] == 0) || (x[3] == 1)));
00215        }
00217        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00218          using namespace Gecode;
00219          IntVarArgs y(8);
00220          for (int i=0; i<4; i++)
00221            y[i]=y[i+4]=x[i];
00222          unshare(home,y);
00223          extensional(home, y,
00224                      ((REG(0) | REG(2)) +
00225                       (REG(-1) | REG(1)) +
00226                       (REG(7) | REG(0) | REG(1)) +
00227                       (REG(0) | REG(1)))(2,2));
00228        }
00229      };
00230 
00232      class RegSharedB : public Test {
00233      public:
00235        RegSharedB(void) : Test("Extensional::Reg::Shared::B",4,2,2) {}
00237        virtual bool solution(const Assignment& x) const {
00238          return (((x[0] == 0) || (x[0] == 2)) &&
00239                  ((x[1] == -1) || (x[1] == 1)) &&
00240                  ((x[2] == 0) || (x[2] == 1)) &&
00241                  ((x[3] == 0) || (x[3] == 1)));
00242        }
00244        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00245          using namespace Gecode;
00246          IntVarArgs y(12);
00247          for (int i=0; i<4; i++)
00248            y[i]=y[i+4]=y[i+8]=x[i];
00249          unshare(home,y);
00250          extensional(home, y,
00251                      ((REG(0) | REG(2)) +
00252                       (REG(-1) | REG(1)) +
00253                       (REG(7) | REG(0) | REG(1)) +
00254                       (REG(0) | REG(1)))(3,3));
00255        }
00256      };
00257 
00259      class RegSharedC : public Test {
00260      public:
00262        RegSharedC(void) : Test("Extensional::Reg::Shared::C",4,0,1) {}
00264        virtual bool solution(const Assignment& x) const {
00265          return (x[1]==1) && (x[2]==0) && (x[3]==1);
00266        }
00268        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00269          using namespace Gecode;
00270          Gecode::BoolVarArgs y(8);
00271          for (int i=0; i<4; i++)
00272            y[i]=y[i+4]=channel(home,x[i]);
00273          unshare(home,y);
00274          extensional(home,y,
00275                      ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(2,2));
00276        }
00277      };
00278 
00280      class RegSharedD : public Test {
00281      public:
00283        RegSharedD(void) : Test("Extensional::Reg::Shared::D",4,0,1) {}
00285        virtual bool solution(const Assignment& x) const {
00286          return (x[1]==1) && (x[2]==0) && (x[3]==1);
00287        }
00289        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00290          using namespace Gecode;
00291          Gecode::BoolVarArgs y(12);
00292          for (int i=0; i<4; i++)
00293            y[i]=y[i+4]=y[i+8]=channel(home,x[i]);
00294          unshare(home, y);
00295          extensional(home, y,
00296                      ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(3,3));
00297        }
00298      };
00299 
00301      class RegEmptyDFA : public Test {
00302      public:
00304        RegEmptyDFA(void) : Test("Extensional::Reg::Empty::DFA",1,0,0) {
00305          testsearch = false;
00306        }
00308        virtual bool solution(const Assignment& x) const {
00309          (void)x;
00310          return false;
00311        }
00313        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00314          Gecode::DFA d;
00315          Gecode::extensional(home, x, d);
00316        }
00317      };
00318 
00320      class RegEmptyREG : public Test {
00321      public:
00323        RegEmptyREG(void) : Test("Extensional::Reg::Empty::REG",1,0,0) {
00324          testsearch = false;
00325        }
00327        virtual bool solution(const Assignment& x) const {
00328          (void)x;
00329          return false;
00330        }
00332        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00333          Gecode::REG r;
00334          Gecode::extensional(home, x, r);
00335        }
00336      };
00337 
00339      class RegOpt : public Test {
00340      protected:
00342        int n;
00343      public:
00345        RegOpt(int n0) 
00346          : Test("Extensional::Reg::Opt::"+str(n0),1,0,15), n(n0) {}
00348        virtual bool solution(const Assignment& x) const {
00349          return (x[0] < n) && ((x[0] & 1) == 0);
00350        }
00352        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00353          using namespace Gecode;
00354          DFA::Transition* t = new DFA::Transition[n+1];
00355          DFA::Transition* ti = t;
00356          int* f = new int[n+1];
00357          int* fi = f;
00358          for (int i=0; i<n; i++) {
00359            ti->i_state = 0;
00360            ti->symbol  = i;
00361            ti->o_state = i+1;
00362            ti++;
00363            if ((i & 1) == 0) {
00364              *fi = i+1; fi++;
00365            }
00366          }
00367          ti->i_state = -1;
00368          *fi = -1;
00369          DFA d(0, t, f, false);
00370          delete [] t;
00371          delete [] f;
00372          extensional(home, x, d);
00373        }
00374        
00375      };
00376 
00378      class TupleSetA : public Test {
00379      protected:
00381        Gecode::ExtensionalPropKind epk;
00382      public:
00384        TupleSetA(Gecode::ExtensionalPropKind epk0)
00385          : Test("Extensional::TupleSet::A::"+str(epk0),
00386                 4,1,5,false,Gecode::ICL_DOM), epk(epk0) {}
00388        virtual bool solution(const Assignment& x) const {
00389          return ((x[0] == 1 && x[1] == 3 && x[2] == 2 && x[3] == 3) ||
00390                  (x[0] == 2 && x[1] == 1 && x[2] == 2 && x[3] == 4) ||
00391                  (x[0] == 2 && x[1] == 2 && x[2] == 1 && x[3] == 4) ||
00392                  (x[0] == 3 && x[1] == 3 && x[2] == 3 && x[3] == 2) ||
00393                  (x[0] == 4 && x[1] == 3 && x[2] == 4 && x[3] == 1)
00394                  );
00395        }
00397        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00398          using namespace Gecode;
00399          TupleSet t;
00400          IntArgs t1(4,  2, 1, 2, 4);
00401          IntArgs t2(4,  2, 2, 1, 4);
00402          IntArgs t3(4,  4, 3, 4, 1);
00403          IntArgs t4(4,  1, 3, 2, 3);
00404          IntArgs t5(4,  3, 3, 3, 2);
00405          t.add(t1);
00406          t.add(t1);
00407          t.add(t2);
00408          t.add(t2);
00409          t.add(t3);
00410          t.add(t3);
00411          t.add(t4);
00412          t.add(t4);
00413          t.add(t5);
00414          t.add(t5);
00415          t.add(t5);
00416          t.add(t5);
00417          t.add(t5);
00418          t.add(t5);
00419          t.add(t5);
00420          t.add(t5);
00421          t.finalize();
00422 
00423          extensional(home, x, t, epk, ICL_DEF);
00424        }
00425      };
00426 
00428      class TupleSetB : public Test {
00429        mutable Gecode::TupleSet t;
00430      protected:
00432        Gecode::ExtensionalPropKind epk;
00433      public:
00435        TupleSetB(Gecode::ExtensionalPropKind epk0)
00436          : Test("Extensional::TupleSet::B::"+str(epk0),
00437                 4,1,5,false,Gecode::ICL_DOM), epk(epk0) {
00438          using namespace Gecode;
00439          IntArgs t1 (4,  2, 1, 2, 4);
00440          IntArgs t2 (4,  2, 2, 1, 4);
00441          IntArgs t3 (4,  4, 3, 4, 1);
00442          IntArgs t4 (4,  1, 3, 2, 3);
00443          IntArgs t5 (4,  3, 3, 3, 2);
00444          IntArgs t6 (4,  5, 1, 4, 4);
00445          IntArgs t7 (4,  2, 5, 1, 5);
00446          IntArgs t8 (4,  4, 3, 5, 1);
00447          IntArgs t9 (4,  1, 5, 2, 5);
00448          IntArgs t10(4,  5, 3, 3, 2);
00449          t.add(t1);
00450          t.add(t2);
00451          t.add(t3);
00452          t.add(t4);
00453          t.add(t5);
00454          t.add(t6);
00455          t.add(t7);
00456          t.add(t8);
00457          t.add(t9);
00458          t.add(t10);
00459          t.finalize();
00460        }
00462        virtual bool solution(const Assignment& x) const {
00463          using namespace Gecode;
00464          for (int i = 0; i < t.tuples(); ++i) {
00465            TupleSet::Tuple l = t[i];
00466            bool same = true;
00467            for (int j = 0; j < t.arity() && same; ++j)
00468              if (l[j] != x[j]) same = false;
00469            if (same) return true;
00470          }
00471          return false;
00472        }
00474        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00475          using namespace Gecode;
00476          extensional(home, x, t, epk, ICL_DEF);
00477        }
00478      };
00479 
00480 
00481 
00483      class TupleSetBool : public Test {
00484        mutable Gecode::TupleSet t;
00485      protected:
00487        Gecode::ExtensionalPropKind epk;
00488      public:
00490        TupleSetBool(Gecode::ExtensionalPropKind epk0, double prob)
00491          : Test("Extensional::TupleSet::Bool::"+str(epk0),
00492                 5,0,1,false,Gecode::ICL_DOM), epk(epk0) {
00493          using namespace Gecode;
00494 
00495          CpltAssignment ass(5, IntSet(0, 1));
00496          while (ass()) {
00497            if (Base::rand(100) <= prob*100) {
00498              IntArgs tuple(5);
00499              for (int i = 5; i--; ) tuple[i] = ass[i];
00500              t.add(tuple);
00501            }
00502            ++ass;
00503          }
00504          t.finalize();
00505        }
00507        virtual bool solution(const Assignment& x) const {
00508          using namespace Gecode;
00509          for (int i = 0; i < t.tuples(); ++i) {
00510            TupleSet::Tuple l = t[i];
00511            bool same = true;
00512            for (int j = 0; j < t.arity() && same; ++j)
00513              if (l[j] != x[j]) same = false;
00514            if (same) return true;
00515          }
00516          return false;
00517        }
00519        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00520          using namespace Gecode;
00521          BoolVarArgs y(x.size());
00522          for (int i = x.size(); i--; ) y[i] = channel(home, x[i]);
00523          extensional(home, y, t, epk, ICL_DEF);
00524        }
00525      };
00526 
00527 
00528      RegSimpleA ra;
00529      RegSimpleB rb;
00530      RegSimpleC rc;
00531 
00532      RegDistinct rd;
00533 
00534      RegRoland rr1(1);
00535      RegRoland rr2(2);
00536      RegRoland rr3(3);
00537      RegRoland rr4(4);
00538 
00539      RegSharedA rsa;
00540      RegSharedB rsb;
00541      RegSharedC rsc;
00542      RegSharedD rsd;
00543 
00544      RegEmptyDFA redfa;
00545      RegEmptyREG rereg;
00546 
00547      RegOpt ro0(CHAR_MAX-1);
00548      RegOpt ro1(CHAR_MAX);
00549      RegOpt ro2(static_cast<int>(UCHAR_MAX-1));
00550      RegOpt ro3(static_cast<int>(UCHAR_MAX));
00551      RegOpt ro4(SHRT_MAX-1);
00552      RegOpt ro5(SHRT_MAX);
00553      RegOpt ro6(static_cast<int>(USHRT_MAX-1));
00554      RegOpt ro7(static_cast<int>(USHRT_MAX));
00555 
00556      TupleSetA tsam(Gecode::EPK_MEMORY);
00557      TupleSetA tsas(Gecode::EPK_SPEED);
00558 
00559      TupleSetB tsbm(Gecode::EPK_MEMORY);
00560      TupleSetB tsbs(Gecode::EPK_SPEED);
00561 
00562      TupleSetBool tsboolm(Gecode::EPK_MEMORY, 0.3);
00563      TupleSetBool tsbools(Gecode::EPK_SPEED, 0.3);
00565 
00566    }
00567 }}
00568 
00569 
00570 // STATISTICS: test-int
00571