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