path.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2003 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-22 11:59:14 +0200 (Thu, 22 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11248 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 Edge { 00062 protected: 00064 Space* _space; 00066 unsigned int _alt; 00068 const Choice* _choice; 00069 public: 00071 Edge(void); 00073 Edge(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<Edge,Heap> ds; 00096 public: 00098 Path(void); 00100 const Choice* push(Worker& stat, Space* s, Space* c); 00102 bool next(Worker& s); 00104 Edge& 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 * Edge for recomputation 00129 * 00130 */ 00131 forceinline 00132 Path::Edge::Edge(void) {} 00133 00134 forceinline 00135 Path::Edge::Edge(Space* s, Space* c) 00136 : _space(c), _alt(0), _choice(s->choice()) {} 00137 00138 forceinline Space* 00139 Path::Edge::space(void) const { 00140 return _space; 00141 } 00142 forceinline void 00143 Path::Edge::space(Space* s) { 00144 _space = s; 00145 } 00146 00147 forceinline unsigned int 00148 Path::Edge::alt(void) const { 00149 return _alt; 00150 } 00151 forceinline bool 00152 Path::Edge::rightmost(void) const { 00153 return _alt+1 == _choice->alternatives(); 00154 } 00155 forceinline void 00156 Path::Edge::next(void) { 00157 _alt++; 00158 } 00159 00160 forceinline const Choice* 00161 Path::Edge::choice(void) const { 00162 return _choice; 00163 } 00164 00165 forceinline void 00166 Path::Edge::dispose(void) { 00167 delete _space; 00168 delete _choice; 00169 } 00170 00171 00172 00173 /* 00174 * Depth-first stack with recomputation 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 Edge 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 while (!ds.empty()) 00192 if (ds.top().rightmost()) { 00193 stat.pop(ds.top().space(),ds.top().choice()); 00194 ds.pop().dispose(); 00195 } else { 00196 ds.top().next(); 00197 return true; 00198 } 00199 return false; 00200 } 00201 00202 forceinline Path::Edge& 00203 Path::top(void) const { 00204 assert(!ds.empty()); 00205 return ds.top(); 00206 } 00207 00208 forceinline bool 00209 Path::empty(void) const { 00210 return ds.empty(); 00211 } 00212 00213 forceinline void 00214 Path::commit(Space* s, int i) const { 00215 const Edge& n = ds[i]; 00216 s->commit(*n.choice(),n.alt()); 00217 } 00218 00219 forceinline int 00220 Path::lc(void) const { 00221 int l = ds.entries()-1; 00222 while (ds[l].space() == NULL) 00223 l--; 00224 return l; 00225 } 00226 00227 forceinline int 00228 Path::entries(void) const { 00229 return ds.entries(); 00230 } 00231 00232 forceinline size_t 00233 Path::size(void) const { 00234 return ds.size(); 00235 } 00236 00237 forceinline void 00238 Path::unwind(int l) { 00239 assert((ds[l].space() == NULL) || ds[l].space()->failed()); 00240 int n = ds.entries(); 00241 for (int i=l; i<n; i++) 00242 ds.pop().dispose(); 00243 assert(ds.entries() == l); 00244 } 00245 00246 inline void 00247 Path::reset(void) { 00248 while (!ds.empty()) 00249 ds.pop().dispose(); 00250 } 00251 00252 forceinline Space* 00253 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) { 00254 assert(!ds.empty()); 00255 // Recompute space according to path 00256 // Also say distance to copy (d == 0) requires immediate copying 00257 00258 // Check for LAO 00259 if ((ds.top().space() != NULL) && ds.top().rightmost()) { 00260 Space* s = ds.top().space(); 00261 stat.lao(s); 00262 s->commit(*ds.top().choice(),ds.top().alt()); 00263 assert(ds.entries()-1 == lc()); 00264 ds.top().space(NULL); 00265 d = 0; 00266 return s; 00267 } 00268 // General case for recomputation 00269 int l = lc(); // Position of last clone 00270 int n = ds.entries(); // Number of stack entries 00271 // New distance, if no adaptive recomputation 00272 d = static_cast<unsigned int>(n - l); 00273 00274 Space* s = ds[l].space()->clone(); // Last clone 00275 00276 if (d < a_d) { 00277 // No adaptive recomputation 00278 for (int i=l; i<n; i++) 00279 commit(s,i); 00280 } else { 00281 int m = l + static_cast<int>(d >> 1); // Middle between copy and top 00282 int i = l; // To iterate over all entries 00283 // Recompute up to middle 00284 for (; i<m; i++ ) 00285 commit(s,i); 00286 // Skip over all rightmost branches 00287 for (; (i<n) && ds[i].rightmost(); i++) 00288 commit(s,i); 00289 // Is there any point to make a copy? 00290 if (i<n-1) { 00291 // Propagate to fixpoint 00292 SpaceStatus ss = s->status(stat); 00293 /* 00294 * Again, the space might already propagate to failure (due to 00295 * weakly monotonic propagators). 00296 */ 00297 if (ss == SS_FAILED) { 00298 // s must be deleted as it is not on the stack 00299 delete s; 00300 stat.fail++; 00301 unwind(i); 00302 return NULL; 00303 } 00304 ds[i].space(s->clone()); 00305 stat.adapt(ds[i].space()); 00306 d = static_cast<unsigned int>(n-i); 00307 } 00308 // Finally do the remaining commits 00309 for (; i<n; i++) 00310 commit(s,i); 00311 } 00312 return s; 00313 } 00314 00315 forceinline Space* 00316 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat, 00317 const Space* best, int& mark) { 00318 assert(!ds.empty()); 00319 // Recompute space according to path 00320 // Also say distance to copy (d == 0) requires immediate copying 00321 00322 // Check for LAO 00323 if ((ds.top().space() != NULL) && ds.top().rightmost()) { 00324 Space* s = ds.top().space(); 00325 stat.lao(s); 00326 s->commit(*ds.top().choice(),ds.top().alt()); 00327 assert(ds.entries()-1 == lc()); 00328 if (mark > ds.entries()-1) { 00329 mark = ds.entries()-1; 00330 s->constrain(*best); 00331 } 00332 ds.top().space(NULL); 00333 d = 0; 00334 return s; 00335 } 00336 // General case for recomputation 00337 int l = lc(); // Position of last clone 00338 int n = ds.entries(); // Number of stack entries 00339 // New distance, if no adaptive recomputation 00340 d = static_cast<unsigned int>(n - l); 00341 00342 Space* s = ds[l].space(); // Last clone 00343 00344 if (l < mark) { 00345 mark = l; 00346 s->constrain(*best); 00347 // The space on the stack could be failed now as an additional 00348 // constraint might have been added. 00349 if (s->status(stat) == SS_FAILED) { 00350 // s does not need deletion as it is on the stack (unwind does this) 00351 stat.fail++; 00352 unwind(l); 00353 return NULL; 00354 } 00355 // It is important to replace the space on the stack with the 00356 // copy: a copy might be much smaller due to flushed caches 00357 // of propagators 00358 Space* c = s->clone(); 00359 ds[l].space(c); 00360 stat.constrained(s,c); 00361 } else { 00362 s = s->clone(); 00363 } 00364 00365 if (d < a_d) { 00366 // No adaptive recomputation 00367 for (int i=l; i<n; i++) 00368 commit(s,i); 00369 } else { 00370 int m = l + static_cast<int>(d >> 1); // Middle between copy and top 00371 int i = l; // To iterate over all entries 00372 // Recompute up to middle 00373 for (; i<m; i++ ) 00374 commit(s,i); 00375 // Skip over all rightmost branches 00376 for (; (i<n) && ds[i].rightmost(); i++) 00377 commit(s,i); 00378 // Is there any point to make a copy? 00379 if (i<n-1) { 00380 // Propagate to fixpoint 00381 SpaceStatus ss = s->status(stat); 00382 /* 00383 * Again, the space might already propagate to failure 00384 * 00385 * This can be for two reasons: 00386 * - constrain is true, so we fail 00387 * - the space has weakly monotonic propagators 00388 */ 00389 if (ss == SS_FAILED) { 00390 // s must be deleted as it is not on the stack 00391 delete s; 00392 stat.fail++; 00393 unwind(i); 00394 return NULL; 00395 } 00396 ds[i].space(s->clone()); 00397 stat.adapt(ds[i].space()); 00398 d = static_cast<unsigned int>(n-i); 00399 } 00400 // Finally do the remaining commits 00401 for (; i<n; i++) 00402 commit(s,i); 00403 } 00404 return s; 00405 } 00406 00407 }}} 00408 00409 #endif 00410 00411 // STATISTICS: search-sequential