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,true,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 }
00086 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00087 Reify r) {
00088 Gecode::cardinality(home, x[0], y[0], r);
00089 }
00090 };
00091 Card _card("Int::Card");
00092
00094 class Min : public SetTest {
00095 public:
00097 Min(const char* t)
00098 : SetTest(t,1,ds_33,true,1) {}
00100 virtual bool solution(const SetAssignment& x) const {
00101 CountableSetRanges xr0(x.lub, x[0]);
00102 return xr0() && xr0.min()==x.intval();
00103 }
00105 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00106 Gecode::min(home, x[0], y[0]);
00107 }
00109 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00110 Reify r) {
00111 Gecode::min(home, x[0], y[0], r);
00112 }
00113 };
00114 Min _min("Int::Min");
00115
00117 class NotMin : public SetTest {
00118 public:
00120 NotMin(const char* t)
00121 : SetTest(t,1,ds_33,false,1) {}
00123 virtual bool solution(const SetAssignment& x) const {
00124 CountableSetRanges xr0(x.lub, x[0]);
00125 return !(xr0() && xr0.min()==x.intval());
00126 }
00128 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00129 Gecode::notMin(home, x[0], y[0]);
00130 }
00131 };
00132 NotMin _notmin("Int::NotMin");
00133
00135 class Max : public SetTest {
00136 public:
00138 Max(const char* t)
00139 : SetTest(t,1,ds_33,true,1) {}
00141 virtual bool solution(const SetAssignment& x) const {
00142 CountableSetRanges xr0(x.lub, x[0]);
00143 IntSet x0(xr0);
00144 return x0.ranges() > 0 && x0.max()==x.intval();
00145 }
00147 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00148 Gecode::max(home, x[0], y[0]);
00149 }
00151 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00152 Reify r) {
00153 Gecode::max(home, x[0], y[0], r);
00154 }
00155 };
00156 Max _max("Int::Max");
00157
00159 class NotMax : public SetTest {
00160 public:
00162 NotMax(const char* t)
00163 : SetTest(t,1,ds_33,false,1) {}
00165 virtual bool solution(const SetAssignment& x) const {
00166 CountableSetRanges xr0(x.lub, x[0]);
00167 IntSet x0(xr0);
00168 return !(x0.ranges() > 0 && x0.max()==x.intval());
00169 }
00171 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00172 Gecode::notMax(home, x[0], y[0]);
00173 }
00174 };
00175 NotMax _notmax("Int::NotMax");
00176
00178 class Elem : public SetTest {
00179 public:
00181 Elem(const char* t)
00182 : SetTest(t,1,ds_33,true,1) {}
00184 virtual bool solution(const SetAssignment& x) const {
00185 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00186 if (xr.val()==x.intval())
00187 return true;
00188 return false;
00189 }
00191 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00192 Gecode::rel(home, x[0], SRT_SUP, y[0]);
00193 }
00195 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00196 Reify r) {
00197 Gecode::rel(home, x[0], SRT_SUP, y[0], r);
00198 }
00199 };
00200 Elem _elem("Int::Elem");
00201
00203 class NoElem : public SetTest {
00204 public:
00206 NoElem(const char* t)
00207 : SetTest(t,1,ds_33,false,1) {}
00209 virtual bool solution(const SetAssignment& x) const {
00210 for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00211 if (xr.val()==x.intval())
00212 return false;
00213 return true;
00214 }
00216 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00217 Gecode::rel(home, x[0], SRT_DISJ, y[0]);
00218 }
00219 };
00220 NoElem _noelem("Int::NoElem");
00221
00223 class Rel : public SetTest {
00224 private:
00226 Gecode::SetRelType srt;
00228 bool swapped;
00229 public:
00231 Rel(Gecode::SetRelType srt0, bool s)
00232 : SetTest("Int::Rel::"+str(srt0)+(s ? "::s" : ""),
00233 1,ds_33,true,1),
00234 srt(srt0), swapped(s) {}
00236 virtual bool solution(const SetAssignment& x) const {
00237 CountableSetRanges xr(x.lub, x[0]);
00238 IntSet is(x.intval(), x.intval());
00239 IntSetRanges dr(is);
00240 Gecode::SetRelType rsrt = srt;
00241 if (swapped) {
00242 switch (srt) {
00243 case SRT_SUB: rsrt = SRT_SUP; break;
00244 case SRT_SUP: rsrt = SRT_SUB; break;
00245 default: break;
00246 }
00247 }
00248 switch (rsrt) {
00249 case SRT_EQ: return Iter::Ranges::equal(xr, dr);
00250 case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
00251 case SRT_SUB: return Iter::Ranges::subset(xr, dr);
00252 case SRT_SUP: return Iter::Ranges::subset(dr, xr);
00253 case SRT_DISJ:
00254 {
00255 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00256 inter(xr, dr);
00257 return !inter();
00258 }
00259 case SRT_CMPL:
00260 {
00261 Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00262 return Iter::Ranges::equal(xr,drc);
00263 }
00264 }
00265 GECODE_NEVER;
00266 return false;
00267 }
00269 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00270 if (!swapped)
00271 Gecode::rel(home, x[0], srt, y[0]);
00272 else
00273 Gecode::rel(home, y[0], srt, x[0]);
00274 }
00276 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00277 Reify r) {
00278 if (!swapped)
00279 Gecode::rel(home, x[0], srt, y[0], r);
00280 else
00281 Gecode::rel(home, y[0], srt, x[0], r);
00282 }
00283 };
00284 Rel _rel_eq(Gecode::SRT_EQ,false);
00285 Rel _rel_nq(Gecode::SRT_NQ,false);
00286 Rel _rel_sub(Gecode::SRT_SUB,false);
00287 Rel _rel_sup(Gecode::SRT_SUP,false);
00288 Rel _rel_disj(Gecode::SRT_DISJ,false);
00289 Rel _rel_cmpl(Gecode::SRT_CMPL,false);
00290 Rel _rel_eqs(Gecode::SRT_EQ,true);
00291 Rel _rel_nqs(Gecode::SRT_NQ,true);
00292 Rel _rel_subs(Gecode::SRT_SUB,true);
00293 Rel _rel_sups(Gecode::SRT_SUP,true);
00294 Rel _rel_disjs(Gecode::SRT_DISJ,true);
00295 Rel _rel_cmpls(Gecode::SRT_CMPL,true);
00296
00298 class IntRel : public SetTest {
00299 private:
00301 Gecode::IntRelType irt;
00303 bool swapped;
00304 public:
00306 IntRel(Gecode::IntRelType irt0, bool s)
00307 : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
00308 (s ? "::s" : ""),1,ds_33,true,1),
00309 irt(irt0), swapped(s) {
00310 testsubsumed = false;
00311 }
00313 virtual bool solution(const SetAssignment& x) const {
00314 CountableSetValues xr(x.lub, x[0]);
00315 if (!xr())
00316 return false;
00317 for (; xr(); ++xr)
00318 switch (irt) {
00319 case Gecode::IRT_EQ:
00320 if (xr.val() != x.intval()) return false;
00321 break;
00322 case Gecode::IRT_NQ:
00323 if (xr.val() == x.intval()) return false;
00324 break;
00325 case Gecode::IRT_GR:
00326 if (!swapped && xr.val() <= x.intval()) return false;
00327 if (swapped && xr.val() >= x.intval()) return false;
00328 break;
00329 case Gecode::IRT_GQ:
00330 if (!swapped && xr.val() < x.intval()) return false;
00331 if (swapped && xr.val() > x.intval()) return false;
00332 break;
00333 case Gecode::IRT_LE:
00334 if (!swapped && xr.val() >= x.intval()) return false;
00335 if (swapped && xr.val() <= x.intval()) return false;
00336 break;
00337 case Gecode::IRT_LQ:
00338 if (!swapped && xr.val() > x.intval()) return false;
00339 if (swapped && xr.val() < x.intval()) return false;
00340 break;
00341 default:
00342 GECODE_NEVER;
00343 return false;
00344 }
00345 return true;
00346 }
00348 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00349 if (!swapped)
00350 Gecode::rel(home, x[0], irt, y[0]);
00351 else
00352 Gecode::rel(home, y[0], irt, x[0]);
00353 }
00355 virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00356 Reify r) {
00357 if (!swapped)
00358 Gecode::rel(home, x[0], irt, y[0], r);
00359 else
00360 Gecode::rel(home, y[0], irt, x[0], r);
00361 }
00362 };
00363 IntRel _intrel_eq(Gecode::IRT_EQ,false);
00364 IntRel _intrel_nq(Gecode::IRT_NQ,false);
00365 IntRel _intrel_gr(Gecode::IRT_GR,false);
00366 IntRel _intrel_gq(Gecode::IRT_GQ,false);
00367 IntRel _intrel_le(Gecode::IRT_LE,false);
00368 IntRel _intrel_lq(Gecode::IRT_LQ,false);
00369 IntRel _intrel_eqs(Gecode::IRT_EQ,true);
00370 IntRel _intrel_nqs(Gecode::IRT_NQ,true);
00371 IntRel _intrel_grs(Gecode::IRT_GR,true);
00372 IntRel _intrel_gqs(Gecode::IRT_GQ,true);
00373 IntRel _intrel_les(Gecode::IRT_LE,true);
00374 IntRel _intrel_lqs(Gecode::IRT_LQ,true);
00375
00376
00377 template<class I>
00378 int weightI(const IntArgs& elements,
00379 const IntArgs& weights,
00380 I& iter) {
00381 int sum = 0;
00382 int i = 0;
00383 for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00384
00385 while (elements[i]<v.val()) i++;
00386 assert(elements[i] == v.val());
00387 sum += weights[i];
00388 }
00389 return sum;
00390 }
00391
00393 class Weights : public SetTest {
00394 public:
00395 IntArgs elements;
00396 IntArgs weights;
00397 int minWeight;
00398 int maxWeight;
00400 Weights(const char* t, IntArgs& el, IntArgs& w,
00401 int min = -10000, int max = 10000)
00402 : SetTest(t,1,ds_33,false,1),
00403 elements(el), weights(w), minWeight(min), maxWeight(max) {}
00405 virtual bool solution(const SetAssignment& x) const {
00406 CountableSetRanges x0(x.lub, x[0]);
00407 return x.intval()==weightI(elements,weights,x0) &&
00408 x.intval() >= minWeight && x.intval() <= maxWeight;
00409 }
00411 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00412 Gecode::rel(home, minWeight <= y[0]);
00413 Gecode::rel(home, maxWeight >= y[0]);
00414 Gecode::weights(home, elements, weights, x[0], y[0]);
00415 }
00416 };
00417
00418 const int el1v[] = {-3,-2,-1,0,1,2,3};
00419 IntArgs el1(7,el1v);
00420 const int w1v[] = {1,-2,1,1,1,6,1};
00421 IntArgs w1(7,w1v);
00422 Weights _weights1("Int::Weights::1", el1, w1);
00423
00424 const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
00425 IntArgs w2(7,w2v);
00426 Weights _weights2("Int::Weights::2", el1, w2);
00427 Weights _weights3("Int::Weights::3", el1, w2, 3);
00428
00429 const int w4v[] = {1,1,0,0,0,0,0};
00430 IntArgs w4(7,w4v);
00431 Weights _weights4("Int::Weights::4", el1, w4);
00432
00433 }}}
00434
00435