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 GECODE_AUTOARRAY(CountableSetRanges, isrs, 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 return false;
00228 if (shared == 3 && (isrs[0]() || isrs[2]()))
00229 return false;
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 return false;
00245 }
00246
00247 case SOT_UNION:
00248 {
00249 if (withConst) {
00250 Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN);
00251 IntSetRanges isr(is);
00252 Iter::Ranges::Union<IntSetRanges,
00253 Iter::Ranges::NaryUnion<CountableSetRanges> > uu(isr, u);
00254 return Iter::Ranges::equal(uu, xnr);
00255 } else {
00256 Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN);
00257 return Iter::Ranges::equal(u, xnr);
00258 }
00259 }
00260 case SOT_INTER:
00261 {
00262 if (withConst) {
00263 Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN);
00264 IntSetRanges isr(is);
00265 Iter::Ranges::Inter<IntSetRanges,
00266 Iter::Ranges::NaryInter<CountableSetRanges> > uu(isr, u);
00267 if (realN == 0)
00268 return Iter::Ranges::equal(isr, xnr);
00269 else
00270 return Iter::Ranges::equal(uu, xnr);
00271 } else {
00272 if (realN == 0) {
00273 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00274 } else {
00275 Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN);
00276 return Iter::Ranges::equal(u, xnr);
00277 }
00278 }
00279 }
00280 default:
00281 GECODE_NEVER;
00282 }
00283 GECODE_NEVER;
00284 return false;
00285 }
00287 void post(Space* home, SetVarArray& x, IntVarArray&) {
00288 int size = shared == 0 ? x.size()-1 : 3;
00289 SetVarArgs xs(size);
00290 SetVar xn;
00291 switch (shared) {
00292 case 0:
00293 for (int i=x.size()-1; i--;)
00294 xs[i]=x[i];
00295 xn = x[x.size()-1];
00296 break;
00297 case 1:
00298 xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
00299 break;
00300 case 2:
00301 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
00302 break;
00303 case 3:
00304 xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
00305 break;
00306 default:
00307 GECODE_NEVER;
00308 break;
00309 }
00310 if (!withConst)
00311 Gecode::rel(home, sot, xs, xn);
00312 else
00313 Gecode::rel(home, sot, xs, is, xn);
00314 }
00315 };
00316
00318 class CreateN {
00319 public:
00321 CreateN(void) {
00322 for (int wc=0; wc<=1; wc++) {
00323 for (int i=0; i<=3; i++) {
00324 (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
00325 (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
00326 (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
00327
00328 if (i>0) {
00329 (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
00330 (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
00331 (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
00332 }
00333 }
00334 }
00335 }
00336 };
00337
00338 CreateN cn;
00339
00341 class RelIntN : public SetTest {
00342 private:
00343 Gecode::SetOpType sot;
00344 int n;
00345 bool withConst;
00346 IntSet is;
00347 public:
00349 RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
00350 : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
00351 "::C"+str(withConst0 ? 1 : 0),
00352 1,ds_12,false,n0)
00353 , sot(sot0), n(n0), withConst(withConst0)
00354 , is(0,1) {}
00356 bool solution(const SetAssignment& x) const {
00357 GECODE_AUTOARRAY(int, isrs, n);
00358 for (int i=0; i<n; i++)
00359 isrs[i] = x.ints()[i];
00360
00361 IntSet iss(isrs,n);
00362 CountableSetRanges xnr(x.lub, x[0]);
00363
00364 switch (sot) {
00365 case SOT_DUNION:
00366 {
00367 IntSetRanges issr(iss);
00368 unsigned int cardSum = Iter::Ranges::size(issr);
00369 if (cardSum != static_cast<unsigned int>(n))
00370 return false;
00371 if (withConst) {
00372 IntSetRanges isr(is);
00373 cardSum += Iter::Ranges::size(isr);
00374 }
00375 CountableSetRanges xnr2(x.lub, x[0]);
00376 if (cardSum != Iter::Ranges::size(xnr2))
00377 return false;
00378 }
00379
00380 case SOT_UNION:
00381 {
00382 if (withConst) {
00383 IntSetRanges issr(iss);
00384 IntSetRanges isr(is);
00385 Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
00386 return Iter::Ranges::equal(uu, xnr);
00387 } else {
00388 IntSetRanges issr(iss);
00389 return Iter::Ranges::equal(issr, xnr);
00390 }
00391 }
00392 case SOT_INTER:
00393 {
00394 bool allEqual = true;
00395 for (int i=1; i<n; i++) {
00396 if (isrs[i] != isrs[0]) {
00397 allEqual = false;
00398 break;
00399 }
00400 }
00401 if (withConst) {
00402 if (allEqual) {
00403 if (n == 0) {
00404 IntSetRanges isr(is);
00405 return Iter::Ranges::equal(isr, xnr);
00406 } else {
00407 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00408 IntSetRanges isr(is);
00409 Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
00410 uu(isr, s);
00411 return Iter::Ranges::equal(uu, xnr);
00412 }
00413 } else {
00414 return Iter::Ranges::size(xnr) == 0;
00415 }
00416 } else {
00417 if (allEqual) {
00418 if (n == 0) {
00419 return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00420 } else {
00421 Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00422 return Iter::Ranges::equal(s, xnr);
00423 }
00424 } else {
00425 return Iter::Ranges::size(xnr) == 0;
00426 }
00427 }
00428 }
00429 default:
00430 GECODE_NEVER;
00431 }
00432 GECODE_NEVER;
00433 return false;
00434 }
00436 void post(Space* home, SetVarArray& x, IntVarArray& y) {
00437 if (!withConst)
00438 Gecode::rel(home, sot, y, x[0]);
00439 else
00440 Gecode::rel(home, sot, y, is, x[0]);
00441 }
00442 };
00443
00445 class CreateIntN {
00446 public:
00448 CreateIntN(void) {
00449 for (int wc=0; wc<=1; wc++) {
00450 for (int i=0; i<=3; i++) {
00451 (void) new RelIntN(Gecode::SOT_UNION, i, wc);
00452 (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
00453 (void) new RelIntN(Gecode::SOT_INTER, i, wc);
00454 }
00455 }
00456 }
00457 };
00458
00459 CreateIntN intcn;
00460
00462
00463 }}}
00464
00465