1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Copyright: 7 * Christian Schulte, 2004 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 #include <gecode/int/rel.hh> 35 36 namespace Gecode { namespace Int { namespace Arithmetic { 37 38 /* 39 * Ternary bounds consistent maximum 40 * 41 */ 42 43 template<class View> 44 forceinline ExecStatus prop_max_bnd(Space & home,View x0,View x1,View x2)45 prop_max_bnd(Space& home, View x0, View x1, View x2) { 46 bool mod = false; 47 do { 48 mod = false; 49 { 50 ModEvent me = x2.lq(home,std::max(x0.max(),x1.max())); 51 if (me_failed(me)) return ES_FAILED; 52 mod |= me_modified(me); 53 } 54 { 55 ModEvent me = x2.gq(home,std::max(x0.min(),x1.min())); 56 if (me_failed(me)) return ES_FAILED; 57 mod |= me_modified(me); 58 } 59 { 60 ModEvent me = x0.lq(home,x2.max()); 61 if (me_failed(me)) return ES_FAILED; 62 mod |= me_modified(me); 63 } 64 { 65 ModEvent me = x1.lq(home,x2.max()); 66 if (me_failed(me)) return ES_FAILED; 67 mod |= me_modified(me); 68 } 69 } while (mod); 70 return ES_OK; 71 } 72 73 template<class View> 74 forceinline MaxBnd(Home home,View x0,View x1,View x2)75 MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2) 76 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {} 77 78 template<class View> 79 ExecStatus post(Home home,View x0,View x1,View x2)80 MaxBnd<View>::post(Home home, View x0, View x1, View x2) { 81 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min()))); 82 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max()))); 83 if (x0 == x1) 84 return Rel::EqBnd<View,View>::post(home,x0,x2); 85 if (x0 == x2) 86 return Rel::Lq<View,View>::post(home,x1,x2); 87 if (x1 == x2) 88 return Rel::Lq<View,View>::post(home,x0,x2); 89 (void) new (home) MaxBnd<View>(home,x0,x1,x2); 90 return ES_OK; 91 } 92 93 template<class View> 94 forceinline MaxBnd(Space & home,MaxBnd<View> & p)95 MaxBnd<View>::MaxBnd(Space& home, MaxBnd<View>& p) 96 : TernaryPropagator<View,PC_INT_BND>(home,p) {} 97 98 template<class View> 99 forceinline MaxBnd(Space & home,Propagator & p,View x0,View x1,View x2)100 MaxBnd<View>::MaxBnd(Space& home, Propagator& p, 101 View x0, View x1, View x2) 102 : TernaryPropagator<View,PC_INT_BND>(home,p,x0,x1,x2) {} 103 104 template<class View> 105 Actor* copy(Space & home)106 MaxBnd<View>::copy(Space& home) { 107 return new (home) MaxBnd<View>(home,*this); 108 } 109 110 template<class View> 111 ExecStatus propagate(Space & home,const ModEventDelta &)112 MaxBnd<View>::propagate(Space& home, const ModEventDelta&) { 113 GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2)); 114 if ((x0.max() <= x1.min()) || (x0.max() < x2.min())) 115 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2))); 116 if ((x1.max() <= x0.min()) || (x1.max() < x2.min())) 117 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2))); 118 return x0.assigned() && x1.assigned() && x2.assigned() ? 119 home.ES_SUBSUMED(*this) : ES_FIX; 120 } 121 122 /* 123 * Nary bounds consistent maximum 124 * 125 */ 126 127 template<class View> 128 forceinline NaryMaxBnd(Home home,ViewArray<View> & x,View y)129 NaryMaxBnd<View>::NaryMaxBnd(Home home, ViewArray<View>& x, View y) 130 : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {} 131 132 template<class View> 133 ExecStatus post(Home home,ViewArray<View> & x,View y)134 NaryMaxBnd<View>::post(Home home, ViewArray<View>& x, View y) { 135 assert(x.size() > 0); 136 x.unique(); 137 if (x.size() == 1) 138 return Rel::EqBnd<View,View>::post(home,x[0],y); 139 if (x.size() == 2) 140 return MaxBnd<View>::post(home,x[0],x[1],y); 141 int l = x[0].min(); 142 int u = x[0].max(); 143 for (int i=1; i<x.size(); i++) { 144 l = std::max(l,x[i].min()); 145 u = std::max(u,x[i].max()); 146 } 147 GECODE_ME_CHECK(y.gq(home,l)); 148 GECODE_ME_CHECK(y.lq(home,u)); 149 if (x.same(y)) { 150 // Check whether y occurs in x 151 for (int i=0; i<x.size(); i++) 152 GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y))); 153 } else { 154 (void) new (home) NaryMaxBnd<View>(home,x,y); 155 } 156 return ES_OK; 157 } 158 159 template<class View> 160 forceinline NaryMaxBnd(Space & home,NaryMaxBnd<View> & p)161 NaryMaxBnd<View>::NaryMaxBnd(Space& home, NaryMaxBnd<View>& p) 162 : NaryOnePropagator<View,PC_INT_BND>(home,p) {} 163 164 template<class View> 165 Actor* copy(Space & home)166 NaryMaxBnd<View>::copy(Space& home) { 167 if (x.size() == 1) 168 return new (home) Rel::EqBnd<View,View>(home,*this,x[0],y); 169 if (x.size() == 2) 170 return new (home) MaxBnd<View>(home,*this,x[0],x[1],y); 171 return new (home) NaryMaxBnd<View>(home,*this); 172 } 173 174 /// Status of propagation for nary max 175 enum MaxPropStatus { 176 MPS_ASSIGNED = 1<<0, ///< All views are assigned 177 MPS_REMOVED = 1<<1, ///< A view is removed 178 MPS_NEW_BOUND = 1<<2 ///< Telling has found a new upper bound 179 }; 180 181 template<class View> 182 forceinline ExecStatus prop_nary_max_bnd(Space & home,Propagator & p,ViewArray<View> & x,View y,PropCond pc)183 prop_nary_max_bnd(Space& home, Propagator& p, 184 ViewArray<View>& x, View y, PropCond pc) { 185 rerun: 186 assert(x.size() > 0); 187 int maxmax = x[0].max(); 188 int maxmin = x[0].min(); 189 for (int i=1; i<x.size(); i++) { 190 maxmax = std::max(x[i].max(),maxmax); 191 maxmin = std::max(x[i].min(),maxmin); 192 } 193 GECODE_ME_CHECK(y.lq(home,maxmax)); 194 GECODE_ME_CHECK(y.gq(home,maxmin)); 195 maxmin = y.min(); 196 maxmax = y.max(); 197 int status = MPS_ASSIGNED; 198 for (int i=x.size(); i--; ) { 199 ModEvent me = x[i].lq(home,maxmax); 200 if (me == ME_INT_FAILED) 201 return ES_FAILED; 202 if (me_modified(me) && (x[i].max() != maxmax)) 203 status |= MPS_NEW_BOUND; 204 if (x[i].max() < maxmin) { 205 x.move_lst(i,home,p,pc); 206 status |= MPS_REMOVED; 207 } else if (!x[i].assigned()) 208 status &= ~MPS_ASSIGNED; 209 } 210 if (x.size() == 0) 211 return ES_FAILED; 212 if ((status & MPS_REMOVED) != 0) 213 goto rerun; 214 if (((status & MPS_ASSIGNED) != 0) && y.assigned()) 215 return home.ES_SUBSUMED(p); 216 return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX; 217 } 218 219 template<class View> 220 ExecStatus propagate(Space & home,const ModEventDelta &)221 NaryMaxBnd<View>::propagate(Space& home, const ModEventDelta&) { 222 ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND); 223 GECODE_ES_CHECK(es); 224 if (x.size() == 1) 225 GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y))); 226 return es; 227 } 228 229 230 /* 231 * Ternary domain consistent maximum 232 * 233 */ 234 235 template<class View> 236 forceinline MaxDom(Home home,View x0,View x1,View x2)237 MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2) 238 : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {} 239 240 template<class View> 241 ExecStatus post(Home home,View x0,View x1,View x2)242 MaxDom<View>::post(Home home, View x0, View x1, View x2) { 243 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min()))); 244 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max()))); 245 if (x0 == x1) 246 return Rel::EqDom<View,View>::post(home,x0,x2); 247 if (x0 == x2) 248 return Rel::Lq<View,View>::post(home,x1,x2); 249 if (x1 == x2) 250 return Rel::Lq<View,View>::post(home,x0,x2); 251 (void) new (home) MaxDom<View>(home,x0,x1,x2); 252 return ES_OK; 253 } 254 255 template<class View> 256 forceinline MaxDom(Space & home,MaxDom<View> & p)257 MaxDom<View>::MaxDom(Space& home, MaxDom<View>& p) 258 : TernaryPropagator<View,PC_INT_DOM>(home,p) {} 259 260 template<class View> 261 forceinline MaxDom(Space & home,Propagator & p,View x0,View x1,View x2)262 MaxDom<View>::MaxDom(Space& home, Propagator& p, 263 View x0, View x1, View x2) 264 : TernaryPropagator<View,PC_INT_DOM>(home,p,x0,x1,x2) {} 265 266 template<class View> 267 Actor* copy(Space & home)268 MaxDom<View>::copy(Space& home) { 269 return new (home) MaxDom<View>(home,*this); 270 } 271 272 template<class View> 273 PropCost cost(const Space &,const ModEventDelta & med) const274 MaxDom<View>::cost(const Space&, const ModEventDelta& med) const { 275 return PropCost::ternary((View::me(med) == ME_INT_DOM) ? 276 PropCost::HI : PropCost::LO); 277 } 278 279 template<class View> 280 ExecStatus propagate(Space & home,const ModEventDelta & med)281 MaxDom<View>::propagate(Space& home, const ModEventDelta& med) { 282 if (View::me(med) != ME_INT_DOM) { 283 GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2)); 284 if ((x0.max() <= x1.min()) || (x0.max() < x2.min())) 285 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2))); 286 if ((x1.max() <= x0.min()) || (x1.max() < x2.min())) 287 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2))); 288 return x0.assigned() && x1.assigned() && x2.assigned() ? 289 home.ES_SUBSUMED(*this) : 290 home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM)); 291 } 292 ViewRanges<View> r0(x0), r1(x1); 293 Iter::Ranges::Union<ViewRanges<View>,ViewRanges<View> > u(r0,r1); 294 GECODE_ME_CHECK(x2.inter_r(home,u,false)); 295 if (rtest_nq_dom(x0,x2) == RT_TRUE) { 296 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x0,x2))); 297 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2))); 298 } 299 if (rtest_nq_dom(x1,x2) == RT_TRUE) { 300 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x1,x2))); 301 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2))); 302 } 303 return ES_FIX; 304 } 305 306 /* 307 * Nary domain consistent maximum 308 * 309 */ 310 311 template<class View> 312 forceinline NaryMaxDom(Home home,ViewArray<View> & x,View y)313 NaryMaxDom<View>::NaryMaxDom(Home home, ViewArray<View>& x, View y) 314 : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {} 315 316 template<class View> 317 ExecStatus post(Home home,ViewArray<View> & x,View y)318 NaryMaxDom<View>::post(Home home, ViewArray<View>& x, View y) { 319 assert(x.size() > 0); 320 x.unique(); 321 if (x.size() == 1) 322 return Rel::EqDom<View,View>::post(home,x[0],y); 323 if (x.size() == 2) 324 return MaxDom<View>::post(home,x[0],x[1],y); 325 int l = x[0].min(); 326 int u = x[0].max(); 327 for (int i=0; i<x.size(); i++) { 328 l = std::max(l,x[i].min()); 329 u = std::max(u,x[i].max()); 330 } 331 GECODE_ME_CHECK(y.gq(home,l)); 332 GECODE_ME_CHECK(y.lq(home,u)); 333 if (x.same(y)) { 334 // Check whether y occurs in x 335 for (int i=0; i<x.size(); i++) 336 GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y))); 337 } else { 338 (void) new (home) NaryMaxDom<View>(home,x,y); 339 } 340 return ES_OK; 341 } 342 343 template<class View> 344 forceinline NaryMaxDom(Space & home,NaryMaxDom<View> & p)345 NaryMaxDom<View>::NaryMaxDom(Space& home, NaryMaxDom<View>& p) 346 : NaryOnePropagator<View,PC_INT_DOM>(home,p) {} 347 348 template<class View> 349 Actor* copy(Space & home)350 NaryMaxDom<View>::copy(Space& home) { 351 if (x.size() == 1) 352 return new (home) Rel::EqDom<View,View>(home,*this,x[0],y); 353 if (x.size() == 2) 354 return new (home) MaxDom<View>(home,*this,x[0],x[1],y); 355 return new (home) NaryMaxDom<View>(home,*this); 356 } 357 358 template<class View> 359 PropCost cost(const Space &,const ModEventDelta & med) const360 NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const { 361 if (View::me(med) == ME_INT_DOM) 362 return PropCost::linear(PropCost::HI, y.size()); 363 else 364 return PropCost::linear(PropCost::LO, x.size()); 365 } 366 367 template<class View> 368 ExecStatus propagate(Space & home,const ModEventDelta & med)369 NaryMaxDom<View>::propagate(Space& home, const ModEventDelta& med) { 370 if (View::me(med) != ME_INT_DOM) { 371 ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM); 372 GECODE_ES_CHECK(es); 373 return (es == ES_FIX) ? 374 home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) : 375 home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM)); 376 } 377 Region r; 378 ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size()); 379 for (int i=0; i<x.size(); i++) { 380 ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi; 381 } 382 Iter::Ranges::NaryUnion u(r, i_x, x.size()); 383 GECODE_ME_CHECK(y.inter_r(home,u,false)); 384 for (int i = x.size(); i--; ) 385 if (rtest_nq_dom(x[i],y) == RT_TRUE) { 386 GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x[i],y))); 387 x.move_lst(i,home,*this,PC_INT_DOM); 388 } 389 assert(x.size() > 0); 390 if (x.size() == 1) 391 GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y))); 392 return ES_FIX; 393 } 394 395 }}} 396 397 // STATISTICS: int-prop 398 399