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