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