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 #include <gecode/kernel.hh>
00039
00040 namespace Gecode {
00041
00042
00043
00044
00045
00046 void
00047 VarImpDisposerBase::dispose(Space&,VarImpBase*) {}
00048
00049 VarImpDisposerBase::~VarImpDisposerBase(void) {}
00050
00051
00052
00053
00054
00055
00056
00057 Actor* Actor::sentinel;
00058
00059 #ifdef __GNUC__
00060
00061 Actor::~Actor(void) {}
00062 #endif
00063
00064
00065
00066
00067
00068
00069
00070 ExecStatus
00071 Propagator::advise(Space&, Advisor&, const Delta&) {
00072 assert(false);
00073 return ES_FAILED;
00074 }
00075
00076
00077
00078
00079
00080
00081 void
00082 NoGoods::post(Space&) {
00083 }
00084
00085
00086
00087
00088
00089
00090 NGL*
00091 Brancher::ngl(Space&, const Choice&, unsigned int) const {
00092 return NULL;
00093 }
00094
00095 void
00096 Brancher::print(const Space&, const Choice&, unsigned int,
00097 std::ostream&) const {
00098 }
00099
00100
00101
00102
00103
00104
00105 StatusStatistics Space::unused_status;
00106 CloneStatistics Space::unused_clone;
00107 CommitStatistics Space::unused_commit;
00108
00109 #ifdef GECODE_HAS_VAR_DISPOSE
00110 VarImpDisposerBase* Space::vd[AllVarConf::idx_d];
00111 #endif
00112
00113 Space::Space(void)
00114 : sm(new SharedMemory), mm(sm), _wmp_afc(0U) {
00115 #ifdef GECODE_HAS_VAR_DISPOSE
00116 for (int i=0; i<AllVarConf::idx_d; i++)
00117 _vars_d[i] = NULL;
00118 #endif
00119
00120 pl.init();
00121 bl.init();
00122 b_status = b_commit = Brancher::cast(&bl);
00123
00124 d_fst = d_cur = d_lst = NULL;
00125
00126 pc.p.active = &pc.p.queue[0]-1;
00127
00128 for (int i=0; i<=PropCost::AC_MAX; i++)
00129 pc.p.queue[i].init();
00130 pc.p.branch_id = reserved_branch_id+1;
00131 pc.p.n_sub = 0;
00132 }
00133
00134 void
00135 Space::notice(Actor& a, ActorProperty p, bool duplicate) {
00136 if (p & AP_DISPOSE) {
00137 if (duplicate && (d_fst != NULL)) {
00138 for (Actor** f = d_fst; f < d_cur; f++)
00139 if (&a == *f)
00140 return;
00141 }
00142 if (d_cur == d_lst) {
00143
00144 if (d_fst == NULL) {
00145
00146 d_fst = alloc<Actor*>(4);
00147 d_cur = d_fst;
00148 d_lst = d_fst+4;
00149 } else {
00150
00151 unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
00152 assert(n != 0);
00153 d_fst = realloc<Actor*>(d_fst,n,2*n);
00154 d_cur = d_fst+n;
00155 d_lst = d_fst+2*n;
00156 }
00157 }
00158 *(d_cur++) = &a;
00159 } else if (p & AP_WEAKLY) {
00160 if (wmp() == 0)
00161 wmp(2);
00162 else
00163 wmp(wmp()+1);
00164 }
00165 }
00166
00167 void
00168 Space::ignore(Actor& a, ActorProperty p, bool duplicate) {
00169 if (p & AP_DISPOSE) {
00170
00171
00172 if (d_fst == NULL)
00173 return;
00174 Actor** f = d_fst;
00175 if (duplicate) {
00176 while (f < d_cur)
00177 if (&a == *f)
00178 break;
00179 else
00180 f++;
00181 if (f == d_cur)
00182 return;
00183 } else {
00184 while (&a != *f)
00185 f++;
00186 }
00187 *f = *(--d_cur);
00188 } else if (p & AP_WEAKLY) {
00189 assert(wmp() > 1U);
00190 wmp(wmp()-1);
00191 }
00192 }
00193
00194 unsigned int
00195 Space::propagators(void) const {
00196 unsigned int n = 0;
00197 for (Propagators p(*this); p(); ++p)
00198 n++;
00199 return n;
00200 }
00201
00202 unsigned int
00203 Space::branchers(void) const {
00204 unsigned int n = 0;
00205 for (Branchers b(*this); b(); ++b)
00206 n++;
00207 return n;
00208 }
00209
00210 void
00211 Space::flush(void) {
00212
00213 sm->flush();
00214 }
00215
00216 Space::~Space(void) {
00217
00218 fail();
00219
00220 {
00221 Actor** a = d_fst;
00222 Actor** e = d_cur;
00223
00224 d_fst = NULL;
00225 while (a < e) {
00226 (void) (*a)->dispose(*this);
00227 a++;
00228 }
00229 }
00230 #ifdef GECODE_HAS_VAR_DISPOSE
00231
00232 for (int i=AllVarConf::idx_d; i--;)
00233 if (_vars_d[i] != NULL)
00234 vd[i]->dispose(*this, _vars_d[i]);
00235 #endif
00236
00237 mm.release(sm);
00238
00239 if (sm->release())
00240 delete sm;
00241 }
00242
00243
00244
00245
00246
00247
00248
00249
00250 SpaceStatus
00251 Space::status(StatusStatistics& stat) {
00252 SpaceStatus s = SS_FAILED;
00253
00254 if (failed()) {
00255 s = SS_FAILED; goto exit;
00256 }
00257 assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
00258
00259 if (pc.p.active >= &pc.p.queue[0]) {
00260 Propagator* p;
00261 ModEventDelta med_o;
00262 goto unstable;
00263 execute:
00264 stat.propagate++;
00265
00266 med_o = p->u.med;
00267
00268 p->u.med = 0;
00269 switch (p->propagate(*this,med_o)) {
00270 case ES_FAILED:
00271
00272 if (afc_enabled())
00273 gafc.fail(p->gafc);
00274
00275 fail(); s = SS_FAILED; goto exit;
00276 case ES_NOFIX:
00277
00278 if (p->u.med != 0) {
00279 unstable:
00280
00281 do {
00282 assert(pc.p.active >= &pc.p.queue[0]);
00283
00284 ActorLink* fst = pc.p.active->next();
00285 if (pc.p.active != fst) {
00286 p = Propagator::cast(fst);
00287 goto execute;
00288 }
00289 pc.p.active--;
00290 } while (true);
00291 GECODE_NEVER;
00292 }
00293
00294 case ES_FIX:
00295
00296 p->u.med = 0; p->unlink(); pl.head(p);
00297 stable_or_unstable:
00298
00299 do {
00300 assert(pc.p.active >= &pc.p.queue[0]);
00301
00302 ActorLink* fst = pc.p.active->next();
00303 if (pc.p.active != fst) {
00304 p = Propagator::cast(fst);
00305 goto execute;
00306 }
00307 } while (--pc.p.active >= &pc.p.queue[0]);
00308 assert(pc.p.active < &pc.p.queue[0]);
00309 goto stable;
00310 case __ES_SUBSUMED:
00311 p->unlink(); rfree(p,p->u.size);
00312 goto stable_or_unstable;
00313 case __ES_PARTIAL:
00314
00315 assert(p->u.med != 0);
00316 enqueue(p);
00317 goto unstable;
00318 default:
00319 GECODE_NEVER;
00320 }
00321 }
00322 stable:
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346 while (b_status != Brancher::cast(&bl))
00347 if (b_status->status(*this)) {
00348
00349 s = SS_BRANCH; goto exit;
00350 } else {
00351
00352 b_status = Brancher::cast(b_status->next());
00353 }
00354
00355 s = SS_SOLVED;
00356 exit:
00357 stat.wmp = (wmp() > 0U);
00358 if (wmp() == 1U)
00359 wmp(0U);
00360 return s;
00361 }
00362
00363
00364 const Choice*
00365 Space::choice(void) {
00366 if (!stable())
00367 throw SpaceNotStable("Space::choice");
00368 if (failed() || (b_status == Brancher::cast(&bl))) {
00369
00370
00371 Brancher* b = Brancher::cast(bl.next());
00372 while (b != Brancher::cast(&bl)) {
00373 Brancher* d = b;
00374 b = Brancher::cast(b->next());
00375 rfree(d,d->dispose(*this));
00376 }
00377 bl.init();
00378 b_status = b_commit = Brancher::cast(&bl);
00379 return NULL;
00380 }
00381
00382
00383
00384
00385 Brancher* b = Brancher::cast(bl.next());
00386 while (b != b_status) {
00387 Brancher* d = b;
00388 b = Brancher::cast(b->next());
00389 d->unlink();
00390 rfree(d,d->dispose(*this));
00391 }
00392
00393 b_commit = b_status;
00394 return b_status->choice(*this);
00395 }
00396
00397 const Choice*
00398 Space::choice(Archive& e) const {
00399 unsigned int id; e >> id;
00400 Brancher* b_cur = Brancher::cast(bl.next());
00401 while (b_cur != Brancher::cast(&bl)) {
00402 if (id == b_cur->id())
00403 return b_cur->choice(*this,e);
00404 b_cur = Brancher::cast(b_cur->next());
00405 }
00406 throw SpaceNoBrancher("Space::choice");
00407 }
00408
00409 void
00410 Space::_commit(const Choice& c, unsigned int a) {
00411 if (a >= c.alternatives())
00412 throw SpaceIllegalAlternative("Space::commit");
00413 if (failed())
00414 return;
00415 if (Brancher* b = brancher(c._id)) {
00416
00417 if (b->commit(*this,c,a) == ES_FAILED)
00418 fail();
00419 } else {
00420
00421 throw SpaceNoBrancher("Space::commit");
00422 }
00423 }
00424
00425 void
00426 Space::_trycommit(const Choice& c, unsigned int a) {
00427 if (a >= c.alternatives())
00428 throw SpaceIllegalAlternative("Space::commit");
00429 if (failed())
00430 return;
00431 if (Brancher* b = brancher(c._id)) {
00432
00433 if (b->commit(*this,c,a) == ES_FAILED)
00434 fail();
00435 }
00436 }
00437
00438 NGL*
00439 Space::ngl(const Choice& c, unsigned int a) {
00440 if (a >= c.alternatives())
00441 throw SpaceIllegalAlternative("Space::ngl");
00442 if (failed())
00443 return NULL;
00444 if (Brancher* b = brancher(c._id)) {
00445
00446 return b->ngl(*this,c,a);
00447 } else {
00448 return NULL;
00449 }
00450 }
00451
00452 void
00453 Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
00454 if (a >= c.alternatives())
00455 throw SpaceIllegalAlternative("Space::print");
00456 if (failed())
00457 return;
00458 if (Brancher* b = const_cast<Space&>(*this).brancher(c._id)) {
00459
00460 b->print(*this,c,a,o);
00461 } else {
00462
00463 throw SpaceNoBrancher("Space::print");
00464 }
00465 }
00466
00467 void
00468 Space::kill_brancher(unsigned int id) {
00469 if (failed())
00470 return;
00471 for (Brancher* b = Brancher::cast(bl.next());
00472 b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
00473 if (b->id() == id) {
00474
00475 if (b_commit == b)
00476 b_commit = Brancher::cast(b->next());
00477 if (b_status == b)
00478 b_status = Brancher::cast(b->next());
00479 b->unlink();
00480 rfree(b,b->dispose(*this));
00481 return;
00482 }
00483 }
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499 Space::Space(bool share, Space& s)
00500 : sm(s.sm->copy(share)),
00501 mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
00502 gafc(s.gafc),
00503 d_fst(&Actor::sentinel),
00504 _wmp_afc(s._wmp_afc) {
00505 #ifdef GECODE_HAS_VAR_DISPOSE
00506 for (int i=0; i<AllVarConf::idx_d; i++)
00507 _vars_d[i] = NULL;
00508 #endif
00509 for (int i=0; i<AllVarConf::idx_c; i++)
00510 pc.c.vars_u[i] = NULL;
00511 pc.c.vars_noidx = NULL;
00512 pc.c.shared = NULL;
00513 pc.c.local = NULL;
00514
00515 {
00516 ActorLink* p = &pl;
00517 ActorLink* e = &s.pl;
00518 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00519 Actor* c = Actor::cast(a)->copy(*this,share);
00520
00521 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00522
00523 p = c;
00524 }
00525
00526 p->next(&pl); pl.prev(p);
00527 }
00528
00529 {
00530 ActorLink* p = &bl;
00531 ActorLink* e = &s.bl;
00532 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00533 Actor* c = Actor::cast(a)->copy(*this,share);
00534
00535 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00536
00537 p = c;
00538 }
00539
00540 p->next(&bl); bl.prev(p);
00541 }
00542
00543 if (s.b_status == &s.bl) {
00544 b_status = Brancher::cast(&bl);
00545 } else {
00546 b_status = Brancher::cast(s.b_status->prev());
00547 }
00548 if (s.b_commit == &s.bl) {
00549 b_commit = Brancher::cast(&bl);
00550 } else {
00551 b_commit = Brancher::cast(s.b_commit->prev());
00552 }
00553 }
00554
00555 Space*
00556 Space::_clone(bool share) {
00557 if (failed())
00558 throw SpaceFailed("Space::clone");
00559 if (!stable())
00560 throw SpaceNotStable("Space::clone");
00561
00562
00563 Space* c = copy(share);
00564
00565 if (c->d_fst != &Actor::sentinel)
00566 throw SpaceNotCloned("Space::clone");
00567
00568
00569 {
00570 unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
00571 if (n == 0) {
00572
00573 c->d_fst = c->d_cur = c->d_lst = NULL;
00574 } else {
00575
00576 c->d_fst = c->alloc<Actor*>(n+1);
00577 c->d_cur = c->d_fst;
00578 c->d_lst = c->d_fst+n+1;
00579 for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
00580 if ((*d_fst_iter)->prev())
00581 *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
00582 }
00583 }
00584 }
00585
00586
00587 VarImp<NoIdxVarImpConf>* x =
00588 static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
00589 while (x != NULL) {
00590 VarImp<NoIdxVarImpConf>* n = x->next();
00591 x->b.base = NULL; x->u.idx[0] = 0;
00592 if (sizeof(ActorLink**) > sizeof(unsigned int))
00593 *(1+&x->u.idx[0]) = 0;
00594 x = n;
00595 }
00596
00597 c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
00598
00599
00600 {
00601 ActorLink* p_a = &pl;
00602 ActorLink* c_a = p_a->next();
00603
00604 while (c_a != &pl) {
00605 Propagator* p = Propagator::cast(c_a);
00606 if (p->u.advisors != NULL) {
00607 ActorLink* a = p->u.advisors;
00608 p->u.advisors = NULL;
00609 do {
00610 a->prev(p); a = a->next();
00611 } while (a != NULL);
00612 }
00613 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00614 }
00615 }
00616 {
00617 ActorLink* p_a = &bl;
00618 ActorLink* c_a = p_a->next();
00619
00620 while (c_a != &bl) {
00621 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00622 }
00623 }
00624
00625
00626 for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
00627 s->fwd = NULL;
00628
00629
00630 for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
00631 l->prev(NULL);
00632
00633
00634 c->pc.p.active = &c->pc.p.queue[0]-1;
00635 for (int i=0; i<=PropCost::AC_MAX; i++)
00636 c->pc.p.queue[i].init();
00637
00638 c->pc.p.n_sub = pc.p.n_sub;
00639 c->pc.p.branch_id = pc.p.branch_id;
00640 return c;
00641 }
00642
00643 void
00644 Space::constrain(const Space&) {
00645 }
00646
00647 void
00648 Space::master(unsigned long int, const Space*, NoGoods& ng) {
00649 ng.post(*this);
00650 }
00651
00652 void
00653 Space::slave(unsigned long int, const Space*) {
00654 }
00655
00656 void
00657 LocalObject::fwdcopy(Space& home, bool share) {
00658 ActorLink::cast(this)->prev(copy(home,share));
00659 next(home.pc.c.local);
00660 home.pc.c.local = this;
00661 }
00662
00663 void
00664 Choice::archive(Archive& e) const {
00665 e << id();
00666 }
00667
00668 void
00669 Space::afc_decay(double d) {
00670 afc_enable();
00671
00672 if (gafc.decay() != 1.0)
00673 for (Propagators p(*this); p(); ++p)
00674 (void) gafc.afc(p.propagator().gafc);
00675 gafc.decay(d);
00676 }
00677
00678 void
00679 Space::afc_set(double a) {
00680 afc_enable();
00681 for (Propagators p(*this); p(); ++p)
00682 gafc.set(p.propagator().gafc,a);
00683 }
00684
00685
00686 bool
00687 NGL::notice(void) const {
00688 return false;
00689 }
00690
00691 }
00692
00693