Generated on Thu Apr 11 13:59:18 2019 for Gecode by doxygen 1.6.3

path.hpp

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Search { namespace Seq {
00035 
00036   /*
00037    * Edge for recomputation
00038    *
00039    */
00040   template<class Tracer>
00041   forceinline
00042   Path<Tracer>::Edge::Edge(void) {}
00043 
00044   template<class Tracer>
00045   forceinline
00046   Path<Tracer>::Edge::Edge(Space* s, Space* c, unsigned int nid)
00047     : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {}
00048 
00049   template<class Tracer>
00050   forceinline Space*
00051   Path<Tracer>::Edge::space(void) const {
00052     return _space;
00053   }
00054   template<class Tracer>
00055   forceinline void
00056   Path<Tracer>::Edge::space(Space* s) {
00057     _space = s;
00058   }
00059 
00060   template<class Tracer>
00061   forceinline unsigned int
00062   Path<Tracer>::Edge::alt(void) const {
00063     return _alt;
00064   }
00065   template<class Tracer>
00066   forceinline unsigned int
00067   Path<Tracer>::Edge::truealt(void) const {
00068     return std::min(_alt,_choice->alternatives()-1);
00069   }
00070   template<class Tracer>
00071   forceinline bool
00072   Path<Tracer>::Edge::leftmost(void) const {
00073     return _alt == 0;
00074   }
00075   template<class Tracer>
00076   forceinline bool
00077   Path<Tracer>::Edge::rightmost(void) const {
00078     return _alt+1 >= _choice->alternatives();
00079   }
00080   template<class Tracer>
00081   forceinline bool
00082   Path<Tracer>::Edge::lao(void) const {
00083     return _alt >= _choice->alternatives();
00084   }
00085   template<class Tracer>
00086   forceinline void
00087   Path<Tracer>::Edge::next(void) {
00088     _alt++;
00089   }
00090 
00091   template<class Tracer>
00092   forceinline const Choice*
00093   Path<Tracer>::Edge::choice(void) const {
00094     return _choice;
00095   }
00096 
00097   template<class Tracer>
00098   forceinline unsigned int
00099   Path<Tracer>::Edge::nid(void) const {
00100     return _nid;
00101   }
00102 
00103   template<class Tracer>
00104   forceinline void
00105   Path<Tracer>::Edge::dispose(void) {
00106     delete _space;
00107     delete _choice;
00108   }
00109 
00110 
00111 
00112   /*
00113    * Depth-first stack with recomputation
00114    *
00115    */
00116 
00117   template<class Tracer>
00118   forceinline
00119   Path<Tracer>::Path(unsigned int l)
00120     : ds(heap), _ngdl(l) {}
00121 
00122   template<class Tracer>
00123   forceinline unsigned int
00124   Path<Tracer>::ngdl(void) const {
00125     return _ngdl;
00126   }
00127 
00128   template<class Tracer>
00129   forceinline void
00130   Path<Tracer>::ngdl(unsigned int l) {
00131     _ngdl = l;
00132   }
00133 
00134   template<class Tracer>
00135   forceinline const Choice*
00136   Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
00137     if (!ds.empty() && ds.top().lao()) {
00138       // Topmost stack entry was LAO -> reuse
00139       ds.pop().dispose();
00140     }
00141     Edge sn(s,c,nid);
00142     ds.push(sn);
00143     stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00144     return sn.choice();
00145   }
00146 
00147   template<class Tracer>
00148   forceinline void
00149   Path<Tracer>::next(void) {
00150     while (!ds.empty())
00151       if (ds.top().rightmost()) {
00152         ds.pop().dispose();
00153       } else {
00154         ds.top().next();
00155         return;
00156       }
00157   }
00158 
00159   template<class Tracer>
00160   forceinline typename Path<Tracer>::Edge&
00161   Path<Tracer>::top(void) const {
00162     assert(!ds.empty());
00163     return ds.top();
00164   }
00165 
00166   template<class Tracer>
00167   forceinline bool
00168   Path<Tracer>::empty(void) const {
00169     return ds.empty();
00170   }
00171 
00172   template<class Tracer>
00173   forceinline void
00174   Path<Tracer>::commit(Space* s, int i) const {
00175     const Edge& n = ds[i];
00176     s->commit(*n.choice(),n.alt());
00177   }
00178 
00179   template<class Tracer>
00180   forceinline int
00181   Path<Tracer>::lc(void) const {
00182     int l = ds.entries()-1;
00183     while (ds[l].space() == NULL)
00184       l--;
00185     return l;
00186   }
00187 
00188   template<class Tracer>
00189   forceinline int
00190   Path<Tracer>::entries(void) const {
00191     return ds.entries();
00192   }
00193 
00194   template<class Tracer>
00195   forceinline void
00196   Path<Tracer>::unwind(int l, Tracer& t) {
00197     assert((ds[l].space() == NULL) || ds[l].space()->failed());
00198     int n = ds.entries();
00199     if (t) {
00200       for (int i=l; i<n; i++) {
00201         Path<Tracer>::Edge& top = ds.top();
00202         unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
00203         for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
00204           SearchTracer::EdgeInfo ei(t.wid(),top.nid(),a);
00205           t.skip(ei);
00206         }
00207         ds.pop().dispose();
00208       }
00209     } else {
00210       for (int i=l; i<n; i++)
00211         ds.pop().dispose();
00212     }
00213     assert(ds.entries() == l);
00214   }
00215 
00216   template<class Tracer>
00217   inline void
00218   Path<Tracer>::reset(void) {
00219     while (!ds.empty())
00220       ds.pop().dispose();
00221   }
00222 
00223   template<class Tracer>
00224   forceinline Space*
00225   Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00226                           Tracer& t) {
00227     assert(!ds.empty());
00228     // Recompute space according to path
00229     // Also say distance to copy (d == 0) requires immediate copying
00230 
00231     // Check for LAO
00232     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00233       Space* s = ds.top().space();
00234       s->commit(*ds.top().choice(),ds.top().alt());
00235       assert(ds.entries()-1 == lc());
00236       ds.top().space(NULL);
00237       // Mark as reusable
00238       if (static_cast<unsigned int>(ds.entries()) > ngdl())
00239         ds.top().next();
00240       d = 0;
00241       return s;
00242     }
00243     // General case for recomputation
00244     int l = lc();             // Position of last clone
00245     int n = ds.entries();     // Number of stack entries
00246     // New distance, if no adaptive recomputation
00247     d = static_cast<unsigned int>(n - l);
00248 
00249     Space* s = ds[l].space()->clone(); // Last clone
00250 
00251     if (d < a_d) {
00252       // No adaptive recomputation
00253       for (int i=l; i<n; i++)
00254         commit(s,i);
00255     } else {
00256       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00257       int i = l; // To iterate over all entries
00258       // Recompute up to middle
00259       for (; i<m; i++ )
00260         commit(s,i);
00261       // Skip over all rightmost branches
00262       for (; (i<n) && ds[i].rightmost(); i++)
00263         commit(s,i);
00264       // Is there any point to make a copy?
00265       if (i<n-1) {
00266         // Propagate to fixpoint
00267         SpaceStatus ss = s->status(stat);
00268         /*
00269          * Again, the space might already propagate to failure (due to
00270          * weakly monotonic propagators).
00271          */
00272         if (ss == SS_FAILED) {
00273           // s must be deleted as it is not on the stack
00274           delete s;
00275           stat.fail++;
00276           unwind(i,t);
00277           return NULL;
00278         }
00279         ds[i].space(s->clone());
00280         d = static_cast<unsigned int>(n-i);
00281       }
00282       // Finally do the remaining commits
00283       for (; i<n; i++)
00284         commit(s,i);
00285     }
00286     return s;
00287   }
00288 
00289   template<class Tracer>
00290   forceinline Space*
00291   Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00292                           const Space& best, int& mark,
00293                           Tracer& t) {
00294     assert(!ds.empty());
00295     // Recompute space according to path
00296     // Also say distance to copy (d == 0) requires immediate copying
00297 
00298     // Check for LAO
00299     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00300       Space* s = ds.top().space();
00301       s->commit(*ds.top().choice(),ds.top().alt());
00302       assert(ds.entries()-1 == lc());
00303       if (mark > ds.entries()-1) {
00304         mark = ds.entries()-1;
00305         s->constrain(best);
00306       }
00307       ds.top().space(NULL);
00308       // Mark as reusable
00309       if (static_cast<unsigned int>(ds.entries()) > ngdl())
00310         ds.top().next();
00311       d = 0;
00312       return s;
00313     }
00314     // General case for recomputation
00315     int l = lc();             // Position of last clone
00316     int n = ds.entries();     // Number of stack entries
00317     // New distance, if no adaptive recomputation
00318     d = static_cast<unsigned int>(n - l);
00319 
00320     Space* s = ds[l].space(); // Last clone
00321 
00322     if (l < mark) {
00323       mark = l;
00324       s->constrain(best);
00325       // The space on the stack could be failed now as an additional
00326       // constraint might have been added.
00327       if (s->status(stat) == SS_FAILED) {
00328         // s does not need deletion as it is on the stack (unwind does this)
00329         stat.fail++;
00330         unwind(l,t);
00331         return NULL;
00332       }
00333       // It is important to replace the space on the stack with the
00334       // copy: a copy might be much smaller due to flushed caches
00335       // of propagators
00336       Space* c = s->clone();
00337       ds[l].space(c);
00338     } else {
00339       s = s->clone();
00340     }
00341 
00342     if (d < a_d) {
00343       // No adaptive recomputation
00344       for (int i=l; i<n; i++)
00345         commit(s,i);
00346     } else {
00347       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00348       int i = l;            // To iterate over all entries
00349       // Recompute up to middle
00350       for (; i<m; i++ )
00351         commit(s,i);
00352       // Skip over all rightmost branches
00353       for (; (i<n) && ds[i].rightmost(); i++)
00354         commit(s,i);
00355       // Is there any point to make a copy?
00356       if (i<n-1) {
00357         // Propagate to fixpoint
00358         SpaceStatus ss = s->status(stat);
00359         /*
00360          * Again, the space might already propagate to failure
00361          *
00362          * This can be for two reasons:
00363          *  - constrain is true, so we fail
00364          *  - the space has weakly monotonic propagators
00365          */
00366         if (ss == SS_FAILED) {
00367           // s must be deleted as it is not on the stack
00368           delete s;
00369           stat.fail++;
00370           unwind(i,t);
00371           return NULL;
00372         }
00373         ds[i].space(s->clone());
00374         d = static_cast<unsigned int>(n-i);
00375       }
00376       // Finally do the remaining commits
00377       for (; i<n; i++)
00378         commit(s,i);
00379     }
00380     return s;
00381   }
00382 
00383   template<class Tracer>
00384   void
00385   Path<Tracer>::post(Space& home) const {
00386     GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
00387   }
00388 
00389 }}}
00390 
00391 // STATISTICS: search-seq