Generated on Mon May 10 06:46:35 2010 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  *  Last modified:
00014  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $
00015  *     $Revision: 10684 $
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<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       // = &home.construct<S>(S::key_compare(),S::allocator_type(home));
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       // repair y on the left
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       // repair y on the right
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 // STATISTICS: int-prop
00497