rel-op.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 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/set.hh" 00039 00040 using namespace Gecode; 00041 00042 namespace Test { namespace Set { 00043 00045 namespace RelOp { 00046 00052 00053 static IntSet ds_22(-2,2); 00054 static IntSet ds_12(-1,2); 00055 00057 class Rel : public SetTest { 00058 private: 00059 Gecode::SetOpType sot; 00060 Gecode::SetRelType srt; 00061 int share; 00062 00063 template<class I, class J> 00064 bool 00065 sol(I& i, J& j) const { 00066 Iter::Ranges::IsRangeIter<I>(); 00067 Iter::Ranges::IsRangeIter<J>(); 00068 switch (srt) { 00069 case SRT_EQ: return Iter::Ranges::equal(i,j); 00070 case SRT_NQ: return !Iter::Ranges::equal(i,j); 00071 case SRT_SUB: return Iter::Ranges::subset(i,j); 00072 case SRT_SUP: return Iter::Ranges::subset(j,i); 00073 case SRT_DISJ: 00074 { 00075 Gecode::Iter::Ranges::Inter<I,J> inter(i,j); 00076 return !inter(); 00077 } 00078 case SRT_CMPL: 00079 { 00080 Gecode::Set::RangesCompl<J> jc(j); 00081 return Iter::Ranges::equal(i,jc); 00082 } 00083 } 00084 GECODE_NEVER; 00085 return false; 00086 } 00087 00088 public: 00090 Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0) 00091 : SetTest("RelOp::"+str(sot0)+"::"+str(srt0)+"::S"+str(share0), 00092 share0 == 0 ? 3 : 2,ds_22,false) 00093 , sot(sot0), srt(srt0), share(share0) {} 00095 bool solution(const SetAssignment& x) const { 00096 int a,b,c; 00097 switch (share) { 00098 case 0: a=x[0]; b=x[1]; c=x[2]; break; 00099 case 1: a=x[0]; b=x[0]; c=x[0]; break; 00100 case 2: a=x[0]; b=x[0]; c=x[1]; break; 00101 case 3: a=x[0]; b=x[1]; c=x[0]; break; 00102 case 4: a=x[0]; b=x[1]; c=x[1]; break; 00103 } 00104 CountableSetRanges xr0(x.lub, a); 00105 CountableSetRanges xr1(x.lub, b); 00106 CountableSetRanges xr2(x.lub, c); 00107 switch (sot) { 00108 case SOT_UNION: 00109 { 00110 Iter::Ranges::Union<CountableSetRanges, CountableSetRanges> 00111 u(xr0,xr1); 00112 return sol(u,xr2); 00113 } 00114 break; 00115 case SOT_DUNION: 00116 { 00117 Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges> 00118 inter(xr0,xr1); 00119 if (inter()) 00120 return false; 00121 Iter::Ranges::Union<CountableSetRanges, CountableSetRanges> 00122 u(xr0,xr1); 00123 return sol(u,xr2); 00124 } 00125 break; 00126 case SOT_INTER: 00127 { 00128 Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges> 00129 u(xr0,xr1); 00130 return sol(u,xr2); 00131 } 00132 break; 00133 case SOT_MINUS: 00134 { 00135 Iter::Ranges::Diff<CountableSetRanges, CountableSetRanges> 00136 u(xr0,xr1); 00137 return sol(u,xr2); 00138 } 00139 break; 00140 } 00141 GECODE_NEVER; 00142 return false; 00143 } 00145 void post(Space& home, SetVarArray& x, IntVarArray&) { 00146 SetVar a,b,c; 00147 switch (share) { 00148 case 0: a=x[0]; b=x[1]; c=x[2]; break; 00149 case 1: a=x[0]; b=x[0]; c=x[0]; break; 00150 case 2: a=x[0]; b=x[0]; c=x[1]; break; 00151 case 3: a=x[0]; b=x[1]; c=x[0]; break; 00152 case 4: a=x[0]; b=x[1]; c=x[1]; break; 00153 } 00154 Gecode::rel(home, a, sot, b, srt, c); 00155 } 00156 }; 00157 00159 class Create { 00160 public: 00162 Create(void) { 00163 using namespace Gecode; 00164 for (SetRelTypes srts; srts(); ++srts) { 00165 for (SetOpTypes sots; sots(); ++sots) { 00166 for (int i=0; i<=4; i++) { 00167 (void) new Rel(sots.sot(),srts.srt(),i); 00168 } 00169 } 00170 } 00171 } 00172 }; 00173 00174 Create c; 00175 00177 class RelN : public SetTest { 00178 private: 00179 Gecode::SetOpType sot; 00180 int n; 00181 int shared; 00182 bool withConst; 00183 IntSet is; 00184 public: 00186 RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0) 00187 : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+ 00188 "::C"+str(withConst0 ? 1 : 0), 00189 shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false) 00190 , sot(sot0), n(n0), shared(shared0), withConst(withConst0) 00191 , is(0,1) {} 00193 bool solution(const SetAssignment& x) const { 00194 int realN = shared == 0 ? n : 3; 00195 00196 CountableSetRanges* isrs = new CountableSetRanges[realN]; 00197 00198 switch (shared) { 00199 case 0: 00200 for (int i=realN; i--; ) 00201 isrs[i].init(x.lub, x[i]); 00202 break; 00203 case 1: 00204 isrs[0].init(x.lub, x[0]); 00205 isrs[1].init(x.lub, x[0]); 00206 isrs[2].init(x.lub, x[1]); 00207 break; 00208 case 2: 00209 isrs[0].init(x.lub, x[0]); 00210 isrs[1].init(x.lub, x[1]); 00211 isrs[2].init(x.lub, x[2]); 00212 break; 00213 case 3: 00214 isrs[0].init(x.lub, x[0]); 00215 isrs[1].init(x.lub, x[1]); 00216 isrs[2].init(x.lub, x[0]); 00217 break; 00218 default: 00219 GECODE_NEVER; 00220 } 00221 00222 int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0); 00223 CountableSetRanges xnr(x.lub, x[result]); 00224 00225 switch (sot) { 00226 case SOT_DUNION: 00227 { 00228 if (shared == 1 && (isrs[0]() || isrs[1]())) { 00229 delete[] isrs; return false; 00230 } 00231 if (shared == 3 && (isrs[0]() || isrs[2]())) { 00232 delete[] isrs; return false; 00233 } 00234 unsigned int cardSum = 0; 00235 if (shared == 1 || shared == 3) { 00236 CountableSetRanges x1r(x.lub, x[1]); 00237 cardSum = Iter::Ranges::size(x1r); 00238 } else { 00239 for (int i=0; i<realN; i++) { 00240 CountableSetRanges xir(x.lub, x[i]); 00241 cardSum += Iter::Ranges::size(xir); 00242 } 00243 } 00244 if (withConst) 00245 cardSum += 2; 00246 CountableSetRanges xnr2(x.lub, x[result]); 00247 if (cardSum != Iter::Ranges::size(xnr2)) { 00248 delete[] isrs; return false; 00249 } 00250 } 00251 // fall through to union case 00252 case SOT_UNION: 00253 { 00254 if (withConst) { 00255 Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN); 00256 IntSetRanges isr(is); 00257 Iter::Ranges::Union<IntSetRanges, 00258 Iter::Ranges::NaryUnion<CountableSetRanges> > uu(isr, u); 00259 bool eq = Iter::Ranges::equal(uu, xnr); 00260 delete[] isrs; 00261 return eq; 00262 } else { 00263 Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN); 00264 bool eq = Iter::Ranges::equal(u, xnr); 00265 delete[] isrs; 00266 return eq; 00267 } 00268 } 00269 case SOT_INTER: 00270 { 00271 if (withConst) { 00272 Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN); 00273 IntSetRanges isr(is); 00274 Iter::Ranges::Inter<IntSetRanges, 00275 Iter::Ranges::NaryInter<CountableSetRanges> > uu(isr, u); 00276 bool eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) : 00277 Iter::Ranges::equal(uu, xnr)); 00278 delete[] isrs; 00279 return eq; 00280 } else { 00281 if (realN == 0) { 00282 bool ret = 00283 Iter::Ranges::size(xnr) == Gecode::Set::Limits::card; 00284 delete[] isrs; 00285 return ret; 00286 } else { 00287 Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN); 00288 bool eq = Iter::Ranges::equal(u, xnr); 00289 delete[] isrs; 00290 return eq; 00291 } 00292 } 00293 } 00294 default: 00295 GECODE_NEVER; 00296 } 00297 GECODE_NEVER; 00298 return false; 00299 } 00301 void post(Space& home, SetVarArray& x, IntVarArray&) { 00302 int size = shared == 0 ? x.size()-1 : 3; 00303 SetVarArgs xs(size); 00304 SetVar xn; 00305 switch (shared) { 00306 case 0: 00307 for (int i=x.size()-1; i--;) 00308 xs[i]=x[i]; 00309 xn = x[x.size()-1]; 00310 break; 00311 case 1: 00312 xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2]; 00313 break; 00314 case 2: 00315 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2]; 00316 break; 00317 case 3: 00318 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0]; 00319 break; 00320 default: 00321 GECODE_NEVER; 00322 break; 00323 } 00324 if (!withConst) 00325 Gecode::rel(home, sot, xs, xn); 00326 else 00327 Gecode::rel(home, sot, xs, is, xn); 00328 } 00329 }; 00330 00332 class CreateN { 00333 public: 00335 CreateN(void) { 00336 for (int wc=0; wc<=1; wc++) { 00337 for (int i=0; i<=3; i++) { 00338 (void) new RelN(Gecode::SOT_UNION, i, 0, wc); 00339 (void) new RelN(Gecode::SOT_DUNION, i, 0, wc); 00340 (void) new RelN(Gecode::SOT_INTER, i, 0, wc); 00341 00342 if (i>0) { 00343 (void) new RelN(Gecode::SOT_UNION, 0, i, wc); 00344 (void) new RelN(Gecode::SOT_DUNION, 0, i, wc); 00345 (void) new RelN(Gecode::SOT_INTER, 0, i, wc); 00346 } 00347 } 00348 } 00349 } 00350 }; 00351 00352 CreateN cn; 00353 00355 class RelIntN : public SetTest { 00356 private: 00357 Gecode::SetOpType sot; 00358 int n; 00359 bool withConst; 00360 IntSet is; 00361 public: 00363 RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0) 00364 : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+ 00365 "::C"+str(withConst0 ? 1 : 0), 00366 1,ds_12,false,n0) 00367 , sot(sot0), n(n0), withConst(withConst0) 00368 , is(0,1) {} 00370 bool solution(const SetAssignment& x) const { 00371 int* isrs = new int[n]; 00372 for (int i=0; i<n; i++) 00373 isrs[i] = x.ints()[i]; 00374 00375 IntSet iss(isrs,n); 00376 CountableSetRanges xnr(x.lub, x[0]); 00377 00378 switch (sot) { 00379 case SOT_DUNION: 00380 { 00381 IntSetRanges issr(iss); 00382 unsigned int cardSum = Iter::Ranges::size(issr); 00383 if (cardSum != static_cast<unsigned int>(n)) { 00384 delete[] isrs; 00385 return false; 00386 } 00387 if (withConst) { 00388 IntSetRanges isr(is); 00389 cardSum += Iter::Ranges::size(isr); 00390 } 00391 CountableSetRanges xnr2(x.lub, x[0]); 00392 if (cardSum != Iter::Ranges::size(xnr2)) { 00393 delete[] isrs; 00394 return false; 00395 } 00396 } 00397 // fall through to union case 00398 case SOT_UNION: 00399 { 00400 if (withConst) { 00401 IntSetRanges issr(iss); 00402 IntSetRanges isr(is); 00403 Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr); 00404 delete[] isrs; 00405 return Iter::Ranges::equal(uu, xnr); 00406 } else { 00407 IntSetRanges issr(iss); 00408 delete[] isrs; 00409 return Iter::Ranges::equal(issr, xnr); 00410 } 00411 } 00412 case SOT_INTER: 00413 { 00414 bool allEqual = true; 00415 for (int i=1; i<n; i++) { 00416 if (isrs[i] != isrs[0]) { 00417 allEqual = false; 00418 break; 00419 } 00420 } 00421 if (withConst) { 00422 if (allEqual) { 00423 if (n == 0) { 00424 IntSetRanges isr(is); 00425 delete[] isrs; 00426 return Iter::Ranges::equal(isr, xnr); 00427 } else { 00428 Iter::Ranges::Singleton s(isrs[0],isrs[0]); 00429 IntSetRanges isr(is); 00430 Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton> 00431 uu(isr, s); 00432 delete[] isrs; 00433 return Iter::Ranges::equal(uu, xnr); 00434 } 00435 } else { 00436 delete[] isrs; 00437 return Iter::Ranges::size(xnr) == 0; 00438 } 00439 } else { 00440 if (allEqual) { 00441 if (n == 0) { 00442 delete[] isrs; 00443 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card; 00444 } else { 00445 Iter::Ranges::Singleton s(isrs[0],isrs[0]); 00446 delete[] isrs; 00447 return Iter::Ranges::equal(s, xnr); 00448 } 00449 } else { 00450 delete[] isrs; 00451 return Iter::Ranges::size(xnr) == 0; 00452 } 00453 } 00454 } 00455 default: 00456 GECODE_NEVER; 00457 } 00458 GECODE_NEVER; 00459 return false; 00460 } 00462 void post(Space& home, SetVarArray& x, IntVarArray& y) { 00463 if (!withConst) 00464 Gecode::rel(home, sot, y, x[0]); 00465 else 00466 Gecode::rel(home, sot, y, is, x[0]); 00467 } 00468 }; 00469 00471 class CreateIntN { 00472 public: 00474 CreateIntN(void) { 00475 for (int wc=0; wc<=1; wc++) { 00476 for (int i=0; i<=3; i++) { 00477 (void) new RelIntN(Gecode::SOT_UNION, i, wc); 00478 (void) new RelIntN(Gecode::SOT_DUNION, i, wc); 00479 (void) new RelIntN(Gecode::SOT_INTER, i, wc); 00480 } 00481 } 00482 } 00483 }; 00484 00485 CreateIntN intcn; 00486 00488 00489 }}} 00490 00491 // STATISTICS: test-set