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,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
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
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