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(Space* 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 Support::Symbol
00066 Intersection<View0,View1,View2>::ati(void) {
00067 return Reflection::mangle<View0,View1,View2>("Gecode::Set::RelOp::Intersection");
00068 }
00069
00070 template <class View0, class View1, class View2>
00071 Reflection::ActorSpec
00072 Intersection<View0,View1,View2>::spec(const Space* home,
00073 Reflection::VarMap& m) const {
00074 return MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00075 View2,PC_SET_ANY>::spec(home, m, ati());
00076 }
00077
00078 template <class View0, class View1, class View2>
00079 void
00080 Intersection<View0,View1,View2>::post(Space* home,
00081 Reflection::VarMap& vars,
00082 const Reflection::ActorSpec& spec) {
00083 spec.checkArity(3);
00084 View0 x0(home, vars, spec[0]);
00085 View1 x1(home, vars, spec[1]);
00086 View2 x2(home, vars, spec[2]);
00087 (void) new (home) Intersection(home,x0,x1,x2);
00088 }
00089
00090 template <class View0, class View1, class View2>
00091 ExecStatus
00092 Intersection<View0,View1,View2>::propagate(Space* home, ModEventDelta) {
00093
00094 bool x0ass=x0.assigned();
00095 bool x1ass=x1.assigned();
00096 bool x2ass=x2.assigned();
00097
00098 {
00099 GlbRanges<View2> x2lb(x2);
00100 GECODE_ME_CHECK( x0.includeI(home,x2lb) );
00101 }
00102 {
00103 GlbRanges<View2> x2lb(x2);
00104 GECODE_ME_CHECK( x1.includeI(home,x2lb) );
00105 }
00106 {
00107 GlbRanges<View0> x0lb(x0);
00108 LubRanges<View2> x2ub(x2);
00109 Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View2> > m1(x0lb,x2ub);
00110 GECODE_ME_CHECK( x1.excludeI(home,m1) );
00111 }
00112 {
00113 GlbRanges<View1> x1lb(x1);
00114 LubRanges<View2> x2ub(x2);
00115
00116 Iter::Ranges::Diff<GlbRanges<View1>,LubRanges<View2> > m2(x1lb,x2ub);
00117 GECODE_ME_CHECK( x0.excludeI(home,m2) );
00118 }
00119 {
00120 GlbRanges<View0> x0lb(x0);
00121 GlbRanges<View1> x1lb(x1);
00122 Iter::Ranges::Inter<GlbRanges<View0>,GlbRanges<View1> > i1(x0lb,x1lb);
00123 GECODE_ME_CHECK( x2.includeI(home,i1) );
00124 }
00125 {
00126 LubRanges<View0> x0ub(x0);
00127 LubRanges<View1> x1ub(x1);
00128 Iter::Ranges::Inter<LubRanges<View0>,LubRanges<View1> > i2(x0ub,x1ub);
00129 GECODE_ME_CHECK( x2.intersectI(home,i2) );
00130 }
00131 unsigned int m, n;
00132 {
00133 LubRanges<View0> x0ub(x0);
00134 LubRanges<View1> x1ub(x1);
00135 Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > u1(x0ub,x1ub);
00136 m = Iter::Ranges::size(u1);
00137 n = x0.cardMin()+x1.cardMin();
00138 if (n>m)
00139 GECODE_ME_CHECK( x2.cardMin(home,n-m) );
00140 }
00141 unsigned int s2;
00142 {
00143 LubRanges<View0> x0ub(x0);
00144 GlbRanges<View1> x1lb(x1);
00145 Iter::Ranges::Diff<GlbRanges<View1>,LubRanges<View0> > d2(x1lb,x0ub);
00146 s2 = Iter::Ranges::size(d2);
00147 assert (s2 <= x1.cardMax());
00148 GECODE_ME_CHECK( x2.cardMax(home,x1.cardMax()-s2) );
00149 }
00150 {
00151 LubRanges<View1> x1ub(x1);
00152 GlbRanges<View0> x0lb(x0);
00153 Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View1> > d1 (x0lb,x1ub);
00154 unsigned int s1 = Iter::Ranges::size(d1);
00155 assert (s1 <= x0.cardMax());
00156 GECODE_ME_CHECK( x2.cardMax(home,x0.cardMax()-s1) );
00157 if (m+x2.cardMax() > x1.cardMin())
00158 GECODE_ME_CHECK( x0.cardMax(home,m+x2.cardMax()-x1.cardMin()) );
00159
00160 if (m+x2.cardMax() > x0.cardMin())
00161 GECODE_ME_CHECK( x1.cardMax(home,m+x2.cardMax()-x0.cardMin()) );
00162
00163 GECODE_ME_CHECK( x0.cardMin(home,s1+x2.cardMin()) );
00164 GECODE_ME_CHECK( x1.cardMin(home,s2+x2.cardMin()) );
00165 }
00166 if ( x0ass + x1ass + x2ass >= 2 ) return ES_SUBSUMED(this,home);
00167
00168 return ES_NOFIX;
00169 }
00170
00171 template <class View0, class View1, class View2>
00172 forceinline
00173 Intersection<View0,View1,View2>::Intersection(Space* home,
00174 View0 y0,View1 y1,View2 y2)
00175 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00176 View2,PC_SET_ANY>(home,y0,y1,y2) {}
00177
00178 template <class View0, class View1, class View2>
00179 forceinline
00180 Intersection<View0,View1,View2>::Intersection(Space* home, bool share,
00181 Intersection<View0,View1,View2>& p)
00182 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00183 View2,PC_SET_ANY>(home,share,p) {}
00184
00185
00186
00187
00188
00189
00190 template <class View0, class View1>
00191 forceinline
00192 IntersectionN<View0,View1>::IntersectionN(Space* home, ViewArray<View0>& x,
00193 View1 y)
00194 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00195 intOfDets(home) {
00196 shared = x.shared() || viewarrayshared(x,y);
00197 }
00198
00199 template <class View0, class View1>
00200 forceinline
00201 IntersectionN<View0,View1>::IntersectionN(Space* home, ViewArray<View0>& x,
00202 const IntSet& z, View1 y)
00203 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00204 intOfDets(home) {
00205 shared = x.shared() || viewarrayshared(x,y);
00206 IntSetRanges rz(z);
00207 intOfDets.intersectI(home, rz);
00208 }
00209
00210 template <class View0, class View1>
00211 forceinline
00212 IntersectionN<View0,View1>::IntersectionN(Space* home, bool share,
00213 IntersectionN& p)
00214 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
00215 shared(p.shared),
00216 intOfDets() {
00217 intOfDets.update(home, p.intOfDets);
00218 }
00219
00220 template <class View0, class View1>
00221 ExecStatus
00222 IntersectionN<View0,View1>::post(Space* home,
00223 ViewArray<View0>& x, View1 y) {
00224 switch (x.size()) {
00225 case 0:
00226 GECODE_ME_CHECK(y.cardMin(home, Limits::card));
00227 return ES_OK;
00228 case 1:
00229 return Rel::Eq<View0,View1>::post(home, x[0], y);
00230 case 2:
00231 return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
00232 default:
00233 (void) new (home) IntersectionN<View0,View1>(home,x,y);
00234 return ES_OK;
00235 }
00236 }
00237
00238 template <class View0, class View1>
00239 ExecStatus
00240 IntersectionN<View0,View1>::post(Space* home, ViewArray<View0>& x,
00241 const IntSet& z, View1 y) {
00242 (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
00243 return ES_OK;
00244 }
00245
00246 template <class View0, class View1>
00247 Actor*
00248 IntersectionN<View0,View1>::copy(Space* home, bool share) {
00249 return new (home) IntersectionN<View0,View1>(home,share,*this);
00250 }
00251
00252 template <class View0, class View1>
00253 PropCost
00254 IntersectionN<View0,View1>::cost(ModEventDelta) const {
00255 return PC_QUADRATIC_LO;
00256 }
00257
00258 template <class View0, class View1>
00259 Support::Symbol
00260 IntersectionN<View0,View1>::ati(void) {
00261 return Reflection::mangle<View0,View1>("Gecode::Set::RelOp::IntersectionN");
00262 }
00263
00264 template <class View0, class View1>
00265 Reflection::ActorSpec
00266 IntersectionN<View0,View1>::spec(const Space* home,
00267 Reflection::VarMap& m) const {
00268 Reflection::ActorSpec s =
00269 MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>
00270 ::spec(home, m, ati());
00271 int count = 0;
00272 for (BndSetRanges iod(intOfDets); iod(); ++iod)
00273 count++;
00274 Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00275 count = 0;
00276 for (BndSetRanges iod(intOfDets); iod(); ++iod) {
00277 (*a)[count++] = iod.min();
00278 (*a)[count++] = iod.max();
00279 }
00280 return s << a;
00281 }
00282
00283 template <class View0, class View1>
00284 void
00285 IntersectionN<View0,View1>::post(Space* home,
00286 Reflection::VarMap& vars,
00287 const Reflection::ActorSpec& spec) {
00288 spec.checkArity(3);
00289 ViewArray<View0> x0(home, vars, spec[0]);
00290 View1 x1(home, vars, spec[1]);
00291 Reflection::IntArrayArgRanges zr(spec[2]->toIntArray());
00292 IntSet z(zr);
00293 (void) new (home) IntersectionN(home,x0,z,x1);
00294 }
00295
00296 template <class View0, class View1>
00297 ExecStatus
00298 IntersectionN<View0,View1>::propagate(Space* home, ModEventDelta) {
00299
00300 bool repeat = false;
00301 do {
00302 repeat = false;
00303 int xsize = x.size();
00304 if (xsize == 0)
00305 goto size0;
00306 for (int i = xsize; i--; ) {
00307 GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
00308 GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
00309 if (x[i].cardMax()==0) {
00310 GECODE_ME_CHECK( y.cardMax(home, 0));
00311 intOfDets.dispose(home);
00312 return ES_SUBSUMED(this,home);
00313 }
00314 }
00315 {
00316 GECODE_AUTOARRAY(GlbRanges<View0>,xLBs,xsize);
00317 GECODE_AUTOARRAY(LubRanges<View0>,xUBs,xsize);
00318 for (int i = xsize; i--; ) {
00319 GlbRanges<View0> lb(x[i]);
00320 LubRanges<View0> ub(x[i]);
00321 xLBs[i]=lb;
00322 xUBs[i]=ub;
00323 }
00324 Iter::Ranges::NaryInter<GlbRanges<View0> > lbi(xLBs,xsize);
00325 BndSetRanges dets1(intOfDets);
00326 Iter::Ranges::Inter< Iter::Ranges::NaryInter<GlbRanges<View0> >,
00327 BndSetRanges >
00328 lbiAll(lbi,dets1);
00329 GECODE_ME_CHECK( y.includeI(home,lbiAll) );
00330
00331 Iter::Ranges::NaryInter<LubRanges<View0> > ubi(xUBs,xsize);
00332 BndSetRanges dets2(intOfDets);
00333 Iter::Ranges::Inter< Iter::Ranges::NaryInter<LubRanges<View0> >,
00334 BndSetRanges >
00335 ubiAll(ubi,dets2);
00336 GECODE_ME_CHECK( y.intersectI(home,ubiAll) );
00337 }
00338
00339 for (int i = xsize; i--; ) {
00340 GlbRanges<View1> ylb(y);
00341 GECODE_ME_CHECK( x[i].includeI(home,ylb) );
00342 }
00343
00344
00345 {
00346 GECODE_AUTOARRAY(GLBndSet, rightSet, xsize);
00347 new (&rightSet[xsize-1]) GLBndSet(home);
00348 rightSet[xsize-1].update(home,intOfDets);
00349 for (int i=xsize-1;i--;) {
00350 GlbRanges<View0> xilb(x[i+1]);
00351 BndSetRanges prev(rightSet[i+1]);
00352 Iter::Ranges::Inter<GlbRanges<View0>,
00353 BndSetRanges> inter(xilb,prev);
00354 new (&rightSet[i]) GLBndSet(home);
00355 rightSet[i].includeI(home,inter);
00356 }
00357
00358 LUBndSet leftAcc(home);
00359
00360 for (int i=0;i<xsize;i++) {
00361 BndSetRanges left(leftAcc);
00362 BndSetRanges right(rightSet[i]);
00363 Iter::Ranges::Inter<BndSetRanges,
00364 BndSetRanges> inter(left, right);
00365 LubRanges<View1> yub(y);
00366 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00367 BndSetRanges>, LubRanges<View1> >
00368 forbidden(inter, yub);
00369 GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
00370 GlbRanges<View0> xlb(x[i]);
00371 leftAcc.intersectI(home,xlb);
00372 }
00373 for (int i=xsize; i--;)
00374 rightSet[i].dispose(home);
00375 leftAcc.dispose(home);
00376 }
00377
00378
00379 for(int i=0;i<x.size();i++){
00380
00381 while (i<x.size() && x[i].assigned()) {
00382 GlbRanges<View0> det(x[i]);
00383 if (intOfDets.intersectI(home,det)) {repeat = true;}
00384 x.move_lst(i);
00385 if (intOfDets.size()==0) {
00386 GECODE_ME_CHECK( y.cardMax(home,0) );
00387 intOfDets.dispose(home);
00388 return ES_SUBSUMED(this,home);
00389 }
00390 }
00391 }
00392 size0:
00393 if (x.size()==0) {
00394 BndSetRanges all1(intOfDets);
00395 GECODE_ME_CHECK( y.intersectI(home,all1) );
00396 BndSetRanges all2(intOfDets);
00397 GECODE_ME_CHECK( y.includeI(home,all2) );
00398 intOfDets.dispose(home);
00399 return ES_SUBSUMED(this,home);
00400 }
00401
00402 } while (repeat);
00403
00404 return shared ? ES_NOFIX : ES_FIX;
00405 }
00406
00407 }}}
00408
00409