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