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