rel.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 * 00006 * Copyright: 00007 * Christian Schulte, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:40:32 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10365 $ 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 <gecode/int/rel.hh> 00039 #include <gecode/int/bool.hh> 00040 00041 #include <algorithm> 00042 00043 namespace Gecode { 00044 00045 using namespace Int; 00046 00047 void 00048 rel(Home home, IntVar x0, IntRelType r, int n, IntConLevel) { 00049 Limits::check(n,"Int::rel"); 00050 if (home.failed()) return; 00051 IntView x(x0); 00052 switch (r) { 00053 case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break; 00054 case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break; 00055 case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break; 00056 case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break; 00057 case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break; 00058 case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break; 00059 default: throw UnknownRelation("Int::rel"); 00060 } 00061 } 00062 00063 void 00064 rel(Home home, const IntVarArgs& x, IntRelType r, int n, IntConLevel) { 00065 Limits::check(n,"Int::rel"); 00066 if (home.failed()) return; 00067 switch (r) { 00068 case IRT_EQ: 00069 for (int i=x.size(); i--; ) { 00070 IntView xi(x[i]); GECODE_ME_FAIL(xi.eq(home,n)); 00071 } 00072 break; 00073 case IRT_NQ: 00074 for (int i=x.size(); i--; ) { 00075 IntView xi(x[i]); GECODE_ME_FAIL(xi.nq(home,n)); 00076 } 00077 break; 00078 case IRT_LQ: 00079 for (int i=x.size(); i--; ) { 00080 IntView xi(x[i]); GECODE_ME_FAIL(xi.lq(home,n)); 00081 } 00082 break; 00083 case IRT_LE: 00084 for (int i=x.size(); i--; ) { 00085 IntView xi(x[i]); GECODE_ME_FAIL(xi.le(home,n)); 00086 } 00087 break; 00088 case IRT_GQ: 00089 for (int i=x.size(); i--; ) { 00090 IntView xi(x[i]); GECODE_ME_FAIL(xi.gq(home,n)); 00091 } 00092 break; 00093 case IRT_GR: 00094 for (int i=x.size(); i--; ) { 00095 IntView xi(x[i]); GECODE_ME_FAIL(xi.gr(home,n)); 00096 } 00097 break; 00098 default: 00099 throw UnknownRelation("Int::rel"); 00100 } 00101 } 00102 00103 void 00104 rel(Home home, IntVar x0, IntRelType r, IntVar x1, IntConLevel icl) { 00105 if (home.failed()) return; 00106 switch (r) { 00107 case IRT_EQ: 00108 if ((icl == ICL_DOM) || (icl == ICL_DEF)) { 00109 GECODE_ES_FAIL((Rel::EqDom<IntView,IntView>::post(home,x0,x1))); 00110 } else { 00111 GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView>::post(home,x0,x1))); 00112 } 00113 break; 00114 case IRT_NQ: 00115 GECODE_ES_FAIL(Rel::Nq<IntView>::post(home,x0,x1)); break; 00116 case IRT_GQ: 00117 std::swap(x0,x1); // Fall through 00118 case IRT_LQ: 00119 GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x0,x1)); break; 00120 case IRT_GR: 00121 std::swap(x0,x1); // Fall through 00122 case IRT_LE: 00123 GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x0,x1)); break; 00124 default: 00125 throw UnknownRelation("Int::rel"); 00126 } 00127 } 00128 00129 void 00130 rel(Home home, const IntVarArgs& x, IntRelType r, IntVar y, 00131 IntConLevel icl) { 00132 if (home.failed()) return; 00133 switch (r) { 00134 case IRT_EQ: 00135 { 00136 ViewArray<IntView> xv(home,x.size()+1); 00137 xv[x.size()]=y; 00138 for (int i=x.size(); i--; ) 00139 xv[i]=x[i]; 00140 if ((icl == ICL_DOM) || (icl == ICL_DEF)) { 00141 GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv)); 00142 } else { 00143 GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv)); 00144 } 00145 } 00146 break; 00147 case IRT_NQ: 00148 for (int i=x.size(); i--; ) { 00149 GECODE_ES_FAIL(Rel::Nq<IntView>::post(home,x[i],y)); 00150 } 00151 break; 00152 case IRT_GQ: 00153 for (int i=x.size(); i--; ) { 00154 GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,y,x[i])); 00155 } 00156 break; 00157 case IRT_LQ: 00158 for (int i=x.size(); i--; ) { 00159 GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x[i],y)); 00160 } 00161 break; 00162 case IRT_GR: 00163 for (int i=x.size(); i--; ) { 00164 GECODE_ES_FAIL(Rel::Le<IntView>::post(home,y,x[i])); 00165 } 00166 break; 00167 case IRT_LE: 00168 for (int i=x.size(); i--; ) { 00169 GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i],y)); 00170 } 00171 break; 00172 default: 00173 throw UnknownRelation("Int::rel"); 00174 } 00175 } 00176 00177 00178 void 00179 rel(Home home, IntVar x0, IntRelType r, IntVar x1, BoolVar b, 00180 IntConLevel icl) { 00181 if (home.failed()) return; 00182 switch (r) { 00183 case IRT_EQ: 00184 if ((icl == ICL_DOM) || (icl == ICL_DEF)) { 00185 GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView>::post(home,x0,x1,b))); 00186 } else { 00187 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView>::post(home,x0,x1,b))); 00188 } 00189 break; 00190 case IRT_NQ: 00191 { 00192 NegBoolView n(b); 00193 if (icl == ICL_BND) { 00194 GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView> 00195 ::post(home,x0,x1,n))); 00196 } else { 00197 GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView> 00198 ::post(home,x0,x1,n))); 00199 } 00200 } 00201 break; 00202 case IRT_GQ: 00203 std::swap(x0,x1); // Fall through 00204 case IRT_LQ: 00205 GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView>::post(home,x0,x1,b))); 00206 break; 00207 case IRT_LE: 00208 std::swap(x0,x1); // Fall through 00209 case IRT_GR: 00210 { 00211 NegBoolView n(b); 00212 GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView>::post(home,x0,x1,n))); 00213 } 00214 break; 00215 default: 00216 throw UnknownRelation("Int::rel"); 00217 } 00218 } 00219 00220 void 00221 rel(Home home, IntVar x, IntRelType r, int n, BoolVar b, 00222 IntConLevel icl) { 00223 Limits::check(n,"Int::rel"); 00224 if (home.failed()) return; 00225 switch (r) { 00226 case IRT_EQ: 00227 if ((icl == ICL_DOM) || (icl == ICL_DEF)) { 00228 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView> 00229 ::post(home,x,n,b))); 00230 } else { 00231 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView> 00232 ::post(home,x,n,b))); 00233 } 00234 break; 00235 case IRT_NQ: 00236 { 00237 NegBoolView nb(b); 00238 if (icl == ICL_BND) { 00239 GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView> 00240 ::post(home,x,n,nb))); 00241 } else { 00242 GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView> 00243 ::post(home,x,n,nb))); 00244 } 00245 } 00246 break; 00247 case IRT_LE: 00248 n--; // Fall through 00249 case IRT_LQ: 00250 GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView> 00251 ::post(home,x,n,b))); 00252 break; 00253 case IRT_GQ: 00254 n--; // Fall through 00255 case IRT_GR: 00256 { 00257 NegBoolView nb(b); 00258 GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView> 00259 ::post(home,x,n,nb))); 00260 } 00261 break; 00262 default: 00263 throw UnknownRelation("Int::rel"); 00264 } 00265 } 00266 00267 void 00268 rel(Home home, const IntVarArgs& x, IntRelType r, 00269 IntConLevel icl) { 00270 if (home.failed() || (x.size() < 2)) return; 00271 switch (r) { 00272 case IRT_EQ: 00273 { 00274 ViewArray<IntView> xv(home,x); 00275 if ((icl == ICL_DOM) || (icl == ICL_DEF)) { 00276 GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv)); 00277 } else { 00278 GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv)); 00279 } 00280 } 00281 break; 00282 case IRT_NQ: 00283 distinct(home,x,icl); 00284 break; 00285 case IRT_LE: 00286 for (int i=x.size()-1; i--; ) 00287 GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i],x[i+1])); 00288 break; 00289 case IRT_LQ: 00290 for (int i=x.size()-1; i--; ) 00291 GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x[i],x[i+1])); 00292 break; 00293 case IRT_GR: 00294 for (int i=x.size()-1; i--; ) 00295 GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i+1],x[i])); 00296 break; 00297 case IRT_GQ: 00298 for (int i=x.size()-1; i--; ) 00299 GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x[i+1],x[i])); 00300 break; 00301 default: 00302 throw UnknownRelation("Int::rel"); 00303 } 00304 } 00305 00306 void 00307 rel(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y, 00308 IntConLevel icl) { 00309 if (x.size() != y.size()) 00310 throw ArgumentSizeMismatch("Int::rel"); 00311 if (home.failed()) return; 00312 00313 switch (r) { 00314 case IRT_GR: 00315 { 00316 ViewArray<IntView> xv(home,x), yv(home,y); 00317 GECODE_ES_FAIL(Rel::Lex<IntView>::post(home,yv,xv,true)); 00318 } 00319 break; 00320 case IRT_LE: 00321 { 00322 ViewArray<IntView> xv(home,x), yv(home,y); 00323 GECODE_ES_FAIL(Rel::Lex<IntView>::post(home,xv,yv,true)); 00324 } 00325 break; 00326 case IRT_GQ: 00327 { 00328 ViewArray<IntView> xv(home,x), yv(home,y); 00329 GECODE_ES_FAIL(Rel::Lex<IntView>::post(home,yv,xv,false)); 00330 } 00331 break; 00332 case IRT_LQ: 00333 { 00334 ViewArray<IntView> xv(home,x), yv(home,y); 00335 GECODE_ES_FAIL(Rel::Lex<IntView>::post(home,xv,yv,false)); 00336 } 00337 break; 00338 case IRT_EQ: 00339 if ((icl == ICL_DOM) || (icl == ICL_DEF)) 00340 for (int i=x.size(); i--; ) { 00341 GECODE_ES_FAIL((Rel::EqDom<IntView,IntView> 00342 ::post(home,x[i],y[i]))); 00343 } 00344 else 00345 for (int i=x.size(); i--; ) { 00346 GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView> 00347 ::post(home,x[i],y[i]))); 00348 } 00349 break; 00350 case IRT_NQ: 00351 { 00352 ViewArray<BoolView> b(home,x.size()); 00353 for (int i=x.size(); i--; ) { 00354 BoolVar bi(home,0,1); b[i]=bi; 00355 NegBoolView n(b[i]); 00356 GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView> 00357 ::post(home,x[i],y[i],n))); 00358 } 00359 GECODE_ES_FAIL(Bool::NaryOrTrue<BoolView>::post(home,b)); 00360 } 00361 break; 00362 default: 00363 throw UnknownRelation("Int::rel"); 00364 } 00365 } 00366 00367 } 00368 00369 // STATISTICS: int-post