00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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
00571