incremental.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Mikael Lagerkvist, 2007 00011 * Christian Schulte, 2008 00012 * 00013 * Last modified: 00014 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00015 * $Revision: 11192 $ 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 Extensional { 00043 00044 /* 00045 * Support advisor 00046 * 00047 */ 00048 00049 template<class View> 00050 forceinline 00051 Incremental<View>::SupportAdvisor:: 00052 SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c, 00053 int i0) 00054 : Advisor(home,p,c), i(i0) {} 00055 00056 template<class View> 00057 forceinline 00058 Incremental<View>::SupportAdvisor:: 00059 SupportAdvisor(Space& home, bool share, SupportAdvisor& a) 00060 : Advisor(home,share,a), i(a.i) {} 00061 00062 template<class View> 00063 forceinline void 00064 Incremental<View>::SupportAdvisor:: 00065 dispose(Space& home, Council<SupportAdvisor>& c) { 00066 Advisor::dispose(home,c); 00067 } 00068 00069 00070 /* 00071 * Support entries 00072 * 00073 */ 00074 template<class View> 00075 forceinline 00076 Incremental<View>::SupportEntry::SupportEntry(Tuple t0) 00077 : t(t0) {} 00078 00079 template<class View> 00080 forceinline 00081 Incremental<View>::SupportEntry::SupportEntry(Tuple t0, SupportEntry* n) 00082 : FreeList(n), t(t0) {} 00083 00084 template<class View> 00085 forceinline typename Incremental<View>::SupportEntry* 00086 Incremental<View>::SupportEntry::next(void) const { 00087 return static_cast<SupportEntry*>(FreeList::next()); 00088 } 00089 00090 template<class View> 00091 forceinline typename Incremental<View>::SupportEntry** 00092 Incremental<View>::SupportEntry::nextRef(void) { 00093 return reinterpret_cast<SupportEntry**>(FreeList::nextRef()); 00094 } 00095 00096 template<class View> 00097 forceinline void 00098 Incremental<View>::SupportEntry::operator delete(void*) {} 00099 00100 template<class View> 00101 forceinline void 00102 Incremental<View>::SupportEntry::operator delete(void*, Space&) { 00103 GECODE_NEVER; 00104 } 00105 00106 template<class View> 00107 forceinline void* 00108 Incremental<View>::SupportEntry::operator new(size_t, Space& home) { 00109 return home.fl_alloc<sizeof(SupportEntry)>(); 00110 } 00111 00112 template<class View> 00113 forceinline void 00114 Incremental<View>::SupportEntry::dispose(Space& home) { 00115 home.fl_dispose<sizeof(SupportEntry)>(this,this); 00116 } 00117 00118 template<class View> 00119 forceinline void 00120 Incremental<View>::SupportEntry::dispose(Space& home, SupportEntry* l) { 00121 home.fl_dispose<sizeof(SupportEntry)>(this,l); 00122 } 00123 00124 00125 /* 00126 * Work entries 00127 * 00128 */ 00129 template<class View> 00130 forceinline 00131 Incremental<View>::WorkEntry::WorkEntry(int i0, int n0, WorkEntry* n) 00132 : FreeList(n), i(i0), n(n0) {} 00133 00134 template<class View> 00135 forceinline typename Incremental<View>::WorkEntry* 00136 Incremental<View>::WorkEntry::next(void) const { 00137 return static_cast<WorkEntry*>(FreeList::next()); 00138 } 00139 00140 template<class View> 00141 forceinline void 00142 Incremental<View>::WorkEntry::next(WorkEntry* n) { 00143 return FreeList::next(n); 00144 } 00145 00146 template<class View> 00147 forceinline void 00148 Incremental<View>::WorkEntry::operator delete(void*) {} 00149 00150 template<class View> 00151 forceinline void 00152 Incremental<View>::WorkEntry::operator delete(void*, Space&) { 00153 GECODE_NEVER; 00154 } 00155 00156 template<class View> 00157 forceinline void* 00158 Incremental<View>::WorkEntry::operator new(size_t, Space& home) { 00159 return home.fl_alloc<sizeof(WorkEntry)>(); 00160 } 00161 00162 template<class View> 00163 forceinline void 00164 Incremental<View>::WorkEntry::dispose(Space& home) { 00165 home.fl_dispose<sizeof(WorkEntry)>(this,this); 00166 } 00167 00168 00169 /* 00170 * Work stack 00171 * 00172 */ 00173 template<class View> 00174 forceinline 00175 Incremental<View>::Work::Work(void) 00176 : we(NULL) {} 00177 template<class View> 00178 forceinline bool 00179 Incremental<View>::Work::empty(void) const { 00180 return we == NULL; 00181 } 00182 template<class View> 00183 forceinline void 00184 Incremental<View>::Work::push(Space& home, int i, int n) { 00185 we = new (home) WorkEntry(i,n,we); 00186 } 00187 template<class View> 00188 forceinline void 00189 Incremental<View>::Work::pop(Space& home, int& i, int& n) { 00190 WorkEntry* d = we; 00191 we = we->next(); 00192 i=d->i; n=d->n; 00193 d->dispose(home); 00194 } 00195 00196 00197 /* 00198 * Support management 00199 * 00200 */ 00201 template<class View> 00202 forceinline typename Incremental<View>::SupportEntry* 00203 Incremental<View>::support(int i, int n) { 00204 return support_data[(i*(ts()->domsize)) + (n - ts()->min)]; 00205 } 00206 00207 template<class View> 00208 forceinline void 00209 Incremental<View>::init_support(Space& home) { 00210 assert(support_data == NULL); 00211 int literals = static_cast<int>(ts()->domsize*x.size()); 00212 support_data = home.alloc<SupportEntry*>(literals); 00213 for (int i = literals; i--; ) 00214 support_data[i] = NULL; 00215 } 00216 00217 template<class View> 00218 forceinline void 00219 Incremental<View>::add_support(Space& home, Tuple l) { 00220 for (int i = x.size(); i--; ) { 00221 int pos = (i*static_cast<int>(ts()->domsize)) + (l[i] - ts()->min); 00222 support_data[pos] = new (home) SupportEntry(l, support_data[pos]); 00223 } 00224 } 00225 00226 template<class View> 00227 forceinline void 00228 Incremental<View>::find_support(Space& home, Domain dom, int i, int n) { 00229 if (support(i,n) == NULL) { 00230 // Find support for value vv.val() in view i 00231 Tuple l = Base<View,false>::find_support(dom,i,n - ts()->min); 00232 if (l == NULL) { 00233 // No possible supports left 00234 w_remove.push(home,i,n); 00235 } else { 00236 // Mark values in support as supported 00237 add_support(home,l); 00238 } 00239 } 00240 } 00241 00242 template<class View> 00243 forceinline void 00244 Incremental<View>::remove_support(Space& home, Tuple l, int i, int n) { 00245 (void) n; 00246 for (int j = x.size(); j--; ) { 00247 int v = l[j]; 00248 int ov = v - ts()->min; 00249 int pos = (j*(static_cast<int>(ts()->domsize))) + ov; 00250 00251 assert(support_data[pos] != NULL); 00252 00253 SupportEntry** a = &(support_data[pos]); 00254 while ((*a)->t != l) { 00255 assert((*a)->next() != NULL); 00256 a = (*a)->nextRef(); 00257 } 00258 SupportEntry* old = *a; 00259 *a = (*a)->next(); 00260 00261 old->dispose(home); 00262 if ((i != j) && (support_data[pos] == NULL)) 00263 w_support.push(home, j, v); 00264 } 00265 } 00266 00267 00268 00269 /* 00270 * The propagator proper 00271 * 00272 */ 00273 00274 template<class View> 00275 forceinline 00276 Incremental<View>::Incremental(Home home, ViewArray<View>& x, 00277 const TupleSet& t) 00278 : Base<View,false>(home,x,t), support_data(NULL), 00279 unassigned(x.size()), ac(home) { 00280 init_support(home); 00281 00282 // Post advisors 00283 for (int i = x.size(); i--; ) 00284 if (x[i].assigned()) { 00285 --unassigned; 00286 } else { 00287 x[i].subscribe(home,*new (home) SupportAdvisor(home,*this,ac,i)); 00288 } 00289 00290 Region r(home); 00291 00292 // Add initial supports 00293 BitSet* dom = r.alloc<BitSet>(x.size()); 00294 init_dom(home, dom); 00295 for (int i = x.size(); i--; ) 00296 for (ViewValues<View> vv(x[i]); vv(); ++vv) 00297 find_support(home, dom, i, vv.val()); 00298 00299 // Work to be done or subsumption 00300 if (!w_support.empty() || !w_remove.empty() || (unassigned == 0)) 00301 View::schedule(home,*this, 00302 (unassigned != x.size()) ? ME_INT_VAL : ME_INT_DOM); 00303 } 00304 00305 template<class View> 00306 forceinline ExecStatus 00307 Incremental<View>::post(Home home, ViewArray<View>& x, const TupleSet& t) { 00308 // All variables in the correct domain 00309 for (int i = x.size(); i--; ) { 00310 GECODE_ME_CHECK(x[i].gq(home, t.min())); 00311 GECODE_ME_CHECK(x[i].lq(home, t.max())); 00312 } 00313 (void) new (home) Incremental<View>(home,x,t); 00314 return ES_OK; 00315 } 00316 00317 template<class View> 00318 forceinline 00319 Incremental<View>::Incremental(Space& home, bool share, Incremental<View>& p) 00320 : Base<View,false>(home,share,p), support_data(NULL), 00321 unassigned(p.unassigned) { 00322 ac.update(home,share,p.ac); 00323 00324 init_support(home); 00325 for (int i = static_cast<int>(ts()->domsize*x.size()); i--; ) { 00326 SupportEntry** n = &(support_data[i]); 00327 SupportEntry* o = p.support_data[i]; 00328 while (o != NULL) { 00329 // Allocate new support entry 00330 SupportEntry* s = new (home) SupportEntry(o->t); 00331 // Link in support entry 00332 (*n) = s; n = s->nextRef(); 00333 // move to next one 00334 o = o->next(); 00335 } 00336 *n = NULL; 00337 } 00338 } 00339 00340 template<class View> 00341 PropCost 00342 Incremental<View>::cost(const Space&, const ModEventDelta& med) const { 00343 if (View::me(med) == ME_INT_VAL) 00344 return PropCost::quadratic(PropCost::HI,x.size()); 00345 else 00346 return PropCost::cubic(PropCost::HI,x.size()); 00347 } 00348 00349 template<class View> 00350 Actor* 00351 Incremental<View>::copy(Space& home, bool share) { 00352 return new (home) Incremental<View>(home,share,*this); 00353 } 00354 00355 template<class View> 00356 forceinline size_t 00357 Incremental<View>::dispose(Space& home) { 00358 if (!home.failed()) { 00359 int literals = static_cast<int>(ts()->domsize*x.size()); 00360 for (int i = literals; i--; ) 00361 if (support_data[i]) { 00362 SupportEntry* lastse = support_data[i]; 00363 while (lastse->next() != NULL) 00364 lastse = lastse->next(); 00365 support_data[i]->dispose(home, lastse); 00366 } 00367 home.rfree(support_data, sizeof(SupportEntry*)*literals); 00368 } 00369 ac.dispose(home); 00370 (void) Base<View,false>::dispose(home); 00371 return sizeof(*this); 00372 } 00373 00374 template<class View> 00375 ExecStatus 00376 Incremental<View>::propagate(Space& home, const ModEventDelta&) { 00377 assert(!w_support.empty() || !w_remove.empty() || unassigned==0); 00378 // Set up datastructures 00379 // Bit-sets for amortized O(1) access to domains 00380 Region r(home); 00381 // Add initial supports 00382 BitSet* dom = r.alloc<BitSet>(x.size()); 00383 init_dom(home, dom); 00384 00385 // Work loop 00386 while (!w_support.empty() || !w_remove.empty()) { 00387 while (!w_remove.empty()) { 00388 int i, n; 00389 w_remove.pop(home,i,n); 00390 // Work is still relevant 00391 if (dom[i].get(static_cast<unsigned int>(n-ts()->min))) { 00392 GECODE_ME_CHECK(x[i].nq(home,n)); 00393 dom[i].clear(static_cast<unsigned int>(n-ts()->min)); 00394 } 00395 } 00396 while (!w_support.empty()) { 00397 int i, n; 00398 w_support.pop(home,i,n); 00399 // Work is still relevant 00400 if (dom[i].get(static_cast<unsigned int>(n-ts()->min))) 00401 find_support(home, dom, i, n); 00402 } 00403 } 00404 if (unassigned != 0) 00405 return ES_FIX; 00406 00407 return home.ES_SUBSUMED(*this); 00408 } 00409 00410 00411 template<class View> 00412 ExecStatus 00413 Incremental<View>::advise(Space& home, Advisor& _a, const Delta& d) { 00414 SupportAdvisor& a = static_cast<SupportAdvisor&>(_a); 00415 ModEvent me = View::modevent(d); 00416 bool scheduled = !w_support.empty() || !w_remove.empty(); 00417 00418 if (x[a.i].any(d)) { 00419 ViewValues<View> vv(x[a.i]); 00420 for (int n = ts()->min; n <= ts()->max; n++) { 00421 if (vv() && (n == vv.val())) { 00422 ++vv; 00423 continue; 00424 } 00425 while (SupportEntry* s = support(a.i,n)) 00426 remove_support(home, s->t, a.i, n); 00427 } 00428 } else { 00429 for (int n = x[a.i].min(d); n <= x[a.i].max(d); n++) 00430 while (SupportEntry* s = support(a.i,n)) 00431 remove_support(home, s->t, a.i, n); 00432 } 00433 00434 if (me == ME_INT_VAL) { 00435 --unassigned; 00436 // nothing to do or already scheduled 00437 // propagator is not subsumed since unassigned!=0 00438 if (((w_support.empty() && w_remove.empty()) || scheduled) && 00439 (unassigned != 0)) 00440 return home.ES_FIX_DISPOSE(ac,a); 00441 else 00442 return home.ES_NOFIX_DISPOSE(ac,a); 00443 } else if ((w_support.empty() && w_remove.empty()) || scheduled) { 00444 // nothing to do or already scheduled 00445 return ES_FIX; 00446 } 00447 return ES_NOFIX; 00448 } 00449 00450 00451 }}} 00452 00453 // STATISTICS: int-prop 00454