Generated on Mon May 10 06:46:44 2010 for Gecode by doxygen 1.6.3

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: 2009-11-25 17:27:09 +0100 (Wed, 25 Nov 2009) $ by $Author: schulte $
00011  *     $Revision: 10126 $
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 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    * Node for recomputation
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    * 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     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     // Generate path for next node and return whether node exists.
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     // Recompute space according to path
00257     // Also say distance to copy (d == 0) requires immediate copying
00258 
00259     // Check for LAO
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     // General case for recomputation
00270     int l = lc();             // Position of last clone
00271     int n = ds.entries();     // Number of stack entries
00272     // New distance, if no adaptive recomputation
00273     d = static_cast<unsigned int>(n - l);
00274 
00275     Space* s = ds[l].space()->clone(); // Last clone
00276 
00277     if (d < a_d) {
00278       // No adaptive recomputation
00279       for (int i=l; i<n; i++)
00280         commit(s,i);
00281     } else {
00282       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00283       int i = l; // To iterate over all entries
00284       // Recompute up to middle
00285       for (; i<m; i++ )
00286         commit(s,i);
00287       // Skip over all rightmost branches
00288       for (; (i<n) && ds[i].rightmost(); i++)
00289         commit(s,i);
00290       // Is there any point to make a copy?
00291       if (i<n-1) {
00292         // Propagate to fixpoint
00293         SpaceStatus ss = s->status(stat);
00294         /*
00295          * Again, the space might already propagate to failure (due to
00296          * weakly monotonic propagators).
00297          */
00298         if (ss == SS_FAILED) {
00299           // s must be deleted as it is not on the stack
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       // Finally do the remaining commits
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     // Recompute space according to path
00321     // Also say distance to copy (d == 0) requires immediate copying
00322 
00323     // Check for LAO
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     // General case for recomputation
00338     int l = lc();             // Position of last clone
00339     int n = ds.entries();     // Number of stack entries
00340     // New distance, if no adaptive recomputation
00341     d = static_cast<unsigned int>(n - l);
00342 
00343     Space* s = ds[l].space(); // Last clone
00344 
00345     if (l < mark) {
00346       mark = l;
00347       s->constrain(*best);
00348       // The space on the stack could be failed now as an additional
00349       // constraint might have been added.
00350       if (s->status(stat) == SS_FAILED) {
00351         // s does not need deletion as it is on the stack (unwind does this)
00352         stat.fail++;
00353         unwind(l);
00354         return NULL;
00355       }
00356       // It is important to replace the space on the stack with the
00357       // copy: a copy might be much smaller due to flushed caches
00358       // of propagators
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       // No adaptive recomputation
00368       for (int i=l; i<n; i++)
00369         commit(s,i);
00370     } else {
00371       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00372       int i = l;            // To iterate over all entries
00373       // Recompute up to middle
00374       for (; i<m; i++ )
00375         commit(s,i);
00376       // Skip over all rightmost branches
00377       for (; (i<n) && ds[i].rightmost(); i++)
00378         commit(s,i);
00379       // Is there any point to make a copy?
00380       if (i<n-1) {
00381         // Propagate to fixpoint
00382         SpaceStatus ss = s->status(stat);
00383         /*
00384          * Again, the space might already propagate to failure
00385          *
00386          * This can be for two reasons:
00387          *  - constrain is true, so we fail
00388          *  - the space has weakly monotonic propagators
00389          */
00390         if (ss == SS_FAILED) {
00391           // s must be deleted as it is not on the stack
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       // Finally do the remaining commits
00402       for (; i<n; i++)
00403         commit(s,i);
00404     }
00405     return s;
00406   }
00407 
00408 }}}
00409 
00410 #endif
00411 
00412 // STATISTICS: search-sequential