bool.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 00042 namespace Test { namespace Int { 00043 00045 namespace Bool { 00046 00047 inline int 00048 check(int x0, Gecode::BoolOpType op, int x1) { 00049 switch (op) { 00050 case Gecode::BOT_AND: return x0 & x1; 00051 case Gecode::BOT_OR: return x0 | x1; 00052 case Gecode::BOT_IMP: return !x0 | x1; 00053 case Gecode::BOT_EQV: return x0 == x1; 00054 case Gecode::BOT_XOR: return x0 != x1; 00055 default: GECODE_NEVER; 00056 } 00057 GECODE_NEVER; 00058 return 0; 00059 } 00060 00066 00067 class BinXYZ : public Test { 00068 protected: 00070 Gecode::BoolOpType op; 00071 public: 00073 BinXYZ(Gecode::BoolOpType op0) 00074 : Test("Bool::Bin::XYZ::"+str(op0),3,0,1), op(op0) {} 00076 virtual bool solution(const Assignment& x) const { 00077 return check(x[0],op,x[1]) == x[2]; 00078 } 00080 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00081 using namespace Gecode; 00082 rel(home, 00083 channel(home,x[0]), op, channel(home,x[1]), 00084 channel(home,x[2])); 00085 } 00086 }; 00087 00089 class BinXXY : public Test { 00090 protected: 00092 Gecode::BoolOpType op; 00093 public: 00095 BinXXY(Gecode::BoolOpType op0) 00096 : Test("Bool::Bin::XXY::"+str(op0),2,0,1), op(op0) {} 00098 virtual bool solution(const Assignment& x) const { 00099 return check(x[0],op,x[0]) == x[1]; 00100 } 00102 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00103 using namespace Gecode; 00104 BoolVar b = channel(home,x[0]); 00105 rel(home, b, op, b, channel(home,x[1])); 00106 } 00107 }; 00108 00110 class BinXYX : public Test { 00111 protected: 00113 Gecode::BoolOpType op; 00114 public: 00116 BinXYX(Gecode::BoolOpType op0) 00117 : Test("Bool::Bin::XYX::"+str(op0),2,0,1), op(op0) {} 00119 virtual bool solution(const Assignment& x) const { 00120 return check(x[0],op,x[1]) == x[0]; 00121 } 00123 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00124 using namespace Gecode; 00125 BoolVar b = channel(home,x[0]); 00126 rel(home, b, op, channel(home,x[1]), b); 00127 } 00128 }; 00129 00131 class BinXYY : public Test { 00132 protected: 00134 Gecode::BoolOpType op; 00135 public: 00137 BinXYY(Gecode::BoolOpType op0) 00138 : Test("Bool::Bin::XYY::"+str(op0),2,0,1), op(op0) {} 00140 virtual bool solution(const Assignment& x) const { 00141 return check(x[0],op,x[1]) == x[1]; 00142 } 00144 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00145 using namespace Gecode; 00146 BoolVar b = channel(home,x[1]); 00147 rel(home, channel(home,x[0]), op, b, b); 00148 } 00149 }; 00150 00152 class BinXXX : public Test { 00153 protected: 00155 Gecode::BoolOpType op; 00156 public: 00158 BinXXX(Gecode::BoolOpType op0) 00159 : Test("Bool::Bin::XXX::"+str(op0),1,0,1), op(op0) {} 00161 virtual bool solution(const Assignment& x) const { 00162 return check(x[0],op,x[0]) == x[0]; 00163 } 00165 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00166 using namespace Gecode; 00167 BoolVar b = channel(home,x[0]); 00168 rel(home, b, op, b, b); 00169 } 00170 }; 00171 00173 class BinConstXY : public Test { 00174 protected: 00176 Gecode::BoolOpType op; 00178 int c; 00179 public: 00181 BinConstXY(Gecode::BoolOpType op0, int c0) 00182 : Test("Bool::Bin::XY::"+str(op0)+"::"+str(c0),2,0,1), 00183 op(op0), c(c0) {} 00185 virtual bool solution(const Assignment& x) const { 00186 return check(x[0],op,x[1]) == c; 00187 } 00189 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00190 using namespace Gecode; 00191 rel(home, channel(home,x[0]), op, channel(home,x[1]), c); 00192 } 00193 }; 00194 00196 class BinConstXX : public Test { 00197 protected: 00199 Gecode::BoolOpType op; 00201 int c; 00202 public: 00204 BinConstXX(Gecode::BoolOpType op0, int c0) 00205 : Test("Bool::Bin::XX::"+str(op0)+"::"+str(c0),1,0,1), 00206 op(op0), c(c0) {} 00208 virtual bool solution(const Assignment& x) const { 00209 return check(x[0],op,x[0]) == c; 00210 } 00212 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00213 using namespace Gecode; 00214 BoolVar b = channel(home,x[0]); 00215 rel(home, b, op, b, c); 00216 } 00217 }; 00218 00220 class Nary : public Test { 00221 protected: 00223 Gecode::BoolOpType op; 00224 public: 00226 Nary(Gecode::BoolOpType op0, int n) 00227 : Test("Bool::Nary::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {} 00229 virtual bool solution(const Assignment& x) const { 00230 int b = check(x[0],op,x[1]); 00231 for (int i=2; i<x.size()-1; i++) 00232 b = check(b,op,x[i]); 00233 return b == x[x.size()-1]; 00234 } 00236 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00237 using namespace Gecode; 00238 BoolVarArgs b(x.size()-1); 00239 for (int i=x.size()-1; i--; ) 00240 b[i]=channel(home,x[i]); 00241 rel(home, op, b, channel(home,x[x.size()-1])); 00242 } 00243 }; 00244 00246 class NaryShared : public Test { 00247 protected: 00249 Gecode::BoolOpType op; 00250 public: 00252 NaryShared(Gecode::BoolOpType op0, int n) 00253 : Test("Bool::Nary::Shared::"+str(op0)+"::"+str(n),n,0,1), 00254 op(op0) {} 00256 virtual bool solution(const Assignment& x) const { 00257 int b = check(x[0],op,x[1]); 00258 for (int i=2; i<x.size(); i++) 00259 b = check(b,op,x[i]); 00260 return b == x[x.size()-1]; 00261 } 00263 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00264 using namespace Gecode; 00265 BoolVarArgs b(x.size()); 00266 for (int i=x.size(); i--; ) 00267 b[i]=channel(home,x[i]); 00268 rel(home, op, b, b[x.size()-1]); 00269 } 00270 }; 00271 00273 class NaryConst : public Test { 00274 protected: 00276 Gecode::BoolOpType op; 00278 int c; 00279 public: 00281 NaryConst(Gecode::BoolOpType op0, int n, int c0) 00282 : Test("Bool::Nary::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1), 00283 op(op0), c(c0) {} 00285 virtual bool solution(const Assignment& x) const { 00286 int b = check(x[0],op,x[1]); 00287 for (int i=2; i<x.size(); i++) 00288 b = check(b,op,x[i]); 00289 return b == c; 00290 } 00292 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00293 using namespace Gecode; 00294 BoolVarArgs b(x.size()); 00295 for (int i=x.size(); i--; ) 00296 b[i]=channel(home,x[i]); 00297 rel(home, op, b, c); 00298 } 00299 }; 00300 00301 00303 class ClauseXYZ : public Test { 00304 protected: 00306 Gecode::BoolOpType op; 00307 public: 00309 ClauseXYZ(Gecode::BoolOpType op0, int n) 00310 : Test("Bool::Clause::XYZ::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {} 00312 virtual bool solution(const Assignment& x) const { 00313 int n = (x.size()-1) / 2; 00314 int b; 00315 if (n == 1) { 00316 b = check(x[0],op,!x[1]); 00317 } else { 00318 b = check(x[0],op,!x[n]); 00319 for (int i=1; i<n; i++) 00320 b = check(b,op,check(x[i],op,!x[n+i])); 00321 } 00322 return b == x[x.size()-1]; 00323 } 00325 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00326 using namespace Gecode; 00327 int n = (x.size()-1) / 2; 00328 BoolVarArgs a(n), b(n); 00329 for (int i=n; i--; ) { 00330 a[i]=channel(home,x[i]); 00331 b[i]=channel(home,x[i+n]); 00332 } 00333 clause(home, op, a, b, channel(home,x[x.size()-1])); 00334 } 00335 }; 00336 00338 class ClauseXXYYX : public Test { 00339 protected: 00341 Gecode::BoolOpType op; 00342 public: 00344 ClauseXXYYX(Gecode::BoolOpType op0, int n) 00345 : Test("Bool::Clause::XXYYX::"+str(op0)+"::"+str(n),n,0,1), 00346 op(op0) {} 00348 virtual bool solution(const Assignment& x) const { 00349 int n = x.size() / 2; 00350 int b; 00351 if (n == 1) { 00352 b = check(x[0],op,!x[1]); 00353 } else { 00354 b = check(x[0],op,!x[n]); 00355 for (int i=1; i<n; i++) 00356 b = check(b,op,check(x[i],op,!x[n+i])); 00357 } 00358 return b == x[0]; 00359 } 00361 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00362 using namespace Gecode; 00363 int n = x.size() / 2; 00364 BoolVarArgs a(2*n), b(2*n); 00365 for (int i=n; i--; ) { 00366 a[i]=a[i+n]=channel(home,x[i]); 00367 b[i]=b[i+n]=channel(home,x[i+n]); 00368 } 00369 clause(home, op, a, b, a[0]); 00370 } 00371 }; 00372 00374 class ClauseXXY : public Test { 00375 protected: 00377 Gecode::BoolOpType op; 00378 public: 00380 ClauseXXY(Gecode::BoolOpType op0, int n) 00381 : Test("Bool::Clause::XXY::"+str(op0)+"::"+str(n),n,0,1), 00382 op(op0) {} 00384 virtual bool solution(const Assignment& x) const { 00385 return (x[0] == 1) == (op == Gecode::BOT_OR); 00386 } 00388 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00389 using namespace Gecode; 00390 int n = x.size() / 2; 00391 BoolVarArgs a(2*n), b(2*n); 00392 for (int i=n; i--; ) { 00393 a[i]=b[i+n]=channel(home,x[i]); 00394 b[i]=a[i+n]=channel(home,x[i+n]); 00395 } 00396 clause(home, op, a, b, a[0]); 00397 } 00398 }; 00399 00401 class ClauseConst : public Test { 00402 protected: 00404 Gecode::BoolOpType op; 00406 int c; 00407 public: 00409 ClauseConst(Gecode::BoolOpType op0, int n, int c0) 00410 : Test("Bool::Clause::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1), 00411 op(op0), c(c0) {} 00413 virtual bool solution(const Assignment& x) const { 00414 int n = x.size() / 2; 00415 int b; 00416 if (n == 1) { 00417 b = check(x[0],op,!x[1]); 00418 } else { 00419 b = check(x[0],op,!x[n]); 00420 for (int i=1; i<n; i++) 00421 b = check(b,op,check(x[i],op,!x[n+i])); 00422 } 00423 return b == c; 00424 } 00426 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00427 using namespace Gecode; 00428 int n = x.size() / 2; 00429 BoolVarArgs a(n), b(n); 00430 for (int i=n; i--; ) { 00431 a[i]=channel(home,x[i]); 00432 b[i]=channel(home,x[i+n]); 00433 } 00434 clause(home, op, a, b, c); 00435 } 00436 }; 00437 00439 class Create { 00440 public: 00442 Create(void) { 00443 using namespace Gecode; 00444 for (BoolOpTypes bots; bots(); ++bots) { 00445 (void) new BinXYZ(bots.bot()); 00446 (void) new BinXXY(bots.bot()); 00447 (void) new BinXYX(bots.bot()); 00448 (void) new BinXYY(bots.bot()); 00449 (void) new BinXXX(bots.bot()); 00450 (void) new BinConstXY(bots.bot(),0); 00451 (void) new BinConstXY(bots.bot(),1); 00452 (void) new BinConstXX(bots.bot(),0); 00453 (void) new BinConstXX(bots.bot(),1); 00454 (void) new Nary(bots.bot(),2); 00455 (void) new Nary(bots.bot(),6); 00456 (void) new Nary(bots.bot(),10); 00457 (void) new NaryShared(bots.bot(),2); 00458 (void) new NaryShared(bots.bot(),6); 00459 (void) new NaryShared(bots.bot(),10); 00460 (void) new NaryConst(bots.bot(),2,0); 00461 (void) new NaryConst(bots.bot(),6,0); 00462 (void) new NaryConst(bots.bot(),10,0); 00463 (void) new NaryConst(bots.bot(),2,1); 00464 (void) new NaryConst(bots.bot(),6,1); 00465 (void) new NaryConst(bots.bot(),10,1); 00466 if ((bots.bot() == BOT_AND) || (bots.bot() == BOT_OR)) { 00467 (void) new ClauseXYZ(bots.bot(),2); 00468 (void) new ClauseXYZ(bots.bot(),6); 00469 (void) new ClauseXYZ(bots.bot(),10); 00470 (void) new ClauseXXYYX(bots.bot(),2); 00471 (void) new ClauseXXYYX(bots.bot(),6); 00472 (void) new ClauseXXYYX(bots.bot(),10); 00473 (void) new ClauseXXY(bots.bot(),2); 00474 (void) new ClauseXXY(bots.bot(),6); 00475 (void) new ClauseXXY(bots.bot(),10); 00476 (void) new ClauseConst(bots.bot(),2,0); 00477 (void) new ClauseConst(bots.bot(),6,0); 00478 (void) new ClauseConst(bots.bot(),10,0); 00479 (void) new ClauseConst(bots.bot(),2,1); 00480 (void) new ClauseConst(bots.bot(),6,1); 00481 (void) new ClauseConst(bots.bot(),10,1); 00482 } 00483 } 00484 } 00485 }; 00486 00487 Create c; 00489 00490 } 00491 }} 00492 00493 // STATISTICS: test-int 00494