00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Search {
00039
00040
00041
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
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
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
00158
00159
00160
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
00171 Space* s;
00172 int l = lc(s);
00173 int n = ds.entries();
00174 d = static_cast<unsigned int>(n - l);
00175
00176 if (constrained) {
00177
00178
00179 if (s->status(stat.propagate) == SS_FAILED) {
00180
00181 stat.fail++;
00182 unwind(l);
00183 return NULL;
00184 }
00185
00186
00187
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
00198 for (int i=l; i<n; i++)
00199 commit(s,i);
00200 } else {
00201 int m = l + static_cast<int>(d >> 1);
00202 int i = l;
00203
00204 for (; i<m; i++ )
00205 commit(s,i);
00206
00207 for (; (i<n) && ds[i].rightmost(); i++)
00208 commit(s,i);
00209
00210 if (i<n-1) {
00211
00212 SpaceStatus ss = s->status(stat.propagate);
00213
00214 if (constrained && (ss == SS_FAILED)) {
00215
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
00228 for (; i<n; i++)
00229 commit(s,i);
00230 }
00231 stat.commit += d;
00232 return s;
00233 }
00234
00235 }}
00236
00237