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 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
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
00184