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 bool subsumed(bool b);
00248 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
00250 void cardinality(int i, int cmin, int cmax);
00252 void rel(int i, Gecode::IntRelType irt, int n);
00254 void rel(bool sol);
00256 void assign(const SetAssignment& a);
00258 bool assigned(void) const;
00260 void removeFromLub(int v, int i, const SetAssignment& a);
00262 void removeFromLub(int v, int i, const SetAssignment& a,
00263 SetTestSpace& c);
00265 void addToGlb(int v, int i, const SetAssignment& a);
00267 void addToGlb(int v, int i, const SetAssignment& a,
00268 SetTestSpace& c);
00270 bool fixprob(void);
00272 bool prune(const SetAssignment& a);
00274 unsigned int propagators(void);
00276 void disable(void);
00278 void enable(void);
00280 bool disabled(const SetAssignment& a, SetTestSpace& c);
00282 bool same(SetTestSpace& c);
00283 };
00284
00289 class SetTest : public Base {
00290 private:
00292 int arity;
00294 Gecode::IntSet lub;
00296 bool reified;
00298 int withInt;
00299
00301 void removeFromLub(int v, Gecode::SetVar& x, int i,
00302 const Gecode::IntSet& a);
00304 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
00306 SetAssignment* make_assignment(void);
00307 protected:
00309 bool disabled;
00311 bool testsubsumed;
00312 public:
00320 SetTest(const std::string& s,
00321 int a, const Gecode::IntSet& d, bool r=false, int w=0)
00322 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
00323 disabled(true), testsubsumed(true) {}
00325 virtual bool solution(const SetAssignment&) const = 0;
00327 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
00328 Gecode::IntVarArray& y) = 0;
00330 virtual void post(Gecode::Space&, Gecode::SetVarArray&,
00331 Gecode::IntVarArray&, Gecode::Reify) {}
00333 virtual bool run(void);
00334
00336
00337
00338 static std::string str(Gecode::SetRelType srt);
00340 static std::string str(Gecode::SetOpType srt);
00342 static std::string str(int i);
00344 static std::string str(const Gecode::IntArgs& i);
00346 };
00348
00350 class SetRelTypes {
00351 private:
00353 static const Gecode::SetRelType srts[6];
00355 int i;
00356 public:
00358 SetRelTypes(void);
00360 bool operator()(void) const;
00362 void operator++(void);
00364 Gecode::SetRelType srt(void) const;
00365 };
00366
00368 class SetOpTypes {
00369 private:
00371 static const Gecode::SetOpType sots[4];
00373 int i;
00374 public:
00376 SetOpTypes(void);
00378 bool operator()(void) const;
00380 void operator++(void);
00382 Gecode::SetOpType sot(void) const;
00383 };
00384
00385 }}
00386
00391 std::ostream&
00392 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
00393
00394 #include "test/set.hpp"
00395
00396 #endif
00397
00398