view.hpp
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, 2003 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10364 $ 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 namespace Gecode { namespace Int { namespace Count { 00039 00040 /* 00041 * General baseclass 00042 * 00043 */ 00044 00045 template<class VX, class VY, class VZ, bool shr> 00046 forceinline 00047 BaseView<VX,VY,VZ,shr>::BaseView(Home home, 00048 ViewArray<VX>& x0, VY y0, VZ z0, int c0) 00049 : Propagator(home), x(x0), y(y0), z(z0), c(c0) { 00050 x.subscribe(home,*this,PC_INT_DOM); 00051 y.subscribe(home,*this,PC_INT_DOM); 00052 z.subscribe(home,*this,PC_INT_BND); 00053 } 00054 00055 template<class VX, class VY, class VZ, bool shr> 00056 forceinline 00057 BaseView<VX,VY,VZ,shr>::BaseView(Space& home, bool share, 00058 BaseView<VX,VY,VZ,shr>& p) 00059 : Propagator(home,shr,p), c(p.c) { 00060 x.update(home,share,p.x); 00061 y.update(home,share,p.y); 00062 z.update(home,share,p.z); 00063 } 00064 00065 template<class VX, class VY, class VZ, bool shr> 00066 PropCost 00067 BaseView<VX,VY,VZ,shr>::cost(const Space&, const ModEventDelta&) const { 00068 return PropCost::linear(PropCost::LO,x.size()+1); 00069 } 00070 00071 template<class VX, class VY, class VZ, bool shr> 00072 forceinline size_t 00073 BaseView<VX,VY,VZ,shr>::dispose(Space& home) { 00074 x.cancel(home,*this,PC_INT_DOM); 00075 y.cancel(home,*this,PC_INT_DOM); 00076 z.cancel(home,*this,PC_INT_BND); 00077 (void) Propagator::dispose(home); 00078 return sizeof(*this); 00079 } 00080 00081 template<class VX, class VY, class VZ, bool shr> 00082 forceinline void 00083 BaseView<VX,VY,VZ,shr>::count(Space& home) { 00084 int n = x.size(); 00085 for (int i=n; i--; ) 00086 switch (holds(x[i],y)) { 00087 case RT_FALSE: 00088 x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n]; 00089 break; 00090 case RT_TRUE: 00091 x[i].cancel(home,*this,PC_INT_DOM); x[i]=x[--n]; 00092 c--; 00093 break; 00094 case RT_MAYBE: 00095 break; 00096 default: 00097 GECODE_NEVER; 00098 } 00099 x.size(n); 00100 } 00101 00102 template<class VX, class VY, class VZ, bool shr> 00103 forceinline int 00104 BaseView<VX,VY,VZ,shr>::atleast(void) const { 00105 return -c; 00106 } 00107 00108 template<class VX, class VY, class VZ, bool shr> 00109 forceinline int 00110 BaseView<VX,VY,VZ,shr>::atmost(void) const { 00111 return x.size()-c; 00112 } 00113 00114 template<class VX, class VY, class VZ, bool shr> 00115 forceinline bool 00116 BaseView<VX,VY,VZ,shr>::sharing(const ViewArray<VX>& x, 00117 const VY& y, const VZ& z) { 00118 if (shared(y,z)) 00119 return true; 00120 for (int i = x.size(); i--; ) 00121 if (shared(x[i],z)) 00122 return true; 00123 return false; 00124 } 00125 00126 /* 00127 * Equality 00128 * 00129 */ 00130 00131 template<class VX, class VY, class VZ, bool shr> 00132 forceinline 00133 EqView<VX,VY,VZ,shr>::EqView(Home home, 00134 ViewArray<VX>& x, VY y, VZ z, int c) 00135 : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {} 00136 00137 template<class VX, class VY, class VZ, bool shr> 00138 ExecStatus 00139 EqView<VX,VY,VZ,shr>::post(Home home, 00140 ViewArray<VX>& x, VY y, VZ z, int c) { 00141 if (z.assigned()) 00142 return EqInt<VX,VY>::post(home,x,y,z.val()+c); 00143 if (sharing(x,y,z)) 00144 (void) new (home) EqView<VX,VY,VZ,true>(home,x,y,z,c); 00145 else 00146 (void) new (home) EqView<VX,VY,VZ,false>(home,x,y,z,c); 00147 return ES_OK; 00148 } 00149 00150 template<class VX, class VY, class VZ, bool shr> 00151 forceinline 00152 EqView<VX,VY,VZ,shr>::EqView(Space& home, bool share, 00153 EqView<VX,VY,VZ,shr>& p) 00154 : BaseView<VX,VY,VZ,shr>(home,share,p) {} 00155 00156 template<class VX, class VY, class VZ, bool shr> 00157 Actor* 00158 EqView<VX,VY,VZ,shr>::copy(Space& home, bool share) { 00159 return new (home) EqView<VX,VY,VZ,shr>(home,share,*this); 00160 } 00161 00162 template<class VX, class VY, class VZ, bool shr> 00163 ExecStatus 00164 EqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) { 00165 count(home); 00166 00167 GECODE_ME_CHECK(z.gq(home,atleast())); 00168 GECODE_ME_CHECK(z.lq(home,atmost())); 00169 00170 if (z.assigned()) { 00171 if (z.val() == atleast()) 00172 return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this); 00173 if (z.val() == atmost()) 00174 return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this); 00175 GECODE_REWRITE(*this,(EqInt<VX,VY>::post(home(*this),x,y,z.val()+c))); 00176 } 00177 return shr ? ES_NOFIX : ES_FIX; 00178 } 00179 00180 00181 00182 00183 /* 00184 * Disequality 00185 * 00186 */ 00187 00188 template<class VX, class VY, class VZ, bool shr> 00189 forceinline 00190 NqView<VX,VY,VZ,shr>::NqView(Home home, 00191 ViewArray<VX>& x, VY y, VZ z, int c) 00192 : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {} 00193 00194 template<class VX, class VY, class VZ, bool shr> 00195 ExecStatus 00196 NqView<VX,VY,VZ,shr>::post(Home home, 00197 ViewArray<VX>& x, VY y, VZ z, int c) { 00198 if (z.assigned()) 00199 return NqInt<VX,VY>::post(home,x,y,z.val()+c); 00200 (void) new (home) NqView<VX,VY,VZ,shr>(home,x,y,z,c); 00201 return ES_OK; 00202 } 00203 00204 template<class VX, class VY, class VZ, bool shr> 00205 forceinline 00206 NqView<VX,VY,VZ,shr>::NqView(Space& home, bool share, 00207 NqView<VX,VY,VZ,shr>& p) 00208 : BaseView<VX,VY,VZ,shr>(home,share,p) {} 00209 00210 template<class VX, class VY, class VZ, bool shr> 00211 Actor* 00212 NqView<VX,VY,VZ,shr>::copy(Space& home, bool share) { 00213 return new (home) NqView<VX,VY,VZ,shr>(home,share,*this); 00214 } 00215 00216 template<class VX, class VY, class VZ, bool shr> 00217 ExecStatus 00218 NqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) { 00219 count(home); 00220 if (atleast() == atmost()) { 00221 GECODE_ME_CHECK(z.nq(home,atleast())); 00222 return home.ES_SUBSUMED(*this); 00223 } 00224 if (z.max() < atleast()) 00225 return home.ES_SUBSUMED(*this); 00226 if (z.min() > atmost()) 00227 return home.ES_SUBSUMED(*this); 00228 if (z.assigned()) 00229 GECODE_REWRITE(*this,(NqInt<VX,VY>::post(home(*this),x,y,z.val()+c))); 00230 return ES_FIX; 00231 } 00232 00233 00234 00235 /* 00236 * Less or equal 00237 * 00238 */ 00239 00240 template<class VX, class VY, class VZ, bool shr> 00241 forceinline 00242 LqView<VX,VY,VZ,shr>::LqView(Home home, ViewArray<VX>& x, 00243 VY y, VZ z, int c) 00244 : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {} 00245 00246 template<class VX, class VY, class VZ, bool shr> 00247 ExecStatus 00248 LqView<VX,VY,VZ,shr>::post(Home home, ViewArray<VX>& x, 00249 VY y, VZ z, int c) { 00250 if (z.assigned()) 00251 return LqInt<VX,VY>::post(home,x,y,z.val()+c); 00252 if (sharing(x,y,z)) 00253 (void) new (home) LqView<VX,VY,VZ,true>(home,x,y,z,c); 00254 else 00255 (void) new (home) LqView<VX,VY,VZ,false>(home,x,y,z,c); 00256 return ES_OK; 00257 } 00258 00259 template<class VX, class VY, class VZ, bool shr> 00260 forceinline 00261 LqView<VX,VY,VZ,shr>::LqView(Space& home, bool share, 00262 LqView<VX,VY,VZ,shr>& p) 00263 : BaseView<VX,VY,VZ,shr>(home,share,p) {} 00264 00265 template<class VX, class VY, class VZ, bool shr> 00266 Actor* 00267 LqView<VX,VY,VZ,shr>::copy(Space& home, bool share) { 00268 return new (home) LqView<VX,VY,VZ,shr>(home,share,*this); 00269 } 00270 00271 template<class VX, class VY, class VZ, bool shr> 00272 ExecStatus 00273 LqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) { 00274 count(home); 00275 GECODE_ME_CHECK(z.gq(home,atleast())); 00276 if (z.max() == atleast()) 00277 return post_false(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this); 00278 if (x.size() == 0) 00279 return home.ES_SUBSUMED(*this); 00280 if (z.assigned()) 00281 GECODE_REWRITE(*this,(LqInt<VX,VY>::post(home(*this),x,y,z.val()+c))); 00282 return shr ? ES_NOFIX : ES_FIX; 00283 } 00284 00285 00286 00287 /* 00288 * Greater or equal 00289 * 00290 */ 00291 00292 template<class VX, class VY, class VZ, bool shr> 00293 forceinline 00294 GqView<VX,VY,VZ,shr>::GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c) 00295 : BaseView<VX,VY,VZ,shr>(home,x,y,z,c) {} 00296 00297 template<class VX, class VY, class VZ, bool shr> 00298 ExecStatus 00299 GqView<VX,VY,VZ,shr>::post(Home home, 00300 ViewArray<VX>& x, VY y, VZ z, int c) { 00301 if (z.assigned()) 00302 return GqInt<VX,VY>::post(home,x,y,z.val()+c); 00303 if (sharing(x,y,z)) 00304 (void) new (home) GqView<VX,VY,VZ,true>(home,x,y,z,c); 00305 else 00306 (void) new (home) GqView<VX,VY,VZ,false>(home,x,y,z,c); 00307 return ES_OK; 00308 } 00309 00310 template<class VX, class VY, class VZ, bool shr> 00311 forceinline 00312 GqView<VX,VY,VZ,shr>::GqView(Space& home, bool share, 00313 GqView<VX,VY,VZ,shr>& p) 00314 : BaseView<VX,VY,VZ,shr>(home,share,p) {} 00315 00316 template<class VX, class VY, class VZ, bool shr> 00317 Actor* 00318 GqView<VX,VY,VZ,shr>::copy(Space& home, bool share) { 00319 return new (home) GqView<VX,VY,VZ,shr>(home,share,*this); 00320 } 00321 00322 template<class VX, class VY, class VZ, bool shr> 00323 ExecStatus 00324 GqView<VX,VY,VZ,shr>::propagate(Space& home, const ModEventDelta&) { 00325 count(home); 00326 00327 GECODE_ME_CHECK(z.lq(home,atmost())); 00328 00329 if (z.min() == atmost()) 00330 return post_true(home,x,y) ? ES_FAILED : home.ES_SUBSUMED(*this); 00331 if (x.size() == 0) 00332 return home.ES_SUBSUMED(*this); 00333 if (z.assigned()) 00334 GECODE_REWRITE(*this,(GqInt<VX,VY>::post(home(*this),x,y,z.val()+c))); 00335 return shr ? ES_NOFIX : ES_FIX; 00336 } 00337 00338 }}} 00339 00340 // STATISTICS: int-prop 00341