Generated on Tue May 22 09:39:59 2018 for Gecode by doxygen 1.6.3

element.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 <gecode/minimodel.hh>
00035 
00036 #include "test/set.hh"
00037 
00038 using namespace Gecode;
00039 
00040 namespace Test { namespace Set {
00041 
00043   namespace Element {
00044 
00050 
00051     static IntSet ds_12(-1,2);
00052     static IntSet ds_13(-1,3);
00053 
00055     class ElementUnion : public SetTest {
00056     public:
00058       ElementUnion(const char* t)
00059         : SetTest(t,5,ds_12,false) {}
00061       virtual bool solution(const SetAssignment& x) const {
00062         int selected = 0;
00063         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00064              ++sel2, selected++) {}
00065         CountableSetValues x4v(x.lub, x[4]);
00066         if (selected==0)
00067           return !x4v();
00068         CountableSetRanges* sel = new CountableSetRanges[selected];
00069         CountableSetValues selector(x.lub, x[3]);
00070         for (int i=selected; i--;++selector) {
00071           if (selector.val()>=3 || selector.val()<0) {
00072             delete[] sel;
00073             return false;
00074           }
00075           sel[i].init(x.lub, x[selector.val()]);
00076         }
00077 
00078         bool ret;
00079         {
00080           Region r;
00081           Iter::Ranges::NaryUnion u(r, sel, selected);
00082 
00083           CountableSetRanges z(x.lub, x[4]);
00084           ret = Iter::Ranges::equal(u, z);
00085         }
00086         delete[] sel;
00087         return ret;
00088       }
00090       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00091         SetVarArgs xs(x.size()-2);
00092         for (int i=x.size()-2; i--;)
00093           xs[i]=x[i];
00094         Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
00095       }
00096     };
00097     ElementUnion _elementunion("Element::Union");
00098 
00100     class ElementUnionConst : public SetTest {
00101     private:
00102       const IntSet i0;
00103       const IntSet i1;
00104       const IntSet i2;
00105     public:
00107       ElementUnionConst(const char* t)
00108         : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
00110       virtual bool solution(const SetAssignment& x) const {
00111         int selected = 0;
00112         for (CountableSetValues sel2(x.lub, x[0]); sel2();
00113              ++sel2, selected++) {}
00114         CountableSetValues x4v(x.lub, x[1]);
00115         if (selected==0)
00116           return !x4v();
00117         IntSet iss[] = {i0, i1, i2};
00118         IntSetRanges* sel = new IntSetRanges[selected];
00119         CountableSetValues selector(x.lub, x[0]);
00120         for (int i=selected; i--;++selector) {
00121           if (selector.val()>=3 || selector.val()<0) {
00122             delete[] sel;
00123             return false;
00124           }
00125           sel[i].init(iss[selector.val()]);
00126         }
00127 
00128         bool ret;
00129         {
00130           Region r;
00131           Iter::Ranges::NaryUnion u(r, sel, selected);
00132 
00133           CountableSetRanges z(x.lub, x[1]);
00134           ret = Iter::Ranges::equal(u, z);
00135         }
00136         delete[] sel;
00137         return ret;
00138       }
00140       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00141         IntSetArgs xs(3);
00142         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00143         Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
00144       }
00145     };
00146     ElementUnionConst _elementunionconst("Element::UnionConst");
00147 
00149     class ElementInter : public SetTest {
00150     public:
00152       ElementInter(const char* t)
00153         : SetTest(t,5,ds_12,false) {}
00155       virtual bool solution(const SetAssignment& x) const {
00156         int selected = 0;
00157         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00158              ++sel2, selected++) {}
00159         CountableSetRanges x4r(x.lub, x[4]);
00160         if (selected==0)
00161           return Iter::Ranges::size(x4r)==Gecode::Set::Limits::card;
00162         CountableSetRanges* sel = new CountableSetRanges[selected];
00163         CountableSetValues selector(x.lub, x[3]);
00164         for (int i=selected; i--;++selector) {
00165           if (selector.val()>=3 || selector.val()<0) {
00166             delete[] sel;
00167             return false;
00168           }
00169           sel[i].init(x.lub, x[selector.val()]);
00170         }
00171         bool ret;
00172         {
00173           Region r;
00174           Iter::Ranges::NaryInter u(r, sel, selected);
00175 
00176           CountableSetRanges z(x.lub, x[4]);
00177           ret = Iter::Ranges::equal(u, z);
00178         }
00179         delete [] sel;
00180         return ret;
00181       }
00183       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00184         SetVarArgs xs(x.size()-2);
00185         for (int i=x.size()-2; i--;)
00186           xs[i]=x[i];
00187         Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
00188       }
00189     };
00190     ElementInter _elementinter("Element::Inter");
00191 
00193     class ElementInterIn : public SetTest {
00194     public:
00196       ElementInterIn(const char* t)
00197         : SetTest(t,5,ds_12,false) {}
00199       virtual bool solution(const SetAssignment& x) const {
00200         int selected = 0;
00201         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00202              ++sel2, selected++) {}
00203         CountableSetRanges x4r(x.lub, x[4]);
00204         if (selected==0)
00205           return Iter::Ranges::size(x4r)==4;
00206         CountableSetRanges* sel = new CountableSetRanges[selected];
00207         CountableSetValues selector(x.lub, x[3]);
00208         for (int i=selected; i--;++selector) {
00209           if (selector.val()>=3 || selector.val()<0) {
00210             delete[] sel;
00211             return false;
00212           }
00213           sel[i].init(x.lub, x[selector.val()]);
00214         }
00215         bool ret;
00216         {
00217           Region r;
00218           Iter::Ranges::NaryInter u(r,sel, selected);
00219 
00220           CountableSetRanges z(x.lub, x[4]);
00221           ret = Iter::Ranges::equal(u, z);
00222         }
00223         delete [] sel;
00224         return ret;
00225       }
00227       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00228         SetVarArgs xs(x.size()-2);
00229         for (int i=x.size()-2; i--;)
00230           xs[i]=x[i];
00231         Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1],
00232           ds_12);
00233       }
00234     };
00235     ElementInterIn _elementinterin("Element::InterIn");
00236 
00238     class ElementDisjoint : public SetTest {
00239     public:
00241       ElementDisjoint(const char* t)
00242         : SetTest(t,5,ds_12,false) {}
00244       virtual bool solution(const SetAssignment& x) const {
00245         int selected = 0;
00246         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00247              ++sel2, selected++) {
00248           if (sel2.val() < 0)
00249             return false;
00250         }
00251         CountableSetValues x4v(x.lub, x[4]);
00252         if (selected == 0)
00253           return !x4v();
00254         CountableSetRanges* sel = new CountableSetRanges[selected];
00255         CountableSetValues selector(x.lub, x[3]);
00256         unsigned int cardsum = 0;
00257         for (int i=selected; i--;++selector) {
00258           if (selector.val()>=3 || selector.val()<0) {
00259             delete[] sel;
00260             return false;
00261           }
00262           sel[i].init(x.lub, x[selector.val()]);
00263           CountableSetRanges xicard(x.lub, x[selector.val()]);
00264           cardsum += Iter::Ranges::size(xicard);
00265         }
00266 
00267         bool ret;
00268         {
00269           Region r;
00270           Iter::Ranges::NaryUnion u(r, sel, selected);
00271           ret = Iter::Ranges::size(u) == cardsum;
00272           u.reset();
00273           CountableSetRanges z(x.lub, x[4]);
00274           ret &= Iter::Ranges::equal(u, z);
00275         }
00276         delete[] sel;
00277         return ret;
00278       }
00280       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00281         SetVarArgs xs(x.size()-2);
00282         for (int i=x.size()-2; i--;)
00283           xs[i]=x[i];
00284         Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
00285       }
00286     };
00287     ElementDisjoint _elementdisjoint("Element::Disjoint");
00288 
00290     class ElementSet : public SetTest {
00291     public:
00293       ElementSet(const char* t)
00294         : SetTest(t,4,ds_12,false,true) {}
00296       virtual bool solution(const SetAssignment& x) const {
00297         if (x.intval() < 0 || x.intval() > 2)
00298           return false;
00299         CountableSetRanges z(x.lub, x[3]);
00300         CountableSetRanges y(x.lub, x[x.intval()]);
00301         return Iter::Ranges::equal(y, z);
00302       }
00304       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00305         SetVarArgs xs(x.size()-1);
00306         for (int i=x.size()-1; i--;)
00307           xs[i]=x[i];
00308         Gecode::element(home, xs, y[0], x[x.size()-1]);
00309       }
00310     };
00311     ElementSet _elementset("Element::Set");
00312 
00314     class ElementSetConst : public SetTest {
00315     private:
00316       const IntSet i0;
00317       const IntSet i1;
00318       const IntSet i2;
00319     public:
00321       ElementSetConst(const char* t)
00322         : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
00324       virtual bool solution(const SetAssignment& x) const {
00325         if (x.intval() < 0 || x.intval() > 2)
00326           return false;
00327         CountableSetRanges xr(x.lub, x[0]);
00328         IntSet iss[] = {i0, i1, i2};
00329         IntSetRanges isr(iss[x.intval()]);
00330         return Iter::Ranges::equal(xr, isr);
00331       }
00333       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00334         IntSetArgs xs(3);
00335         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00336         Gecode::element(home, xs, y[0], x[0]);
00337       }
00338     };
00339     ElementSetConst _elementsetconst("Element::SetConst");
00340 
00342     class MatrixIntSet : public SetTest {
00343      protected:
00345        Gecode::IntSetArgs tm;
00346      public:
00348        MatrixIntSet(void)
00349          : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2),
00350            tm(4) {
00351          tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
00352          tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
00353        }
00355        virtual bool solution(const SetAssignment& x) const {
00356          // Get integer assignment
00357          const Int::Assignment& y = x.ints();
00358          // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
00359          using namespace Gecode;
00360          if ((y[0] > 1) || (y[1] > 1))
00361            return false;
00362          Matrix<IntSetArgs> m(tm,2,2);
00363          IntSetRanges a(m(y[0],y[1]));
00364          CountableSetRanges b(x.lub, x[0]);
00365          return Iter::Ranges::equal(a,b);
00366        }
00368        virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00369                          Gecode::IntVarArray& y) {
00370          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00371          using namespace Gecode;
00372          Matrix<IntSetArgs> m(tm,2,2);
00373          element(home, m, y[0], y[1], x[0]);
00374        }
00375      };
00376 
00377     MatrixIntSet _emis;
00378 
00380 
00381 }}}
00382 
00383 // STATISTICS: test-set