core.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/kernel.hh"
00023
00024 namespace Gecode {
00025
00026 unsigned long int Space::unused_uli;
00027 unsigned int Space::unused_ui;
00028
00029
00030
00031
00032
00033
00034 Space::VarTypeData Space::vtd[VTI_LAST];
00035
00036 VarTypeProcessorBase::~VarTypeProcessorBase(void) {}
00037
00038 Space::Space(void) {
00039
00040 for (int i=0; i<VTI_LAST; i++)
00041 vars[i]=NULL;
00042
00043 pool_next = 0;
00044 for (int i=0; i<=PC_MAX; i++)
00045 pool[i].init();
00046
00047 a_actors.init();
00048 a_actors.init_delete();
00049 b_fst = static_cast<Branching*>(&a_actors);
00050 }
00051
00052
00053
00054
00055
00056
00057
00058
00059 void
00060 Actor::flush(void) {}
00061
00062 size_t
00063 Actor::cached(void) const {
00064 return 0;
00065 }
00066
00067 void
00068 Space::flush(void) {
00069
00070 ActorDeleteLink* e = &a_actors;
00071 ActorDeleteLink* a = e->next_delete();
00072 while (a != e) {
00073 static_cast<Actor*>(a)->flush(); a = a->next_delete();
00074 }
00075 }
00076
00077 size_t
00078 Space::cached(void) const {
00079 size_t s = 0;
00080 const ActorDeleteLink* e = &a_actors;
00081 const ActorDeleteLink* a = e->next_delete();
00082 while (a != e) {
00083 s += static_cast<const Actor*>(a)->cached();
00084 a = a->next_delete();
00085 }
00086 return s;
00087 }
00088
00089 Space::~Space(void) {
00090
00091 fail();
00092
00093 ActorDeleteLink* e = &a_actors;
00094 ActorDeleteLink* a = e->next_delete();
00095 while (a != e) {
00096 Actor* d = static_cast<Actor*>(a);
00097 a = a->next_delete();
00098 d->dispose(this);
00099 }
00100 }
00101
00102
00103
00104
00105
00106
00107
00108 forceinline void
00109 Space::process(void) {
00110 for (int vti=VTI_LAST; vti--; ) {
00111 VarBase* vs = vars[vti];
00112 if (vs != NULL) {
00113 vars[vti] = NULL; vtd[vti].proc->process(this,vs);
00114 }
00115 }
00116 }
00117
00118 forceinline bool
00119 Space::pool_get(Propagator*& p) {
00120 for (int c = pool_next+1; c--; ) {
00121
00122 ActorLink* lnk = &pool[c];
00123
00124 ActorLink* fst = lnk->next();
00125 if (lnk != fst) {
00126 pool_next = c;
00127
00128 ActorLink* snd = fst->next();
00129 lnk->next(snd); snd->prev(lnk);
00130 p = static_cast<Propagator*>(fst);
00131 return true;
00132 }
00133 }
00134 pool_next = 0;
00135 return false;
00136 }
00137
00138 unsigned long int
00139 Space::_propagate(void) {
00140 if (failed())
00141 return 0;
00142 const PropModEvent PME_NONE = 0;
00143 const PropModEvent PME_ASSIGNED =
00144 ((ME_GEN_ASSIGNED << 0) | (ME_GEN_ASSIGNED << 4) |
00145 (ME_GEN_ASSIGNED << 8) | (ME_GEN_ASSIGNED << 12) |
00146 (ME_GEN_ASSIGNED << 16) | (ME_GEN_ASSIGNED << 20) |
00147 (ME_GEN_ASSIGNED << 24) | (ME_GEN_ASSIGNED << 28));
00148
00149
00150
00151
00152 unsigned long int pn = 0;
00153
00154
00155
00156
00157
00158 process();
00159 Propagator* p;
00160 while (pool_get(p)) {
00161 pn++;
00162 switch (p->propagate(this)) {
00163 case ES_FAILED:
00164 fail();
00165 return pn;
00166 case ES_FIX:
00167 {
00168
00169 propagator(p);
00170
00171 p->pme = PME_ASSIGNED;
00172 process();
00173 p->pme = PME_NONE;
00174 }
00175 break;
00176 case ES_NOFIX:
00177 {
00178
00179 propagator(p);
00180 p->pme = PME_NONE;
00181 process();
00182 }
00183 break;
00184 case ES_SUBSUMED:
00185 {
00186
00187 p->pme = PME_ASSIGNED;
00188 process();
00189 p->destruct(this);
00190 }
00191 break;
00192 case __ES_FIX_PARTIAL:
00193 {
00194
00195 PropModEvent keep = p->pme;
00196
00197 p->pme = PME_ASSIGNED;
00198 process();
00199 p->pme = keep;
00200 assert(p->pme);
00201 pool_put(p);
00202 }
00203 break;
00204 case __ES_NOFIX_PARTIAL:
00205 {
00206
00207 pool_put(p);
00208 process();
00209 }
00210 break;
00211 }
00212 }
00213 return pn;
00214 }
00215
00216
00217
00218
00219
00220
00221
00222 unsigned int
00223 Space::_branch(void) {
00224 while (b_fst != &a_actors) {
00225 unsigned int alt = b_fst->branch(this);
00226 if (alt > 0)
00227 return alt;
00228 Branching* b = b_fst;
00229 b_fst = static_cast<Branching*>(b->next());
00230 b->unlink();
00231 b->destruct(this);
00232 }
00233 return 0;
00234 }
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249 SpaceStatus
00250 Space::status(unsigned int& a, unsigned long int& pn) {
00251
00252 pn += _propagate();
00253 if (failed())
00254 return SS_FAILED;
00255
00256
00257 a = _branch();
00258 return (a > 0) ? SS_BRANCH : SS_SOLVED;
00259 }
00260
00261 void
00262 Space::commit(unsigned int a, BranchingDesc* d,
00263 unsigned long int& pn) {
00264 if (d == NULL) {
00265
00266
00267
00268 pn += _propagate();
00269 if (failed())
00270 throw SpaceFailed("Space::commit");
00271 unsigned int alt = _branch();
00272 if (alt == 0)
00273 throw SpaceNoBranching();
00274 if (a >= alt)
00275 throw SpaceIllegalAlternative();
00276 assert(b_fst != NULL);
00277
00278 if (b_fst->commit(this,a,NULL) == ES_FAILED)
00279 fail();
00280 } else {
00281 if (failed())
00282 throw SpaceFailed("Space::commit");
00283
00284
00285
00286
00287
00288
00289 while (d->id != b_fst->id) {
00290 Branching* b = b_fst;
00291 b_fst = static_cast<Branching*>(b_fst->next());
00292 b->unlink();
00293 b->destruct(this);
00294 }
00295 if (b_fst->commit(this,a,d) == ES_FAILED)
00296 fail();
00297 }
00298 }
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313 Space::Space(bool share, Space& s) : mm(s.mm) {
00314
00315 for (int i=0; i<VTI_LAST; i++)
00316 vars[i]=NULL;
00317
00318 pool_next = 0;
00319 for (int i=0; i<=PC_MAX; i++)
00320 pool[i].init();
00321
00322 {
00323 ActorLink* p = &a_actors;
00324 ActorLink* e = &s.a_actors;
00325 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00326 ActorLink* c = static_cast<Actor*>(a)->copy(this,share);
00327
00328 p->next(c); c->prev(p);
00329
00330 a->prev(c);
00331
00332 static_cast<ActorDeleteLink*>(c)->init_delete();
00333 p = c;
00334 }
00335
00336 p->next(&a_actors); a_actors.prev(p);
00337 }
00338
00339 {
00340 ActorDeleteLink* p = &a_actors;
00341 ActorDeleteLink* e = &s.a_actors;
00342 for (ActorDeleteLink* a = e->next_delete(); a != e;
00343 a = a->next_delete()) {
00344 ActorDeleteLink* c = static_cast<ActorDeleteLink*>(a->prev());
00345
00346 p->next_delete(c); c->prev_delete(p);
00347
00348 p = c;
00349 }
00350
00351 p->next_delete(&a_actors); a_actors.prev_delete(p);
00352 }
00353
00354 if (s.b_fst == &s.a_actors) {
00355 b_fst = static_cast<Branching*>(&a_actors);
00356 } else {
00357 b_fst = static_cast<Branching*>(s.b_fst->prev());
00358 }
00359 }
00360
00361
00362
00363
00364
00365
00366
00367 Space*
00368 Space::clone(bool share, unsigned long int& pn) {
00369 pn += _propagate();
00370 if (failed())
00371 throw SpaceFailed("Space::clone");
00372
00373 Space* c = copy(share);
00374
00375 for (int vti=VTI_LAST; vti--; ) {
00376 VarBase* vs = c->vars[vti];
00377 if (vs != NULL) {
00378 c->vars[vti] = NULL; vtd[vti].proc->update(c,vs);
00379 }
00380 }
00381
00382 ActorLink* p = &a_actors;
00383 ActorLink* a = p->next();
00384 while (a != &a_actors) {
00385 a->prev(p); p = a; a = a->next();
00386 }
00387 assert(a->prev() == p);
00388 return c;
00389 }
00390
00391 unsigned int
00392 Space::propagators(void) const {
00393 if (failed())
00394 throw SpaceFailed("Space::propagators");
00395 unsigned int n = 0;
00396 for (const ActorLink* a = a_actors.next(); a != b_fst; a = a->next())
00397 n++;
00398 return n;
00399 }
00400
00401 unsigned int
00402 Space::branchings(void) const {
00403 if (failed())
00404 throw SpaceFailed("Space::branchings");
00405 unsigned int n = 0;
00406 for (const ActorLink* a = b_fst; a != &a_actors; a = a->next())
00407 n++;
00408 return n;
00409 }
00410
00411 }
00412
00413
00414