view.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * David Rijsman <David.Rijsman@quintiq.com> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * David Rijsman, 2009 00011 * Christian Schulte, 2009 00012 * 00013 * Last modified: 00014 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ 00015 * $Revision: 11192 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 // Sets element idx of cumulative array to v 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 // = &home.construct<S>(S::key_compare(),S::allocator_type(home)); 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 // repair y on the left 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 // repair y on the right 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_ME_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_ME_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_ME_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 // STATISTICS: int-prop 00499