dom.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include "test/set.hh" 00039 00040 using namespace Gecode; 00041 00042 namespace Test { namespace Set { 00043 00045 namespace Dom { 00046 00052 00053 static const int d1r[4][2] = { 00054 {-4,-3},{-1,-1},{1,1},{3,5} 00055 }; 00056 static IntSet d1(d1r,4); 00057 00058 static const int d1cr[5][2] = { 00059 {Gecode::Set::Limits::min,-5}, 00060 {-2,-2},{0,0},{2,2}, 00061 {6,Gecode::Set::Limits::max} 00062 }; 00063 static IntSet d1c(d1cr,5); 00064 00065 static IntSet ds_33(-3,3); 00066 00067 static const int d2r[2][2] = { 00068 {Gecode::Set::Limits::min,-4}, {4,Gecode::Set::Limits::max} 00069 }; 00070 static IntSet ds_33c(d2r,2); 00071 static IntSet ds_55(-5,5); 00072 00074 class DomRange : public SetTest { 00075 private: 00076 Gecode::SetRelType srt; 00077 IntSet is; 00078 public: 00080 DomRange(SetRelType srt0) 00081 : SetTest("Dom::Range::"+str(srt0),1,ds_55,true), srt(srt0) 00082 , is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {} 00084 virtual bool solution(const SetAssignment& x) const { 00085 CountableSetRanges xr(x.lub, x[0]); 00086 IntSetRanges dr(is); 00087 switch (srt) { 00088 case SRT_EQ: return Iter::Ranges::equal(xr, dr); 00089 case SRT_NQ: return !Iter::Ranges::equal(xr, dr); 00090 case SRT_SUB: return Iter::Ranges::subset(xr, dr); 00091 case SRT_SUP: return Iter::Ranges::subset(dr, xr); 00092 case SRT_DISJ: 00093 { 00094 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges> 00095 inter(xr, dr); 00096 return !inter(); 00097 } 00098 case SRT_CMPL: 00099 { 00100 Gecode::Set::RangesCompl<IntSetRanges> drc(dr); 00101 return Iter::Ranges::equal(xr,drc); 00102 } 00103 } 00104 GECODE_NEVER; 00105 return false; 00106 } 00108 virtual void post(Space& home, SetVarArray& x, IntVarArray&) { 00109 Gecode::dom(home, x[0], srt, is); 00110 } 00112 virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) { 00113 Gecode::dom(home, x[0], srt, is, b); 00114 } 00115 }; 00116 DomRange _domrange_eq(SRT_EQ); 00117 DomRange _domrange_nq(SRT_NQ); 00118 DomRange _domrange_sub(SRT_SUB); 00119 DomRange _domrange_sup(SRT_SUP); 00120 DomRange _domrange_disj(SRT_DISJ); 00121 DomRange _domrange_cmpl(SRT_CMPL); 00122 00124 class DomIntRange : public SetTest { 00125 private: 00126 Gecode::SetRelType srt; 00127 public: 00129 DomIntRange(Gecode::SetRelType srt0) 00130 : SetTest("Dom::IntRange::"+str(srt0),1,ds_55,true), srt(srt0) {} 00132 virtual bool solution(const SetAssignment& x) const { 00133 CountableSetRanges xr(x.lub, x[0]); 00134 IntSet is(-3,-1); 00135 IntSetRanges dr(is); 00136 switch (srt) { 00137 case SRT_EQ: return Iter::Ranges::equal(xr, dr); 00138 case SRT_NQ: return !Iter::Ranges::equal(xr, dr); 00139 case SRT_SUB: return Iter::Ranges::subset(xr, dr); 00140 case SRT_SUP: return Iter::Ranges::subset(dr, xr); 00141 case SRT_DISJ: 00142 { 00143 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges> 00144 inter(xr, dr); 00145 return !inter(); 00146 } 00147 case SRT_CMPL: 00148 { 00149 Gecode::Set::RangesCompl<IntSetRanges> drc(dr); 00150 return Iter::Ranges::equal(xr,drc); 00151 } 00152 } 00153 GECODE_NEVER; 00154 return false; 00155 } 00157 virtual void post(Space& home, SetVarArray& x, IntVarArray&) { 00158 Gecode::dom(home, x[0], srt, -3, -1); 00159 } 00161 virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) { 00162 Gecode::dom(home, x[0], srt, -3, -1, b); 00163 } 00164 }; 00165 DomIntRange _domintrange_eq(SRT_EQ); 00166 DomIntRange _domintrange_nq(SRT_NQ); 00167 DomIntRange _domintrange_sub(SRT_SUB); 00168 DomIntRange _domintrange_sup(SRT_SUP); 00169 DomIntRange _domintrange_disj(SRT_DISJ); 00170 DomIntRange _domintrange_cmpl(SRT_CMPL); 00171 00173 class DomInt : public SetTest { 00174 private: 00175 Gecode::SetRelType srt; 00176 public: 00178 DomInt(Gecode::SetRelType srt0) 00179 : SetTest("Dom::Int::"+str(srt0),1,ds_55,true), srt(srt0) {} 00181 virtual bool solution(const SetAssignment& x) const { 00182 CountableSetRanges xr(x.lub, x[0]); 00183 IntSet is(-3,-3); 00184 IntSetRanges dr(is); 00185 switch (srt) { 00186 case SRT_EQ: return Iter::Ranges::equal(xr, dr); 00187 case SRT_NQ: return !Iter::Ranges::equal(xr, dr); 00188 case SRT_SUB: return Iter::Ranges::subset(xr, dr); 00189 case SRT_SUP: return Iter::Ranges::subset(dr, xr); 00190 case SRT_DISJ: 00191 { 00192 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges> 00193 inter(xr, dr); 00194 return !inter(); 00195 } 00196 case SRT_CMPL: 00197 { 00198 Gecode::Set::RangesCompl<IntSetRanges> drc(dr); 00199 return Iter::Ranges::equal(xr,drc); 00200 } 00201 } 00202 GECODE_NEVER; 00203 return false; 00204 } 00206 virtual void post(Space& home, SetVarArray& x, IntVarArray&) { 00207 Gecode::dom(home, x[0], srt, -3); 00208 } 00210 virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) { 00211 Gecode::dom(home, x[0], srt, -3, b); 00212 } 00213 }; 00214 DomInt _domint_eq(SRT_EQ); 00215 DomInt _domint_nq(SRT_NQ); 00216 DomInt _domint_sub(SRT_SUB); 00217 DomInt _domint_sup(SRT_SUP); 00218 DomInt _domint_disj(SRT_DISJ); 00219 DomInt _domint_cmpl(SRT_CMPL); 00220 00222 class DomDom : public SetTest { 00223 private: 00224 Gecode::SetRelType srt; 00225 Gecode::IntSet is; 00226 public: 00228 DomDom(Gecode::SetRelType srt0) 00229 : SetTest("Dom::Dom::"+str(srt0),1,d1,true), srt(srt0) 00230 , is(srt == Gecode::SRT_CMPL ? d1c: d1) {} 00232 virtual bool solution(const SetAssignment& x) const { 00233 CountableSetRanges xr(x.lub, x[0]); 00234 IntSetRanges dr(is); 00235 switch (srt) { 00236 case SRT_EQ: return Iter::Ranges::equal(xr, dr); 00237 case SRT_NQ: return !Iter::Ranges::equal(xr, dr); 00238 case SRT_SUB: return Iter::Ranges::subset(xr, dr); 00239 case SRT_SUP: return Iter::Ranges::subset(dr, xr); 00240 case SRT_DISJ: 00241 { 00242 Gecode::Iter::Ranges::Inter<CountableSetRanges,IntSetRanges> 00243 inter(xr, dr); 00244 return !inter(); 00245 } 00246 case SRT_CMPL: 00247 { 00248 Gecode::Set::RangesCompl<IntSetRanges> drc(dr); 00249 return Iter::Ranges::equal(xr,drc); 00250 } 00251 } 00252 GECODE_NEVER; 00253 return false; 00254 } 00256 virtual void post(Space& home, SetVarArray& x, IntVarArray&) { 00257 Gecode::dom(home, x[0], srt, is); 00258 } 00260 virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) { 00261 Gecode::dom(home, x[0], srt, is, b); 00262 } 00263 }; 00264 DomDom _domdom_eq(SRT_EQ); 00265 DomDom _domdom_nq(SRT_NQ); 00266 DomDom _domdom_sub(SRT_SUB); 00267 DomDom _domdom_sup(SRT_SUP); 00268 DomDom _domdom_disj(SRT_DISJ); 00269 DomDom _domdom_cmpl(SRT_CMPL); 00270 00272 class CardRange : public SetTest { 00273 public: 00275 CardRange(void) 00276 : SetTest("Dom::CardRange",1,d1,false) {} 00278 virtual bool solution(const SetAssignment& x) const { 00279 CountableSetRanges xr(x.lub, x[0]); 00280 unsigned int card = Iter::Ranges::size(xr); 00281 return card >= 2 && card <= 3; 00282 } 00284 virtual void post(Space& home, SetVarArray& x, IntVarArray&) { 00285 Gecode::cardinality(home, x[0], 2, 3); 00286 } 00287 }; 00288 CardRange _cardRange; 00289 00290 }}} 00291 00292 // STATISTICS: test-set