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