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 VarDisposerBase::dispose(Space*,VarImpBase*) {}
00048
00049 VarDisposerBase::~VarDisposerBase(void) {}
00050
00051
00052
00053
00054
00055
00056
00057 Reflection::ActorSpec
00058 Actor::spec(const Space*, Reflection::VarMap&) const {
00059 throw Reflection::NoReflectionDefinedException();
00060 }
00061
00062 size_t
00063 Actor::allocated(void) const {
00064 return 0;
00065 }
00066
00067 #ifdef __GNUC__
00069 Actor::~Actor(void) {}
00070 #endif
00071
00072
00073
00074
00075
00076
00077
00078 ExecStatus
00079 Propagator::advise(Space*, Advisor*, const Delta*) {
00080 assert(false);
00081 return ES_FAILED;
00082 }
00083
00084
00085
00086
00087
00088
00089
00090 Reflection::BranchingSpec
00091 Branching::branchingSpec(const Space*,
00092 Reflection::VarMap&, const BranchingDesc*) const {
00093 throw Reflection::NoReflectionDefinedException();
00094 }
00095
00096
00097
00098
00099
00100
00101
00102 unsigned long int Space::unused_uli;
00103
00104 #ifdef GECODE_HAS_VAR_DISPOSE
00105 VarDisposerBase* Space::vd[AllVarConf::idx_d];
00106 #endif
00107
00108 Space::Space(void) {
00109 #ifdef GECODE_HAS_VAR_DISPOSE
00110 for (int i=0; i<AllVarConf::idx_d; i++)
00111 _vars_d[i] = NULL;
00112 #endif
00113
00114 a_actors.init();
00115 b_status = b_commit = Branching::cast(&a_actors);
00116
00117 d_fst = d_cur = d_lst = NULL;
00118
00119 pc.p.active = &pc.p.queue[0]-1;
00120 for (int i=0; i<=PC_MAX; i++)
00121 pc.p.queue[i].init();
00122 pc.p.branch_id = 0;
00123 pc.p.n_sub = 0;
00124 }
00125
00126 size_t
00127 Space::allocated(void) const {
00128 size_t s = mm.allocated();
00129 Actor** a = d_fst;
00130 Actor** e = d_cur;
00131 while (a < e) {
00132 s += (*a)->allocated(); a++;
00133 }
00134 return s;
00135 }
00136
00137 void
00138 Space::d_resize(void) {
00139 if (d_fst == NULL) {
00140
00141 d_fst = static_cast<Actor**>(alloc(4*sizeof(Actor*)));
00142 d_cur = d_fst;
00143 d_lst = d_fst+4;
00144 } else {
00145
00146 ptrdiff_t n = d_lst - d_fst;
00147 assert(n != 0);
00148 Actor** a = static_cast<Actor**>(alloc(2*n*sizeof(Actor*)));
00149 memcpy(a, d_fst, n*sizeof(Actor*));
00150 reuse(d_fst,n*sizeof(Actor*));
00151 d_fst = a;
00152 d_cur = a+n;
00153 d_lst = a+2*n;
00154 }
00155 }
00156
00157 unsigned int
00158 Space::propagators(void) const {
00159 unsigned int n = 0;
00160 for (ActorLink* q = pc.p.active; q >= &pc.p.queue[0]; q--)
00161 for (ActorLink* a = q->next(); a != q; a = a->next())
00162 n++;
00163 for (ActorLink* a = a_actors.next();
00164 Branching::cast(a) != b_commit; a = a->next())
00165 n++;
00166 return n;
00167 }
00168
00169 unsigned int
00170 Space::branchings(void) const {
00171 unsigned int n = 0;
00172 for (ActorLink* a = Branching::cast(b_status);
00173 a != &a_actors; a = a->next())
00174 n++;
00175 return n;
00176 }
00177
00178 void
00179 Space::getVars(Reflection::VarMap&, bool) {}
00180
00181 Reflection::BranchingSpec
00182 Space::branchingSpec(Reflection::VarMap& m, const BranchingDesc* d) const {
00183 const Branching* b = b_commit;
00184 while ((b != Branching::cast(&a_actors)) && (d->_id != b->id))
00185 b = Branching::cast(b->next());
00186 if (b == Branching::cast(&a_actors))
00187 throw SpaceNoBranching();
00188 return b->branchingSpec(this, m, d);
00189 }
00190
00191 Space::~Space(void) {
00192
00193 fail();
00194
00195 {
00196 Actor** a = d_fst;
00197 Actor** e = d_cur;
00198
00199 d_fst = NULL;
00200 while (a < e) {
00201 (void) (*a)->dispose(this);
00202 a++;
00203 }
00204 }
00205 #ifdef GECODE_HAS_VAR_DISPOSE
00206
00207 for (int i=AllVarConf::idx_d; i--;)
00208 if (_vars_d[i] != NULL)
00209 vd[i]->dispose(this, _vars_d[i]);
00210 #endif
00211 }
00212
00213
00214
00215
00216
00217
00218
00219 SpaceStatus
00220 Space::status(unsigned long int& pn) {
00221 if (failed())
00222 return SS_FAILED;
00223 if (!stable()) {
00224 assert(pc.p.active >= &pc.p.queue[0]);
00225 Propagator* p;
00226 ModEventDelta med_o;
00227 goto unstable;
00228 execute:
00229 pn++;
00230
00231 med_o = p->u.med;
00232
00233 p->u.med = 0;
00234 switch (p->propagate(this,med_o)) {
00235 case ES_FAILED:
00236 fail();
00237 return SS_FAILED;
00238 case ES_NOFIX:
00239
00240 if (p->u.med != 0) {
00241 unstable:
00242
00243 do {
00244 assert(pc.p.active >= &pc.p.queue[0]);
00245
00246 ActorLink* fst = pc.p.active->next();
00247 if (pc.p.active != fst) {
00248 p = Propagator::cast(fst);
00249 goto execute;
00250 }
00251 pc.p.active--;
00252 } while (true);
00253 GECODE_NEVER;
00254 }
00255
00256 case ES_FIX:
00257
00258 p->u.med = 0; p->unlink(); a_actors.head(p);
00259 stable_or_unstable:
00260
00261 do {
00262 assert(pc.p.active >= &pc.p.queue[0]);
00263
00264 ActorLink* fst = pc.p.active->next();
00265 if (pc.p.active != fst) {
00266 p = Propagator::cast(fst);
00267 goto execute;
00268 }
00269 } while (--pc.p.active >= &pc.p.queue[0]);
00270 assert(pc.p.active < &pc.p.queue[0]);
00271 goto stable;
00272 case __ES_SUBSUMED:
00273 p->unlink(); reuse(p,p->u.size);
00274 goto stable_or_unstable;
00275 case __ES_PARTIAL:
00276
00277 enqueue(p);
00278 goto unstable;
00279 default:
00280 GECODE_NEVER;
00281 }
00282 }
00283 stable:
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307 while (b_status != Branching::cast(&a_actors)) {
00308 if (b_status->status(this))
00309 return SS_BRANCH;
00310 b_status = Branching::cast(b_status->next());
00311 }
00312
00313 return SS_SOLVED;
00314 }
00315
00316
00317 void
00318 Space::commit(const BranchingDesc* d, unsigned int a) {
00319 if (failed())
00320 return;
00321
00322
00323
00324
00325
00326
00327
00328
00329 while ((b_commit != Branching::cast(&a_actors)) &&
00330 (d->_id != b_commit->id)) {
00331 Branching* b = b_commit;
00332 b_commit = Branching::cast(b_commit->next());
00333 if (b == b_status)
00334 b_status = b_commit;
00335 b->unlink();
00336 reuse(b,b->dispose(this));
00337 }
00338 if (b_commit == Branching::cast(&a_actors))
00339 throw SpaceNoBranching();
00340 if (a >= d->alternatives())
00341 throw SpaceIllegalAlternative();
00342 if (b_commit->commit(this,d,a) == ES_FAILED)
00343 fail();
00344 }
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359 Space::Space(bool share, Space& s)
00360 : mm(s.mm,s.pc.p.n_sub*sizeof(Propagator**)) {
00361 #ifdef GECODE_HAS_VAR_DISPOSE
00362 for (int i=0; i<AllVarConf::idx_d; i++)
00363 _vars_d[i] = NULL;
00364 #endif
00365 for (int i=0; i<AllVarConf::idx_c; i++)
00366 pc.c.vars_u[i] = NULL;
00367 pc.c.vars_noidx = NULL;
00368 pc.c.shared = NULL;
00369
00370 {
00371 ActorLink* p = &a_actors;
00372 ActorLink* e = &s.a_actors;
00373 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00374 Actor* c = Actor::cast(a)->copy(this,share);
00375
00376 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00377
00378 p = c;
00379 }
00380
00381 p->next(&a_actors); a_actors.prev(p);
00382 }
00383
00384 {
00385 ptrdiff_t n = s.d_cur - s.d_fst;
00386 if (n == 0) {
00387
00388 d_fst = d_cur = d_lst = NULL;
00389 } else {
00390
00391 Actor** a = static_cast<Actor**>(alloc((n+1)*sizeof(Actor*)));
00392 d_fst = a;
00393 d_cur = a+n;
00394 d_lst = a+n+1;
00395 Actor** f = s.d_fst;
00396 do {
00397 n--;
00398 a[n] = Actor::cast(f[n]->prev());
00399 } while (n != 0);
00400 }
00401 }
00402
00403 if (s.b_status == &s.a_actors) {
00404 b_status = Branching::cast(&a_actors);
00405 } else {
00406 b_status = Branching::cast(s.b_status->prev());
00407 }
00408 if (s.b_commit == &s.a_actors) {
00409 b_commit = Branching::cast(&a_actors);
00410 } else {
00411 b_commit = Branching::cast(s.b_commit->prev());
00412 }
00413 }
00414
00415 Space*
00416 Space::clone(bool share) {
00417 if (failed())
00418 throw SpaceFailed("Space::clone");
00419 if (!stable())
00420 throw SpaceNotStable("Space::clone");
00421
00422
00423 Space* c = copy(share);
00424
00425
00426 VarImp<NoIdxVarImpConf>* x =
00427 static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
00428 while (x != NULL) {
00429 VarImp<NoIdxVarImpConf>* n = x->next();
00430 x->idx[0] = x->idx[1] = NULL;
00431 x = n;
00432 }
00433
00434 c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
00435
00436
00437 ActorLink* p_a = &a_actors;
00438 ActorLink* c_a = p_a->next();
00439
00440 while (c_a != b_commit) {
00441 Propagator* p = Propagator::cast(c_a);
00442 if (p->u.advisors != NULL) {
00443 ActorLink* a = p->u.advisors;
00444 p->u.advisors = NULL;
00445 do {
00446 a->prev(p); a = a->next();
00447 } while (a != NULL);
00448 }
00449 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00450 }
00451
00452 while (c_a != &a_actors) {
00453 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00454 }
00455 assert(c_a->prev() == p_a);
00456
00457
00458 for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
00459 s->fwd = NULL;
00460
00461
00462 c->pc.p.active = &c->pc.p.queue[0]-1;
00463 for (int i=0; i<=PC_MAX; i++)
00464 c->pc.p.queue[i].init();
00465
00466 c->pc.p.n_sub = pc.p.n_sub;
00467 c->pc.p.branch_id = pc.p.branch_id;
00468 return c;
00469 }
00470
00471 }
00472
00473