Generated on Sat Feb 12 2011 17:40:54 for Gecode by doxygen 1.7.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  *  Last modified:
00010  *     $Date: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $
00011  *     $Revision: 11390 $
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         
00082         FakeSpace* fs = new FakeSpace;
00083         bool ret;
00084         {
00085           Region r(*fs);
00086           Iter::Ranges::NaryUnion<CountableSetRanges> u(r, sel, selected);
00087           
00088           CountableSetRanges z(x.lub, x[4]);
00089           ret = Iter::Ranges::equal(u, z);
00090         }
00091         delete[] sel;
00092         delete fs;
00093         return ret;
00094       }
00096       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00097         SetVarArgs xs(x.size()-2);
00098         for (int i=x.size()-2; i--;)
00099           xs[i]=x[i];
00100         Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
00101       }
00102     };
00103     ElementUnion _elementunion("Element::Union");
00104 
00106     class ElementUnionConst : public SetTest {
00107     private:
00108       const IntSet i0;
00109       const IntSet i1;
00110       const IntSet i2;
00111     public:
00113       ElementUnionConst(const char* t)
00114         : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
00116       virtual bool solution(const SetAssignment& x) const {
00117         int selected = 0;
00118         for (CountableSetValues sel2(x.lub, x[0]); sel2();
00119              ++sel2, selected++) {}
00120         CountableSetValues x4v(x.lub, x[1]);
00121         if (selected==0)
00122           return !x4v();
00123         IntSet iss[] = {i0, i1, i2};
00124         IntSetRanges* sel = new IntSetRanges[selected];
00125         CountableSetValues selector(x.lub, x[0]);
00126         for (int i=selected; i--;++selector) {
00127           if (selector.val()>=3 || selector.val()<0) {
00128             delete[] sel;
00129             return false;
00130           }
00131           sel[i].init(iss[selector.val()]);
00132         }
00133 
00134         FakeSpace* fs = new FakeSpace;
00135         bool ret;
00136         {
00137           Region r(*fs);
00138           Iter::Ranges::NaryUnion<IntSetRanges> u(r, sel, selected);
00139 
00140           CountableSetRanges z(x.lub, x[1]);
00141           ret = Iter::Ranges::equal(u, z);
00142         }
00143         delete[] sel;
00144         delete fs;
00145         return ret;
00146       }
00148       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00149         IntSetArgs xs(3);
00150         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00151         Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
00152       }
00153     };
00154     ElementUnionConst _elementunionconst("Element::UnionConst");
00155 
00157     class ElementInter : public SetTest {
00158     public:
00160       ElementInter(const char* t)
00161         : SetTest(t,5,ds_12,false) {}
00163       virtual bool solution(const SetAssignment& x) const {
00164         int selected = 0;
00165         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00166              ++sel2, selected++) {}
00167         CountableSetRanges x4r(x.lub, x[4]);
00168         if (selected==0)
00169           return Iter::Ranges::size(x4r)==Gecode::Set::Limits::card;
00170         CountableSetRanges* sel = new CountableSetRanges[selected];
00171         CountableSetValues selector(x.lub, x[3]);
00172         for (int i=selected; i--;++selector) {
00173           if (selector.val()>=3 || selector.val()<0) {
00174             delete[] sel;
00175             return false;
00176           }
00177           sel[i].init(x.lub, x[selector.val()]);
00178         }
00179         Iter::Ranges::NaryInter<CountableSetRanges> u(sel, selected);
00180 
00181         CountableSetRanges z(x.lub, x[4]);
00182         bool ret = Iter::Ranges::equal(u, z);
00183         delete[] sel;
00184         return ret;
00185       }
00187       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00188         SetVarArgs xs(x.size()-2);
00189         for (int i=x.size()-2; i--;)
00190           xs[i]=x[i];
00191         Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
00192       }
00193     };
00194     ElementInter _elementinter("Element::Inter");
00195 
00197     class ElementInterIn : public SetTest {
00198     public:
00200       ElementInterIn(const char* t)
00201         : SetTest(t,5,ds_12,false) {}
00203       virtual bool solution(const SetAssignment& x) const {
00204         int selected = 0;
00205         for (CountableSetValues sel2(x.lub, x[3]); sel2();
00206              ++sel2, selected++) {}
00207         CountableSetRanges x4r(x.lub, x[4]);
00208         if (selected==0)
00209           return Iter::Ranges::size(x4r)==4;
00210         CountableSetRanges* sel = new CountableSetRanges[selected];
00211         CountableSetValues selector(x.lub, x[3]);
00212         for (int i=selected; i--;++selector) {
00213           if (selector.val()>=3 || selector.val()<0) {
00214             delete[] sel;
00215             return false;
00216           }
00217           sel[i].init(x.lub, x[selector.val()]);
00218         }
00219         Iter::Ranges::NaryInter<CountableSetRanges> u(sel, selected);
00220 
00221         CountableSetRanges z(x.lub, x[4]);
00222         bool ret = Iter::Ranges::equal(u, z);
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         FakeSpace* fs = new FakeSpace;
00269         {
00270           Region r(*fs);
00271           Iter::Ranges::NaryUnion<CountableSetRanges> u(r, sel, selected);
00272           ret = Iter::Ranges::size(u) == cardsum;
00273           u.reset();
00274           CountableSetRanges z(x.lub, x[4]);
00275           ret &= Iter::Ranges::equal(u, z);
00276         }
00277         delete fs;
00278         delete[] sel;
00279         return ret;
00280       }
00282       virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
00283         SetVarArgs xs(x.size()-2);
00284         for (int i=x.size()-2; i--;)
00285           xs[i]=x[i];
00286         Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
00287       }
00288     };
00289     ElementDisjoint _elementdisjoint("Element::Disjoint");
00290 
00292     class ElementSet : public SetTest {
00293     public:
00295       ElementSet(const char* t)
00296         : SetTest(t,4,ds_12,false,true) {}
00298       virtual bool solution(const SetAssignment& x) const {
00299         if (x.intval() < 0 || x.intval() > 2)
00300           return false;
00301         CountableSetRanges z(x.lub, x[3]);
00302         CountableSetRanges y(x.lub, x[x.intval()]);
00303         return Iter::Ranges::equal(y, z);
00304       }
00306       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00307         SetVarArgs xs(x.size()-1);
00308         for (int i=x.size()-1; i--;)
00309           xs[i]=x[i];
00310         Gecode::element(home, xs, y[0], x[x.size()-1]);
00311       }
00312     };
00313     ElementSet _elementset("Element::Set");
00314 
00316     class ElementSetConst : public SetTest {
00317     private:
00318       const IntSet i0;
00319       const IntSet i1;
00320       const IntSet i2;
00321     public:
00323       ElementSetConst(const char* t)
00324         : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
00326       virtual bool solution(const SetAssignment& x) const {
00327         if (x.intval() < 0 || x.intval() > 2)
00328           return false;
00329         CountableSetRanges xr(x.lub, x[0]);
00330         IntSet iss[] = {i0, i1, i2};
00331         IntSetRanges isr(iss[x.intval()]);
00332         return Iter::Ranges::equal(xr, isr);
00333       }
00335       virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
00336         IntSetArgs xs(3);
00337         xs[0] = i0; xs[1] = i1; xs[2] = i2;
00338         Gecode::element(home, xs, y[0], x[0]);
00339       }
00340     };
00341     ElementSetConst _elementsetconst("Element::SetConst");
00342 
00344     class MatrixIntSet : public SetTest {
00345      protected:
00347        Gecode::IntSetArgs tm;
00348      public:
00350        MatrixIntSet(void)
00351          : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2), 
00352            tm(4) {
00353          tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
00354          tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
00355        }
00357        virtual bool solution(const SetAssignment& x) const {
00358          // Get integer assignment
00359          const Int::Assignment& y = x.ints();
00360          // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
00361          using namespace Gecode;
00362          if ((y[0] > 1) || (y[1] > 1))
00363            return false;
00364          Matrix<IntSetArgs> m(tm,2,2);
00365          IntSetRanges a(m(y[0],y[1]));
00366          CountableSetRanges b(x.lub, x[0]);
00367          return Iter::Ranges::equal(a,b);
00368        }
00370        virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00371                          Gecode::IntVarArray& y) {
00372          // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
00373          using namespace Gecode;
00374          Matrix<IntSetArgs> m(tm,2,2);
00375          element(home, m, y[0], y[1], x[0]);
00376        }
00377      };
00378 
00379     MatrixIntSet _emis;
00380 
00382 
00383 }}}
00384 
00385 // STATISTICS: test-set