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