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