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 RelOp {
00041
00042
00043
00044
00045
00046
00047 template<class View0, class View1, class View2> ExecStatus
00048 Intersection<View0,View1,View2>::post(Home home,
00049 View0 x0,View1 x1,View2 x2) {
00050 (void) new (home) Intersection<View0,View1,View2>(home,x0,x1,x2);
00051 return ES_OK;
00052 }
00053
00054 template<class View0, class View1, class View2>
00055 Actor*
00056 Intersection<View0,View1,View2>::copy(Space& home) {
00057 return new (home) Intersection(home,*this);
00058 }
00059
00060 template<class View0, class View1, class View2>
00061 ExecStatus
00062 Intersection<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) {
00063
00064
00065
00066 bool x0ass = x0.assigned();
00067 bool x1ass = x1.assigned();
00068 bool x2ass = x2.assigned();
00069
00070 ModEvent me0 = View0::me(med);
00071 ModEvent me1 = View1::me(med);
00072 ModEvent me2 = View2::me(med);
00073
00074 bool x0lbmod = false;
00075 bool x1lbmod = false;
00076 bool modified = false;
00077
00078 do {
00079
00080 modified = false;
00081 do {
00082
00083 {
00084 GlbRanges<View0> x0lb(x0);
00085 GlbRanges<View1> x1lb(x1);
00086 Iter::Ranges::Inter<GlbRanges<View0>, GlbRanges<View1> >
00087 i2(x0lb,x1lb);
00088 GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,i2) );
00089 }
00090
00091 if (modified || Rel::testSetEventLB(me2) )
00092 {
00093 modified = false;
00094
00095 GlbRanges<View2> x2lb1(x2);
00096 GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,x2lb1) );
00097 x0lbmod |= modified;
00098
00099
00100 bool modified2=false;
00101 GlbRanges<View2> x2lb2(x2);
00102 GECODE_ME_CHECK_MODIFIED(modified2, x1.includeI(home,x2lb2) );
00103 x1lbmod |= modified2;
00104 modified |= modified2;
00105 }
00106
00107 } while (modified);
00108
00109 modified = false;
00110 do {
00111 bool modifiedOld = modified;
00112 modified = false;
00113
00114 if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me0)
00115 || x0lbmod || modifiedOld)
00116 {
00117
00118 GlbRanges<View0> x0lb(x0);
00119 LubRanges<View2> x2ub(x2);
00120 Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View2> >
00121 diff(x0lb, x2ub);
00122 GECODE_ME_CHECK_MODIFIED(modified, x1.excludeI(home,diff) );
00123 }
00124
00125 if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me1)
00126 || x1lbmod || modifiedOld)
00127 {
00128
00129 GlbRanges<View1> x1lb(x1);
00130 LubRanges<View2> x2ub(x2);
00131 Iter::Ranges::Diff<GlbRanges<View1>, LubRanges<View2> >
00132 diff(x1lb, x2ub);
00133 GECODE_ME_CHECK_MODIFIED(modified, x0.excludeI(home,diff) );
00134 }
00135
00136 if (Rel::testSetEventUB(me0,me1) || modified)
00137 {
00138
00139
00140 LubRanges<View0> x0ub(x0);
00141 LubRanges<View1> x1ub(x1);
00142 Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> >
00143 i1(x0ub,x1ub);
00144 GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,i1) );
00145 }
00146
00147 } while(modified);
00148
00149 modified = false;
00150 {
00151
00152 ExecStatus ret = interCard(home,modified, x0, x1, x2);
00153 GECODE_ES_CHECK(ret);
00154 }
00155
00156 if (x2.cardMin() == Set::Limits::card) {
00157 GECODE_ME_CHECK( x0.cardMin(home, Set::Limits::card) );
00158 GECODE_ME_CHECK( x1.cardMin(home, Set::Limits::card) );
00159 return home.ES_SUBSUMED(*this);
00160 }
00161
00162 if (x0.cardMin() == Set::Limits::card)
00163 GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
00164 if (x1.cardMin() == Set::Limits::card)
00165 GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
00166
00167 } while(modified);
00168
00169 if (shared(x0,x1,x2)) {
00170 return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00171 } else {
00172 if (x0ass && x1ass && x2ass)
00173 return home.ES_SUBSUMED(*this);
00174 if (x0ass != x0.assigned() ||
00175 x1ass != x1.assigned() ||
00176 x2ass != x2.assigned()) {
00177 return ES_NOFIX;
00178 } else {
00179 return ES_FIX;
00180 }
00181 }
00182 }
00183
00184 template<class View0, class View1, class View2>
00185 forceinline
00186 Intersection<View0,View1,View2>::Intersection(Home home,
00187 View0 y0,View1 y1,View2 y2)
00188 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00189 View2,PC_SET_ANY>(home,y0,y1,y2) {}
00190
00191 template<class View0, class View1, class View2>
00192 forceinline
00193 Intersection<View0,View1,View2>::Intersection(Space& home,
00194 Intersection<View0,View1,View2>& p)
00195 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00196 View2,PC_SET_ANY>(home,p) {}
00197
00198
00199
00200
00201
00202
00203 template<class View0, class View1>
00204 forceinline
00205 IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x,
00206 View1 y)
00207 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00208 intOfDets(home) {
00209 shared = x.shared() || viewarrayshared(x,y);
00210 }
00211
00212 template<class View0, class View1>
00213 forceinline
00214 IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x,
00215 const IntSet& z, View1 y)
00216 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00217 intOfDets(home) {
00218 shared = x.shared() || viewarrayshared(x,y);
00219 IntSetRanges rz(z);
00220 intOfDets.intersectI(home, rz);
00221 }
00222
00223 template<class View0, class View1>
00224 forceinline
00225 IntersectionN<View0,View1>::IntersectionN(Space& home,
00226 IntersectionN& p)
00227 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
00228 shared(p.shared),
00229 intOfDets() {
00230 intOfDets.update(home, p.intOfDets);
00231 }
00232
00233 template<class View0, class View1>
00234 ExecStatus
00235 IntersectionN<View0,View1>::post(Home home,
00236 ViewArray<View0>& x, View1 y) {
00237 switch (x.size()) {
00238 case 0:
00239 GECODE_ME_CHECK(y.cardMin(home, Limits::card));
00240 return ES_OK;
00241 case 1:
00242 return Rel::Eq<View0,View1>::post(home, x[0], y);
00243 case 2:
00244 return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
00245 default:
00246 (void) new (home) IntersectionN<View0,View1>(home,x,y);
00247 return ES_OK;
00248 }
00249 }
00250
00251 template<class View0, class View1>
00252 ExecStatus
00253 IntersectionN<View0,View1>::post(Home home, ViewArray<View0>& x,
00254 const IntSet& z, View1 y) {
00255 (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
00256 return ES_OK;
00257 }
00258
00259 template<class View0, class View1>
00260 Actor*
00261 IntersectionN<View0,View1>::copy(Space& home) {
00262 return new (home) IntersectionN<View0,View1>(home,*this);
00263 }
00264
00265 template<class View0, class View1>
00266 PropCost
00267 IntersectionN<View0,View1>::cost(const Space&, const ModEventDelta&) const {
00268 return PropCost::quadratic(PropCost::HI, x.size()+1);
00269 }
00270
00271 template<class View0, class View1>
00272 ExecStatus
00273 IntersectionN<View0,View1>::propagate(Space& home, const ModEventDelta&) {
00274 bool repeat = false;
00275 do {
00276 repeat = false;
00277 int xsize = x.size();
00278 if (xsize == 0)
00279 goto size0;
00280 for (int i = xsize; i--; ) {
00281 GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
00282 GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
00283 if (x[i].cardMax()==0) {
00284 GECODE_ME_CHECK( y.cardMax(home, 0));
00285 intOfDets.dispose(home);
00286 return home.ES_SUBSUMED(*this);
00287 }
00288 }
00289 {
00290 Region r;
00291 GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize);
00292 LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize);
00293 for (int i = xsize; i--; ) {
00294 GlbRanges<View0> lb(x[i]);
00295 LubRanges<View0> ub(x[i]);
00296 xLBs[i]=lb;
00297 xUBs[i]=ub;
00298 }
00299 {
00300 Iter::Ranges::NaryInter lbi(r,xLBs,xsize);
00301 BndSetRanges dets(intOfDets);
00302 lbi &= dets;
00303 GECODE_ME_CHECK(y.includeI(home,lbi));
00304 }
00305 {
00306 Iter::Ranges::NaryInter ubi(r,xUBs,xsize);
00307 BndSetRanges dets(intOfDets);
00308 ubi &= dets;
00309 GECODE_ME_CHECK(y.intersectI(home,ubi));
00310 }
00311 }
00312
00313 for (int i = xsize; i--; ) {
00314 GlbRanges<View1> ylb(y);
00315 GECODE_ME_CHECK( x[i].includeI(home,ylb) );
00316 }
00317
00318
00319 {
00320 Region r;
00321 GLBndSet* rightSet =
00322 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
00323 new (&rightSet[xsize-1]) GLBndSet(home);
00324 rightSet[xsize-1].update(home,intOfDets);
00325 for (int i=xsize-1;i--;) {
00326 GlbRanges<View0> xilb(x[i+1]);
00327 BndSetRanges prev(rightSet[i+1]);
00328 Iter::Ranges::Inter<GlbRanges<View0>,
00329 BndSetRanges> inter(xilb,prev);
00330 new (&rightSet[i]) GLBndSet(home);
00331 rightSet[i].includeI(home,inter);
00332 }
00333
00334 LUBndSet leftAcc(home);
00335
00336 for (int i=0;i<xsize;i++) {
00337 BndSetRanges left(leftAcc);
00338 BndSetRanges right(rightSet[i]);
00339 Iter::Ranges::Inter<BndSetRanges,
00340 BndSetRanges> inter(left, right);
00341 LubRanges<View1> yub(y);
00342 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00343 BndSetRanges>, LubRanges<View1> >
00344 forbidden(inter, yub);
00345 GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
00346 GlbRanges<View0> xlb(x[i]);
00347 leftAcc.intersectI(home,xlb);
00348 }
00349 for (int i=xsize; i--;)
00350 rightSet[i].dispose(home);
00351 leftAcc.dispose(home);
00352 }
00353
00354
00355 for(int i=0;i<x.size();i++) {
00356
00357 while (i<x.size() && x[i].assigned()) {
00358 GlbRanges<View0> det(x[i]);
00359 if (intOfDets.intersectI(home,det)) {repeat = true;}
00360 x.move_lst(i);
00361 if (intOfDets.size()==0) {
00362 GECODE_ME_CHECK( y.cardMax(home,0) );
00363 intOfDets.dispose(home);
00364 return home.ES_SUBSUMED(*this);
00365 }
00366 }
00367 }
00368 size0:
00369 if (x.size()==0) {
00370 BndSetRanges all1(intOfDets);
00371 GECODE_ME_CHECK( y.intersectI(home,all1) );
00372 BndSetRanges all2(intOfDets);
00373 GECODE_ME_CHECK( y.includeI(home,all2) );
00374 intOfDets.dispose(home);
00375 return home.ES_SUBSUMED(*this);
00376 }
00377
00378 } while (repeat);
00379
00380 return shared ? ES_NOFIX : ES_FIX;
00381 }
00382
00383 }}}
00384
00385