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