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 public:
00057 Distinct(const Gecode::IntSet& d0, Gecode::IntConLevel icl,
00058 int n=6)
00059 : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00060 str(icl)+"::Sparse::"+str(n),n,d0,false,icl) {}
00062 Distinct(int min, int max, Gecode::IntConLevel icl)
00063 : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00064 str(icl)+"::Dense",6,min,max,false,icl) {}
00066 virtual bool solution(const Assignment& x) const {
00067 for (int i=0; i<x.size(); i++)
00068 for (int j=i+1; j<x.size(); j++)
00069 if (x[i]==x[j])
00070 return false;
00071 return true;
00072 }
00074 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00075 if (!useCount) {
00076 Gecode::distinct(home, x, icl);
00077 } else {
00078 Gecode::IntSetRanges dr(dom);
00079 int i = 0;
00080 Gecode::IntArgs ia(Gecode::Iter::Ranges::size(dr));
00081 for (Gecode::IntSetValues dr2(dom); dr2(); ++dr2)
00082 ia[i++] = dr2.val();
00083 Gecode::count(home, x, Gecode::IntSet(0,1), ia, icl);
00084 }
00085 }
00086 };
00087
00089 class Offset : public Test {
00090 public:
00092 Offset(const Gecode::IntSet& d, Gecode::IntConLevel icl)
00093 : Test("Distinct::Offset::Sparse::"+str(icl),6,d,false,icl) {}
00095 Offset(int min, int max, Gecode::IntConLevel icl)
00096 : Test("Distinct::Offset::Dense::"+str(icl),6,min,max,false,icl) {}
00098 virtual bool solution(const Assignment& x) const {
00099 for (int i=0; i<x.size(); i++)
00100 for (int j=i+1; j<x.size(); j++)
00101 if (x[i]+i==x[j]+j)
00102 return false;
00103 return true;
00104 }
00106 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00107 Gecode::IntArgs c(x.size());
00108 for (int i=0; i<x.size(); i++)
00109 c[i]=i;
00110 Gecode::distinct(home, c, x, icl);
00111 }
00112 };
00113
00115 class Random : public Test {
00116 public:
00118 Random(int n, int min, int max, Gecode::IntConLevel icl)
00119 : Test("Distinct::Random::"+str(icl),n,min,max,false,icl) {
00120 testsearch = false;
00121 }
00123 virtual Assignment* assignment(void) const {
00124 return new RandomAssignment(arity,dom,100);
00125 }
00127 virtual bool solution(const Assignment& x) const {
00128 for (int i=0; i<x.size(); i++)
00129 for (int j=i+1; j<x.size(); j++)
00130 if (x[i]==x[j])
00131 return false;
00132 return true;
00133 }
00135 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00136 Gecode::distinct(home, x, icl);
00137 }
00138 };
00139
00141 class Pathological : public Base {
00142 protected:
00144 int n;
00146 Gecode::IntConLevel icl;
00148 class TestSpace : public Gecode::Space {
00149 public:
00151 TestSpace(void) {}
00153 TestSpace(bool share, TestSpace& s)
00154 : Gecode::Space(share,s) {}
00156 virtual Gecode::Space* copy(bool share) {
00157 return new TestSpace(share,*this);
00158 }
00159 };
00160 public:
00162 Pathological(int n0, Gecode::IntConLevel icl0)
00163 : Base("Int::Distinct::Pathological::"+
00164 Test::str(n0)+"::"+Test::str(icl0)), n(n0), icl(icl0) {}
00166 virtual bool run(void) {
00167 using namespace Gecode;
00168 {
00169 TestSpace* s = new TestSpace;
00170 IntVarArgs x(n);
00171 for (int i=0; i<n; i++)
00172 x[i] = IntVar(*s,0,i);
00173 distinct(*s,x,icl);
00174 if (s->status() == SS_FAILED) {
00175 delete s; return false;
00176 }
00177 for (int i=0; i<n; i++)
00178 if (!x[i].assigned() || (x[i].val() != i)) {
00179 delete s; return false;
00180 }
00181 delete s;
00182 }
00183 {
00184 TestSpace* s = new TestSpace;
00185 IntVarArgs x(2*n);
00186 for (int i=0; i<n; i++) {
00187 int v[] = {0,i};
00188 IntSet d(v,2);
00189 x[i] = IntVar(*s,d);
00190 }
00191 for (int i=n; i<2*n; i++)
00192 x[i] = IntVar(*s,n-1,i);
00193 distinct(*s,x,icl);
00194 if (s->status() == SS_FAILED) {
00195 delete s; return false;
00196 }
00197 for (int i=0; i<n; i++)
00198 if (!x[i].assigned() || (x[i].val() != i)) {
00199 delete s; return false;
00200 }
00201 delete s;
00202 }
00203 return true;
00204 }
00205 };
00206
00207 const int v[7] = {-1001,-1000,-10,0,10,1000,1001};
00208 Gecode::IntSet d(v,7);
00209 const int vl[6] = {Gecode::Int::Limits::min+0,
00210 Gecode::Int::Limits::min+1,
00211 Gecode::Int::Limits::min+2,
00212 Gecode::Int::Limits::max-2,
00213 Gecode::Int::Limits::max-1,
00214 Gecode::Int::Limits::max-0};
00215 Gecode::IntSet dl(vl,6);
00216
00217 Distinct<false> dom_d(-3,3,Gecode::ICL_DOM);
00218 Distinct<false> bnd_d(-3,3,Gecode::ICL_BND);
00219 Distinct<false> val_d(-3,3,Gecode::ICL_VAL);
00220 Distinct<false> dom_s(d,Gecode::ICL_DOM);
00221 Distinct<false> bnd_s(d,Gecode::ICL_BND);
00222 Distinct<false> val_s(d,Gecode::ICL_VAL);
00223
00224 Distinct<false> dom_l(dl,Gecode::ICL_DOM,5);
00225 Distinct<false> bnd_l(dl,Gecode::ICL_BND,5);
00226 Distinct<false> val_l(dl,Gecode::ICL_VAL,5);
00227
00228 Distinct<true> count_dom_d(-3,3,Gecode::ICL_DOM);
00229 Distinct<true> count_bnd_d(-3,3,Gecode::ICL_BND);
00230 Distinct<true> count_val_d(-3,3,Gecode::ICL_VAL);
00231 Distinct<true> count_dom_s(d,Gecode::ICL_DOM);
00232 Distinct<true> count_bnd_s(d,Gecode::ICL_BND);
00233 Distinct<true> count_val_s(d,Gecode::ICL_VAL);
00234
00235 Offset dom_od(-3,3,Gecode::ICL_DOM);
00236 Offset bnd_od(-3,3,Gecode::ICL_BND);
00237 Offset val_od(-3,3,Gecode::ICL_VAL);
00238 Offset dom_os(d,Gecode::ICL_DOM);
00239 Offset bnd_os(d,Gecode::ICL_BND);
00240 Offset val_os(d,Gecode::ICL_VAL);
00241
00242 Random dom_r(20,-50,50,Gecode::ICL_DOM);
00243 Random bnd_r(50,-500,500,Gecode::ICL_BND);
00244 Random val_r(50,-500,500,Gecode::ICL_VAL);
00245
00246 Pathological p_16_v(16,Gecode::ICL_VAL);
00247 Pathological p_16_b(16,Gecode::ICL_BND);
00248 Pathological p_16_d(16,Gecode::ICL_DOM);
00249
00250 Pathological p_32_v(32,Gecode::ICL_VAL);
00251 Pathological p_32_b(32,Gecode::ICL_BND);
00252 Pathological p_32_d(32,Gecode::ICL_DOM);
00254
00255 }
00256 }}
00257
00258