set.hh
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 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Copyright: 00008 * Guido Tack, 2005 00009 * Christian Schulte, 2005 00010 * 00011 * Last modified: 00012 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00013 * $Revision: 10684 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #ifndef __GECODE_TEST_SET_HH__ 00041 #define __GECODE_TEST_SET_HH__ 00042 00043 #include <gecode/set.hh> 00044 #include "test/test.hh" 00045 #include "test/int.hh" 00046 00047 namespace Test { 00048 00050 namespace Set { 00051 00062 00064 class CountableSetValues { 00065 private: 00066 Gecode::IntSetValues dv; 00067 int cur; 00068 int i; 00069 public: 00071 CountableSetValues(void) {} 00073 CountableSetValues(const Gecode::IntSet& d0, int cur0) 00074 : dv(d0), cur(cur0), i(1) { 00075 if (! (i & cur)) 00076 operator++(); 00077 } 00079 void init(const Gecode::IntSet& d0, int cur0) { 00080 dv = d0; 00081 cur = cur0; 00082 i = 1; 00083 if (! (i & cur)) 00084 operator++(); 00085 } 00087 bool operator()(void) const { 00088 return i<=cur; 00089 } 00091 void operator++(void) { 00092 do { 00093 ++dv; 00094 i = i<<1; 00095 } while (! (i & cur) && i<cur); 00096 } 00098 int val(void) const { return dv.val(); } 00099 }; 00100 00102 class CountableSetRanges 00103 : public Gecode::Iter::Values::ToRanges<CountableSetValues> { 00104 private: 00106 CountableSetValues v; 00107 public: 00109 CountableSetRanges(void) {} 00111 CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) { 00112 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v); 00113 } 00115 void init(const Gecode::IntSet& d, int cur) { 00116 v.init(d, cur); 00117 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v); 00118 } 00119 }; 00120 00122 class CountableSet { 00123 private: 00125 Gecode::IntSet d; 00127 unsigned int cur; 00129 unsigned int lubmax; 00130 public: 00132 CountableSet(const Gecode::IntSet& s); 00134 CountableSet(void) {} 00136 void init(const Gecode::IntSet& s); 00138 bool operator()(void) const { return cur<lubmax; } 00140 void operator++(void); 00142 int val(void) const; 00143 }; 00144 00146 class SetAssignment { 00147 private: 00149 int n; 00151 CountableSet* dsv; 00153 Test::Int::CpltAssignment ir; 00155 bool done; 00156 public: 00158 Gecode::IntSet lub; 00160 int withInt; 00162 SetAssignment(int n, const Gecode::IntSet& d, int i = 0); 00164 bool operator()(void) const { return !done; } 00166 void operator++(void); 00168 int operator[](int i) const { 00169 assert((i>=0) && (i<n)); 00170 return dsv[i].val(); 00171 } 00173 int intval(void) const { return ir[0]; } 00175 const Test::Int::Assignment& ints(void) const { return ir; } 00177 int size(void) const { return n; } 00179 ~SetAssignment(void) { delete [] dsv; } 00180 }; 00181 00182 00183 class SetTest; 00184 00186 class SetTestSpace : public Gecode::Space { 00187 public: 00189 Gecode::IntSet d; 00191 Gecode::SetVarArray x; 00193 Gecode::IntVarArray y; 00195 int withInt; 00197 Gecode::BoolVar b; 00199 bool reified; 00201 SetTest* test; 00202 00212 SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t, 00213 bool log=true); 00215 SetTestSpace(bool share, SetTestSpace& s); 00217 virtual Gecode::Space* copy(bool share); 00219 void post(void); 00221 bool failed(void); 00223 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is); 00225 void cardinality(int i, int cmin, int cmax); 00227 void rel(int i, Gecode::IntRelType irt, int n); 00229 void rel(bool sol); 00231 void assign(const SetAssignment& a); 00233 bool assigned(void) const; 00235 void removeFromLub(int v, int i, const SetAssignment& a); 00237 void addToGlb(int v, int i, const SetAssignment& a); 00239 bool fixprob(void); 00241 bool prune(const SetAssignment& a); 00242 }; 00243 00248 class SetTest : public Base { 00249 private: 00251 int arity; 00253 Gecode::IntSet lub; 00255 bool reified; 00257 int withInt; 00258 00260 void removeFromLub(int v, Gecode::SetVar& x, int i, 00261 const Gecode::IntSet& a); 00263 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a); 00264 SetAssignment* make_assignment(void); 00265 public: 00273 SetTest(const std::string& s, 00274 int a, const Gecode::IntSet& d, bool r=false, int w=0) 00275 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w) {} 00277 virtual bool solution(const SetAssignment&) const = 0; 00279 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x, 00280 Gecode::IntVarArray& y) = 0; 00282 virtual void post(Gecode::Space&, Gecode::SetVarArray&, 00283 Gecode::IntVarArray&, Gecode::BoolVar) {} 00285 virtual bool run(void); 00286 00288 00289 00290 static std::string str(Gecode::SetRelType srt); 00292 static std::string str(Gecode::SetOpType srt); 00294 static std::string str(int i); 00296 }; 00298 00300 class SetRelTypes { 00301 private: 00303 static const Gecode::SetRelType srts[6]; 00305 int i; 00306 public: 00308 SetRelTypes(void); 00310 bool operator()(void) const; 00312 void operator++(void); 00314 Gecode::SetRelType srt(void) const; 00315 }; 00316 00318 class SetOpTypes { 00319 private: 00321 static const Gecode::SetOpType sots[4]; 00323 int i; 00324 public: 00326 SetOpTypes(void); 00328 bool operator()(void) const; 00330 void operator++(void); 00332 Gecode::SetOpType sot(void) const; 00333 }; 00334 00335 }} 00336 00341 std::ostream& 00342 operator<<(std::ostream&, const Test::Set::SetAssignment& a); 00343 00344 #include "test/set.hpp" 00345 00346 #endif 00347 00348 // STATISTICS: test-set