path.hh
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 GECODE_VTABLE_EXPORT 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 unsigned int _ngdl;
00108 public:
00110 Path(unsigned int l);
00112 unsigned int ngdl(void) const;
00114 void ngdl(unsigned int l);
00116 const Choice* push(Worker& stat, Space* s, Space* c);
00118 void 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 GECODE_SEARCH_EXPORT virtual void post(Space& home) const;
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(unsigned int l)
00209 : ds(heap), _ngdl(l) {}
00210
00211 forceinline unsigned int
00212 Path::ngdl(void) const {
00213 return _ngdl;
00214 }
00215
00216 forceinline void
00217 Path::ngdl(unsigned 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 void
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;
00241 }
00242 }
00243
00244 forceinline Path::Edge&
00245 Path::top(void) const {
00246 assert(!ds.empty());
00247 return ds.top();
00248 }
00249
00250 forceinline bool
00251 Path::empty(void) const {
00252 return ds.empty();
00253 }
00254
00255 forceinline void
00256 Path::commit(Space* s, int i) const {
00257 const Edge& n = ds[i];
00258 s->commit(*n.choice(),n.alt());
00259 }
00260
00261 forceinline int
00262 Path::lc(void) const {
00263 int l = ds.entries()-1;
00264 while (ds[l].space() == NULL)
00265 l--;
00266 return l;
00267 }
00268
00269 forceinline int
00270 Path::entries(void) const {
00271 return ds.entries();
00272 }
00273
00274 forceinline void
00275 Path::unwind(int l) {
00276 assert((ds[l].space() == NULL) || ds[l].space()->failed());
00277 int n = ds.entries();
00278 for (int i=l; i<n; i++)
00279 ds.pop().dispose();
00280 assert(ds.entries() == l);
00281 }
00282
00283 inline void
00284 Path::reset(void) {
00285 while (!ds.empty())
00286 ds.pop().dispose();
00287 }
00288
00289 forceinline Space*
00290 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00291 assert(!ds.empty());
00292
00293
00294
00295
00296 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00297 Space* s = ds.top().space();
00298 s->commit(*ds.top().choice(),ds.top().alt());
00299 assert(ds.entries()-1 == lc());
00300 ds.top().space(NULL);
00301
00302 if (static_cast<unsigned int>(ds.entries()) > ngdl())
00303 ds.top().next();
00304 d = 0;
00305 return s;
00306 }
00307
00308 int l = lc();
00309 int n = ds.entries();
00310
00311 d = static_cast<unsigned int>(n - l);
00312
00313 Space* s = ds[l].space()->clone();
00314
00315 if (d < a_d) {
00316
00317 for (int i=l; i<n; i++)
00318 commit(s,i);
00319 } else {
00320 int m = l + static_cast<int>(d >> 1);
00321 int i = l;
00322
00323 for (; i<m; i++ )
00324 commit(s,i);
00325
00326 for (; (i<n) && ds[i].rightmost(); i++)
00327 commit(s,i);
00328
00329 if (i<n-1) {
00330
00331 SpaceStatus ss = s->status(stat);
00332
00333
00334
00335
00336 if (ss == SS_FAILED) {
00337
00338 delete s;
00339 stat.fail++;
00340 unwind(i);
00341 return NULL;
00342 }
00343 ds[i].space(s->clone());
00344 d = static_cast<unsigned int>(n-i);
00345 }
00346
00347 for (; i<n; i++)
00348 commit(s,i);
00349 }
00350 return s;
00351 }
00352
00353 forceinline Space*
00354 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00355 const Space& best, int& mark) {
00356 assert(!ds.empty());
00357
00358
00359
00360
00361 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00362 Space* s = ds.top().space();
00363 s->commit(*ds.top().choice(),ds.top().alt());
00364 assert(ds.entries()-1 == lc());
00365 if (mark > ds.entries()-1) {
00366 mark = ds.entries()-1;
00367 s->constrain(best);
00368 }
00369 ds.top().space(NULL);
00370
00371 if (static_cast<unsigned int>(ds.entries()) > ngdl())
00372 ds.top().next();
00373 d = 0;
00374 return s;
00375 }
00376
00377 int l = lc();
00378 int n = ds.entries();
00379
00380 d = static_cast<unsigned int>(n - l);
00381
00382 Space* s = ds[l].space();
00383
00384 if (l < mark) {
00385 mark = l;
00386 s->constrain(best);
00387
00388
00389 if (s->status(stat) == SS_FAILED) {
00390
00391 stat.fail++;
00392 unwind(l);
00393 return NULL;
00394 }
00395
00396
00397
00398 Space* c = s->clone();
00399 ds[l].space(c);
00400 } else {
00401 s = s->clone();
00402 }
00403
00404 if (d < a_d) {
00405
00406 for (int i=l; i<n; i++)
00407 commit(s,i);
00408 } else {
00409 int m = l + static_cast<int>(d >> 1);
00410 int i = l;
00411
00412 for (; i<m; i++ )
00413 commit(s,i);
00414
00415 for (; (i<n) && ds[i].rightmost(); i++)
00416 commit(s,i);
00417
00418 if (i<n-1) {
00419
00420 SpaceStatus ss = s->status(stat);
00421
00422
00423
00424
00425
00426
00427
00428 if (ss == SS_FAILED) {
00429
00430 delete s;
00431 stat.fail++;
00432 unwind(i);
00433 return NULL;
00434 }
00435 ds[i].space(s->clone());
00436 d = static_cast<unsigned int>(n-i);
00437 }
00438
00439 for (; i<n; i++)
00440 commit(s,i);
00441 }
00442 return s;
00443 }
00444
00445 }}}
00446
00447 #endif
00448
00449