Generated on Thu Apr 11 13:59:13 2019 for Gecode by doxygen 1.6.3

int.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2005
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include "test/set.hh"
00035 #include "test/int.hh"
00036 #include <gecode/minimodel.hh>
00037 
00038 using namespace Gecode;
00039 
00040 namespace Test { namespace Set {
00041 
00043   namespace Int {
00044 
00050 
00051     static const int d1r[4][2] = {
00052       {-4,-3},{-1,-1},{1,1},{3,5}
00053     };
00054     static IntSet d1(d1r,4);
00055 
00056     static IntSet d2(-1,3);
00057     static IntSet d3(0,3);
00058 
00059     static IntSet d4(0,4);
00060 
00061     static IntSet ds_33(-3,3);
00062 
00064     class Card : public SetTest {
00065     public:
00067       Card(const char* t)
00068         : SetTest(t,1,ds_33,true,1) {}
00070       virtual bool solution(const SetAssignment& x) const {
00071         unsigned int s = 0;
00072         for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width();
00073         if (x.intval() < 0)
00074           return false;
00075         return s==(unsigned int)x.intval();
00076       }
00078       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00079         Gecode::cardinality(home, x[0], y[0]);
00080       }
00082       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00083                         Reify r) {
00084         Gecode::cardinality(home, x[0], y[0], r);
00085       }
00086     };
00087     Card _card("Int::Card");
00088 
00090     class Min : public SetTest {
00091     public:
00093       Min(const char* t)
00094         : SetTest(t,1,ds_33,true,1) {}
00096       virtual bool solution(const SetAssignment& x) const {
00097         CountableSetRanges xr0(x.lub, x[0]);
00098         return xr0() && xr0.min()==x.intval();
00099       }
00101       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00102         Gecode::min(home, x[0], y[0]);
00103       }
00105       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00106                         Reify r) {
00107         Gecode::min(home, x[0], y[0], r);
00108       }
00109     };
00110     Min _min("Int::Min");
00111 
00113     class NotMin : public SetTest {
00114     public:
00116       NotMin(const char* t)
00117         : SetTest(t,1,ds_33,false,1) {}
00119       virtual bool solution(const SetAssignment& x) const {
00120         CountableSetRanges xr0(x.lub, x[0]);
00121         return !(xr0() && xr0.min()==x.intval());
00122       }
00124       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00125         Gecode::notMin(home, x[0], y[0]);
00126       }
00127     };
00128     NotMin _notmin("Int::NotMin");
00129 
00131     class Max : public SetTest {
00132     public:
00134       Max(const char* t)
00135         : SetTest(t,1,ds_33,true,1) {}
00137       virtual bool solution(const SetAssignment& x) const {
00138         CountableSetRanges xr0(x.lub, x[0]);
00139         IntSet x0(xr0);
00140         return x0.ranges() > 0 && x0.max()==x.intval();
00141       }
00143       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00144         Gecode::max(home, x[0], y[0]);
00145       }
00147       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00148                         Reify r) {
00149         Gecode::max(home, x[0], y[0], r);
00150       }
00151     };
00152     Max _max("Int::Max");
00153 
00155     class NotMax : public SetTest {
00156     public:
00158       NotMax(const char* t)
00159         : SetTest(t,1,ds_33,false,1) {}
00161       virtual bool solution(const SetAssignment& x) const {
00162         CountableSetRanges xr0(x.lub, x[0]);
00163         IntSet x0(xr0);
00164         return !(x0.ranges() > 0 && x0.max()==x.intval());
00165       }
00167       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00168         Gecode::notMax(home, x[0], y[0]);
00169       }
00170     };
00171     NotMax _notmax("Int::NotMax");
00172 
00174     class Elem : public SetTest {
00175     public:
00177       Elem(const char* t)
00178         : SetTest(t,1,ds_33,true,1) {}
00180       virtual bool solution(const SetAssignment& x) const {
00181         for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00182           if (xr.val()==x.intval())
00183             return true;
00184         return false;
00185       }
00187       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00188         Gecode::rel(home, x[0], SRT_SUP, y[0]);
00189       }
00191       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00192                         Reify r) {
00193         Gecode::rel(home, x[0], SRT_SUP, y[0], r);
00194       }
00195     };
00196     Elem _elem("Int::Elem");
00197 
00199     class NoElem : public SetTest {
00200     public:
00202       NoElem(const char* t)
00203         : SetTest(t,1,ds_33,false,1) {}
00205       virtual bool solution(const SetAssignment& x) const {
00206         for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
00207           if (xr.val()==x.intval())
00208             return false;
00209         return true;
00210       }
00212       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00213         Gecode::rel(home, x[0], SRT_DISJ, y[0]);
00214       }
00215     };
00216     NoElem _noelem("Int::NoElem");
00217 
00219     class Rel : public SetTest {
00220     private:
00222       Gecode::SetRelType srt;
00224       bool swapped;
00225     public:
00227       Rel(Gecode::SetRelType srt0, bool s)
00228         : SetTest("Int::Rel::"+str(srt0)+(s ? "::s" : ""),
00229                   1,ds_33,true,1),
00230           srt(srt0), swapped(s) {}
00232       virtual bool solution(const SetAssignment& x) const {
00233         CountableSetRanges xr(x.lub, x[0]);
00234         IntSet is(x.intval(), x.intval());
00235         IntSetRanges dr(is);
00236         Gecode::SetRelType rsrt = srt;
00237         if (swapped) {
00238           switch (srt) {
00239             case SRT_SUB: rsrt = SRT_SUP; break;
00240             case SRT_SUP: rsrt = SRT_SUB; break;
00241             default: break;
00242           }
00243         }
00244         switch (rsrt) {
00245         case SRT_EQ: return Iter::Ranges::equal(xr, dr);
00246         case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
00247         case SRT_SUB: return Iter::Ranges::subset(xr, dr);
00248         case SRT_SUP: return Iter::Ranges::subset(dr, xr);
00249         case SRT_DISJ:
00250           {
00251             Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges>
00252               inter(xr, dr);
00253             return !inter();
00254           }
00255         case SRT_CMPL:
00256           {
00257             Gecode::Set::RangesCompl<IntSetRanges> drc(dr);
00258             return Iter::Ranges::equal(xr,drc);
00259           }
00260         default: GECODE_NEVER;
00261         }
00262         return false;
00263       }
00265       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00266         if (!swapped)
00267           Gecode::rel(home, x[0], srt, y[0]);
00268         else
00269           Gecode::rel(home, y[0], srt, x[0]);
00270       }
00272       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00273                         Reify r) {
00274         if (!swapped)
00275           Gecode::rel(home, x[0], srt, y[0], r);
00276         else
00277           Gecode::rel(home, y[0], srt, x[0], r);
00278       }
00279     };
00280     Rel _rel_eq(Gecode::SRT_EQ,false);
00281     Rel _rel_nq(Gecode::SRT_NQ,false);
00282     Rel _rel_sub(Gecode::SRT_SUB,false);
00283     Rel _rel_sup(Gecode::SRT_SUP,false);
00284     Rel _rel_disj(Gecode::SRT_DISJ,false);
00285     Rel _rel_cmpl(Gecode::SRT_CMPL,false);
00286     Rel _rel_eqs(Gecode::SRT_EQ,true);
00287     Rel _rel_nqs(Gecode::SRT_NQ,true);
00288     Rel _rel_subs(Gecode::SRT_SUB,true);
00289     Rel _rel_sups(Gecode::SRT_SUP,true);
00290     Rel _rel_disjs(Gecode::SRT_DISJ,true);
00291     Rel _rel_cmpls(Gecode::SRT_CMPL,true);
00292 
00294     class IntRel : public SetTest {
00295     private:
00297       Gecode::IntRelType irt;
00299       bool swapped;
00300     public:
00302       IntRel(Gecode::IntRelType irt0, bool s)
00303         : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
00304                   (s ? "::s" : ""),1,ds_33,true,1),
00305           irt(irt0), swapped(s) {
00306         testsubsumed = false;
00307       }
00309       virtual bool solution(const SetAssignment& x) const {
00310         CountableSetValues xr(x.lub, x[0]);
00311         if (!xr())
00312           return false;
00313         for (; xr(); ++xr)
00314           switch (irt) {
00315           case Gecode::IRT_EQ:
00316             if (xr.val() != x.intval()) return false;
00317             break;
00318           case Gecode::IRT_NQ:
00319             if (xr.val() == x.intval()) return false;
00320             break;
00321           case Gecode::IRT_GR:
00322             if (!swapped && xr.val() <= x.intval()) return false;
00323             if (swapped && xr.val() >= x.intval()) return false;
00324             break;
00325           case Gecode::IRT_GQ:
00326             if (!swapped && xr.val() < x.intval()) return false;
00327             if (swapped && xr.val() > x.intval()) return false;
00328             break;
00329           case Gecode::IRT_LE:
00330             if (!swapped && xr.val() >= x.intval()) return false;
00331             if (swapped && xr.val() <= x.intval()) return false;
00332             break;
00333           case Gecode::IRT_LQ:
00334             if (!swapped && xr.val() > x.intval()) return false;
00335             if (swapped && xr.val() < x.intval()) return false;
00336             break;
00337           default:
00338             GECODE_NEVER;
00339             return false;
00340           }
00341         return true;
00342       }
00344       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00345         if (!swapped)
00346           Gecode::rel(home, x[0], irt, y[0]);
00347         else
00348           Gecode::rel(home, y[0], irt, x[0]);
00349       }
00351       virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
00352                         Reify r) {
00353         assert((x.size() == 1) && (y.size() == 1));
00354         if ((r.mode() != Gecode::RM_EQV) || (Base::rand(2) != 0)) {
00355           if (!swapped)
00356             Gecode::rel(home, x[0], irt, y[0], r);
00357           else
00358             Gecode::rel(home, y[0], irt, x[0], r);
00359         } else if (swapped) {
00360           switch (irt) {
00361           case Gecode::IRT_EQ:
00362             Gecode::rel(home, (y[0] == x[0]) == r.var()); break;
00363           case Gecode::IRT_NQ:
00364             Gecode::rel(home, (y[0] != x[0]) == r.var()); break;
00365           case Gecode::IRT_LE:
00366             Gecode::rel(home, (y[0] < x[0]) == r.var()); break;
00367           case Gecode::IRT_LQ:
00368             Gecode::rel(home, (y[0] <= x[0]) == r.var()); break;
00369           case Gecode::IRT_GR:
00370             Gecode::rel(home, (y[0] > x[0]) == r.var()); break;
00371           case Gecode::IRT_GQ:
00372             Gecode::rel(home, (y[0] >= x[0]) == r.var()); break;
00373           default: GECODE_NEVER;
00374           }
00375         } else {
00376           switch (irt) {
00377           case Gecode::IRT_EQ:
00378             Gecode::rel(home, (x[0] == y[0]) == r.var()); break;
00379           case Gecode::IRT_NQ:
00380             Gecode::rel(home, (x[0] != y[0]) == r.var()); break;
00381           case Gecode::IRT_LE:
00382             Gecode::rel(home, (x[0] < y[0]) == r.var()); break;
00383           case Gecode::IRT_LQ:
00384             Gecode::rel(home, (x[0] <= y[0]) == r.var()); break;
00385           case Gecode::IRT_GR:
00386             Gecode::rel(home, (x[0] > y[0]) == r.var()); break;
00387           case Gecode::IRT_GQ:
00388             Gecode::rel(home, (x[0] >= y[0]) == r.var()); break;
00389           default: GECODE_NEVER;
00390           }
00391         }
00392       }
00393     };
00394     IntRel _intrel_eq(Gecode::IRT_EQ,false);
00395     IntRel _intrel_nq(Gecode::IRT_NQ,false);
00396     IntRel _intrel_gr(Gecode::IRT_GR,false);
00397     IntRel _intrel_gq(Gecode::IRT_GQ,false);
00398     IntRel _intrel_le(Gecode::IRT_LE,false);
00399     IntRel _intrel_lq(Gecode::IRT_LQ,false);
00400     IntRel _intrel_eqs(Gecode::IRT_EQ,true);
00401     IntRel _intrel_nqs(Gecode::IRT_NQ,true);
00402     IntRel _intrel_grs(Gecode::IRT_GR,true);
00403     IntRel _intrel_gqs(Gecode::IRT_GQ,true);
00404     IntRel _intrel_les(Gecode::IRT_LE,true);
00405     IntRel _intrel_lqs(Gecode::IRT_LQ,true);
00406 
00407 
00408     template<class I>
00409     int weightI(const IntArgs& elements,
00410                 const IntArgs& weights,
00411                 I& iter) {
00412       int sum = 0;
00413       int i = 0;
00414       for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00415         // Skip all elements below the current
00416         while (elements[i]<v.val()) i++;
00417         assert(elements[i] == v.val());
00418         sum += weights[i];
00419       }
00420       return sum;
00421     }
00422 
00424     class Weights : public SetTest {
00425     public:
00426       IntArgs elements;
00427       IntArgs weights;
00428       int minWeight;
00429       int maxWeight;
00431       Weights(const char* t, IntArgs& el, IntArgs& w,
00432               int min = -10000, int max = 10000)
00433         : SetTest(t,1,ds_33,false,1),
00434           elements(el), weights(w), minWeight(min), maxWeight(max) {}
00436       virtual bool solution(const SetAssignment& x) const {
00437         CountableSetRanges x0(x.lub, x[0]);
00438         return x.intval()==weightI(elements,weights,x0) &&
00439                x.intval() >= minWeight && x.intval() <= maxWeight;
00440       }
00442       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00443         Gecode::rel(home, minWeight <= y[0]);
00444         Gecode::rel(home, maxWeight >= y[0]);
00445         Gecode::weights(home, elements, weights, x[0], y[0]);
00446       }
00447     };
00448 
00449     const int el1v[] = {-3,-2,-1,0,1,2,3};
00450     IntArgs el1(7,el1v);
00451     const int w1v[] = {1,-2,1,1,1,6,1};
00452     IntArgs w1(7,w1v);
00453     Weights _weights1("Int::Weights::1", el1, w1);
00454 
00455     const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
00456     IntArgs w2(7,w2v);
00457     Weights _weights2("Int::Weights::2", el1, w2);
00458     Weights _weights3("Int::Weights::3", el1, w2, 3);
00459 
00460     const int w4v[] = {1,1,0,0,0,0,0};
00461     IntArgs w4(7,w4v);
00462     Weights _weights4("Int::Weights::4", el1, w4);
00463 
00464 }}}
00465 
00466 // STATISTICS: test-set