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