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