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 namespace Gecode { namespace Set { namespace Element {
00037
00038 template<class SView, class RView>
00039 forceinline
00040 ElementUnionConst<SView,RView>::
00041 ElementUnionConst(Home home, SView y0,
00042 const IntSetArgs& iv0,
00043 RView y1)
00044 : Propagator(home), x0(y0), n_iv(iv0.size()), x1(y1) {
00045 home.notice(*this,AP_DISPOSE);
00046 x0.subscribe(home,*this, PC_SET_ANY);
00047 x1.subscribe(home,*this, PC_SET_ANY);
00048 iv=static_cast<Space&>(home).alloc<IntSet>(n_iv);
00049 for (unsigned int i=iv0.size(); i--;)
00050 iv[i]=iv0[i];
00051 }
00052
00053 template<class SView, class RView>
00054 forceinline
00055 ElementUnionConst<SView,RView>::
00056 ElementUnionConst(Space& home, ElementUnionConst<SView,RView>& p)
00057 : Propagator(home,p), n_iv(p.n_iv) {
00058 x0.update(home,p.x0);
00059 x1.update(home,p.x1);
00060 iv=home.alloc<IntSet>(n_iv);
00061 for (unsigned int i=n_iv; i--;)
00062 iv[i]=p.iv[i];
00063 }
00064
00065 template<class SView, class RView>
00066 PropCost
00067 ElementUnionConst<SView,RView>::cost(const Space&, const ModEventDelta&) const {
00068 return PropCost::linear(PropCost::HI, n_iv+2);
00069 }
00070
00071 template<class SView, class RView>
00072 void
00073 ElementUnionConst<SView,RView>::reschedule(Space& home) {
00074 x0.reschedule(home,*this, PC_SET_ANY);
00075 x1.reschedule(home,*this, PC_SET_ANY);
00076 }
00077
00078 template<class SView, class RView>
00079 forceinline size_t
00080 ElementUnionConst<SView,RView>::dispose(Space& home) {
00081 home.ignore(*this,AP_DISPOSE);
00082 if (!home.failed()) {
00083 x0.cancel(home,*this, PC_SET_ANY);
00084 x1.cancel(home,*this, PC_SET_ANY);
00085 }
00086 for (unsigned int i=n_iv; i--;)
00087 iv[i].~IntSet();
00088 (void) Propagator::dispose(home);
00089 return sizeof(*this);
00090 }
00091
00092 template<class SView, class RView>
00093 ExecStatus
00094 ElementUnionConst<SView,RView>::
00095 post(Home home, SView x0, const IntSetArgs& xs,
00096 RView x1) {
00097 int n = xs.size();
00098
00099
00100 Iter::Ranges::Singleton s(0, n-1);
00101 GECODE_ME_CHECK(x1.intersectI(home,s));
00102 (void) new (home)
00103 ElementUnionConst<SView,RView>(home,x0,xs,x1);
00104 return ES_OK;
00105 }
00106
00107 template<class SView, class RView>
00108 Actor*
00109 ElementUnionConst<SView,RView>::copy(Space& home) {
00110 return new (home) ElementUnionConst<SView,RView>(home,*this);
00111 }
00112
00113 template<class SView, class RView>
00114 ExecStatus
00115 ElementUnionConst<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00116 Region r;
00117
00118 bool* stillSelected = r.alloc<bool>(n_iv);
00119
00120 bool loopVar;
00121 do {
00122 loopVar = false;
00123 for (int i=n_iv; i--;)
00124 stillSelected[i] = false;
00125
00126
00127
00128 LubRanges<RView> x1ub(x1);
00129 Iter::Ranges::Cache x1ubc(r,x1ub);
00130 Iter::Ranges::ToValues<Iter::Ranges::Cache>
00131 vx1ub(x1ubc);
00132
00133 GlbRanges<RView> x1lb(x1);
00134 Iter::Ranges::Cache x1lbc(r,x1lb);
00135 Iter::Ranges::ToValues<Iter::Ranges::Cache>
00136 vx1(x1lbc);
00137
00138
00139
00140
00141
00142 GLBndSet sofarBefore(home);
00143 LUBndSet selectedInter(home, IntSet (Limits::min,
00144 Limits::max));
00145 GLBndSet* before =
00146 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n_iv));
00147
00148 unsigned int maxCard = 0;
00149 unsigned int minCard = Limits::card;
00150
00151 while (vx1ub()) {
00152 int i = vx1ub.val();
00153
00154 IntSetRanges candCardR(iv[i]);
00155 unsigned int candidateCard = Iter::Ranges::size(candCardR);
00156
00157 IntSetRanges candlb(iv[i]);
00158 LubRanges<SView> x0ub(x0);
00159 Iter::Ranges::Diff<IntSetRanges,
00160 LubRanges<SView> > diff(candlb, x0ub);
00161
00162 bool selectSingleInconsistent = false;
00163 if (x1.cardMax() <= 1) {
00164 GlbRanges<SView> x0lb(x0);
00165 IntSetRanges candub(iv[i]);
00166 Iter::Ranges::Diff<GlbRanges<SView>,
00167 IntSetRanges > diff2(x0lb, candub);
00168 selectSingleInconsistent = diff2() || candidateCard < x0.cardMin();
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179 if (selectSingleInconsistent ||
00180 candidateCard > x0.cardMax() ||
00181 diff()) {
00182 ModEvent me = (x1.exclude(home,i));
00183 loopVar |= me_modified(me);
00184 GECODE_ME_CHECK(me);
00185 } else {
00186 stillSelected[i] = true;
00187
00188
00189 if (vx1() && vx1.val()==i) {
00190
00191
00192 IntSetRanges candlb(iv[i]);
00193 ModEvent me = x0.includeI(home,candlb);
00194 loopVar |= me_modified(me);
00195 GECODE_ME_CHECK(me);
00196 ++vx1;
00197 }
00198 new (&before[i]) GLBndSet(home);
00199 before[i].update(home,sofarBefore);
00200 IntSetRanges cub(iv[i]);
00201 sofarBefore.includeI(home,cub);
00202 IntSetRanges clb(iv[i]);
00203 selectedInter.intersectI(home,clb);
00204 maxCard = std::max(maxCard, candidateCard);
00205 minCard = std::min(minCard, candidateCard);
00206 }
00207
00208 ++vx1ub;
00209 }
00210
00211 if (x1.cardMax()==0) {
00212
00213 {
00214 GECODE_ME_CHECK(x0.cardMax(home,0));
00215 }
00216 for (int i=n_iv; i--;)
00217 if (stillSelected[i])
00218 before[i].dispose(home);
00219 selectedInter.dispose(home);
00220 sofarBefore.dispose(home);
00221 return home.ES_SUBSUMED(*this);
00222 }
00223
00224 if (x1.cardMin() > 0) {
00225
00226
00227 BndSetRanges si(selectedInter);
00228 ModEvent me = x0.includeI(home, si);
00229 loopVar |= me_modified(me);
00230 GECODE_ME_CHECK(me);
00231 me = x0.cardMin(home, minCard);
00232 loopVar |= me_modified(me);
00233 GECODE_ME_CHECK(me);
00234 }
00235 selectedInter.dispose(home);
00236
00237 if (x1.cardMax() <= 1) {
00238 ModEvent me = x0.cardMax(home, maxCard);
00239 loopVar |= me_modified(me);
00240 GECODE_ME_CHECK(me);
00241 }
00242
00243 {
00244
00245 BndSetRanges sfB(sofarBefore);
00246 ModEvent me = x0.intersectI(home,sfB);
00247 loopVar |= me_modified(me);
00248 GECODE_ME_CHECK(me);
00249 }
00250
00251 sofarBefore.dispose(home);
00252
00253 GLBndSet sofarAfter(home);
00254
00255
00256
00257 for (int i=n_iv; i--;) {
00258 if (!stillSelected[i])
00259 continue;
00260 BndSetRanges b(before[i]);
00261 BndSetRanges s(sofarAfter);
00262 GlbRanges<SView> x0lb(x0);
00263 Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
00264 Iter::Ranges::Diff<GlbRanges<SView>,
00265 Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter);
00266 if (diff()) {
00267 ModEvent me = (x1.include(home,i));
00268 loopVar |= me_modified(me);
00269 GECODE_ME_CHECK(me);
00270
00271
00272 IntSetRanges ivi(iv[i]);
00273 if (!Iter::Ranges::subset(diff, ivi))
00274 GECODE_ME_CHECK(ME_SET_FAILED);
00275 }
00276
00277 IntSetRanges iviub(iv[i]);
00278 sofarAfter.includeI(home,iviub);
00279 before[i].dispose(home);
00280 }
00281 sofarAfter.dispose(home);
00282
00283 } while (loopVar);
00284
00285 if (x1.assigned()) {
00286 assert(x0.assigned());
00287 return home.ES_SUBSUMED(*this);
00288 }
00289
00290 return ES_FIX;
00291 }
00292
00293 }}}
00294
00295