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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
00039 #define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/meta/nogoods.hh>
00045
00046 namespace Gecode { namespace Search { namespace Sequential {
00047
00061 class Path : public NoGoods {
00062 friend class Search::Meta::NoGoodsProp;
00063 public:
00065 class Edge {
00066 protected:
00068 Space* _space;
00070 unsigned int _alt;
00072 const Choice* _choice;
00073 public:
00075 Edge(void);
00077 Edge(Space* s, Space* c);
00078
00080 Space* space(void) const;
00082 void space(Space* s);
00083
00085 const Choice* choice(void) const;
00086
00088 unsigned int alt(void) const;
00090 unsigned int truealt(void) const;
00092 bool leftmost(void) const;
00094 bool rightmost(void) const;
00096 void next(void);
00098 bool lao(void) const;
00099
00101 void dispose(void);
00102 };
00103 protected:
00105 Support::DynamicStack<Edge,Heap> ds;
00107 int _ngdl;
00108 public:
00110 Path(int l);
00112 int ngdl(void) const;
00114 void ngdl(int l);
00116 const Choice* push(Worker& stat, Space* s, Space* c);
00118 bool next(void);
00120 Edge& top(void) const;
00122 bool empty(void) const;
00124 int lc(void) const;
00126 void unwind(int l);
00128 void commit(Space* s, int i) const;
00130 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
00132 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
00133 const Space* best, int& mark);
00135 int entries(void) const;
00137 void reset(void);
00139 void virtual post(Space& home);
00140 };
00141
00142
00143
00144
00145
00146
00147 forceinline
00148 Path::Edge::Edge(void) {}
00149
00150 forceinline
00151 Path::Edge::Edge(Space* s, Space* c)
00152 : _space(c), _alt(0), _choice(s->choice()) {}
00153
00154 forceinline Space*
00155 Path::Edge::space(void) const {
00156 return _space;
00157 }
00158 forceinline void
00159 Path::Edge::space(Space* s) {
00160 _space = s;
00161 }
00162
00163 forceinline unsigned int
00164 Path::Edge::alt(void) const {
00165 return _alt;
00166 }
00167 forceinline unsigned int
00168 Path::Edge::truealt(void) const {
00169 assert(_alt < _choice->alternatives());
00170 return _alt;
00171 }
00172 forceinline bool
00173 Path::Edge::leftmost(void) const {
00174 return _alt == 0;
00175 }
00176 forceinline bool
00177 Path::Edge::rightmost(void) const {
00178 return _alt+1 >= _choice->alternatives();
00179 }
00180 forceinline bool
00181 Path::Edge::lao(void) const {
00182 return _alt >= _choice->alternatives();
00183 }
00184 forceinline void
00185 Path::Edge::next(void) {
00186 _alt++;
00187 }
00188
00189 forceinline const Choice*
00190 Path::Edge::choice(void) const {
00191 return _choice;
00192 }
00193
00194 forceinline void
00195 Path::Edge::dispose(void) {
00196 delete _space;
00197 delete _choice;
00198 }
00199
00200
00201
00202
00203
00204
00205
00206
00207 forceinline
00208 Path::Path(int l)
00209 : ds(heap), _ngdl(l) {}
00210
00211 forceinline int
00212 Path::ngdl(void) const {
00213 return _ngdl;
00214 }
00215
00216 forceinline void
00217 Path::ngdl(int l) {
00218 _ngdl = l;
00219 }
00220
00221 forceinline const Choice*
00222 Path::push(Worker& stat, Space* s, Space* c) {
00223 if (!ds.empty() && ds.top().lao()) {
00224
00225 ds.pop().dispose();
00226 }
00227 Edge sn(s,c);
00228 ds.push(sn);
00229 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00230 return sn.choice();
00231 }
00232
00233 forceinline bool
00234 Path::next(void) {
00235 while (!ds.empty())
00236 if (ds.top().rightmost()) {
00237 ds.pop().dispose();
00238 } else {
00239 ds.top().next();
00240 return true;
00241 }
00242 return false;
00243 }
00244
00245 forceinline Path::Edge&
00246 Path::top(void) const {
00247 assert(!ds.empty());
00248 return ds.top();
00249 }
00250
00251 forceinline bool
00252 Path::empty(void) const {
00253 return ds.empty();
00254 }
00255
00256 forceinline void
00257 Path::commit(Space* s, int i) const {
00258 const Edge& n = ds[i];
00259 s->commit(*n.choice(),n.alt());
00260 }
00261
00262 forceinline int
00263 Path::lc(void) const {
00264 int l = ds.entries()-1;
00265 while (ds[l].space() == NULL)
00266 l--;
00267 return l;
00268 }
00269
00270 forceinline int
00271 Path::entries(void) const {
00272 return ds.entries();
00273 }
00274
00275 forceinline void
00276 Path::unwind(int l) {
00277 assert((ds[l].space() == NULL) || ds[l].space()->failed());
00278 int n = ds.entries();
00279 for (int i=l; i<n; i++)
00280 ds.pop().dispose();
00281 assert(ds.entries() == l);
00282 }
00283
00284 inline void
00285 Path::reset(void) {
00286 while (!ds.empty())
00287 ds.pop().dispose();
00288 }
00289
00290 forceinline Space*
00291 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00292 assert(!ds.empty());
00293
00294
00295
00296
00297 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00298 Space* s = ds.top().space();
00299 s->commit(*ds.top().choice(),ds.top().alt());
00300 assert(ds.entries()-1 == lc());
00301 ds.top().space(NULL);
00302
00303 if (ds.entries() > ngdl())
00304 ds.top().next();
00305 d = 0;
00306 return s;
00307 }
00308
00309 int l = lc();
00310 int n = ds.entries();
00311
00312 d = static_cast<unsigned int>(n - l);
00313
00314 Space* s = ds[l].space()->clone();
00315
00316 if (d < a_d) {
00317
00318 for (int i=l; i<n; i++)
00319 commit(s,i);
00320 } else {
00321 int m = l + static_cast<int>(d >> 1);
00322 int i = l;
00323
00324 for (; i<m; i++ )
00325 commit(s,i);
00326
00327 for (; (i<n) && ds[i].rightmost(); i++)
00328 commit(s,i);
00329
00330 if (i<n-1) {
00331
00332 SpaceStatus ss = s->status(stat);
00333
00334
00335
00336
00337 if (ss == SS_FAILED) {
00338
00339 delete s;
00340 stat.fail++;
00341 unwind(i);
00342 return NULL;
00343 }
00344 ds[i].space(s->clone());
00345 d = static_cast<unsigned int>(n-i);
00346 }
00347
00348 for (; i<n; i++)
00349 commit(s,i);
00350 }
00351 return s;
00352 }
00353
00354 forceinline Space*
00355 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00356 const Space* best, int& mark) {
00357 assert(!ds.empty());
00358
00359
00360
00361
00362 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00363 Space* s = ds.top().space();
00364 s->commit(*ds.top().choice(),ds.top().alt());
00365 assert(ds.entries()-1 == lc());
00366 if (mark > ds.entries()-1) {
00367 mark = ds.entries()-1;
00368 s->constrain(*best);
00369 }
00370 ds.top().space(NULL);
00371
00372 if (ds.entries() > ngdl())
00373 ds.top().next();
00374 d = 0;
00375 return s;
00376 }
00377
00378 int l = lc();
00379 int n = ds.entries();
00380
00381 d = static_cast<unsigned int>(n - l);
00382
00383 Space* s = ds[l].space();
00384
00385 if (l < mark) {
00386 mark = l;
00387 s->constrain(*best);
00388
00389
00390 if (s->status(stat) == SS_FAILED) {
00391
00392 stat.fail++;
00393 unwind(l);
00394 return NULL;
00395 }
00396
00397
00398
00399 Space* c = s->clone();
00400 ds[l].space(c);
00401 } else {
00402 s = s->clone();
00403 }
00404
00405 if (d < a_d) {
00406
00407 for (int i=l; i<n; i++)
00408 commit(s,i);
00409 } else {
00410 int m = l + static_cast<int>(d >> 1);
00411 int i = l;
00412
00413 for (; i<m; i++ )
00414 commit(s,i);
00415
00416 for (; (i<n) && ds[i].rightmost(); i++)
00417 commit(s,i);
00418
00419 if (i<n-1) {
00420
00421 SpaceStatus ss = s->status(stat);
00422
00423
00424
00425
00426
00427
00428
00429 if (ss == SS_FAILED) {
00430
00431 delete s;
00432 stat.fail++;
00433 unwind(i);
00434 return NULL;
00435 }
00436 ds[i].space(s->clone());
00437 d = static_cast<unsigned int>(n-i);
00438 }
00439
00440 for (; i<n; i++)
00441 commit(s,i);
00442 }
00443 return s;
00444 }
00445
00446 }}}
00447
00448 #endif
00449
00450