Generated on Fri Oct 19 11:25:04 2018 for Gecode by doxygen 1.6.3

int.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 
00040   template<class View, class Val>
00041   forceinline
00042   Sequence<View,Val>::Sequence(Home home, ViewArray<View>& x0, Val s0,
00043                                int q0, int l0, int u0)
00044     : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0),
00045       vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home),
00046       tofail(false) {
00047     home.notice(*this,AP_DISPOSE);
00048     bool assigned = false;
00049     for (int i=x.size(); i--; ) {
00050       if (undecided(x[i],s))
00051         x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i));
00052       if (x[i].assigned())
00053         assigned = true;
00054     }
00055     View::schedule(home,*this,assigned ? ME_INT_VAL : ME_INT_BND);
00056   }
00057 
00058   template<class View, class Val>
00059   forceinline
00060   Sequence<View,Val>::Sequence(Space& home, Sequence& p)
00061     : Propagator(home,p), s(p.s), q(p.q), l(p.l), u(p.u),
00062       vvsamax(), vvsamin(), tofail(p.tofail) {
00063     x.update(home,p.x);
00064     ac.update(home,p.ac);
00065     vvsamax.update(home,p.vvsamax);
00066     vvsamin.update(home,p.vvsamin);
00067   }
00068 
00069   template<class View,class Val>
00070   ExecStatus
00071   Sequence<View,Val>::advise(Space& home, Advisor& _a, const Delta& d) {
00072     SupportAdvisor<View>& a = static_cast<SupportAdvisor<View>&>(_a);
00073     ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d);
00074     if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) {
00075       status = ES_NOFIX;
00076     }
00077 
00078     if (!undecided(x[a.i],s)) {
00079       if (!x[a.i].assigned())
00080         x[a.i].cancel(home,a);
00081 
00082       if ( ES_NOFIX == status ) {
00083         return home.ES_NOFIX_DISPOSE(ac,a);
00084       } else {
00085         return home.ES_FIX_DISPOSE(ac,a);
00086       }
00087     }
00088 
00089     if ((status == ES_FAILED) && disabled()) {
00090       tofail = true;
00091       return ES_FIX;
00092     }
00093 
00094     return status;
00095   }
00096 
00097   template<class View, class Val>
00098   forceinline size_t
00099   Sequence<View,Val>::dispose(Space& home) {
00100     home.ignore(*this,AP_DISPOSE);
00101     ac.dispose(home);
00102     s.~Val();
00103     (void) Propagator::dispose(home);
00104     return sizeof(*this);
00105   }
00106 
00107   template<class View, class Val>
00108   forceinline ExecStatus
00109   Sequence<View,Val>::check(ViewArray<View>& x, Val s, int q, int l, int u) {
00110     Region r;
00111     // could do this with an array of length q...
00112     int* upper = r.alloc<int>(x.size()+1);
00113     int* lower = r.alloc<int>(x.size()+1);
00114     upper[0] = 0;
00115     lower[0] = 0;
00116     for ( int j=0; j<x.size(); j++ ) {
00117       upper[j+1] = upper[j];
00118       lower[j+1] = lower[j];
00119       if (includes(x[j],s)) {
00120         upper[j+1] += 1;
00121       } else if (excludes(x[j],s)) {
00122         lower[j+1] += 1;
00123       }
00124       if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) {
00125         return ES_FAILED;
00126       }
00127     }
00128     return ES_OK;
00129   }
00130 
00131   template<class View, class Val>
00132   ExecStatus
00133   Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) {
00134     GECODE_ES_CHECK(check(x,s,q,l,u));
00135     Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u);
00136 
00137     GECODE_ES_CHECK(p->vvsamax.propagate(home,x,s,q,l,u));
00138     GECODE_ES_CHECK(p->vvsamin.propagate(home,x,s,q,l,u));
00139 
00140    return ES_OK;
00141   }
00142 
00143   template<class View, class Val>
00144   Actor*
00145   Sequence<View,Val>::copy(Space& home) {
00146     return new (home) Sequence<View,Val>(home,*this);
00147   }
00148 
00149   template<class View, class Val>
00150   PropCost
00151   Sequence<View,Val>::cost(const Space&, const ModEventDelta&) const {
00152     return PropCost::cubic(PropCost::HI,x.size());
00153   }
00154 
00155   template<class View, class Val>
00156   void
00157   Sequence<View,Val>::reschedule(Space& home) {
00158     for (int i=x.size(); i--; )
00159       if (!undecided(x[i],s))
00160         x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
00161     if (tofail)
00162       View::schedule(home,*this,ME_INT_BND);
00163   }
00164 
00165   template<class View, class Val>
00166   ExecStatus
00167   Sequence<View,Val>::propagate(Space& home, const ModEventDelta&) {
00168     if (tofail)
00169       return ES_FAILED;
00170 
00171     GECODE_ES_CHECK(vvsamax.propagate(home,x,s,q,l,u));
00172     GECODE_ES_CHECK(vvsamin.propagate(home,x,s,q,l,u));
00173 
00174     for (int i=x.size(); i--; )
00175       if (undecided(x[i],s))
00176         return ES_FIX;
00177 
00178     return home.ES_SUBSUMED(*this);
00179   }
00180 
00181 }}}
00182 
00183 // STATISTICS: int-prop
00184