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