Generated on Tue May 22 09:39:51 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Sets element idx of cumulative array to v
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       // = &home.construct<S>(S::key_compare(),S::allocator_type(home));
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       // repair y on the left
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       // repair y on the right
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 // STATISTICS: int-prop
00494