element.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 #include <climits> 00042 00043 namespace Test { namespace Int { 00044 00046 namespace Element { 00047 00053 00054 class IntIntVar : public Test { 00055 protected: 00057 Gecode::IntArgs c; 00058 public: 00060 IntIntVar(const std::string& s, const Gecode::IntArgs& c0, 00061 int min, int max) 00062 : Test("Element::Int::Int::Var::"+s,2,min,max), 00063 c(c0) {} 00065 virtual bool solution(const Assignment& x) const { 00066 return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1]; 00067 } 00069 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00070 Gecode::element(home, c, x[0], x[1]); 00071 } 00072 }; 00073 00075 class IntIntInt : public Test { 00076 protected: 00078 Gecode::IntArgs c; 00080 int r; 00081 public: 00083 IntIntInt(const std::string& s, const Gecode::IntArgs& c0, int r0) 00084 : Test("Element::Int::Int::Int::"+s+"::"+str(r0),1,-4,8), 00085 c(c0), r(r0) {} 00087 virtual bool solution(const Assignment& x) const { 00088 return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r; 00089 } 00091 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00092 Gecode::element(home, c, x[0], r); 00093 } 00094 }; 00095 00097 class IntIntShared : public Test { 00098 protected: 00100 Gecode::IntArgs c; 00101 public: 00103 IntIntShared(const std::string& s, const Gecode::IntArgs& c0, 00104 int minDomain=-4) 00105 : Test("Element::Int::Int::Shared::"+s,1,minDomain,8), c(c0) {} 00107 virtual bool solution(const Assignment& x) const { 00108 return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[0]; 00109 } 00111 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00112 Gecode::element(home, c, x[0], x[0]); 00113 } 00114 }; 00115 00117 class IntBoolVar : public Test { 00118 protected: 00120 Gecode::IntArgs c; 00121 public: 00123 IntBoolVar(const std::string& s, const Gecode::IntArgs& c0) 00124 : Test("Element::Int::Bool::Var::"+s,2,-4,8), c(c0) {} 00126 virtual bool solution(const Assignment& x) const { 00127 return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1]; 00128 } 00130 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00131 Gecode::element(home, c, x[0], Gecode::channel(home,x[1])); 00132 } 00133 }; 00134 00136 class IntBoolInt : public Test { 00137 protected: 00139 Gecode::IntArgs c; 00141 int r; 00142 public: 00144 IntBoolInt(const std::string& s, const Gecode::IntArgs& c0, int r0) 00145 : Test("Element::Int::Bool::Int::"+s+"::"+str(r0),1,-4,8), 00146 c(c0), r(r0) {} 00148 virtual bool solution(const Assignment& x) const { 00149 return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r; 00150 } 00152 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00153 Gecode::element(home, c, x[0], r); 00154 } 00155 }; 00156 00158 class VarIntVar : public Test { 00159 public: 00161 VarIntVar(Gecode::IntConLevel icl) 00162 : Test("Element::Var::Int::Var::"+str(icl),6,-1,3,false,icl) {} 00164 virtual bool solution(const Assignment& x) const { 00165 return (x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1]; 00166 } 00168 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00169 Gecode::IntVarArgs c(x.size()-2); 00170 for (int i=0; i<x.size()-2; i++) 00171 c[i]=x[2+i]; 00172 Gecode::element(home, c, x[0], x[1], icl); 00173 } 00174 }; 00175 00177 class VarIntInt : public Test { 00178 protected: 00180 int r; 00181 public: 00183 VarIntInt(Gecode::IntConLevel icl, int r0) 00184 : Test("Element::Var::Int::Int::"+str(icl)+"::"+str(r0), 00185 5,-1,3,false,icl), r(r0) { 00186 contest = CTL_NONE; 00187 } 00189 virtual bool solution(const Assignment& x) const { 00190 return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r; 00191 } 00193 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00194 Gecode::IntVarArgs c(x.size()-1); 00195 for (int i=0; i<x.size()-1; i++) 00196 c[i]=x[1+i]; 00197 Gecode::element(home, c, x[0], r, icl); 00198 } 00199 }; 00200 00202 class VarIntShared : public Test { 00203 public: 00205 VarIntShared(Gecode::IntConLevel icl) 00206 : Test("Element::Var::Int::Shared::"+str(icl),5,-1,3,false,icl) { 00207 contest = CTL_NONE; 00208 } 00210 virtual bool solution(const Assignment& x) const { 00211 return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==x[0]; 00212 } 00214 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00215 Gecode::IntVarArgs c(x.size()-1); 00216 for (int i=0; i<x.size()-1; i++) 00217 c[i]=x[1+i]; 00218 Gecode::element(home, c, x[0], x[0], icl); 00219 } 00220 }; 00221 00223 class VarBoolVar : public Test { 00224 public: 00226 VarBoolVar(void) : Test("Element::Var::Bool::Var",6,-1,3,false) {} 00228 virtual bool solution(const Assignment& x) const { 00229 for (int i=0; i<x.size()-2; i++) 00230 if ((x[2+i] < 0) || (x[2+i]>1)) 00231 return false; 00232 return ((x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1] 00233 && (x[1]>=0) && (x[1]<=1)); 00234 } 00236 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00237 using namespace Gecode; 00238 BoolVarArgs c(x.size()-2); 00239 for (int i=0; i<x.size()-2; i++) 00240 c[i]=channel(home,x[2+i]); 00241 element(home, c, x[0], channel(home,x[1])); 00242 } 00243 }; 00244 00246 class VarBoolInt : public Test { 00247 protected: 00249 int r; 00250 public: 00252 VarBoolInt(int r0) 00253 : Test("Element::Var::Bool::Int::"+str(r0),5,-1,3,false), r(r0) {} 00255 virtual bool solution(const Assignment& x) const { 00256 for (int i=0; i<x.size()-1; i++) 00257 if ((x[1+i] < 0) || (x[1+i]>1)) 00258 return false; 00259 return ((x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r); 00260 } 00262 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00263 using namespace Gecode; 00264 BoolVarArgs c(x.size()-1); 00265 for (int i=0; i<x.size()-1; i++) 00266 c[i]=channel(home,x[1+i]); 00267 element(home, c, x[0], r); 00268 } 00269 }; 00270 00271 00273 class MatrixIntIntVarXY : public Test { 00274 protected: 00276 Gecode::IntArgs tm; 00277 public: 00279 MatrixIntIntVarXY(void) 00280 : Test("Element::Matrix::Int::IntVar::XY",3,0,5,false), 00281 tm(6, 0,1,2,3,4,5) {} 00283 virtual bool solution(const Assignment& x) const { 00284 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00285 using namespace Gecode; 00286 if ((x[0] > 2) || (x[1] > 1)) 00287 return false; 00288 Matrix<IntArgs> m(tm,3,2); 00289 return m(x[0],x[1]) == x[2]; 00290 } 00292 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00293 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00294 using namespace Gecode; 00295 Matrix<IntArgs> m(tm,3,2); 00296 element(home, m, x[0], x[1], x[2]); 00297 } 00298 }; 00299 00301 class MatrixIntIntVarXX : public Test { 00302 protected: 00304 Gecode::IntArgs tm; 00305 public: 00307 MatrixIntIntVarXX(void) 00308 : Test("Element::Matrix::Int::IntVar::XX",2,0,3,false), 00309 tm(4, 0,1,2,3) {} 00311 virtual bool solution(const Assignment& x) const { 00312 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00313 using namespace Gecode; 00314 if (x[0] > 1) 00315 return false; 00316 Matrix<IntArgs> m(tm,2,2); 00317 return m(x[0],x[0]) == x[1]; 00318 } 00320 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00321 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00322 using namespace Gecode; 00323 Matrix<IntArgs> m(tm,2,2); 00324 element(home, m, x[0], x[0], x[1]); 00325 } 00326 }; 00327 00329 class MatrixIntBoolVarXY : public Test { 00330 protected: 00332 Gecode::IntArgs tm; 00333 public: 00335 MatrixIntBoolVarXY(void) 00336 : Test("Element::Matrix::Int::BoolVar::XY",3,0,3,false), 00337 tm(4, 0,1,1,0) {} 00339 virtual bool solution(const Assignment& x) const { 00340 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00341 using namespace Gecode; 00342 if ((x[0] > 1) || (x[1] > 1)) 00343 return false; 00344 Matrix<IntArgs> m(tm,2,2); 00345 return m(x[0],x[1]) == x[2]; 00346 } 00348 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00349 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00350 using namespace Gecode; 00351 Matrix<IntArgs> m(tm,2,2); 00352 element(home, m, x[0], x[1], channel(home,x[2])); 00353 } 00354 }; 00355 00357 class MatrixIntBoolVarXX : public Test { 00358 protected: 00360 Gecode::IntArgs tm; 00361 public: 00363 MatrixIntBoolVarXX(void) 00364 : Test("Element::Matrix::Int::BoolVar::XX",2,0,3,false), 00365 tm(4, 0,1,1,0) {} 00367 virtual bool solution(const Assignment& x) const { 00368 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00369 using namespace Gecode; 00370 if (x[0] > 1) 00371 return false; 00372 Matrix<IntArgs> m(tm,2,2); 00373 return m(x[0],x[0]) == x[1]; 00374 } 00376 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00377 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00378 using namespace Gecode; 00379 Matrix<IntArgs> m(tm,2,2); 00380 element(home, m, x[0], x[0], channel(home,x[1])); 00381 } 00382 }; 00383 00385 class MatrixIntVarIntVarXY : public Test { 00386 public: 00388 MatrixIntVarIntVarXY(void) 00389 : Test("Element::Matrix::IntVar::IntVar::XY",3+4,0,3,false) {} 00391 virtual bool solution(const Assignment& x) const { 00392 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00393 // remaining: matrix 00394 using namespace Gecode; 00395 if ((x[0] > 1) || (x[1] > 1)) 00396 return false; 00397 IntArgs tm(4); 00398 tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6]; 00399 Matrix<IntArgs> m(tm,2,2); 00400 return m(x[0],x[1]) == x[2]; 00401 } 00403 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00404 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00405 using namespace Gecode; 00406 IntVarArgs tm(4); 00407 tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6]; 00408 Matrix<IntVarArgs> m(tm,2,2); 00409 element(home, m, x[0], x[1], x[2]); 00410 } 00411 }; 00412 00414 class MatrixIntVarIntVarXX : public Test { 00415 public: 00417 MatrixIntVarIntVarXX(void) 00418 : Test("Element::Matrix::IntVar::IntVar::XX",2+4,0,3,false) {} 00420 virtual bool solution(const Assignment& x) const { 00421 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00422 // remaining: matrix 00423 using namespace Gecode; 00424 if (x[0] > 1) 00425 return false; 00426 IntArgs tm(4); 00427 tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5]; 00428 Matrix<IntArgs> m(tm,2,2); 00429 return m(x[0],x[0]) == x[1]; 00430 } 00432 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00433 // x-coordinate: x[0], y-coordinate: x[1], result: x[1] 00434 using namespace Gecode; 00435 IntVarArgs tm(4); 00436 tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5]; 00437 Matrix<IntVarArgs> m(tm,2,2); 00438 element(home, m, x[0], x[0], x[1]); 00439 } 00440 }; 00441 00443 class MatrixBoolVarBoolVarXY : public Test { 00444 public: 00446 MatrixBoolVarBoolVarXY(void) 00447 : Test("Element::Matrix::BoolVar::BoolVar::XY",3+4,0,1,false) {} 00449 virtual bool solution(const Assignment& x) const { 00450 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00451 // remaining: matrix 00452 using namespace Gecode; 00453 IntArgs tm(4); 00454 tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6]; 00455 Matrix<IntArgs> m(tm,2,2); 00456 return m(x[0],x[1]) == x[2]; 00457 } 00459 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00460 // x-coordinate: x[0], y-coordinate: x[1], result: x[2] 00461 using namespace Gecode; 00462 BoolVarArgs tm(4); 00463 tm[0]=channel(home,x[3]); tm[1]=channel(home,x[4]); 00464 tm[2]=channel(home,x[5]); tm[3]=channel(home,x[6]); 00465 Matrix<BoolVarArgs> m(tm,2,2); 00466 element(home, m, x[0], x[1], channel(home,x[2])); 00467 } 00468 }; 00469 00471 class MatrixBoolVarBoolVarXX : public Test { 00472 public: 00474 MatrixBoolVarBoolVarXX(void) 00475 : Test("Element::Matrix::BoolVar::BoolVar::XX",2+4,0,1,false) {} 00477 virtual bool solution(const Assignment& x) const { 00478 // x-coordinate: x[0], y-coordinate: x[0], result: x[1] 00479 // remaining: matrix 00480 using namespace Gecode; 00481 IntArgs tm(4); 00482 tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5]; 00483 Matrix<IntArgs> m(tm,2,2); 00484 return m(x[0],x[0]) == x[1]; 00485 } 00487 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00488 // x-coordinate: x[0], y-coordinate: x[1], result: x[1] 00489 using namespace Gecode; 00490 BoolVarArgs tm(4); 00491 tm[0]=channel(home,x[2]); tm[1]=channel(home,x[3]); 00492 tm[2]=channel(home,x[4]); tm[3]=channel(home,x[5]); 00493 Matrix<BoolVarArgs> m(tm,2,2); 00494 element(home, m, x[0], x[0], channel(home,x[1])); 00495 } 00496 }; 00497 00498 00499 00500 00502 class Create { 00503 public: 00505 void optimized(int idx, int val) { 00506 Gecode::IntArgs c(idx); 00507 for (int i=0; i<idx; i++) 00508 c[i]=std::max(val-i,0); 00509 (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::val",c, 00510 val-8,val-1); 00511 if (idx != val) 00512 (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::idx",c, 00513 idx-8,idx-1); 00514 } 00516 Create(void) { 00517 using namespace Gecode; 00518 IntArgs ic1(5, -1,1,-3,3,-4); 00519 IntArgs ic2(8, -1,1,-1,1,-1,1,0,0); 00520 IntArgs ic3(1, -1); 00521 IntArgs ic4(7, 0,-1,2,-2,4,-3,6); 00522 IntArgs ic5(6, 0,0,1,2,3,4); 00523 00524 IntArgs bc1(5, 0,1,1,0,1); 00525 IntArgs bc2(8, 1,1,0,1,0,1,0,0); 00526 IntArgs bc3(1, 1); 00527 00528 (void) new IntIntVar("A",ic1,-8,8); 00529 (void) new IntIntVar("B",ic2,-8,8); 00530 (void) new IntIntVar("C",ic3,-8,8); 00531 (void) new IntIntVar("D",ic4,-8,8); 00532 00533 // Test optimizations 00534 { 00535 int ov[] = { 00536 SCHAR_MAX-1,SCHAR_MAX, 00537 SHRT_MAX-1,SHRT_MAX, 00538 0 00539 }; 00540 for (int i=0; ov[i] != 0; i++) 00541 for (int j=0; ov[j] != 0; j++) 00542 optimized(ov[i],ov[j]); 00543 } 00544 00545 for (int i=-4; i<=4; i++) { 00546 (void) new IntIntInt("A",ic1,i); 00547 (void) new IntIntInt("B",ic2,i); 00548 (void) new IntIntInt("C",ic3,i); 00549 (void) new IntIntInt("D",ic4,i); 00550 } 00551 00552 (void) new IntIntShared("A",ic1); 00553 (void) new IntIntShared("B",ic2); 00554 (void) new IntIntShared("C",ic3); 00555 (void) new IntIntShared("D",ic4); 00556 (void) new IntIntShared("E",ic5,1); 00557 00558 (void) new IntBoolVar("A",bc1); 00559 (void) new IntBoolVar("B",bc2); 00560 (void) new IntBoolVar("C",bc3); 00561 00562 for (int i=0; i<=1; i++) { 00563 (void) new IntBoolInt("A",bc1,i); 00564 (void) new IntBoolInt("B",bc2,i); 00565 (void) new IntBoolInt("C",bc3,i); 00566 } 00567 00568 (void) new VarIntVar(ICL_BND); 00569 (void) new VarIntVar(ICL_DOM); 00570 00571 for (int i=-4; i<=4; i++) { 00572 (void) new VarIntInt(ICL_BND,i); 00573 (void) new VarIntInt(ICL_DOM,i); 00574 } 00575 00576 (void) new VarIntShared(ICL_BND); 00577 (void) new VarIntShared(ICL_DOM); 00578 00579 (void) new VarBoolVar(); 00580 (void) new VarBoolInt(0); 00581 (void) new VarBoolInt(1); 00582 00583 // Matrix tests 00584 (void) new MatrixIntIntVarXY(); 00585 (void) new MatrixIntIntVarXX(); 00586 (void) new MatrixIntBoolVarXY(); 00587 (void) new MatrixIntBoolVarXX(); 00588 00589 (void) new MatrixIntVarIntVarXY(); 00590 (void) new MatrixIntVarIntVarXX(); 00591 (void) new MatrixBoolVarBoolVarXY(); 00592 (void) new MatrixBoolVarBoolVarXX(); 00593 } 00594 }; 00595 00596 Create c; 00598 00599 } 00600 }} 00601 00602 // STATISTICS: test-int