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 #include "test/int.hh"
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00044 namespace Test { namespace Set {
00045
00047 namespace Int {
00048
00054
00055 static const int d1r[4][2] = {
00056 {-4,-3},{-1,-1},{1,1},{3,5}
00057 };
00058 static IntSet d1(d1r,4);
00059
00060 static IntSet d2(-1,3);
00061 static IntSet d3(0,3);
00062
00063 static IntSet d4(0,4);
00064
00065 static IntSet ds_33(-3,3);
00066
00068 class Card : public SetTest {
00069 public:
00071 Card(const char* t)
00072 : SetTest(t,1,ds_33,false,1) {}
00074 virtual bool solution(const SetAssignment& x) const {
00075 unsigned int s = 0;
00076 for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width();
00077 if (x.intval() < 0)
00078 return false;
00079 return s==(unsigned int)x.intval();
00080 }
00082 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00083 Gecode::cardinality(home, x[0], y[0]);
00084 }
00085 };
00086 Card _card("Int::Card");
00087
00089 class Min : public SetTest {
00090 public:
00092 Min(const char* t)
00093 : SetTest(t,1,ds_33,true,1) {}
00095 virtual bool solution(const SetAssignment& x) const {
00096 CountableSetRanges xr0(x.lub, x[0]);
00097 return xr0() && xr0.min()==x.intval();
00098 }
00100 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00101 Gecode::min(home, x[0], y[0]);
00102 }
00104 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00105 BoolVar b) {
00106 Gecode::min(home, x[0], y[0], b);
00107 }
00108 };
00109 Min _min("Int::Min");
00110
00112 class NotMin : public SetTest {
00113 public:
00115 NotMin(const char* t)
00116 : SetTest(t,1,ds_33,false,1) {}
00118 virtual bool solution(const SetAssignment& x) const {
00119 CountableSetRanges xr0(x.lub, x[0]);
00120 return !(xr0() && xr0.min()==x.intval());
00121 }
00123 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00124 Gecode::notMin(home, x[0], y[0]);
00125 }
00126 };
00127 NotMin _notmin("Int::NotMin");
00128
00130 class Max : public SetTest {
00131 public:
00133 Max(const char* t)
00134 : SetTest(t,1,ds_33,true,1) {}
00136 virtual bool solution(const SetAssignment& x) const {
00137 CountableSetRanges xr0(x.lub, x[0]);
00138 IntSet x0(xr0);
00139 return x0.ranges() > 0 && x0.max()==x.intval();
00140 }
00142 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00143 Gecode::max(home, x[0], y[0]);
00144 }
00146 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00147 BoolVar b) {
00148 Gecode::max(home, x[0], y[0], b);
00149 }
00150 };
00151 Max _max("Int::Max");
00152
00154 class NotMax : public SetTest {
00155 public:
00157 NotMax(const char* t)
00158 : SetTest(t,1,ds_33,false,1) {}
00160 virtual bool solution(const SetAssignment& x) const {
00161 CountableSetRanges xr0(x.lub, x[0]);
00162 IntSet x0(xr0);
00163 return !(x0.ranges() > 0 && x0.max()==x.intval());
00164 }
00166 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00167 Gecode::notMax(home, x[0], y[0]);
00168 }
00169 };
00170 NotMax _notmax("Int::NotMax");
00171
00173 class Elem : public SetTest {
00174 public:
00176 Elem(const char* t)
00177 : SetTest(t,1,ds_33,true,1) {}
00179 virtual bool solution(const SetAssignment& x) const {
00180 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00181 if (xr.val()==x.intval())
00182 return true;
00183 return false;
00184 }
00186 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00187 Gecode::rel(home, x[0], SRT_SUP, y[0]);
00188 }
00190 virtual void post(Space& home, SetVarArray& x, IntVarArray& y, BoolVar b) {
00191 Gecode::rel(home, x[0], SRT_SUP, y[0], b);
00192 }
00193 };
00194 Elem _elem("Int::Elem");
00195
00197 class NoElem : public SetTest {
00198 public:
00200 NoElem(const char* t)
00201 : SetTest(t,1,ds_33,false,1) {}
00203 virtual bool solution(const SetAssignment& x) const {
00204 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00205 if (xr.val()==x.intval())
00206 return false;
00207 return true;
00208 }
00210 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00211 Gecode::rel(home, x[0], SRT_DISJ, y[0]);
00212 }
00213 };
00214 NoElem _noelem("Int::NoElem");
00215
00217 class Rel : public SetTest {
00218 private:
00219 Gecode::SetRelType srt;
00220 bool inverse;
00221 public:
00223 Rel(Gecode::SetRelType srt0, bool inverse0)
00224 : SetTest("Int::Rel::"+str(srt0)+(inverse0 ? "::i" : ""),
00225 1,ds_33,true,1)
00226 , srt(srt0)
00227 , inverse(inverse0) {}
00229 virtual bool solution(const SetAssignment& x) const {
00230 CountableSetRanges xr(x.lub, x[0]);
00231 IntSet is(x.intval(), x.intval());
00232 IntSetRanges dr(is);
00233 Gecode::SetRelType rsrt = srt;
00234 if (inverse) {
00235 switch (srt) {
00236 case SRT_SUB: rsrt = SRT_SUP; break;
00237 case SRT_SUP: rsrt = SRT_SUB; break;
00238 default: break;
00239 }
00240 }
00241 switch (rsrt) {
00242 case SRT_EQ: return Iter::Ranges::equal(xr, dr);
00243 case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
00244 case SRT_SUB: return Iter::Ranges::subset(xr, dr);
00245 case SRT_SUP: return Iter::Ranges::subset(dr, xr);
00246 case SRT_DISJ:
00247 {
00248 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00249 inter(xr, dr);
00250 return !inter();
00251 }
00252 case SRT_CMPL:
00253 {
00254 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00255 return Iter::Ranges::equal(xr,drc);
00256 }
00257 }
00258 GECODE_NEVER;
00259 return false;
00260 }
00262 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00263 if (!inverse)
00264 Gecode::rel(home, x[0], srt, y[0]);
00265 else
00266 Gecode::rel(home, y[0], srt, x[0]);
00267 }
00269 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00270 BoolVar b) {
00271 if (!inverse)
00272 Gecode::rel(home, x[0], srt, y[0], b);
00273 else
00274 Gecode::rel(home, y[0], srt, x[0], b);
00275 }
00276 };
00277 Rel _rel_eq(Gecode::SRT_EQ,false);
00278 Rel _rel_nq(Gecode::SRT_NQ,false);
00279 Rel _rel_sub(Gecode::SRT_SUB,false);
00280 Rel _rel_sup(Gecode::SRT_SUP,false);
00281 Rel _rel_disj(Gecode::SRT_DISJ,false);
00282 Rel _rel_cmpl(Gecode::SRT_CMPL,false);
00283 Rel _rel_eqi(Gecode::SRT_EQ,true);
00284 Rel _rel_nqi(Gecode::SRT_NQ,true);
00285 Rel _rel_subi(Gecode::SRT_SUB,true);
00286 Rel _rel_supi(Gecode::SRT_SUP,true);
00287 Rel _rel_disji(Gecode::SRT_DISJ,true);
00288 Rel _rel_cmpli(Gecode::SRT_CMPL,true);
00289
00291 class IntRel : public SetTest {
00292 private:
00293 Gecode::IntRelType irt;
00294 bool inverse;
00295 public:
00297 IntRel(Gecode::IntRelType irt0, bool inverse0)
00298 : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
00299 (inverse0 ? "::i" : ""),1,ds_33,false,1)
00300 , irt(irt0)
00301 , inverse(inverse0) {}
00303 virtual bool solution(const SetAssignment& x) const {
00304 CountableSetValues xr(x.lub, x[0]);
00305 if (!xr())
00306 return false;
00307 for (; xr(); ++xr) {
00308 switch (irt) {
00309 case Gecode::IRT_EQ:
00310 if (xr.val() != x.intval()) return false;
00311 break;
00312 case Gecode::IRT_NQ:
00313 if (xr.val() == x.intval()) return false;
00314 break;
00315 case Gecode::IRT_GR:
00316 if (!inverse && xr.val() <= x.intval()) return false;
00317 if (inverse && xr.val() >= x.intval()) return false;
00318 break;
00319 case Gecode::IRT_GQ:
00320 if (!inverse && xr.val() < x.intval()) return false;
00321 if (inverse && xr.val() > x.intval()) return false;
00322 break;
00323 case Gecode::IRT_LE:
00324 if (!inverse && xr.val() >= x.intval()) return false;
00325 if (inverse && xr.val() <= x.intval()) return false;
00326 break;
00327 case Gecode::IRT_LQ:
00328 if (!inverse && xr.val() > x.intval()) return false;
00329 if (inverse && xr.val() < x.intval()) return false;
00330 break;
00331 default:
00332 GECODE_NEVER;
00333 return false;
00334 }
00335 }
00336 return true;
00337 }
00339 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00340 if (!inverse)
00341 Gecode::rel(home, x[0], irt, y[0]);
00342 else
00343 Gecode::rel(home, y[0], irt, x[0]);
00344 }
00345 };
00346 IntRel _intrel_eq(Gecode::IRT_EQ,false);
00347 IntRel _intrel_nq(Gecode::IRT_NQ,false);
00348 IntRel _intrel_gr(Gecode::IRT_GR,false);
00349 IntRel _intrel_gq(Gecode::IRT_GQ,false);
00350 IntRel _intrel_le(Gecode::IRT_LE,false);
00351 IntRel _intrel_lq(Gecode::IRT_LQ,false);
00352 IntRel _intrel_eqi(Gecode::IRT_EQ,true);
00353 IntRel _intrel_nqi(Gecode::IRT_NQ,true);
00354 IntRel _intrel_gri(Gecode::IRT_GR,true);
00355 IntRel _intrel_gqi(Gecode::IRT_GQ,true);
00356 IntRel _intrel_lei(Gecode::IRT_LE,true);
00357 IntRel _intrel_lqi(Gecode::IRT_LQ,true);
00358
00359
00360 template<class I>
00361 int weightI(const IntArgs& elements,
00362 const IntArgs& weights,
00363 I& iter) {
00364 Iter::Ranges::IsRangeIter<I>();
00365 int sum = 0;
00366 int i = 0;
00367 for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00368
00369 while (elements[i]<v.val()) i++;
00370 assert(elements[i] == v.val());
00371 sum += weights[i];
00372 }
00373 return sum;
00374 }
00375
00377 class Weights : public SetTest {
00378 public:
00379 IntArgs elements;
00380 IntArgs weights;
00381 int minWeight;
00382 int maxWeight;
00384 Weights(const char* t, IntArgs& el, IntArgs& w,
00385 int min = -10000, int max = 10000)
00386 : SetTest(t,1,ds_33,false,1),
00387 elements(el), weights(w), minWeight(min), maxWeight(max) {}
00389 virtual bool solution(const SetAssignment& x) const {
00390 CountableSetRanges x0(x.lub, x[0]);
00391 return x.intval()==weightI(elements,weights,x0) &&
00392 x.intval() >= minWeight && x.intval() <= maxWeight;
00393 }
00395 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00396 Gecode::post(home, minWeight <= y[0]);
00397 Gecode::post(home, maxWeight >= y[0]);
00398 Gecode::weights(home, elements, weights, x[0], y[0]);
00399 }
00400 };
00401
00402 const int el1v[] = {-3,-2,-1,0,1,2,3};
00403 IntArgs el1(7,el1v);
00404 const int w1v[] = {1,-2,1,1,1,6,1};
00405 IntArgs w1(7,w1v);
00406 Weights _weights1("Int::Weights::1", el1, w1);
00407
00408 const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
00409 IntArgs w2(7,w2v);
00410 Weights _weights2("Int::Weights::2", el1, w2);
00411 Weights _weights3("Int::Weights::3", el1, w2, 3);
00412
00413 const int w4v[] = {1,1,0,0,0,0,0};
00414 IntArgs w4(7,w4v);
00415 Weights _weights4("Int::Weights::4", el1, w4);
00416
00418 class Match : public SetTest {
00419 public:
00421 Match(const char* t)
00422 : SetTest(t,1,ds_33,false,3) {}
00424 virtual bool solution(const SetAssignment& x) const {
00425 if (x.ints()[0]>=x.ints()[1] ||
00426 x.ints()[1]>=x.ints()[2])
00427 return false;
00428 CountableSetValues xr(x.lub, x[0]);
00429 if (!xr())
00430 return false;
00431 if (xr.val() != x.ints()[0])
00432 return false;
00433 ++xr;
00434 if (!xr())
00435 return false;
00436 if (xr.val() != x.ints()[1])
00437 return false;
00438 ++xr;
00439 if (!xr())
00440 return false;
00441 if (xr.val() != x.ints()[2])
00442 return false;
00443 ++xr;
00444 if (xr())
00445 return false;
00446 return true;
00447 }
00449 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00450 Gecode::channel(home, y, x[0]);
00451 }
00452 };
00453 Match _match("Int::Match");
00454
00456 class ChannelInt : public SetTest {
00457 private:
00458 int ssize, isize;
00459 public:
00461 ChannelInt(const char* t, const IntSet& d, int _ssize, int _isize)
00462 : SetTest(t,_ssize,d,false,_isize), ssize(_ssize), isize(_isize) {}
00464 virtual bool solution(const SetAssignment& x) const {
00465 for (int i=0; i<isize; i++) {
00466 if (x.ints()[i] < 0 || x.ints()[i] >= ssize)
00467 return false;
00468 Iter::Ranges::Singleton single(i,i);
00469 CountableSetRanges csr(x.lub, x[x.ints()[i]]);
00470 if (!Iter::Ranges::subset(single, csr))
00471 return false;
00472 }
00473 for (int i=0; i<ssize; i++) {
00474 int size = 0;
00475 for (CountableSetValues csv(x.lub, x[i]); csv(); ++csv) {
00476 if (csv.val() < 0 || csv.val() >= isize) return false;
00477 if (x.ints()[csv.val()] != i) return false;
00478 size++;
00479 }
00480 }
00481 return true;
00482 }
00484 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00485 Gecode::channel(home, y, x);
00486 }
00487 };
00488
00489 ChannelInt _channelint1("Int::Channel::Int::1", d2, 2, 3);
00490 ChannelInt _channelint2("Int::Channel::Int::2", d3, 3, 3);
00491
00493 class ChannelBool : public SetTest {
00494 private:
00495 int isize;
00496 public:
00498 ChannelBool(const char* t, const IntSet& d, int _isize)
00499 : SetTest(t,1,d,false,_isize), isize(_isize) {}
00501 virtual bool solution(const SetAssignment& x) const {
00502 for (int i=0; i<isize; i++) {
00503 if (x.ints()[i] < 0 || x.ints()[i] > 1)
00504 return false;
00505 }
00506 int cur = 0;
00507 for (CountableSetValues csv(x.lub, x[0]); csv(); ++csv) {
00508 if (csv.val() < 0 || csv.val() >= isize) return false;
00509 if (x.ints()[csv.val()] != 1) return false;
00510 for (; cur<csv.val(); cur++)
00511 if (x.ints()[cur] != 0) return false;
00512 cur = csv.val() + 1;
00513 }
00514 for (; cur<isize; cur++)
00515 if (x.ints()[cur] != 0) return false;
00516 return true;
00517 }
00519 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00520 BoolVarArgs b(y.size());
00521 for (int i=y.size(); i--;)
00522 b[i] = channel(home, y[i]);
00523 Gecode::channel(home, b, x[0]);
00524 }
00525 };
00526
00527 ChannelBool _channelbool1("Int::Channel::Bool::1", d2, 3);
00528 ChannelBool _channelbool2("Int::Channel::Bool::2", d3, 3);
00529 ChannelBool _channelbool3("Int::Channel::Bool::3", d4, 5);
00530
00531 }}}
00532
00533