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<unsigned 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 (void) i;
00179 return includes(a[idx-1],s) || (iss && (idx-1 == i));
00180 }
00181
00182 template<class View, class Val,bool iss>
00183 forceinline bool
00184 ViewValSupport<View,Val,iss>::s_not_possible
00185 (ViewArray<View>& a, Val s, int i, int idx) const {
00186 (void) i;
00187 return excludes(a[idx-1],s) || (!iss && (i == idx-1));
00188 }
00189
00190
00191 template<class View, class Val,bool iss>
00192 forceinline void
00193 ViewValSupport<View,Val,iss>::init(Space& home, ViewArray<View>& a, Val s,
00194 int i, int q) {
00195 y = home.alloc<int>(a.size()+1);
00196 v.init(home,static_cast<unsigned int>(a.size()));
00197 y[0] = 0;
00198 for ( int l=0; l<a.size(); l++ ) {
00199 if ( alternative_not_possible(a,s,i,l+1) ) {
00200 y[l+1] = y[l] + 1;
00201 } else {
00202 y[l+1] = y[l];
00203 }
00204 if ( l+1 >= q ) {
00205 potential_violation(l+1-q);
00206 }
00207 if ( l <= a.size() - q ) {
00208 potential_violation(l);
00209 }
00210
00211 }
00212 }
00213
00214 template<class View, class Val,bool iss>
00215 forceinline void
00216 ViewValSupport<View,Val,iss>::update(Space& home, bool share,
00217 ViewValSupport<View,Val,iss>& vvs,
00218 int n0) {
00219 y = NULL;
00220 if ( !vvs.retired() ) {
00221 y = home.alloc<int>(n0);
00222 for ( int l=0; l<n0; l++ ) {
00223 y[l] = vvs.y[l];
00224 }
00225 v.update(home,share,vvs.v);
00226
00227 }
00228 }
00229
00230 template<class View,class Val,bool iss>
00231 forceinline bool
00232 ViewValSupport<View,Val,iss>::shaved(const View& x, Val s, int) const {
00233 if (iss)
00234 return excludes(x,s);
00235 else
00236 return includes(x,s);
00237 }
00238
00239 template<class View,class Val,bool iss>
00240 forceinline ExecStatus
00241 ViewValSupport<View,Val,iss>::schedule_conclusion(ViewArray<View>& a, Val s,
00242 int i) {
00243 if (!retired()) {
00244 if ((iss && includes(a[i],s)) || (!iss && excludes(a[i],s)))
00245 return ES_FAILED;
00246 y[0] = 1;
00247 potential_violation(0);
00248 }
00249
00250 return ES_OK;
00251 }
00252
00253 template<class View,class Val,bool iss>
00254 forceinline bool
00255 ViewValSupport<View,Val,iss>::conlusion_scheduled(void) const {
00256 return !retired() && y[0] > 0;
00257 }
00258
00259 template<class View,class Val,bool iss>
00260 forceinline int
00261 ViewValSupport<View,Val,iss>::values(int j, int q) const {
00262 return y[j+q]-y[j];
00263 }
00264
00265 template<class View,class Val,bool iss>
00266 forceinline bool
00267 ViewValSupport<View,Val,iss>::violated(int j, int q, int l, int u) const {
00268 return values(j,q) < l || values(j,q) > u;
00269 }
00270
00271 template<class View,class Val,bool iss>
00272 forceinline ExecStatus
00273 ViewValSupport<View,Val,iss>::conclude(Space& home,ViewArray<View>& a,
00274 Val s, int i) {
00275 if ( iss ) {
00276 GECODE_ME_CHECK(exclude(home,a[i],s));
00277 } else {
00278 GECODE_ME_CHECK(include(home,a[i],s));
00279 }
00280
00281 retire();
00282
00283 return ES_OK;
00284 }
00285
00286 template<class View,class Val,bool iss>
00287 forceinline void
00288 ViewValSupport<View,Val,iss>::potential_violation(int idx, int q, int n) {
00289 if ( idx >= q ) {
00290 potential_violation(idx-q);
00291 }
00292 if ( idx <= n - q - 1) {
00293 potential_violation(idx);
00294 }
00295 }
00296
00297 template<class View,class Val,bool iss>
00298 forceinline void
00299 ViewValSupport<View,Val,iss>::set(int idx, int v, int q, int n) {
00300 assert(y[idx]<=v);
00301 if ( y[idx] < v ) {
00302 y[idx] = v;
00303 potential_violation(idx,q,n);
00304 }
00305 }
00306
00307 template<class View,class Val,bool iss>
00308 forceinline bool
00309 ViewValSupport<View,Val,iss>::pushup(ViewArray<View>& a,Val s,int i,int q,int idx, int v) {
00310 if ( !retired() ) {
00311 int n = a.size() + 1;
00312
00313 set(idx,y[idx]+v,q,n);
00314
00315 if ( y[idx] > idx ) {
00316 return false;
00317 }
00318
00319 int t = idx;
00320
00321
00322 while ( idx > 0 && ((y[idx]-y[idx-1]>1) || ((y[idx]-y[idx-1]==1 && s_not_possible(a,s,i,idx)))) ) {
00323 if ( s_not_possible(a,s,i,idx) ) {
00324 set(idx-1,y[idx],q,n);
00325 } else {
00326 set(idx-1,y[idx]-1,q,n);
00327 }
00328 if ( y[idx-1]>idx-1 ) {
00329 return false;
00330 }
00331 idx -= 1;
00332 }
00333
00334 idx = t;
00335
00336
00337 while ( idx < a.size() && ((y[idx]-y[idx+1]>0) || ((y[idx]-y[idx+1]==0) && alternative_not_possible(a,s,i,idx+1))) ) {
00338 if ( alternative_not_possible(a,s,i,idx+1) ) {
00339 set(idx+1,y[idx]+1,q,n);
00340 } else {
00341 set(idx+1,y[idx],q,n);
00342 }
00343 idx += 1;
00344 }
00345 }
00346
00347 return true;
00348 }
00349
00350 template<class View,class Val,bool iss>
00351 forceinline ExecStatus
00352 ViewValSupport<View,Val,iss>::advise(Space&, ViewArray<View>& a,
00353 Val s,int i,int q, int j,
00354 const Delta&) {
00355 ExecStatus status = ES_FIX;
00356 if (!retired()) {
00357 if ((j == i) && shaved(a[j],s,j)) {
00358 retire();
00359 } else {
00360 switch (takes(a[j],s)) {
00361 case TS_YES:
00362 if (y[j+1]-y[j] == 0) {
00363 if (!pushup(a,s,i,q,j+1,1)) {
00364 GECODE_ES_CHECK(schedule_conclusion(a,s,i));
00365 }
00366 }
00367 break;
00368 case TS_NO:
00369 if (y[j+1]-y[j] > 0) {
00370 if (!pushup(a,s,i,q,j,y[j+1]-y[j])) {
00371 GECODE_ES_CHECK(schedule_conclusion(a,s,i));
00372 }
00373 }
00374 break;
00375 case TS_MAYBE:
00376 break;
00377 default:
00378 GECODE_NEVER;
00379 }
00380
00381 if ( has_potential_violation() )
00382 status = ES_NOFIX;
00383 }
00384 }
00385
00386 return status;
00387 }
00388
00389 template<class View,class Val,bool iss>
00390 forceinline ExecStatus
00391 ViewValSupport<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int i,int q,int l,int u) {
00392 if ( !retired() ) {
00393 if ( conlusion_scheduled() ) {
00394 return conclude(home,a,s,i);
00395 }
00396
00397 while (has_potential_violation()) {
00398 int j = next_potential_violation();
00399 if (violated(j,q,l,u)) {
00400 int forced_to_s = values(j,q);
00401 if (forced_to_s < l) {
00402 if (!pushup(a,s,i,q,j+q,l-forced_to_s))
00403 return conclude(home,a,s,i);
00404 } else {
00405 if (!pushup(a,s,i,q,j,forced_to_s-u))
00406 return conclude(home,a,s,i);
00407 }
00408 if (violated(j,q,l,u))
00409 return conclude(home,a,s,i);
00410 }
00411 }
00412 }
00413 return ES_OK;
00414 }
00415
00416 template<class View,class Val,bool iss>
00417 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(void) : xs(NULL), n(0) {
00418 }
00419
00420 template<class View,class Val,bool iss>
00421 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(const ViewValSupportArray<View,Val,iss>& a) {
00422 n = a.n; xs = a.xs;
00423 }
00424
00425 template<class View,class Val,bool iss>
00426 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home,ViewArray<View>& x, Val s, int q) : xs(NULL) {
00427 n = x.size();
00428 if ( n > 0 ) {
00429 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00430 for (int i = n; i--; ) {
00431 xs[i].init(home,x,s,i,q);
00432 }
00433 }
00434 }
00435
00436 template<class View,class Val,bool iss>
00437 ViewValSupportArray<View,Val,iss>::ViewValSupportArray(Space& home, int n0) : xs(NULL) {
00438 n = n0;
00439 if (n>0) {
00440 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00441 }
00442 }
00443
00444 template<class View,class Val,bool iss>
00445 forceinline int
00446 ViewValSupportArray<View,Val,iss>::size(void) const {
00447 return n;
00448 }
00449
00450 template<class View,class Val,bool iss>
00451 forceinline ViewValSupport<View,Val,iss>&
00452 ViewValSupportArray<View,Val,iss>::operator [](int i) {
00453 assert((i >= 0) && (i < size()));
00454 return xs[i];
00455 }
00456
00457 template<class View,class Val,bool iss>
00458 forceinline const ViewValSupport<View,Val,iss>&
00459 ViewValSupportArray<View,Val,iss>::operator [](int i) const {
00460 assert((i >= 0) && (i < size()));
00461 return xs[i];
00462 }
00463
00464 template<class View,class Val,bool iss>
00465 void
00466 ViewValSupportArray<View,Val,iss>::update(Space& home, bool share, ViewValSupportArray<View,Val,iss>& a) {
00467 n = a.size();
00468 if (n>0) {
00469 xs = ViewValSupport<View,Val,iss>::allocate(home,n);
00470 for (int i=n; i--; ) {
00471 xs[i].update(home,share,a[i],n+1);
00472 }
00473 }
00474 }
00475
00476 template<class View,class Val,bool iss>
00477 ExecStatus
00478 ViewValSupportArray<View,Val,iss>::propagate(Space& home,ViewArray<View>& a,Val s,int q,int l,int u) {
00479 for (int i=n; i--; ) {
00480 GECODE_ES_CHECK(xs[i].propagate(home,a,s,i,q,l,u));
00481 }
00482 return ES_OK;
00483 }
00484
00485 template<class View,class Val,bool iss>
00486 ExecStatus
00487 ViewValSupportArray<View,Val,iss>::advise(Space& home,ViewArray<View>& a,Val s,int q,int j,const Delta& d) {
00488 ExecStatus status = ES_FIX;
00489 for (int i=n; i--; ) {
00490 if ( ES_NOFIX == xs[i].advise(home,a,s,i,q,j,d) )
00491 status = ES_NOFIX;
00492 }
00493 return status;
00494 }
00495 }}}
00496
00497
00498
00499