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 #ifndef __GECODE_TEST_SET_HH__
00037 #define __GECODE_TEST_SET_HH__
00038
00039 #include <gecode/set.hh>
00040 #include "test/test.hh"
00041 #include "test/int.hh"
00042
00043 namespace Test {
00044
00046 namespace Set {
00047
00058
00060 class CountableSetValues {
00061 private:
00062 Gecode::IntSetValues dv;
00063 int cur;
00064 int i;
00065 public:
00067 CountableSetValues(void) {}
00069 CountableSetValues(const Gecode::IntSet& d0, int cur0)
00070 : dv(d0), cur(cur0), i(1) {
00071 if (! (i & cur))
00072 operator++();
00073 }
00075 void init(const Gecode::IntSet& d0, int cur0) {
00076 dv = d0;
00077 cur = cur0;
00078 i = 1;
00079 if (! (i & cur))
00080 operator++();
00081 }
00083 bool operator()(void) const {
00084 return i<=cur;
00085 }
00087 void operator++(void) {
00088 do {
00089 ++dv;
00090 i = i<<1;
00091 } while (! (i & cur) && i<cur);
00092 }
00094 int val(void) const { return dv.val(); }
00095 };
00096
00098 class CountableSetRanges
00099 : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
00100 private:
00102 CountableSetValues v;
00103 public:
00105 CountableSetRanges(void) {}
00107 CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
00108 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00109 }
00111 void init(const Gecode::IntSet& d, int cur) {
00112 v.init(d, cur);
00113 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
00114 }
00115 };
00116
00118 class CountableSet {
00119 private:
00121 Gecode::IntSet d;
00123 unsigned int cur;
00125 unsigned int lubmax;
00126 public:
00128 CountableSet(const Gecode::IntSet& s);
00130 CountableSet(void) {}
00132 void init(const Gecode::IntSet& s);
00134 bool operator()(void) const { return cur<lubmax; }
00136 void operator++(void);
00138 int val(void) const;
00139 };
00140
00142 class SetAssignment {
00143 private:
00145 int n;
00147 CountableSet* dsv;
00149 Test::Int::CpltAssignment ir;
00151 bool done;
00152 public:
00154 Gecode::IntSet lub;
00156 int withInt;
00158 SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
00160 bool operator()(void) const { return !done; }
00162 void operator++(void);
00164 int operator[](int i) const {
00165 assert((i>=0) && (i<n));
00166 return dsv[i].val();
00167 }
00169 int intval(void) const { return ir[0]; }
00171 const Test::Int::Assignment& ints(void) const { return ir; }
00173 int size(void) const { return n; }
00175 ~SetAssignment(void) { delete [] dsv; }
00176 };
00177
00178
00179 class SetTest;
00180
00182 class SetTestSpace : public Gecode::Space {
00183 public:
00185 Gecode::IntSet d;
00187 Gecode::SetVarArray x;
00189 Gecode::IntVarArray y;
00191 int withInt;
00193 Gecode::Reify r;
00195 bool reified;
00197 SetTest* test;
00198
00208 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00209 bool log=true);
00219 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
00220 Gecode::ReifyMode rm, bool log=true);
00222 SetTestSpace(SetTestSpace& s);
00224 virtual Gecode::Space* copy(void);
00226 void post(void);
00228 bool failed(void);
00230 bool subsumed(bool b);
00232 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00234 void cardinality(int i, int cmin, int cmax);
00236 void rel(int i, Gecode::IntRelType irt, int n);
00238 void rel(bool sol);
00240 void assign(const SetAssignment& a);
00242 bool assigned(void) const;
00244 void removeFromLub(int v, int i, const SetAssignment& a);
00246 void removeFromLub(int v, int i, const SetAssignment& a,
00247 SetTestSpace& c);
00249 void addToGlb(int v, int i, const SetAssignment& a);
00251 void addToGlb(int v, int i, const SetAssignment& a,
00252 SetTestSpace& c);
00254 bool fixprob(void);
00256 bool prune(const SetAssignment& a);
00258 unsigned int propagators(void);
00260 void disable(void);
00262 void enable(void);
00264 bool disabled(const SetAssignment& a, SetTestSpace& c);
00266 bool same(SetTestSpace& c);
00267 };
00268
00273 class SetTest : public Base {
00274 private:
00276 int arity;
00278 Gecode::IntSet lub;
00280 bool reified;
00282 int withInt;
00283
00285 void removeFromLub(int v, Gecode::SetVar& x, int i,
00286 const Gecode::IntSet& a);
00288 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00290 SetAssignment* make_assignment(void);
00291 protected:
00293 bool disabled;
00295 bool testsubsumed;
00296 public:
00304 SetTest(const std::string& s,
00305 int a, const Gecode::IntSet& d, bool r=false, int w=0)
00306 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
00307 disabled(true), testsubsumed(true) {}
00309 virtual bool solution(const SetAssignment&) const = 0;
00311 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00312 Gecode::IntVarArray& y) = 0;
00314 virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00315 Gecode::IntVarArray&, Gecode::Reify) {}
00317 virtual bool run(void);
00318
00320
00321
00322 static std::string str(Gecode::SetRelType srt);
00324 static std::string str(Gecode::SetOpType srt);
00326 static std::string str(int i);
00328 static std::string str(const Gecode::IntArgs& i);
00330 };
00332
00334 class SetRelTypes {
00335 private:
00337 static const Gecode::SetRelType srts[6];
00339 int i;
00340 public:
00342 SetRelTypes(void);
00344 bool operator()(void) const;
00346 void operator++(void);
00348 Gecode::SetRelType srt(void) const;
00349 };
00350
00352 class SetOpTypes {
00353 private:
00355 static const Gecode::SetOpType sots[4];
00357 int i;
00358 public:
00360 SetOpTypes(void);
00362 bool operator()(void) const;
00364 void operator++(void);
00366 Gecode::SetOpType sot(void) const;
00367 };
00368
00369 }}
00370
00375 std::ostream&
00376 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00377
00378 #include "test/set.hpp"
00379
00380 #endif
00381
00382