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