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-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $ 00013 * $Revision: 11390 $ 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 00057 00058 class FakeSpace : public Gecode::Space { 00059 public: 00061 FakeSpace(void) {} 00063 virtual Gecode::Space* copy(bool share) { 00064 return NULL; 00065 } 00066 }; 00067 00073 00075 class CountableSetValues { 00076 private: 00077 Gecode::IntSetValues dv; 00078 int cur; 00079 int i; 00080 public: 00082 CountableSetValues(void) {} 00084 CountableSetValues(const Gecode::IntSet& d0, int cur0) 00085 : dv(d0), cur(cur0), i(1) { 00086 if (! (i & cur)) 00087 operator++(); 00088 } 00090 void init(const Gecode::IntSet& d0, int cur0) { 00091 dv = d0; 00092 cur = cur0; 00093 i = 1; 00094 if (! (i & cur)) 00095 operator++(); 00096 } 00098 bool operator()(void) const { 00099 return i<=cur; 00100 } 00102 void operator++(void) { 00103 do { 00104 ++dv; 00105 i = i<<1; 00106 } while (! (i & cur) && i<cur); 00107 } 00109 int val(void) const { return dv.val(); } 00110 }; 00111 00113 class CountableSetRanges 00114 : public Gecode::Iter::Values::ToRanges<CountableSetValues> { 00115 private: 00117 CountableSetValues v; 00118 public: 00120 CountableSetRanges(void) {} 00122 CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) { 00123 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v); 00124 } 00126 void init(const Gecode::IntSet& d, int cur) { 00127 v.init(d, cur); 00128 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v); 00129 } 00130 }; 00131 00133 class CountableSet { 00134 private: 00136 Gecode::IntSet d; 00138 unsigned int cur; 00140 unsigned int lubmax; 00141 public: 00143 CountableSet(const Gecode::IntSet& s); 00145 CountableSet(void) {} 00147 void init(const Gecode::IntSet& s); 00149 bool operator()(void) const { return cur<lubmax; } 00151 void operator++(void); 00153 int val(void) const; 00154 }; 00155 00157 class SetAssignment { 00158 private: 00160 int n; 00162 CountableSet* dsv; 00164 Test::Int::CpltAssignment ir; 00166 bool done; 00167 public: 00169 Gecode::IntSet lub; 00171 int withInt; 00173 SetAssignment(int n, const Gecode::IntSet& d, int i = 0); 00175 bool operator()(void) const { return !done; } 00177 void operator++(void); 00179 int operator[](int i) const { 00180 assert((i>=0) && (i<n)); 00181 return dsv[i].val(); 00182 } 00184 int intval(void) const { return ir[0]; } 00186 const Test::Int::Assignment& ints(void) const { return ir; } 00188 int size(void) const { return n; } 00190 ~SetAssignment(void) { delete [] dsv; } 00191 }; 00192 00193 00194 class SetTest; 00195 00197 class SetTestSpace : public Gecode::Space { 00198 public: 00200 Gecode::IntSet d; 00202 Gecode::SetVarArray x; 00204 Gecode::IntVarArray y; 00206 int withInt; 00208 Gecode::BoolVar b; 00210 bool reified; 00212 SetTest* test; 00213 00223 SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t, 00224 bool log=true); 00226 SetTestSpace(bool share, SetTestSpace& s); 00228 virtual Gecode::Space* copy(bool share); 00230 void post(void); 00232 bool failed(void); 00234 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is); 00236 void cardinality(int i, int cmin, int cmax); 00238 void rel(int i, Gecode::IntRelType irt, int n); 00240 void rel(bool sol); 00242 void assign(const SetAssignment& a); 00244 bool assigned(void) const; 00246 void removeFromLub(int v, int i, const SetAssignment& a); 00248 void addToGlb(int v, int i, const SetAssignment& a); 00250 bool fixprob(void); 00252 bool prune(const SetAssignment& a); 00253 }; 00254 00259 class SetTest : public Base { 00260 private: 00262 int arity; 00264 Gecode::IntSet lub; 00266 bool reified; 00268 int withInt; 00269 00271 void removeFromLub(int v, Gecode::SetVar& x, int i, 00272 const Gecode::IntSet& a); 00274 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a); 00275 SetAssignment* make_assignment(void); 00276 public: 00284 SetTest(const std::string& s, 00285 int a, const Gecode::IntSet& d, bool r=false, int w=0) 00286 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w) {} 00288 virtual bool solution(const SetAssignment&) const = 0; 00290 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x, 00291 Gecode::IntVarArray& y) = 0; 00293 virtual void post(Gecode::Space&, Gecode::SetVarArray&, 00294 Gecode::IntVarArray&, Gecode::BoolVar) {} 00296 virtual bool run(void); 00297 00299 00300 00301 static std::string str(Gecode::SetRelType srt); 00303 static std::string str(Gecode::SetOpType srt); 00305 static std::string str(int i); 00307 }; 00309 00311 class SetRelTypes { 00312 private: 00314 static const Gecode::SetRelType srts[6]; 00316 int i; 00317 public: 00319 SetRelTypes(void); 00321 bool operator()(void) const; 00323 void operator++(void); 00325 Gecode::SetRelType srt(void) const; 00326 }; 00327 00329 class SetOpTypes { 00330 private: 00332 static const Gecode::SetOpType sots[4]; 00334 int i; 00335 public: 00337 SetOpTypes(void); 00339 bool operator()(void) const; 00341 void operator++(void); 00343 Gecode::SetOpType sot(void) const; 00344 }; 00345 00346 }} 00347 00352 std::ostream& 00353 operator<<(std::ostream&, const Test::Set::SetAssignment& a); 00354 00355 #include "test/set.hpp" 00356 00357 #endif 00358 00359 // STATISTICS: test-set