00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 namespace Gecode { namespace Int { namespace Extensional {
00043
00044
00045
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
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
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
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
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
00231 Tuple l = Base<View,false>::find_support(dom,i,n - ts()->min);
00232 if (l == NULL) {
00233
00234 w_remove.push(home,i,n);
00235 } else {
00236
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
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
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
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
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
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
00330 SupportEntry* s = new (home) SupportEntry(o->t);
00331
00332 (*n) = s; n = s->nextRef();
00333
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
00379
00380 Region r(home);
00381
00382 BitSet* dom = r.alloc<BitSet>(x.size());
00383 init_dom(home, dom);
00384
00385
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
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
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
00437
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
00445 return ES_FIX;
00446 }
00447 return ES_NOFIX;
00448 }
00449
00450
00451 }}}
00452
00453
00454