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 #include "test/int.hh"
00041
00042 namespace Test { namespace Int {
00043
00045 namespace Distinct {
00046
00052
00053 template<bool useCount>
00054 class Distinct : public Test {
00055 private:
00056 Gecode::IntSet d;
00057 public:
00059 Distinct(const Gecode::IntSet& d0, Gecode::IntConLevel icl)
00060 : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00061 str(icl)+"::Sparse",6,d0,false,icl), d(d0) {}
00063 Distinct(int min, int max, Gecode::IntConLevel icl)
00064 : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00065 str(icl)+"::Dense",6,min,max,false,icl), d(min,max) {}
00067 virtual bool solution(const Assignment& x) const {
00068 for (int i=0; i<x.size(); i++)
00069 for (int j=i+1; j<x.size(); j++)
00070 if (x[i]==x[j])
00071 return false;
00072 return true;
00073 }
00075 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00076 if (!useCount) {
00077 Gecode::distinct(home, x, icl);
00078 } else {
00079 Gecode::IntSetRanges dr(d);
00080 int i = 0;
00081 Gecode::IntArgs ia(Gecode::Iter::Ranges::size(dr));
00082 for (Gecode::IntSetValues dr2(d); dr2(); ++dr2)
00083 ia[i++] = dr2.val();
00084 Gecode::count(home, x, Gecode::IntSet(0,1), ia, icl);
00085 }
00086 }
00087 };
00088
00090 class Offset : public Test {
00091 public:
00093 Offset(const Gecode::IntSet& d, Gecode::IntConLevel icl)
00094 : Test("Distinct::Offset::Sparse::"+str(icl),6,d,false,icl) {}
00096 Offset(int min, int max, Gecode::IntConLevel icl)
00097 : Test("Distinct::Offset::Dense::"+str(icl),6,min,max,false,icl) {}
00099 virtual bool solution(const Assignment& x) const {
00100 for (int i=0; i<x.size(); i++)
00101 for (int j=i+1; j<x.size(); j++)
00102 if (x[i]+i==x[j]+j)
00103 return false;
00104 return true;
00105 }
00107 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00108 Gecode::IntArgs c(x.size());
00109 for (int i=0; i<x.size(); i++)
00110 c[i]=i;
00111 Gecode::distinct(home, c, x, icl);
00112 }
00113 };
00114
00116 class Random : public Test {
00117 public:
00119 Random(int n, int min, int max, Gecode::IntConLevel icl)
00120 : Test("Distinct::Random::"+str(icl),n,min,max,false,icl) {
00121 testsearch = false;
00122 }
00124 virtual Assignment* assignment(void) const {
00125 return new RandomAssignment(arity,dom,100);
00126 }
00128 virtual bool solution(const Assignment& x) const {
00129 for (int i=0; i<x.size(); i++)
00130 for (int j=i+1; j<x.size(); j++)
00131 if (x[i]==x[j])
00132 return false;
00133 return true;
00134 }
00136 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00137 Gecode::distinct(home, x, icl);
00138 }
00139 };
00140
00142 class Pathological : public Base {
00143 protected:
00145 int n;
00147 Gecode::IntConLevel icl;
00149 class TestSpace : public Gecode::Space {
00150 public:
00152 TestSpace(void) {}
00154 TestSpace(bool share, TestSpace& s)
00155 : Gecode::Space(share,s) {}
00157 virtual Gecode::Space* copy(bool share) {
00158 return new TestSpace(share,*this);
00159 }
00160 };
00161 public:
00163 Pathological(int n0, Gecode::IntConLevel icl0)
00164 : Base("Int::Distinct::Pathological::"+
00165 Test::str(n0)+"::"+Test::str(icl0)), n(n0), icl(icl0) {}
00167 virtual bool run(void) {
00168 using namespace Gecode;
00169 {
00170 TestSpace* s = new TestSpace;
00171 IntVarArgs x(n);
00172 for (int i=0; i<n; i++)
00173 x[i] = IntVar(*s,0,i);
00174 distinct(*s,x,icl);
00175 if (s->status() == SS_FAILED) {
00176 delete s; return false;
00177 }
00178 for (int i=0; i<n; i++)
00179 if (!x[i].assigned() || (x[i].val() != i)) {
00180 delete s; return false;
00181 }
00182 delete s;
00183 }
00184 {
00185 TestSpace* s = new TestSpace;
00186 IntVarArgs x(2*n);
00187 for (int i=0; i<n; i++) {
00188 int v[] = {0,i};
00189 IntSet d(v,2);
00190 x[i] = IntVar(*s,d);
00191 }
00192 for (int i=n; i<2*n; i++)
00193 x[i] = IntVar(*s,n-1,i);
00194 distinct(*s,x,icl);
00195 if (s->status() == SS_FAILED) {
00196 delete s; return false;
00197 }
00198 for (int i=0; i<n; i++)
00199 if (!x[i].assigned() || (x[i].val() != i)) {
00200 delete s; return false;
00201 }
00202 delete s;
00203 }
00204 return true;
00205 }
00206 };
00207
00208 const int v[7] = {-1001,-1000,-10,0,10,1000,1001};
00209 Gecode::IntSet d(v,7);
00210
00211 Distinct<false> dom_d(-3,3,Gecode::ICL_DOM);
00212 Distinct<false> bnd_d(-3,3,Gecode::ICL_BND);
00213 Distinct<false> val_d(-3,3,Gecode::ICL_VAL);
00214 Distinct<false> dom_s(d,Gecode::ICL_DOM);
00215 Distinct<false> bnd_s(d,Gecode::ICL_BND);
00216 Distinct<false> val_s(d,Gecode::ICL_VAL);
00217
00218 Distinct<true> count_dom_d(-3,3,Gecode::ICL_DOM);
00219 Distinct<true> count_bnd_d(-3,3,Gecode::ICL_BND);
00220 Distinct<true> count_val_d(-3,3,Gecode::ICL_VAL);
00221 Distinct<true> count_dom_s(d,Gecode::ICL_DOM);
00222 Distinct<true> count_bnd_s(d,Gecode::ICL_BND);
00223 Distinct<true> count_val_s(d,Gecode::ICL_VAL);
00224
00225 Offset dom_od(-3,3,Gecode::ICL_DOM);
00226 Offset bnd_od(-3,3,Gecode::ICL_BND);
00227 Offset val_od(-3,3,Gecode::ICL_VAL);
00228 Offset dom_os(d,Gecode::ICL_DOM);
00229 Offset bnd_os(d,Gecode::ICL_BND);
00230 Offset val_os(d,Gecode::ICL_VAL);
00231
00232 Random dom_r(20,-50,50,Gecode::ICL_DOM);
00233 Random bnd_r(50,-500,500,Gecode::ICL_BND);
00234 Random val_r(50,-500,500,Gecode::ICL_VAL);
00235
00236 Pathological p_16_v(16,Gecode::ICL_VAL);
00237 Pathological p_16_b(16,Gecode::ICL_BND);
00238 Pathological p_16_d(16,Gecode::ICL_DOM);
00239
00240 Pathological p_32_v(32,Gecode::ICL_VAL);
00241 Pathological p_32_b(32,Gecode::ICL_BND);
00242 Pathological p_32_d(32,Gecode::ICL_DOM);
00244
00245 }
00246 }}
00247
00248