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 }
00078 GECODE_NEVER;
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 }
00135 GECODE_NEVER;
00136 return false;
00137 }
00139 void post(Space& home, SetVarArray& x, IntVarArray&) {
00140 SetVar a,b,c;
00141 switch (share) {
00142 case 0: a=x[0]; b=x[1]; c=x[2]; break;
00143 case 1: a=x[0]; b=x[0]; c=x[0]; break;
00144 case 2: a=x[0]; b=x[0]; c=x[1]; break;
00145 case 3: a=x[0]; b=x[1]; c=x[0]; break;
00146 case 4: a=x[0]; b=x[1]; c=x[1]; break;
00147 }
00148 Gecode::rel(home, a, sot, b, srt, c);
00149 }
00150 };
00151
00153 class Create {
00154 public:
00156 Create(void) {
00157 using namespace Gecode;
00158 for (SetRelTypes srts; srts(); ++srts) {
00159 for (SetOpTypes sots; sots(); ++sots) {
00160 for (int i=0; i<=4; i++) {
00161 (void) new Rel(sots.sot(),srts.srt(),i);
00162 }
00163 }
00164 }
00165 }
00166 };
00167
00168 Create c;
00169
00171 class RelN : public SetTest {
00172 private:
00173 Gecode::SetOpType sot;
00174 int n;
00175 int shared;
00176 bool withConst;
00177 IntSet is;
00178 public:
00180 RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
00181 : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
00182 "::C"+str(withConst0 ? 1 : 0),
00183 shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
00184 , sot(sot0), n(n0), shared(shared0), withConst(withConst0)
00185 , is(0,1) {
00186 }
00188 bool solution(const SetAssignment& x) const {
00189 int realN = shared == 0 ? n : 3;
00190
00191 CountableSetRanges* isrs = new CountableSetRanges[realN];
00192
00193 switch (shared) {
00194 case 0:
00195 for (int i=realN; i--; )
00196 isrs[i].init(x.lub, x[i]);
00197 break;
00198 case 1:
00199 isrs[0].init(x.lub, x[0]);
00200 isrs[1].init(x.lub, x[0]);
00201 isrs[2].init(x.lub, x[1]);
00202 break;
00203 case 2:
00204 isrs[0].init(x.lub, x[0]);
00205 isrs[1].init(x.lub, x[1]);
00206 isrs[2].init(x.lub, x[2]);
00207 break;
00208 case 3:
00209 isrs[0].init(x.lub, x[0]);
00210 isrs[1].init(x.lub, x[1]);
00211 isrs[2].init(x.lub, x[0]);
00212 break;
00213 default:
00214 GECODE_NEVER;
00215 }
00216
00217 int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
00218 CountableSetRanges xnr(x.lub, x[result]);
00219
00220 switch (sot) {
00221 case SOT_DUNION:
00222 {
00223 if (shared == 1 && (isrs[0]() || isrs[1]())) {
00224 delete[] isrs; return false;
00225 }
00226 if (shared == 3 && (isrs[0]() || isrs[2]())) {
00227 delete[] isrs; return false;
00228 }
00229 unsigned int cardSum = 0;
00230 if (shared == 1 || shared == 3) {
00231 CountableSetRanges x1r(x.lub, x[1]);
00232 cardSum = Iter::Ranges::size(x1r);
00233 } else {
00234 for (int i=0; i<realN; i++) {
00235 CountableSetRanges xir(x.lub, x[i]);
00236 cardSum += Iter::Ranges::size(xir);
00237 }
00238 }
00239 if (withConst)
00240 cardSum += 2;
00241 CountableSetRanges xnr2(x.lub, x[result]);
00242 if (cardSum != Iter::Ranges::size(xnr2)) {
00243 delete[] isrs; return false;
00244 }
00245 }
00246
00247 case SOT_UNION:
00248 {
00249 bool eq;
00250 if (withConst) {
00251 Region r;
00252 Iter::Ranges::NaryUnion u(r, isrs, realN);
00253 IntSetRanges isr(is);
00254 Iter::Ranges::Union<IntSetRanges,
00255 Iter::Ranges::NaryUnion> uu(isr, u);
00256 eq = Iter::Ranges::equal(uu, xnr);
00257 } else {
00258 Region r;
00259 Iter::Ranges::NaryUnion u(r, isrs, realN);
00260 eq = Iter::Ranges::equal(u, xnr);
00261 }
00262 delete [] isrs;
00263 return eq;
00264 }
00265 case SOT_INTER:
00266 {
00267 if (withConst) {
00268 bool eq;
00269 {
00270 Region r;
00271 Iter::Ranges::NaryInter u(r, isrs, realN);
00272 IntSetRanges isr(is);
00273 Iter::Ranges::Inter<IntSetRanges,
00274 Iter::Ranges::NaryInter> uu(isr, u);
00275 eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
00276 Iter::Ranges::equal(uu, xnr));
00277 delete [] isrs;
00278 }
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 bool eq;
00288 {
00289 Region r;
00290 Iter::Ranges::NaryInter u(r,isrs, realN);
00291 eq = Iter::Ranges::equal(u, xnr);
00292 }
00293 delete [] isrs;
00294 return eq;
00295 }
00296 }
00297 }
00298 default:
00299 GECODE_NEVER;
00300 }
00301 GECODE_NEVER;
00302 return false;
00303 }
00305 void post(Space& home, SetVarArray& x, IntVarArray&) {
00306 int size = shared == 0 ? x.size()-1 : 3;
00307 SetVarArgs xs(size);
00308 SetVar xn;
00309 switch (shared) {
00310 case 0:
00311 for (int i=x.size()-1; i--;)
00312 xs[i]=x[i];
00313 xn = x[x.size()-1];
00314 break;
00315 case 1:
00316 xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
00317 break;
00318 case 2:
00319 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
00320 break;
00321 case 3:
00322 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
00323 break;
00324 default:
00325 GECODE_NEVER;
00326 break;
00327 }
00328 if (!withConst)
00329 Gecode::rel(home, sot, xs, xn);
00330 else
00331 Gecode::rel(home, sot, xs, is, xn);
00332 }
00333 };
00334
00336 class CreateN {
00337 public:
00339 CreateN(void) {
00340 for (int wc=0; wc<=1; wc++) {
00341 for (int i=0; i<=3; i++) {
00342 (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
00343 (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
00344 (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
00345
00346 if (i>0) {
00347 (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
00348 (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
00349 (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
00350 }
00351 }
00352 }
00353 }
00354 };
00355
00356 CreateN cn;
00357
00359 class RelIntN : public SetTest {
00360 private:
00361 Gecode::SetOpType sot;
00362 int n;
00363 bool withConst;
00364 IntSet is;
00365 public:
00367 RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
00368 : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
00369 "::C"+str(withConst0 ? 1 : 0),
00370 1,ds_12,false,n0)
00371 , sot(sot0), n(n0), withConst(withConst0)
00372 , is(0,1) {
00373 }
00375 bool solution(const SetAssignment& x) const {
00376 int* isrs = new int[n];
00377 for (int i=0; i<n; i++)
00378 isrs[i] = x.ints()[i];
00379
00380 IntSet iss(isrs,n);
00381 CountableSetRanges xnr(x.lub, x[0]);
00382
00383 switch (sot) {
00384 case SOT_DUNION:
00385 {
00386 IntSetRanges issr(iss);
00387 unsigned int cardSum = Iter::Ranges::size(issr);
00388 if (cardSum != static_cast<unsigned int>(n)) {
00389 delete[] isrs;
00390 return false;
00391 }
00392 if (withConst) {
00393 IntSetRanges isr(is);
00394 cardSum += Iter::Ranges::size(isr);
00395 }
00396 CountableSetRanges xnr2(x.lub, x[0]);
00397 if (cardSum != Iter::Ranges::size(xnr2)) {
00398 delete[] isrs;
00399 return false;
00400 }
00401 }
00402
00403 case SOT_UNION:
00404 {
00405 if (withConst) {
00406 IntSetRanges issr(iss);
00407 IntSetRanges isr(is);
00408 Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
00409 delete[] isrs;
00410 return Iter::Ranges::equal(uu, xnr);
00411 } else {
00412 IntSetRanges issr(iss);
00413 delete[] isrs;
00414 return Iter::Ranges::equal(issr, xnr);
00415 }
00416 }
00417 case SOT_INTER:
00418 {
00419 bool allEqual = true;
00420 for (int i=1; i<n; i++) {
00421 if (isrs[i] != isrs[0]) {
00422 allEqual = false;
00423 break;
00424 }
00425 }
00426 if (withConst) {
00427 if (allEqual) {
00428 if (n == 0) {
00429 IntSetRanges isr(is);
00430 delete[] isrs;
00431 return Iter::Ranges::equal(isr, xnr);
00432 } else {
00433 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00434 IntSetRanges isr(is);
00435 Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
00436 uu(isr, s);
00437 delete[] isrs;
00438 return Iter::Ranges::equal(uu, xnr);
00439 }
00440 } else {
00441 delete[] isrs;
00442 return Iter::Ranges::size(xnr) == 0;
00443 }
00444 } else {
00445 if (allEqual) {
00446 if (n == 0) {
00447 delete[] isrs;
00448 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00449 } else {
00450 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00451 delete[] isrs;
00452 return Iter::Ranges::equal(s, xnr);
00453 }
00454 } else {
00455 delete[] isrs;
00456 return Iter::Ranges::size(xnr) == 0;
00457 }
00458 }
00459 }
00460 default:
00461 GECODE_NEVER;
00462 }
00463 GECODE_NEVER;
00464 return false;
00465 }
00467 void post(Space& home, SetVarArray& x, IntVarArray& y) {
00468 if (!withConst)
00469 Gecode::rel(home, sot, y, x[0]);
00470 else
00471 Gecode::rel(home, sot, y, is, x[0]);
00472 }
00473 };
00474
00476 class CreateIntN {
00477 public:
00479 CreateIntN(void) {
00480 for (int wc=0; wc<=1; wc++) {
00481 for (int i=0; i<=3; i++) {
00482 (void) new RelIntN(Gecode::SOT_UNION, i, wc);
00483 (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
00484 (void) new RelIntN(Gecode::SOT_INTER, i, wc);
00485 }
00486 }
00487 }
00488 };
00489
00490 CreateIntN intcn;
00491
00493
00494 }}}
00495
00496