00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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=0, b=0, c=0;
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) {
00190 }
00192 bool solution(const SetAssignment& x) const {
00193 int realN = shared == 0 ? n : 3;
00194
00195 CountableSetRanges* isrs = new CountableSetRanges[realN];
00196
00197 switch (shared) {
00198 case 0:
00199 for (int i=realN; i--; )
00200 isrs[i].init(x.lub, x[i]);
00201 break;
00202 case 1:
00203 isrs[0].init(x.lub, x[0]);
00204 isrs[1].init(x.lub, x[0]);
00205 isrs[2].init(x.lub, x[1]);
00206 break;
00207 case 2:
00208 isrs[0].init(x.lub, x[0]);
00209 isrs[1].init(x.lub, x[1]);
00210 isrs[2].init(x.lub, x[2]);
00211 break;
00212 case 3:
00213 isrs[0].init(x.lub, x[0]);
00214 isrs[1].init(x.lub, x[1]);
00215 isrs[2].init(x.lub, x[0]);
00216 break;
00217 default:
00218 GECODE_NEVER;
00219 }
00220
00221 int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
00222 CountableSetRanges xnr(x.lub, x[result]);
00223
00224 switch (sot) {
00225 case SOT_DUNION:
00226 {
00227 if (shared == 1 && (isrs[0]() || isrs[1]())) {
00228 delete[] isrs; return false;
00229 }
00230 if (shared == 3 && (isrs[0]() || isrs[2]())) {
00231 delete[] isrs; return false;
00232 }
00233 unsigned int cardSum = 0;
00234 if (shared == 1 || shared == 3) {
00235 CountableSetRanges x1r(x.lub, x[1]);
00236 cardSum = Iter::Ranges::size(x1r);
00237 } else {
00238 for (int i=0; i<realN; i++) {
00239 CountableSetRanges xir(x.lub, x[i]);
00240 cardSum += Iter::Ranges::size(xir);
00241 }
00242 }
00243 if (withConst)
00244 cardSum += 2;
00245 CountableSetRanges xnr2(x.lub, x[result]);
00246 if (cardSum != Iter::Ranges::size(xnr2)) {
00247 delete[] isrs; return false;
00248 }
00249 }
00250
00251 case SOT_UNION:
00252 {
00253 FakeSpace* fs = new FakeSpace;
00254 bool eq;
00255 if (withConst) {
00256 Region r(*fs);
00257 Iter::Ranges::NaryUnion u(r, isrs, realN);
00258 IntSetRanges isr(is);
00259 Iter::Ranges::Union<IntSetRanges,
00260 Iter::Ranges::NaryUnion> uu(isr, u);
00261 eq = Iter::Ranges::equal(uu, xnr);
00262 } else {
00263 Region r(*fs);
00264 Iter::Ranges::NaryUnion u(r, isrs, realN);
00265 eq = Iter::Ranges::equal(u, xnr);
00266 }
00267 delete [] isrs;
00268 delete fs;
00269 return eq;
00270 }
00271 case SOT_INTER:
00272 {
00273 if (withConst) {
00274 FakeSpace* fs = new FakeSpace;
00275 bool eq;
00276 {
00277 Region r(*fs);
00278 Iter::Ranges::NaryInter u(r, isrs, realN);
00279 IntSetRanges isr(is);
00280 Iter::Ranges::Inter<IntSetRanges,
00281 Iter::Ranges::NaryInter> uu(isr, u);
00282 eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
00283 Iter::Ranges::equal(uu, xnr));
00284 delete [] isrs;
00285 }
00286 delete fs;
00287 return eq;
00288 } else {
00289 if (realN == 0) {
00290 bool ret =
00291 Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00292 delete [] isrs;
00293 return ret;
00294 } else {
00295 FakeSpace* fs = new FakeSpace;
00296 bool eq;
00297 {
00298 Region r(*fs);
00299 Iter::Ranges::NaryInter u(r,isrs, realN);
00300 eq = Iter::Ranges::equal(u, xnr);
00301 }
00302 delete [] isrs;
00303 delete fs;
00304 return eq;
00305 }
00306 }
00307 }
00308 default:
00309 GECODE_NEVER;
00310 }
00311 GECODE_NEVER;
00312 return false;
00313 }
00315 void post(Space& home, SetVarArray& x, IntVarArray&) {
00316 int size = shared == 0 ? x.size()-1 : 3;
00317 SetVarArgs xs(size);
00318 SetVar xn;
00319 switch (shared) {
00320 case 0:
00321 for (int i=x.size()-1; i--;)
00322 xs[i]=x[i];
00323 xn = x[x.size()-1];
00324 break;
00325 case 1:
00326 xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
00327 break;
00328 case 2:
00329 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
00330 break;
00331 case 3:
00332 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
00333 break;
00334 default:
00335 GECODE_NEVER;
00336 break;
00337 }
00338 if (!withConst)
00339 Gecode::rel(home, sot, xs, xn);
00340 else
00341 Gecode::rel(home, sot, xs, is, xn);
00342 }
00343 };
00344
00346 class CreateN {
00347 public:
00349 CreateN(void) {
00350 for (int wc=0; wc<=1; wc++) {
00351 for (int i=0; i<=3; i++) {
00352 (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
00353 (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
00354 (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
00355
00356 if (i>0) {
00357 (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
00358 (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
00359 (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
00360 }
00361 }
00362 }
00363 }
00364 };
00365
00366 CreateN cn;
00367
00369 class RelIntN : public SetTest {
00370 private:
00371 Gecode::SetOpType sot;
00372 int n;
00373 bool withConst;
00374 IntSet is;
00375 public:
00377 RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
00378 : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
00379 "::C"+str(withConst0 ? 1 : 0),
00380 1,ds_12,false,n0)
00381 , sot(sot0), n(n0), withConst(withConst0)
00382 , is(0,1) {
00383 }
00385 bool solution(const SetAssignment& x) const {
00386 int* isrs = new int[n];
00387 for (int i=0; i<n; i++)
00388 isrs[i] = x.ints()[i];
00389
00390 IntSet iss(isrs,n);
00391 CountableSetRanges xnr(x.lub, x[0]);
00392
00393 switch (sot) {
00394 case SOT_DUNION:
00395 {
00396 IntSetRanges issr(iss);
00397 unsigned int cardSum = Iter::Ranges::size(issr);
00398 if (cardSum != static_cast<unsigned int>(n)) {
00399 delete[] isrs;
00400 return false;
00401 }
00402 if (withConst) {
00403 IntSetRanges isr(is);
00404 cardSum += Iter::Ranges::size(isr);
00405 }
00406 CountableSetRanges xnr2(x.lub, x[0]);
00407 if (cardSum != Iter::Ranges::size(xnr2)) {
00408 delete[] isrs;
00409 return false;
00410 }
00411 }
00412
00413 case SOT_UNION:
00414 {
00415 if (withConst) {
00416 IntSetRanges issr(iss);
00417 IntSetRanges isr(is);
00418 Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
00419 delete[] isrs;
00420 return Iter::Ranges::equal(uu, xnr);
00421 } else {
00422 IntSetRanges issr(iss);
00423 delete[] isrs;
00424 return Iter::Ranges::equal(issr, xnr);
00425 }
00426 }
00427 case SOT_INTER:
00428 {
00429 bool allEqual = true;
00430 for (int i=1; i<n; i++) {
00431 if (isrs[i] != isrs[0]) {
00432 allEqual = false;
00433 break;
00434 }
00435 }
00436 if (withConst) {
00437 if (allEqual) {
00438 if (n == 0) {
00439 IntSetRanges isr(is);
00440 delete[] isrs;
00441 return Iter::Ranges::equal(isr, xnr);
00442 } else {
00443 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00444 IntSetRanges isr(is);
00445 Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
00446 uu(isr, s);
00447 delete[] isrs;
00448 return Iter::Ranges::equal(uu, xnr);
00449 }
00450 } else {
00451 delete[] isrs;
00452 return Iter::Ranges::size(xnr) == 0;
00453 }
00454 } else {
00455 if (allEqual) {
00456 if (n == 0) {
00457 delete[] isrs;
00458 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00459 } else {
00460 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00461 delete[] isrs;
00462 return Iter::Ranges::equal(s, xnr);
00463 }
00464 } else {
00465 delete[] isrs;
00466 return Iter::Ranges::size(xnr) == 0;
00467 }
00468 }
00469 }
00470 default:
00471 GECODE_NEVER;
00472 }
00473 GECODE_NEVER;
00474 return false;
00475 }
00477 void post(Space& home, SetVarArray& x, IntVarArray& y) {
00478 if (!withConst)
00479 Gecode::rel(home, sot, y, x[0]);
00480 else
00481 Gecode::rel(home, sot, y, is, x[0]);
00482 }
00483 };
00484
00486 class CreateIntN {
00487 public:
00489 CreateIntN(void) {
00490 for (int wc=0; wc<=1; wc++) {
00491 for (int i=0; i<=3; i++) {
00492 (void) new RelIntN(Gecode::SOT_UNION, i, wc);
00493 (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
00494 (void) new RelIntN(Gecode::SOT_INTER, i, wc);
00495 }
00496 }
00497 }
00498 };
00499
00500 CreateIntN intcn;
00501
00503
00504 }}}
00505
00506