Generated on Mon May 5 05:54:00 2008 for Gecode by doxygen 1.5.5

reco-stack.icc

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: 2008-01-19 13:19:23 +0100 (Sat, 19 Jan 2008) $ by $Author: schulte $
00011  *     $Revision: 5916 $
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 namespace Gecode { namespace Search {
00039 
00040   /*
00041    * Node for recomputation
00042    *
00043    */
00044 
00045   forceinline
00046   ReCoNode::ReCoNode(Space* s, Space* c)
00047     : _space(c), _alt(0), _desc(s->description()) {}
00048 
00049   forceinline Space*
00050   ReCoNode::space(void) const {
00051     return _space;
00052   }
00053   forceinline void
00054   ReCoNode::space(Space* s) {
00055     _space = s;
00056   }
00057 
00058   forceinline unsigned int
00059   ReCoNode::alt(void) const {
00060     return _alt;
00061   }
00062   forceinline bool
00063   ReCoNode::rightmost(void) const {
00064     return _alt+1 == _desc->alternatives();
00065   }
00066   forceinline void
00067   ReCoNode::next(void) {
00068     _alt++;
00069   }
00070 
00071   forceinline const BranchingDesc*
00072   ReCoNode::desc(void) const {
00073     return _desc;
00074   }
00075 
00076   forceinline void
00077   ReCoNode::dispose(void) {
00078     delete _space;
00079     delete _desc;
00080   }
00081 
00082 
00083 
00084   /*
00085    * Depth-first stack with recomputation
00086    *
00087    */
00088 
00089   forceinline
00090   ReCoStack::ReCoStack(unsigned int a_d0) : a_d(a_d0) {}
00091 
00092   forceinline const BranchingDesc*
00093   ReCoStack::push(Space* s, Space* c) {
00094     ReCoNode sn(s,c);
00095     ds.push(sn);
00096     return sn.desc();
00097   }
00098 
00099   forceinline bool
00100   ReCoStack::next(EngineCtrl& stat) {
00101     // Generate path for next node and return whether node exists.
00102     while (!ds.empty())
00103       if (ds.top().rightmost()) {
00104         stat.pop(ds.top().space(),ds.top().desc());
00105         ds.pop().dispose();
00106       } else {
00107         ds.top().next();
00108         return true;
00109       }
00110     return false;
00111   }
00112 
00113   forceinline void
00114   ReCoStack::commit(Space* s, int i) const {
00115     const ReCoNode& n = ds[i];
00116     s->commit(n.desc(),n.alt());
00117   }
00118 
00119   forceinline int
00120   ReCoStack::lc(Space*& s) const {
00121     int l = ds.entries()-1;
00122     while (ds[l].space() == NULL)
00123       l--;
00124     s = ds[l].space();
00125     return l;
00126   }
00127 
00128   forceinline int
00129   ReCoStack::entries(void) const {
00130     return ds.entries();
00131   }
00132 
00133   forceinline size_t
00134   ReCoStack::stacksize(void) const {
00135     return ds.size();
00136   }
00137 
00138   forceinline void
00139   ReCoStack::unwind(int l) {
00140     assert((ds[l].space() == NULL) || ds[l].space()->failed());
00141     int n = ds.entries();
00142     for (int i=l; i<n; i++)
00143       ds.pop().dispose();
00144     assert(ds.entries() == l);
00145   }
00146 
00147   inline void
00148   ReCoStack::reset(void) {
00149     while (!ds.empty())
00150       ds.pop().dispose();
00151   }
00152 
00153   template <bool constrained>
00154   forceinline Space*
00155   ReCoStack::recompute(unsigned int& d, EngineCtrl& stat) {
00156     assert(!ds.empty());
00157     // Recompute space according to path
00158     // Also say distance to copy (d == 0) requires immediate copying
00159 
00160     // Check for LAO
00161     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00162       Space* s = ds.top().space();
00163       s->commit(ds.top().desc(),ds.top().alt());
00164       ds.top().space(NULL);
00165       stat.lao(s);
00166       d = 0;
00167       stat.commit++;
00168       return s;
00169     }
00170     // General case for recomputation
00171     Space* s;             // Last clone
00172     int l = lc(s);        // Position of last clone
00173     int n = ds.entries(); // Number of stack entries
00174     d = static_cast<unsigned int>(n - l); // New distance, if no adaptive recomputation
00175 
00176     if (constrained) {
00177       // The space on the stack could be failed now as an additional
00178       // constraint might have been added.
00179       if (s->status(stat.propagate) == SS_FAILED) {
00180         // s does not need deletion as it is on the stack (unwind does this)
00181         stat.fail++;
00182         unwind(l);
00183         return NULL;
00184       }
00185       // It is important to replace the space on the stack with the
00186       // copy: a copy might be much smaller due to flushed caches
00187       // of propagators
00188       Space* c = s->clone();
00189       ds[l].space(c);
00190       stat.constrained(s,c);
00191     } else {
00192       s = s->clone();
00193     }
00194     stat.clone++;
00195 
00196     if (d < a_d) {
00197       // No adaptive recomputation
00198       for (int i=l; i<n; i++)
00199         commit(s,i);
00200     } else {
00201       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00202       int i = l;            // To iterate over all entries
00203       // Recompute up to middle
00204       for (; i<m; i++ )
00205         commit(s,i);
00206       // Skip over all rightmost branches
00207       for (; (i<n) && ds[i].rightmost(); i++)
00208         commit(s,i);
00209       // Is there any point to make a copy?
00210       if (i<n-1) {
00211         // Propagate to fixpoint
00212         SpaceStatus ss = s->status(stat.propagate);
00213         // Again, the space might already propagate to failure
00214         if (constrained &&  (ss == SS_FAILED)) {
00215           // s must be deleted as it is not on the stack
00216           delete s;
00217           stat.commit += (i-l);
00218           stat.fail++;
00219           unwind(i);
00220           return NULL;
00221         }
00222         stat.clone++;
00223         ds[i].space(s->clone());
00224         stat.adapt(ds[i].space());
00225         d = static_cast<unsigned int>(n-i);
00226       }
00227       // Finally do the remaining commits
00228       for (; i<n; i++)
00229         commit(s,i);
00230     }
00231     stat.commit += d;
00232     return s;
00233   }
00234 
00235 }}
00236 
00237 // STATISTICS: search-any