Generated on Mon Nov 30 23:53:25 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00010  *     $Date: 2009-06-08 11:14:18 +0200 (Mon, 08 Jun 2009) $ by $Author: schulte $
00011  *     $Revision: 9211 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/minimodel.hh>
00039 
00040 #include "test/set.hh"
00041 
00042 using namespace Gecode;
00043 
00044 namespace Test { namespace Set {
00045 
00047   namespace Element {
00048 
00054 
00055     static IntSet ds_12(-1,2);
00056     static IntSet ds_13(-1,3);
00057 
00059     class ElementUnion : public SetTest {
00060     public:
00062       ElementUnion(const char* t)
00063         : SetTest(t,5,ds_12,false) {}
00065       virtual bool solution(const SetAssignment& x) const {
00066         int selected = 0;
00067         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00068              ++sel2, selected++) {}
00069         CountableSetValues x4v(x.lub, x[4]);
00070         if (selected==0)
00071           return !x4v();
00072         CountableSetRanges* sel = new CountableSetRanges[selected];
00073         CountableSetValues selector(x.lub, x[3]);
00074         for (int i=selected; i--;++selector) {
00075           if (selector.val()>=3 || selector.val()<0) {
00076             delete[] sel;
00077             return false;
00078           }
00079           sel[i].init(x.lub, x[selector.val()]);
00080         }
00081         Iter::Ranges::NaryUnion<CountableSetRanges> u(sel, selected);
00082 
00083         CountableSetRanges z(x.lub, x[4]);
00084         bool ret = Iter::Ranges::equal(u, z);
00085         delete[] sel;
00086         return ret;
00087       }
00089       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00090         SetVarArgs xs(x.size()-2);
00091         for (int i=x.size()-2; i--;)
00092           xs[i]=x[i];
00093         Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
00094       }
00095     };
00096     ElementUnion _elementunion("Element::Union");
00097 
00099     class ElementUnionConst : public SetTest {
00100     private:
00101       const IntSet i0;
00102       const IntSet i1;
00103       const IntSet i2;
00104     public:
00106       ElementUnionConst(const char* t)
00107         : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
00109       virtual bool solution(const SetAssignment& x) const {
00110         int selected = 0;
00111         for (CountableSetValues sel2(x.lub, x[0]); sel2();
00112              ++sel2, selected++) {}
00113         CountableSetValues x4v(x.lub, x[1]);
00114         if (selected==0)
00115           return !x4v();
00116         IntSet iss[] = {i0, i1, i2};
00117         IntSetRanges* sel = new IntSetRanges[selected];
00118         CountableSetValues selector(x.lub, x[0]);
00119         for (int i=selected; i--;++selector) {
00120           if (selector.val()>=3 || selector.val()<0) {
00121             delete[] sel;
00122             return false;
00123           }
00124           sel[i].init(iss[selector.val()]);
00125         }
00126         Iter::Ranges::NaryUnion<IntSetRanges> u(sel, selected);
00127 
00128         CountableSetRanges z(x.lub, x[1]);
00129         bool ret = Iter::Ranges::equal(u, z);
00130         delete[] sel;
00131         return ret;
00132       }
00134       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00135         IntSetArgs xs(3);
00136         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00137         Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
00138       }
00139     };
00140     ElementUnionConst _elementunionconst("Element::UnionConst");
00141 
00143     class ElementInter : public SetTest {
00144     public:
00146       ElementInter(const char* t)
00147         : SetTest(t,5,ds_12,false) {}
00149       virtual bool solution(const SetAssignment& x) const {
00150         int selected = 0;
00151         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00152              ++sel2, selected++) {}
00153         CountableSetRanges x4r(x.lub, x[4]);
00154         if (selected==0)
00155           return Iter::Ranges::size(x4r)==Gecode::Set::Limits::card;
00156         CountableSetRanges* sel = new CountableSetRanges[selected];
00157         CountableSetValues selector(x.lub, x[3]);
00158         for (int i=selected; i--;++selector) {
00159           if (selector.val()>=3 || selector.val()<0) {
00160             delete[] sel;
00161             return false;
00162           }
00163           sel[i].init(x.lub, x[selector.val()]);
00164         }
00165         Iter::Ranges::NaryInter<CountableSetRanges> u(sel, selected);
00166 
00167         CountableSetRanges z(x.lub, x[4]);
00168         bool ret = Iter::Ranges::equal(u, z);
00169         delete[] sel;
00170         return ret;
00171       }
00173       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00174         SetVarArgs xs(x.size()-2);
00175         for (int i=x.size()-2; i--;)
00176           xs[i]=x[i];
00177         Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
00178       }
00179     };
00180     ElementInter _elementinter("Element::Inter");
00181 
00183     class ElementInterIn : public SetTest {
00184     public:
00186       ElementInterIn(const char* t)
00187         : SetTest(t,5,ds_12,false) {}
00189       virtual bool solution(const SetAssignment& x) const {
00190         int selected = 0;
00191         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00192              ++sel2, selected++) {}
00193         CountableSetRanges x4r(x.lub, x[4]);
00194         if (selected==0)
00195           return Iter::Ranges::size(x4r)==4;
00196         CountableSetRanges* sel = new CountableSetRanges[selected];
00197         CountableSetValues selector(x.lub, x[3]);
00198         for (int i=selected; i--;++selector) {
00199           if (selector.val()>=3 || selector.val()<0) {
00200             delete[] sel;
00201             return false;
00202           }
00203           sel[i].init(x.lub, x[selector.val()]);
00204         }
00205         Iter::Ranges::NaryInter<CountableSetRanges> u(sel, selected);
00206 
00207         CountableSetRanges z(x.lub, x[4]);
00208         bool ret = Iter::Ranges::equal(u, z);
00209         delete[] sel;
00210         return ret;
00211       }
00213       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00214         SetVarArgs xs(x.size()-2);
00215         for (int i=x.size()-2; i--;)
00216           xs[i]=x[i];
00217         Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1], 
00218           ds_12);
00219       }
00220     };
00221     ElementInterIn _elementinterin("Element::InterIn");
00222 
00224     class ElementDisjoint : public SetTest {
00225     public:
00227       ElementDisjoint(const char* t)
00228         : SetTest(t,5,ds_12,false) {}
00230       virtual bool solution(const SetAssignment& x) const {
00231         int selected = 0;
00232         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00233              ++sel2, selected++) {
00234           if (sel2.val() < 0)
00235             return false;
00236         }
00237         CountableSetValues x4v(x.lub, x[4]);
00238         if (selected == 0)
00239           return !x4v();
00240         CountableSetRanges* sel = new CountableSetRanges[selected];
00241         CountableSetValues selector(x.lub, x[3]);
00242         unsigned int cardsum = 0;
00243         for (int i=selected; i--;++selector) {
00244           if (selector.val()>=3 || selector.val()<0) {
00245             delete[] sel;
00246             return false;
00247           }
00248           sel[i].init(x.lub, x[selector.val()]);
00249           CountableSetRanges xicard(x.lub, x[selector.val()]);
00250           cardsum += Iter::Ranges::size(xicard);
00251         }
00252         Iter::Ranges::NaryUnion<CountableSetRanges> u(sel, selected);
00253         Iter::Ranges::Cache<Iter::Ranges::NaryUnion<CountableSetRanges> >
00254           uc(u);
00255         bool ret = Iter::Ranges::size(uc) == cardsum;
00256         uc.reset();
00257         CountableSetRanges z(x.lub, x[4]);
00258         ret &= Iter::Ranges::equal(uc, z);
00259         delete[] sel;
00260         return ret;
00261       }
00263       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00264         SetVarArgs xs(x.size()-2);
00265         for (int i=x.size()-2; i--;)
00266           xs[i]=x[i];
00267         Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
00268       }
00269     };
00270     ElementDisjoint _elementdisjoint("Element::Disjoint");
00271 
00273     class ElementSet : public SetTest {
00274     public:
00276       ElementSet(const char* t)
00277         : SetTest(t,4,ds_12,false,true) {}
00279       virtual bool solution(const SetAssignment& x) const {
00280         if (x.intval() < 0 || x.intval() > 2)
00281           return false;
00282         CountableSetRanges z(x.lub, x[3]);
00283         CountableSetRanges y(x.lub, x[x.intval()]);
00284         return Iter::Ranges::equal(y, z);
00285       }
00287       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00288         SetVarArgs xs(x.size()-1);
00289         for (int i=x.size()-1; i--;)
00290           xs[i]=x[i];
00291         Gecode::element(home, xs, y[0], x[x.size()-1]);
00292       }
00293     };
00294     ElementSet _elementset("Element::Set");
00295 
00297     class ElementSetConst : public SetTest {
00298     private:
00299       const IntSet i0;
00300       const IntSet i1;
00301       const IntSet i2;
00302     public:
00304       ElementSetConst(const char* t)
00305         : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
00307       virtual bool solution(const SetAssignment& x) const {
00308         if (x.intval() < 0 || x.intval() > 2)
00309           return false;
00310         CountableSetRanges xr(x.lub, x[0]);
00311         IntSet iss[] = {i0, i1, i2};
00312         IntSetRanges isr(iss[x.intval()]);
00313         return Iter::Ranges::equal(xr, isr);
00314       }
00316       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00317         IntSetArgs xs(3);
00318         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00319         Gecode::element(home, xs, y[0], x[0]);
00320       }
00321     };
00322     ElementSetConst _elementsetconst("Element::SetConst");
00323 
00325     class MatrixIntSet : public SetTest {
00326      protected:
00328        Gecode::IntSetArgs tm;
00329      public:
00331        MatrixIntSet(void)
00332          : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2), 
00333            tm(4) {
00334          tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
00335          tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
00336        }
00338        virtual bool solution(const SetAssignment& x) const {
00339          // Get integer assignment
00340          const Int::Assignment& y = x.ints();
00341          // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
00342          using namespace Gecode;
00343          if ((y[0] > 1) || (y[1] > 1))
00344            return false;
00345          Matrix<IntSetArgs> m(tm,2,2);
00346          IntSetRanges a(m(y[0],y[1]));
00347          CountableSetRanges b(x.lub, x[0]);
00348          return Iter::Ranges::equal(a,b);
00349        }
00351        virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00352                          Gecode::IntVarArray& y) {
00353          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00354          using namespace Gecode;
00355          Matrix<IntSetArgs> m(tm,2,2);
00356          element(home, m, y[0], y[1], x[0]);
00357        }
00358      };
00359 
00360     MatrixIntSet _emis;
00361 
00363 
00364 }}}
00365 
00366 // STATISTICS: test-set