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
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