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