stack.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00029
00030
00031
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
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
00062 for (; i < mid; i++ )
00063 s->commit(operator[](i).alt(),
00064 operator[](i).desc(),stat.propagate);
00065
00066 for (; operator[](i).rightmost() && (i < entries()); i++)
00067 s->commit(operator[](i).alt(),
00068 operator[](i).desc(),stat.propagate);
00069
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
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