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