Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

stack.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-08-09 21:44:53 +0200 (Tue, 09 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2192 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "search/stack.hh"
00023 
00024 namespace Gecode { namespace Search {
00025 
00026   Space*
00027   ReCoStack::recompute(unsigned int& d, FullStatistics& stat) {
00028     // Recompute space according to path
00029     // Also say distance to copy (d == 0) requires immediate copying
00030 
00031     // Check for LAO
00032     if ((top().space() != NULL) && top().rightmost()) {
00033       Space* s = top().space();
00034       s->commit(top().alt(),top().desc(),stat.propagate);
00035       top().space(NULL);
00036       stat.pop(s);
00037       d = 0;
00038       stat.commit++;
00039       return s;
00040     }
00041     // General case for recomputation
00042     unsigned int last = entries()-1;
00043 
00044     while (!operator[](last).space())
00045       last--;
00046 
00047     stat.clone++;
00048     Space* s = operator[](last).space()->clone();
00049 
00050     unsigned int dist = entries() - last;
00051     stat.commit += dist;
00052     if (dist < a_d) {
00053       for (unsigned int i = last; i < entries(); i++)
00054         s->commit(operator[](i).alt(),
00055                   operator[](i).desc(),stat.propagate);
00056       d = dist;
00057     } else {
00058       unsigned int mid  = last + (dist >> 1);
00059       unsigned int i    = last;
00060 
00061       // Recompute up to middle
00062       for (; i < mid; i++ )
00063         s->commit(operator[](i).alt(),
00064                   operator[](i).desc(),stat.propagate);
00065       // Skip over all rightmost branches
00066       for (; operator[](i).rightmost() && (i < entries()); i++)
00067         s->commit(operator[](i).alt(),
00068                   operator[](i).desc(),stat.propagate);
00069       // Is there any point to make a copy?
00070       if (i < entries()-1) {
00071         stat.clone++;
00072         operator[](i).space(s->clone());
00073         stat.push(operator[](i).space());
00074         d = entries()-i;
00075       } else {
00076         d = entries()-last;
00077       }
00078       // Finally do the remaining commits
00079       for (; i < entries(); i++ )
00080         s->commit(operator[](i).alt(),
00081                   operator[](i).desc(),stat.propagate);
00082     }
00083     return s;
00084   }
00085 
00086 }}
00087 
00088 // STATISTICS: search-any