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 (void) share;
00065 return NULL;
00066 }
00067 };
00068
00074
00076 class CountableSetValues {
00077 private:
00078 Gecode::IntSetValues dv;
00079 int cur;
00080 int i;
00081 public:
00083 CountableSetValues(void) {}
00085 CountableSetValues(const Gecode::IntSet& d0, int cur0)
00086 : dv(d0), cur(cur0), i(1) {
00087 if (! (i & cur))
00088 operator++();
00089 }
00091 void init(const Gecode::IntSet& d0, int cur0) {
00092 dv = d0;
00093 cur = cur0;
00094 i = 1;
00095 if (! (i & cur))
00096 operator++();
00097 }
00099 bool operator()(void) const {
00100 return i<=cur;
00101 }
00103 void operator++(void) {
00104 do {
00105 ++dv;
00106 i = i<<1;
00107 } while (! (i & cur) && i<cur);
00108 }
00110 int val(void) const { return dv.val(); }
00111 };
00112
00114 class CountableSetRanges
00115 : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
00116 private:
00118 CountableSetValues v;
00119 public:
00121 CountableSetRanges(void) {}
00123 CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
00124 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00125 }
00127 void init(const Gecode::IntSet& d, int cur) {
00128 v.init(d, cur);
00129 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00130 }
00131 };
00132
00134 class CountableSet {
00135 private:
00137 Gecode::IntSet d;
00139 unsigned int cur;
00141 unsigned int lubmax;
00142 public:
00144 CountableSet(const Gecode::IntSet& s);
00146 CountableSet(void) {}
00148 void init(const Gecode::IntSet& s);
00150 bool operator()(void) const { return cur<lubmax; }
00152 void operator++(void);
00154 int val(void) const;
00155 };
00156
00158 class SetAssignment {
00159 private:
00161 int n;
00163 CountableSet* dsv;
00165 Test::Int::CpltAssignment ir;
00167 bool done;
00168 public:
00170 Gecode::IntSet lub;
00172 int withInt;
00174 SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
00176 bool operator()(void) const { return !done; }
00178 void operator++(void);
00180 int operator[](int i) const {
00181 assert((i>=0) && (i<n));
00182 return dsv[i].val();
00183 }
00185 int intval(void) const { return ir[0]; }
00187 const Test::Int::Assignment& ints(void) const { return ir; }
00189 int size(void) const { return n; }
00191 ~SetAssignment(void) { delete [] dsv; }
00192 };
00193
00194
00195 class SetTest;
00196
00198 class SetTestSpace : public Gecode::Space {
00199 public:
00201 Gecode::IntSet d;
00203 Gecode::SetVarArray x;
00205 Gecode::IntVarArray y;
00207 int withInt;
00209 Gecode::BoolVar b;
00211 bool reified;
00213 SetTest* test;
00214
00224 SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t,
00225 bool log=true);
00227 SetTestSpace(bool share, SetTestSpace& s);
00229 virtual Gecode::Space* copy(bool share);
00231 void post(void);
00233 bool failed(void);
00235 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00237 void cardinality(int i, int cmin, int cmax);
00239 void rel(int i, Gecode::IntRelType irt, int n);
00241 void rel(bool sol);
00243 void assign(const SetAssignment& a);
00245 bool assigned(void) const;
00247 void removeFromLub(int v, int i, const SetAssignment& a);
00249 void addToGlb(int v, int i, const SetAssignment& a);
00251 bool fixprob(void);
00253 bool prune(const SetAssignment& a);
00254 };
00255
00260 class SetTest : public Base {
00261 private:
00263 int arity;
00265 Gecode::IntSet lub;
00267 bool reified;
00269 int withInt;
00270
00272 void removeFromLub(int v, Gecode::SetVar& x, int i,
00273 const Gecode::IntSet& a);
00275 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00276 SetAssignment* make_assignment(void);
00277 public:
00285 SetTest(const std::string& s,
00286 int a, const Gecode::IntSet& d, bool r=false, int w=0)
00287 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w) {}
00289 virtual bool solution(const SetAssignment&) const = 0;
00291 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00292 Gecode::IntVarArray& y) = 0;
00294 virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00295 Gecode::IntVarArray&, Gecode::BoolVar) {}
00297 virtual bool run(void);
00298
00300
00301
00302 static std::string str(Gecode::SetRelType srt);
00304 static std::string str(Gecode::SetOpType srt);
00306 static std::string str(int i);
00308 static std::string str(const Gecode::IntArgs& i);
00310 };
00312
00314 class SetRelTypes {
00315 private:
00317 static const Gecode::SetRelType srts[6];
00319 int i;
00320 public:
00322 SetRelTypes(void);
00324 bool operator()(void) const;
00326 void operator++(void);
00328 Gecode::SetRelType srt(void) const;
00329 };
00330
00332 class SetOpTypes {
00333 private:
00335 static const Gecode::SetOpType sots[4];
00337 int i;
00338 public:
00340 SetOpTypes(void);
00342 bool operator()(void) const;
00344 void operator++(void);
00346 Gecode::SetOpType sot(void) const;
00347 };
00348
00349 }}
00350
00355 std::ostream&
00356 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00357
00358 #include "test/set.hpp"
00359
00360 #endif
00361
00362