dom.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 * Contributing authors: 00007 * Mikael Lagerkvist <lagerkvist@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2006 00011 * Mikael Lagerkvist, 2006 00012 * 00013 * Last modified: 00014 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00015 * $Revision: 10364 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 namespace Gecode { namespace Int { namespace Channel { 00043 00048 template<class View> 00049 class DomInfo { 00050 public: 00052 View view; 00054 unsigned int size; 00056 int min; 00058 int max; 00060 void init(View x, int n); 00062 void update(Space& home, bool share, DomInfo<View>& vcb); 00064 bool doval(void) const; 00066 bool dodom(void) const; 00068 void assigned(void); 00070 void removed(int i); 00072 void done(void); 00073 }; 00074 00075 template<class View> 00076 forceinline void 00077 DomInfo<View>::init(View x, int n) { 00078 view = x; 00079 size = static_cast<unsigned int>(n); 00080 min = 0; 00081 max = n-1; 00082 } 00083 00084 template<class View> 00085 forceinline void 00086 DomInfo<View>::update(Space& home, bool share, DomInfo<View>& di) { 00087 view.update(home,share,di.view); 00088 size = di.size; 00089 min = di.min; 00090 max = di.max; 00091 } 00092 00093 template<class View> 00094 forceinline bool 00095 DomInfo<View>::doval(void) const { 00096 return (size != 1) && view.assigned(); 00097 } 00098 00099 template<class View> 00100 forceinline bool 00101 DomInfo<View>::dodom(void) const { 00102 return size != view.size(); 00103 } 00104 00105 template<class View> 00106 forceinline void 00107 DomInfo<View>::assigned(void) { 00108 size = 1; 00109 } 00110 00111 template<class View> 00112 forceinline void 00113 DomInfo<View>::removed(int i) { 00114 size--; 00115 if (i == min) 00116 min++; 00117 else if (i == max) 00118 max--; 00119 } 00120 00121 template<class View> 00122 forceinline void 00123 DomInfo<View>::done(void) { 00124 size = view.size(); 00125 min = view.min(); 00126 max = view.max(); 00127 } 00128 00129 // Propagate domain information from x to y 00130 template<class View> 00131 ExecStatus 00132 prop_dom(Space& home, int n, DomInfo<View>* x, DomInfo<View>* y, 00133 ProcessStack& ya) { 00134 for (int i = n; i--; ) 00135 // Only views with not yet propagated missing values 00136 if (x[i].dodom()) { 00137 // Iterate the values in the complement of x[i] 00138 ViewRanges<View> 00139 xir(x[i].view); 00140 Iter::Ranges::ComplVal<ViewRanges<View> > 00141 xirc(x[i].min,x[i].max,xir); 00142 Iter::Ranges::ToValues<Iter::Ranges::ComplVal<ViewRanges<View> > > 00143 jv(xirc); 00144 while (jv()) { 00145 // j is not in the domain of x[i], so prune i from y[j] 00146 int j = jv.val(); 00147 ModEvent me = y[j].view.nq(home,i); 00148 if (me_failed(me)) 00149 return ES_FAILED; 00150 if (me_modified(me)) { 00151 if (me == ME_INT_VAL) { 00152 // Record that y[j] has been assigned and must be propagated 00153 ya.push(j); 00154 } else { 00155 // Obvious as x[i] is different from j 00156 y[j].removed(i); 00157 } 00158 } 00159 ++jv; 00160 } 00161 // Update which values have been propagated and what are the new bounds 00162 x[i].done(); 00163 } 00164 return ES_OK; 00165 } 00166 00167 /* 00168 * The actual propagator 00169 * 00170 */ 00171 template<class View, bool shared> 00172 forceinline 00173 Dom<View,shared>::Dom(Home home, int n, DomInfo<View>* xy) 00174 : Base<DomInfo<View>,PC_INT_DOM>(home,n,xy) {} 00175 00176 template<class View, bool shared> 00177 forceinline 00178 Dom<View,shared>::Dom(Space& home, bool share, Dom<View,shared>& p) 00179 : Base<DomInfo<View>,PC_INT_DOM>(home,share,p) {} 00180 00181 template<class View, bool shared> 00182 Actor* 00183 Dom<View,shared>::copy(Space& home, bool share) { 00184 return new (home) Dom<View,shared>(home,share,*this); 00185 } 00186 00187 template<class View, bool shared> 00188 PropCost 00189 Dom<View,shared>::cost(const Space&, const ModEventDelta& med) const { 00190 if (View::me(med) == ME_INT_VAL) 00191 return PropCost::quadratic(PropCost::LO, 2*n); 00192 else 00193 return PropCost::quadratic(PropCost::HI, 2*n); 00194 } 00195 00196 template<class View, bool shared> 00197 ExecStatus 00198 Dom<View,shared>::propagate(Space& home, const ModEventDelta& med) { 00199 Region r(home); 00200 ProcessStack xa(r,n); 00201 ProcessStack ya(r,n); 00202 00203 DomInfo<View>* x = xy; 00204 DomInfo<View>* y = xy+n; 00205 00206 if (View::me(med) == ME_INT_VAL) { 00207 // Scan x and y for assigned but not yet propagated views 00208 for (int i = n; i--; ) { 00209 if (x[i].doval()) xa.push(i); 00210 if (y[i].doval()) ya.push(i); 00211 } 00212 00213 if (shared) { 00214 do { 00215 // Propagate assigned views for x 00216 GECODE_ES_CHECK((prop_val<View,DomInfo<View> > 00217 (home,n,x,y,n_na,xa,ya))); 00218 // Propagate assigned views for y 00219 GECODE_ES_CHECK((prop_val<View,DomInfo<View> > 00220 (home,n,y,x,n_na,ya,xa))); 00221 assert(ya.empty()); 00222 } while (!xa.empty() || !ya.empty()); 00223 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM)); 00224 } else { 00225 do { 00226 // Propagate assigned views for x 00227 GECODE_ES_CHECK((prop_val<View,DomInfo<View> > 00228 (home,n,x,y,n_na,xa,ya))); 00229 // Propagate assigned views for y 00230 GECODE_ES_CHECK((prop_val<View,DomInfo<View> > 00231 (home,n,y,x,n_na,ya,xa))); 00232 assert(ya.empty()); 00233 } while (!xa.empty()); 00234 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)); 00235 } 00236 } 00237 00238 // Process changed views for y 00239 // This propagates from y to x and possibly records xs that 00240 // got assigned 00241 GECODE_ES_CHECK(prop_dom(home,n,y,x,xa)); 00242 00243 // Process assigned views for x 00244 GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,x,y,n_na,xa,ya))); 00245 00246 // Perform domain consistent propagation for distinct on the x views 00247 if (dc.available()) { 00248 GECODE_ES_CHECK(dc.sync(home)); 00249 } else { 00250 View* xv = r.alloc<View>(n); 00251 for (int i=n; i--; ) 00252 xv[i] = x[i].view; 00253 GECODE_ES_CHECK(dc.init(home,n,&xv[0])); 00254 } 00255 bool assigned; 00256 GECODE_ES_CHECK(dc.propagate(home,assigned)); 00257 if (assigned) { 00258 // This has assigned some more views in x which goes unnoticed 00259 // (that is, not recorded in xa). This must be checked and propagated 00260 // to the y views, however the distinctness on x is already 00261 // propagated. 00262 for (int i=n; i--; ) 00263 if (x[i].doval()) { 00264 int j = x[i].view.val(); 00265 // Assign the y variable to i (or test if already assigned!) 00266 ModEvent me = y[j].view.eq(home,i); 00267 if (me_failed(me)) 00268 return ES_FAILED; 00269 if (me_modified(me)) { 00270 // Record that y[j] has been assigned and must be propagated 00271 assert(me == ME_INT_VAL); 00272 // Otherwise the modification event would not be ME_INT_VAL 00273 ya.push(j); 00274 } 00275 x[i].assigned(); n_na--; 00276 } 00277 } 00278 00279 // Process changed views for x 00280 // This propagates from x to y and possibly records ys that 00281 // got assigned 00282 GECODE_ES_CHECK(prop_dom(home,n,x,y,ya)); 00283 00284 // Process assigned view again (some might have been found above) 00285 while (!xa.empty() || !ya.empty()) { 00286 // Process assigned views for x 00287 GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,x,y,n_na,xa,ya))); 00288 // Process assigned views for y 00289 GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,y,x,n_na,ya,xa))); 00290 }; 00291 00292 if (shared) { 00293 for (int i=2*n; i--; ) 00294 if (!xy[i].view.assigned()) 00295 return ES_NOFIX; 00296 return home.ES_SUBSUMED(*this); 00297 } else { 00298 return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX; 00299 } 00300 } 00301 00302 template<class View, bool shared> 00303 ExecStatus 00304 Dom<View,shared>::post(Home home, int n, DomInfo<View>* xy) { 00305 assert(n > 0); 00306 if (n == 1) { 00307 GECODE_ME_CHECK(xy[0].view.eq(home,0)); 00308 GECODE_ME_CHECK(xy[1].view.eq(home,0)); 00309 return ES_OK; 00310 } 00311 for (int i=2*n; i--; ) { 00312 GECODE_ME_CHECK(xy[i].view.gq(home,0)); 00313 GECODE_ME_CHECK(xy[i].view.le(home,n)); 00314 } 00315 (void) new (home) Dom<View,shared>(home,n,xy); 00316 return ES_OK; 00317 } 00318 00319 }}} 00320 00321 // STATISTICS: int-prop 00322