Generated on Wed Nov 5 2014 05:18:31 for Gecode by doxygen 1.7.6.1
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: 2013-07-12 18:20:11 +0200 (Fri, 12 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13877 $
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 #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    * Edge for recomputation
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    * Depth-first stack with recomputation
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       // Topmost stack entry was LAO -> reuse
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     // Recompute space according to path
00294     // Also say distance to copy (d == 0) requires immediate copying
00295 
00296     // Check for LAO
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       // Mark as reusable
00303       if (ds.entries() > ngdl())
00304         ds.top().next();
00305       d = 0;
00306       return s;
00307     }
00308     // General case for recomputation
00309     int l = lc();             // Position of last clone
00310     int n = ds.entries();     // Number of stack entries
00311     // New distance, if no adaptive recomputation
00312     d = static_cast<unsigned int>(n - l);
00313 
00314     Space* s = ds[l].space()->clone(); // Last clone
00315 
00316     if (d < a_d) {
00317       // No adaptive recomputation
00318       for (int i=l; i<n; i++)
00319         commit(s,i);
00320     } else {
00321       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00322       int i = l; // To iterate over all entries
00323       // Recompute up to middle
00324       for (; i<m; i++ )
00325         commit(s,i);
00326       // Skip over all rightmost branches
00327       for (; (i<n) && ds[i].rightmost(); i++)
00328         commit(s,i);
00329       // Is there any point to make a copy?
00330       if (i<n-1) {
00331         // Propagate to fixpoint
00332         SpaceStatus ss = s->status(stat);
00333         /*
00334          * Again, the space might already propagate to failure (due to
00335          * weakly monotonic propagators).
00336          */
00337         if (ss == SS_FAILED) {
00338           // s must be deleted as it is not on the stack
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       // Finally do the remaining commits
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     // Recompute space according to path
00359     // Also say distance to copy (d == 0) requires immediate copying
00360 
00361     // Check for LAO
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       // Mark as reusable
00372       if (ds.entries() > ngdl())
00373         ds.top().next();
00374       d = 0;
00375       return s;
00376     }
00377     // General case for recomputation
00378     int l = lc();             // Position of last clone
00379     int n = ds.entries();     // Number of stack entries
00380     // New distance, if no adaptive recomputation
00381     d = static_cast<unsigned int>(n - l);
00382 
00383     Space* s = ds[l].space(); // Last clone
00384 
00385     if (l < mark) {
00386       mark = l;
00387       s->constrain(*best);
00388       // The space on the stack could be failed now as an additional
00389       // constraint might have been added.
00390       if (s->status(stat) == SS_FAILED) {
00391         // s does not need deletion as it is on the stack (unwind does this)
00392         stat.fail++;
00393         unwind(l);
00394         return NULL;
00395       }
00396       // It is important to replace the space on the stack with the
00397       // copy: a copy might be much smaller due to flushed caches
00398       // of propagators
00399       Space* c = s->clone();
00400       ds[l].space(c);
00401     } else {
00402       s = s->clone();
00403     }
00404 
00405     if (d < a_d) {
00406       // No adaptive recomputation
00407       for (int i=l; i<n; i++)
00408         commit(s,i);
00409     } else {
00410       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00411       int i = l;            // To iterate over all entries
00412       // Recompute up to middle
00413       for (; i<m; i++ )
00414         commit(s,i);
00415       // Skip over all rightmost branches
00416       for (; (i<n) && ds[i].rightmost(); i++)
00417         commit(s,i);
00418       // Is there any point to make a copy?
00419       if (i<n-1) {
00420         // Propagate to fixpoint
00421         SpaceStatus ss = s->status(stat);
00422         /*
00423          * Again, the space might already propagate to failure
00424          *
00425          * This can be for two reasons:
00426          *  - constrain is true, so we fail
00427          *  - the space has weakly monotonic propagators
00428          */
00429         if (ss == SS_FAILED) {
00430           // s must be deleted as it is not on the stack
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       // Finally do the remaining commits
00440       for (; i<n; i++)
00441         commit(s,i);
00442     }
00443     return s;
00444   }
00445 
00446 }}}
00447 
00448 #endif
00449 
00450 // STATISTICS: search-sequential