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 public:
00381 TupleSetA(Gecode::IntPropLevel ipl0)
00382 : Test("Extensional::TupleSet::A::"+str(ipl0),
00383 4,1,5,false,ipl0) {}
00385 virtual bool solution(const Assignment& x) const {
00386 return ((x[0] == 1 && x[1] == 3 && x[2] == 2 && x[3] == 3) ||
00387 (x[0] == 2 && x[1] == 1 && x[2] == 2 && x[3] == 4) ||
00388 (x[0] == 2 && x[1] == 2 && x[2] == 1 && x[3] == 4) ||
00389 (x[0] == 3 && x[1] == 3 && x[2] == 3 && x[3] == 2) ||
00390 (x[0] == 4 && x[1] == 3 && x[2] == 4 && x[3] == 1)
00391 );
00392 }
00394 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00395 using namespace Gecode;
00396 TupleSet t;
00397 IntArgs t1(4, 2, 1, 2, 4);
00398 IntArgs t2(4, 2, 2, 1, 4);
00399 IntArgs t3(4, 4, 3, 4, 1);
00400 IntArgs t4(4, 1, 3, 2, 3);
00401 IntArgs t5(4, 3, 3, 3, 2);
00402 t.add(t1);
00403 t.add(t1);
00404 t.add(t2);
00405 t.add(t2);
00406 t.add(t3);
00407 t.add(t3);
00408 t.add(t4);
00409 t.add(t4);
00410 t.add(t5);
00411 t.add(t5);
00412 t.add(t5);
00413 t.add(t5);
00414 t.add(t5);
00415 t.add(t5);
00416 t.add(t5);
00417 t.add(t5);
00418 t.finalize();
00419
00420 extensional(home, x, t, ipl);
00421 }
00422 };
00423
00425 class TupleSetB : public Test {
00426 mutable Gecode::TupleSet t;
00427 public:
00429 TupleSetB(Gecode::IntPropLevel ipl0)
00430 : Test("Extensional::TupleSet::B::"+str(ipl0),
00431 4,1,5,false,ipl0) {
00432 using namespace Gecode;
00433 IntArgs t1 (4, 2, 1, 2, 4);
00434 IntArgs t2 (4, 2, 2, 1, 4);
00435 IntArgs t3 (4, 4, 3, 4, 1);
00436 IntArgs t4 (4, 1, 3, 2, 3);
00437 IntArgs t5 (4, 3, 3, 3, 2);
00438 IntArgs t6 (4, 5, 1, 4, 4);
00439 IntArgs t7 (4, 2, 5, 1, 5);
00440 IntArgs t8 (4, 4, 3, 5, 1);
00441 IntArgs t9 (4, 1, 5, 2, 5);
00442 IntArgs t10(4, 5, 3, 3, 2);
00443 t.add(t1);
00444 t.add(t2);
00445 t.add(t3);
00446 t.add(t4);
00447 t.add(t5);
00448 t.add(t6);
00449 t.add(t7);
00450 t.add(t8);
00451 t.add(t9);
00452 t.add(t10);
00453 t.finalize();
00454 }
00456 virtual bool solution(const Assignment& x) const {
00457 using namespace Gecode;
00458 for (int i = 0; i < t.tuples(); ++i) {
00459 TupleSet::Tuple l = t[i];
00460 bool same = true;
00461 for (int j = 0; j < t.arity() && same; ++j)
00462 if (l[j] != x[j]) same = false;
00463 if (same) return true;
00464 }
00465 return false;
00466 }
00468 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00469 using namespace Gecode;
00470 extensional(home, x, t, ipl);
00471 }
00472 };
00473
00474
00475
00477 class TupleSetBool : public Test {
00478 mutable Gecode::TupleSet t;
00479 public:
00481 TupleSetBool(Gecode::IntPropLevel ipl0, double prob)
00482 : Test("Extensional::TupleSet::Bool::"+str(ipl0),
00483 5,0,1,false,ipl0) {
00484 using namespace Gecode;
00485
00486 CpltAssignment ass(5, IntSet(0, 1));
00487 while (ass()) {
00488 if (Base::rand(100) <= prob*100) {
00489 IntArgs tuple(5);
00490 for (int i = 5; i--; ) tuple[i] = ass[i];
00491 t.add(tuple);
00492 }
00493 ++ass;
00494 }
00495 t.finalize();
00496 }
00498 virtual bool solution(const Assignment& x) const {
00499 using namespace Gecode;
00500 for (int i = 0; i < t.tuples(); ++i) {
00501 TupleSet::Tuple l = t[i];
00502 bool same = true;
00503 for (int j = 0; j < t.arity() && same; ++j)
00504 if (l[j] != x[j]) same = false;
00505 if (same) return true;
00506 }
00507 return false;
00508 }
00510 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00511 using namespace Gecode;
00512 BoolVarArgs y(x.size());
00513 for (int i = x.size(); i--; )
00514 y[i] = channel(home, x[i]);
00515 extensional(home, y, t, ipl);
00516 }
00517 };
00518
00519
00520 RegSimpleA ra;
00521 RegSimpleB rb;
00522 RegSimpleC rc;
00523
00524 RegDistinct rd;
00525
00526 RegRoland rr1(1);
00527 RegRoland rr2(2);
00528 RegRoland rr3(3);
00529 RegRoland rr4(4);
00530
00531 RegSharedA rsa;
00532 RegSharedB rsb;
00533 RegSharedC rsc;
00534 RegSharedD rsd;
00535
00536 RegEmptyDFA redfa;
00537 RegEmptyREG rereg;
00538
00539 RegOpt ro0(CHAR_MAX-1);
00540 RegOpt ro1(CHAR_MAX);
00541 RegOpt ro2(static_cast<int>(UCHAR_MAX-1));
00542 RegOpt ro3(static_cast<int>(UCHAR_MAX));
00543 RegOpt ro4(SHRT_MAX-1);
00544 RegOpt ro5(SHRT_MAX);
00545 RegOpt ro6(static_cast<int>(USHRT_MAX-1));
00546 RegOpt ro7(static_cast<int>(USHRT_MAX));
00547
00548 TupleSetA tsam(Gecode::IPL_MEMORY);
00549 TupleSetA tsas(Gecode::IPL_SPEED);
00550
00551 TupleSetB tsbm(Gecode::IPL_MEMORY);
00552 TupleSetB tsbs(Gecode::IPL_SPEED);
00553
00554 TupleSetBool tsboolm(Gecode::IPL_MEMORY, 0.3);
00555 TupleSetBool tsbools(Gecode::IPL_SPEED, 0.3);
00557
00558 }
00559 }}
00560
00561
00562
00563