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::Reify r;
00211 bool reified;
00213 SetTest* test;
00214
00224 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00225 bool log=true);
00235 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00236 Gecode::ReifyMode rm, bool log=true);
00238 SetTestSpace(bool share, SetTestSpace& s);
00240 virtual Gecode::Space* copy(bool share);
00242 void post(void);
00244 bool failed(void);
00246 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00248 void cardinality(int i, int cmin, int cmax);
00250 void rel(int i, Gecode::IntRelType irt, int n);
00252 void rel(bool sol);
00254 void assign(const SetAssignment& a);
00256 bool assigned(void) const;
00258 void removeFromLub(int v, int i, const SetAssignment& a);
00260 void addToGlb(int v, int i, const SetAssignment& a);
00262 bool fixprob(void);
00264 bool prune(const SetAssignment& a);
00265 };
00266
00271 class SetTest : public Base {
00272 private:
00274 int arity;
00276 Gecode::IntSet lub;
00278 bool reified;
00280 int withInt;
00281
00283 void removeFromLub(int v, Gecode::SetVar& x, int i,
00284 const Gecode::IntSet& a);
00286 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00287 SetAssignment* make_assignment(void);
00288 public:
00296 SetTest(const std::string& s,
00297 int a, const Gecode::IntSet& d, bool r=false, int w=0)
00298 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w) {}
00300 virtual bool solution(const SetAssignment&) const = 0;
00302 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00303 Gecode::IntVarArray& y) = 0;
00305 virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00306 Gecode::IntVarArray&, Gecode::Reify) {}
00308 virtual bool run(void);
00309
00311
00312
00313 static std::string str(Gecode::SetRelType srt);
00315 static std::string str(Gecode::SetOpType srt);
00317 static std::string str(int i);
00319 static std::string str(const Gecode::IntArgs& i);
00321 };
00323
00325 class SetRelTypes {
00326 private:
00328 static const Gecode::SetRelType srts[6];
00330 int i;
00331 public:
00333 SetRelTypes(void);
00335 bool operator()(void) const;
00337 void operator++(void);
00339 Gecode::SetRelType srt(void) const;
00340 };
00341
00343 class SetOpTypes {
00344 private:
00346 static const Gecode::SetOpType sots[4];
00348 int i;
00349 public:
00351 SetOpTypes(void);
00353 bool operator()(void) const;
00355 void operator++(void);
00357 Gecode::SetOpType sot(void) const;
00358 };
00359
00360 }}
00361
00366 std::ostream&
00367 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00368
00369 #include "test/set.hpp"
00370
00371 #endif
00372
00373