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