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
00039
00040
00041
00042 namespace Gecode { namespace Int { namespace Sequence {
00043
00047 template<class View>
00048 class SupportAdvisor : public Advisor {
00049 public:
00051 int i;
00053 SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00054 int i0);
00056 SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
00058 void dispose(Space& home, Council<SupportAdvisor>& c);
00059 };
00060
00061 template<class View>
00062 forceinline
00063 SupportAdvisor<View>::SupportAdvisor(Space& home, Propagator& p,
00064 Council<SupportAdvisor>& c,int i0)
00065 : Advisor(home,p,c), i(i0) {
00066 }
00067
00068 template<class View>
00069 forceinline
00070 SupportAdvisor<View>::SupportAdvisor(Space& home, bool share,
00071 SupportAdvisor& a)
00072 : Advisor(home,share,a), i(a.i) {
00073 }
00074
00075 template<class View>
00076 forceinline void
00077 SupportAdvisor<View>::dispose(Space& home, Council<SupportAdvisor>& c) {
00078 Advisor::dispose(home,c);
00079 }
00080
00084 template<class View, class Val,bool iss>
00085 class ViewValSupport {
00086 public:
00088 void init(Space& home, ViewArray<View>& x,Val s, int i, int q);
00090 void update(Space& home, bool share, ViewValSupport<View,Val,iss>& vvs, int n0);
00092 ExecStatus advise(Space& home,ViewArray<View>& a,Val s,int i,int q, int j,const Delta& d);
00094 ExecStatus propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u);
00096 bool violated(int j, int q, int l, int u) const;
00098 bool retired(void) const;
00100 static ViewValSupport* allocate(Space&,int);
00101 private:
00103 ExecStatus schedule_conclusion(ViewArray<View>& a,Val s,int i);
00105 bool conlusion_scheduled(void) const;
00107 void retire(void);
00109 int values(int j, int q) const;
00111 bool shaved(const View& x, Val s, int i) const;
00113 bool pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v);
00115 ExecStatus conclude(Space& home,ViewArray<View>& a,Val s,int i);
00117 bool s_not_possible(ViewArray<View>& a, Val s, int i, int idx) const;
00119 bool alternative_not_possible(ViewArray<View>& a,Val s,int i, int idx) const;
00121 bool has_potential_violation(void) const;
00123 int next_potential_violation(void);
00125 void potential_violation(int i);
00126
00127 void set(int idx, int v, int q, int n);
00129 void potential_violation(int idx, int q, int n);
00131 int* y;
00133 Violations v;
00134 };
00135
00136
00137 template<class View, class Val,bool iss>
00138 forceinline ViewValSupport<View,Val,iss>*
00139 ViewValSupport<View,Val,iss>::allocate(Space& home, int n) {
00140 return home.alloc<ViewValSupport<View,Val,iss> >(n);
00141 }
00142
00143 template<class View, class Val,bool iss>
00144 forceinline bool
00145 ViewValSupport<View,Val,iss>::has_potential_violation(void) const {
00146 return !v.empty();
00147 }
00148
00149 template<class View, class Val,bool iss>
00150 forceinline int
00151 ViewValSupport<View,Val,iss>::next_potential_violation(void) {
00152 return static_cast<int>(v.get());
00153 }
00154
00155 template<class View, class Val,bool iss>
00156 forceinline void
00157 ViewValSupport<View,Val,iss>::potential_violation(int k) {
00158 v.add(static_cast<int>(k));
00159 }
00160
00161
00162 template<class View, class Val,bool iss>
00163 forceinline bool
00164 ViewValSupport<View,Val,iss>::retired(void) const {
00165 return NULL == y;
00166 }
00167
00168 template<class View, class Val,bool iss>
00169 forceinline void
00170 ViewValSupport<View,Val,iss>::retire(void) {
00171 y = NULL;
00172 }
00173
00174 template<class View,class Val,bool iss>
00175 forceinline bool
00176 ViewValSupport<View,Val,iss>::alternative_not_possible
00177 (ViewArray<View>& a, Val s, int i, int idx) const {
00178 return includes(a[idx-1],s) || (iss && (idx-1 == i));
00179 }
00180
00181 template<class View, class Val,bool iss>
00182 forceinline bool
00183 ViewValSupport<View,Val,iss>::s_not_possible
00184 (ViewArray<View>& a, Val s, int i, int idx) const {
00185 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
00186 }
00187
00188
00189 template<class View, class Val,bool iss>
00190 forceinline void
00191 ViewValSupport<View,Val,iss>::init(Space& home, ViewArray<View>& a, Val s,
00192 int i, int q) {
00193 y = home.alloc<int>(a.size()+1);
00194 v.init(home,static_cast<unsigned int>(a.size()));
00195 y[0] = 0;
00196 for ( int l=0; l<a.size(); l++ ) {
00197 if ( alternative_not_possible(a,s,i,l+1) ) {
00198 y[l+1] = y[l] + 1;
00199 } else {
00200 y[l+1] = y[l];
00201 }
00202 if ( l+1 >= q ) {
00203 potential_violation(l+1-q);
00204 }
00205 if ( l <= a.size() - q ) {
00206 potential_violation(l);
00207 }
00208
00209 }
00210 }
00211
00212 template<class View, class Val,bool iss>
00213 forceinline void
00214 ViewValSupport<View,Val,iss>::update(Space& home, bool share,
00215 ViewValSupport<View,Val,iss>& vvs,
00216 int n0) {
00217 y = NULL;
00218 if ( !vvs.retired() ) {
00219 y = home.alloc<int>(n0);
00220 for ( int l=0; l<n0; l++ ) {
00221 y[l] = vvs.y[l];
00222 }
00223 v.update(home,share,vvs.v);
00224
00225 }
00226 }
00227
00228 template<class View,class Val,bool iss>
00229 forceinline bool
00230 ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
00231 if (iss)
00232 return excludes(x,s);
00233 else
00234 return includes(x,s);
00235 }
00236
00237 template<class View,class Val,bool iss>
00238 forceinline ExecStatus
00239 ViewValSupport<View,Val,iss>::schedule_conclusion(ViewArray<View>& a, Val s,
00240 int i) {
00241 if (!retired()) {
00242 if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
00243 return ES_FAILED;
00244 y[0] = 1;
00245 potential_violation(0);
00246 }
00247
00248 return ES_OK;
00249 }
00250
00251 template<class View,class Val,bool iss>
00252 forceinline bool
00253 ViewValSupport<View,Val,iss>::conlusion_scheduled(void) const {
00254 return !retired() && y[0] > 0;
00255 }
00256
00257 template<class View,class Val,bool iss>
00258 forceinline int
00259 ViewValSupport<View,Val,iss>::values(int j, int q) const {
00260 return y[j+q]-y[j];
00261 }
00262
00263 template<class View,class Val,bool iss>
00264 forceinline bool
00265 ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
00266 return values(j,q) < l || values(j,q) > u;
00267 }
00268
00269 template<class View,class Val,bool iss>
00270 forceinline ExecStatus
00271 ViewValSupport<View,Val,iss>::conclude(Space& home,ViewArray<View>& a,
00272 Val s, int i) {
00273 if ( iss ) {
00274 GECODE_ME_CHECK(exclude(home,a[i],s));
00275 } else {
00276 GECODE_ME_CHECK(include(home,a[i],s));
00277 }
00278
00279 retire();
00280
00281 return ES_OK;
00282 }
00283
00284 template<class View,class Val,bool iss>
00285 forceinline void
00286 ViewValSupport<View,Val,iss>::potential_violation(int idx, int q, int n) {
00287 if ( idx >= q ) {
00288 potential_violation(idx-q);
00289 }
00290 if ( idx <= n - q - 1) {
00291 potential_violation(idx);
00292 }
00293 }
00294
00295 template<class View,class Val,bool iss>
00296 forceinline void
00297 ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
00298 assert(y[idx]<=v);
00299 if ( y[idx] < v ) {
00300 y[idx] = v;
00301 potential_violation(idx,q,n);
00302 }
00303 }
00304
00305 template<class View,class Val,bool iss>
00306 forceinline bool
00307 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
00308 if ( !retired() ) {
00309 int n = a.size() + 1;
00310
00311 set(idx,y[idx]+v,q,n);
00312
00313 if ( y[idx] > idx ) {
00314 return false;
00315 }
00316
00317 int t = idx;
00318
00319
00320 while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
00321 if ( s_not_possible(a,s,i,idx) ) {
00322 set(idx-1,y[idx],q,n);
00323 } else {
00324 set(idx-1,y[idx]-1,q,n);
00325 }
00326 if ( y[idx-1]>idx-1 ) {
00327 return false;
00328 }
00329 idx -= 1;
00330 }
00331
00332 idx = t;
00333
00334
00335 while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
00336 if ( alternative_not_possible(a,s,i,idx+1) ) {
00337 set(idx+1,y[idx]+1,q,n);
00338 } else {
00339 set(idx+1,y[idx],q,n);
00340 }
00341 idx += 1;
00342 }
00343 }
00344
00345 return true;
00346 }
00347
00348 template<class View,class Val,bool iss>
00349 forceinline ExecStatus
00350 ViewValSupport<View,Val,iss>::advise(Space&, ViewArray<View>& a,
00351 Val s,int i,int q, int j,
00352 const Delta&) {
00353 ExecStatus status = ES_FIX;
00354 if (!retired()) {
00355 if ((j == i) && shaved(a[j],s,j)) {
00356 retire();
00357 } else {
00358 switch (takes(a[j],s)) {
00359 case TS_YES:
00360 if (y[j+1]-y[j] == 0) {
00361 if (!pushup(a,s,i,q,j+1,1)) {
00362 GECODE_ME_CHECK(schedule_conclusion(a,s,i));
00363 }
00364 }
00365 break;
00366 case TS_NO:
00367 if (y[j+1]-y[j] > 0) {
00368 if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
00369 GECODE_ME_CHECK(schedule_conclusion(a,s,i));
00370 }
00371 }
00372 break;
00373 case TS_MAYBE:
00374 break;
00375 default:
00376 GECODE_NEVER;
00377 }
00378
00379 if ( has_potential_violation() )
00380 status = ES_NOFIX;
00381 }
00382 }
00383
00384 return status;
00385 }
00386
00387 template<class View,class Val,bool iss>
00388 forceinline ExecStatus
00389 ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
00390 if ( !retired() ) {
00391 if ( conlusion_scheduled() ) {
00392 return conclude(home,a,s,i);
00393 }
00394
00395 while (has_potential_violation()) {
00396 int j = next_potential_violation();
00397 if (violated(j,q,l,u)) {
00398 int forced_to_s = values(j,q);
00399 if (forced_to_s < l) {
00400 if (!pushup(a,s,i,q,j+q,l-forced_to_s))
00401 return conclude(home,a,s,i);
00402 } else {
00403 if (!pushup(a,s,i,q,j,forced_to_s-u))
00404 return conclude(home,a,s,i);
00405 }
00406 if (violated(j,q,l,u))
00407 return conclude(home,a,s,i);
00408 }
00409 }
00410 }
00411 return ES_OK;
00412 }
00413
00414 template<class View,class Val,bool iss>
00415 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(void) : xs(NULL), n(0) {
00416 }
00417
00418 template<class View,class Val,bool iss>
00419 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(const ViewValSupportArray<View,Val,iss>& a) {
00420 n = a.n; xs = a.xs;
00421 }
00422
00423 template<class View,class Val,bool iss>
00424 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home,ViewArray<View>& x, Val s, int q) : xs(NULL) {
00425 n = x.size();
00426 if ( n > 0 ) {
00427 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00428 for (int i = n; i--; ) {
00429 xs[i].init(home,x,s,i,q);
00430 }
00431 }
00432 }
00433
00434 template<class View,class Val,bool iss>
00435 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home, int n0) : xs(NULL) {
00436 n = n0;
00437 if (n>0) {
00438 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00439 }
00440 }
00441
00442 template<class View,class Val,bool iss>
00443 forceinline int
00444 ViewValSupportArray<View,Val,iss>::size(void) const {
00445 return n;
00446 }
00447
00448 template<class View,class Val,bool iss>
00449 forceinline ViewValSupport<View,Val,iss>&
00450 ViewValSupportArray<View,Val,iss>::operator [](int i) {
00451 assert((i >= 0) && (i < size()));
00452 return xs[i];
00453 }
00454
00455 template<class View,class Val,bool iss>
00456 forceinline const ViewValSupport<View,Val,iss>&
00457 ViewValSupportArray<View,Val,iss>::operator [](int i) const {
00458 assert((i >= 0) && (i < size()));
00459 return xs[i];
00460 }
00461
00462 template<class View,class Val,bool iss>
00463 void
00464 ViewValSupportArray<View,Val,iss>::update(Space& home, bool share, ViewValSupportArray<View,Val,iss>& a) {
00465 n = a.size();
00466 if (n>0) {
00467 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00468 for (int i=n; i--; ) {
00469 xs[i].update(home,share,a[i],n+1);
00470 }
00471 }
00472 }
00473
00474 template<class View,class Val,bool iss>
00475 ExecStatus
00476 ViewValSupportArray<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int q,int l,int u) {
00477 for (int i=n; i--; ) {
00478 GECODE_ME_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
00479 }
00480 return ES_OK;
00481 }
00482
00483 template<class View,class Val,bool iss>
00484 ExecStatus
00485 ViewValSupportArray<View,Val,iss>::advise(Space& home,ViewArray<View>& a,Val s,int q,int j,const Delta& d) {
00486 ExecStatus status = ES_FIX;
00487 for (int i=n; i--; ) {
00488 if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
00489 status = ES_NOFIX;
00490 }
00491 return status;
00492 }
00493 }}}
00494
00495
00496
00497