distinct.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Mikael Lagerkvist <lagerkvist@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2005 00009 * Mikael Lagerkvist, 2006 00010 * 00011 * Last modified: 00012 * $Date: 2010-06-04 16:13:00 +0200 (Fri, 04 Jun 2010) $ by $Author: schulte $ 00013 * $Revision: 11028 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 "::Sparse::"+str(icl),6,d0,false,icl), d(d0) {} 00063 Distinct(int min, int max, Gecode::IntConLevel icl) 00064 : Test(std::string(useCount ? "Count::Distinct" : "Distinct")+ 00065 "::Dense::"+str(icl),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 // STATISTICS: test-int