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-05-31 13:53:25 +0200 (Mon, 31 May 2010) $ by $Author: tack $ 00011 * $Revision: 10995 $ 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