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