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
00043 namespace Gecode { namespace Search { namespace Sequential {
00044
00058 class Path {
00059 public:
00061 class Node {
00062 protected:
00064 Space* _space;
00066 unsigned int _alt;
00068 const Choice* _choice;
00069 public:
00071 Node(void);
00073 Node(Space* s, Space* c);
00074
00076 Space* space(void) const;
00078 void space(Space* s);
00079
00081 const Choice* choice(void) const;
00082
00084 unsigned int alt(void) const;
00086 bool rightmost(void) const;
00088 void next(void);
00089
00091 void dispose(void);
00092 };
00093 protected:
00095 Support::DynamicStack<Node,Heap> ds;
00096 public:
00098 Path(void);
00100 const Choice* push(Worker& stat, Space* s, Space* c);
00102 bool next(Worker& s);
00104 Node& top(void) const;
00106 bool empty(void) const;
00108 int lc(void) const;
00110 void unwind(int l);
00112 void commit(Space* s, int i) const;
00114 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
00116 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
00117 const Space* best, int& mark);
00119 int entries(void) const;
00121 size_t size(void) const;
00123 void reset(void);
00124 };
00125
00126
00127
00128
00129
00130
00131 forceinline
00132 Path::Node::Node(void) {}
00133
00134 forceinline
00135 Path::Node::Node(Space* s, Space* c)
00136 : _space(c), _alt(0), _choice(s->choice()) {}
00137
00138 forceinline Space*
00139 Path::Node::space(void) const {
00140 return _space;
00141 }
00142 forceinline void
00143 Path::Node::space(Space* s) {
00144 _space = s;
00145 }
00146
00147 forceinline unsigned int
00148 Path::Node::alt(void) const {
00149 return _alt;
00150 }
00151 forceinline bool
00152 Path::Node::rightmost(void) const {
00153 return _alt+1 == _choice->alternatives();
00154 }
00155 forceinline void
00156 Path::Node::next(void) {
00157 _alt++;
00158 }
00159
00160 forceinline const Choice*
00161 Path::Node::choice(void) const {
00162 return _choice;
00163 }
00164
00165 forceinline void
00166 Path::Node::dispose(void) {
00167 delete _space;
00168 delete _choice;
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178 forceinline
00179 Path::Path(void) : ds(heap) {}
00180
00181 forceinline const Choice*
00182 Path::push(Worker& stat, Space* s, Space* c) {
00183 Node sn(s,c);
00184 ds.push(sn);
00185 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00186 return sn.choice();
00187 }
00188
00189 forceinline bool
00190 Path::next(Worker& stat) {
00191
00192 while (!ds.empty())
00193 if (ds.top().rightmost()) {
00194 stat.pop(ds.top().space(),ds.top().choice());
00195 ds.pop().dispose();
00196 } else {
00197 ds.top().next();
00198 return true;
00199 }
00200 return false;
00201 }
00202
00203 forceinline Path::Node&
00204 Path::top(void) const {
00205 assert(!ds.empty());
00206 return ds.top();
00207 }
00208
00209 forceinline bool
00210 Path::empty(void) const {
00211 return ds.empty();
00212 }
00213
00214 forceinline void
00215 Path::commit(Space* s, int i) const {
00216 const Node& n = ds[i];
00217 s->commit(*n.choice(),n.alt());
00218 }
00219
00220 forceinline int
00221 Path::lc(void) const {
00222 int l = ds.entries()-1;
00223 while (ds[l].space() == NULL)
00224 l--;
00225 return l;
00226 }
00227
00228 forceinline int
00229 Path::entries(void) const {
00230 return ds.entries();
00231 }
00232
00233 forceinline size_t
00234 Path::size(void) const {
00235 return ds.size();
00236 }
00237
00238 forceinline void
00239 Path::unwind(int l) {
00240 assert((ds[l].space() == NULL) || ds[l].space()->failed());
00241 int n = ds.entries();
00242 for (int i=l; i<n; i++)
00243 ds.pop().dispose();
00244 assert(ds.entries() == l);
00245 }
00246
00247 inline void
00248 Path::reset(void) {
00249 while (!ds.empty())
00250 ds.pop().dispose();
00251 }
00252
00253 forceinline Space*
00254 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00255 assert(!ds.empty());
00256
00257
00258
00259
00260 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00261 Space* s = ds.top().space();
00262 stat.lao(s);
00263 s->commit(*ds.top().choice(),ds.top().alt());
00264 assert(ds.entries()-1 == lc());
00265 ds.top().space(NULL);
00266 d = 0;
00267 return s;
00268 }
00269
00270 int l = lc();
00271 int n = ds.entries();
00272
00273 d = static_cast<unsigned int>(n - l);
00274
00275 Space* s = ds[l].space()->clone();
00276
00277 if (d < a_d) {
00278
00279 for (int i=l; i<n; i++)
00280 commit(s,i);
00281 } else {
00282 int m = l + static_cast<int>(d >> 1);
00283 int i = l;
00284
00285 for (; i<m; i++ )
00286 commit(s,i);
00287
00288 for (; (i<n) && ds[i].rightmost(); i++)
00289 commit(s,i);
00290
00291 if (i<n-1) {
00292
00293 SpaceStatus ss = s->status(stat);
00294
00295
00296
00297
00298 if (ss == SS_FAILED) {
00299
00300 delete s;
00301 stat.fail++;
00302 unwind(i);
00303 return NULL;
00304 }
00305 ds[i].space(s->clone());
00306 stat.adapt(ds[i].space());
00307 d = static_cast<unsigned int>(n-i);
00308 }
00309
00310 for (; i<n; i++)
00311 commit(s,i);
00312 }
00313 return s;
00314 }
00315
00316 forceinline Space*
00317 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00318 const Space* best, int& mark) {
00319 assert(!ds.empty());
00320
00321
00322
00323
00324 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00325 Space* s = ds.top().space();
00326 stat.lao(s);
00327 s->commit(*ds.top().choice(),ds.top().alt());
00328 assert(ds.entries()-1 == lc());
00329 if (mark > ds.entries()-1) {
00330 mark = ds.entries()-1;
00331 s->constrain(*best);
00332 }
00333 ds.top().space(NULL);
00334 d = 0;
00335 return s;
00336 }
00337
00338 int l = lc();
00339 int n = ds.entries();
00340
00341 d = static_cast<unsigned int>(n - l);
00342
00343 Space* s = ds[l].space();
00344
00345 if (l < mark) {
00346 mark = l;
00347 s->constrain(*best);
00348
00349
00350 if (s->status(stat) == SS_FAILED) {
00351
00352 stat.fail++;
00353 unwind(l);
00354 return NULL;
00355 }
00356
00357
00358
00359 Space* c = s->clone();
00360 ds[l].space(c);
00361 stat.constrained(s,c);
00362 } else {
00363 s = s->clone();
00364 }
00365
00366 if (d < a_d) {
00367
00368 for (int i=l; i<n; i++)
00369 commit(s,i);
00370 } else {
00371 int m = l + static_cast<int>(d >> 1);
00372 int i = l;
00373
00374 for (; i<m; i++ )
00375 commit(s,i);
00376
00377 for (; (i<n) && ds[i].rightmost(); i++)
00378 commit(s,i);
00379
00380 if (i<n-1) {
00381
00382 SpaceStatus ss = s->status(stat);
00383
00384
00385
00386
00387
00388
00389
00390 if (ss == SS_FAILED) {
00391
00392 delete s;
00393 stat.fail++;
00394 unwind(i);
00395 return NULL;
00396 }
00397 ds[i].space(s->clone());
00398 stat.adapt(ds[i].space());
00399 d = static_cast<unsigned int>(n-i);
00400 }
00401
00402 for (; i<n; i++)
00403 commit(s,i);
00404 }
00405 return s;
00406 }
00407
00408 }}}
00409
00410 #endif
00411
00412