00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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