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>
00048 forceinline
00049 Union<View0,View1,View2>::Union(Home home, View0 y0,View1 y1,View2 y2)
00050 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00051 View2,PC_SET_ANY>(home,y0,y1,y2) {}
00052
00053 template<class View0, class View1, class View2>
00054 forceinline
00055 Union<View0,View1,View2>::Union(Space& home,
00056 Union<View0,View1,View2>& p)
00057 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00058 View2,PC_SET_ANY>(home,p) {}
00059
00060 template<class View0, class View1, class View2>
00061 ExecStatus Union<View0,View1,View2>::post(Home home, View0 x0,
00062 View1 x1, View2 x2) {
00063 (void) new (home) Union<View0,View1,View2>(home,x0,x1,x2);
00064 return ES_OK;
00065 }
00066
00067 template<class View0, class View1, class View2>
00068 Actor*
00069 Union<View0,View1,View2>::copy(Space& home) {
00070 return new (home) Union(home,*this);
00071 }
00072
00073 template<class View0, class View1, class View2>
00074 ExecStatus
00075 Union<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) {
00076
00077
00078
00079 bool x0ass = x0.assigned();
00080 bool x1ass = x1.assigned();
00081 bool x2ass = x2.assigned();
00082
00083 ModEvent me0 = View0::me(med);
00084 ModEvent me1 = View1::me(med);
00085 ModEvent me2 = View2::me(med);
00086
00087 bool x0ubmod = false;
00088 bool x1ubmod = false;
00089 bool modified = false;
00090
00091 do {
00092
00093 modified = false;
00094 do {
00095
00096 {
00097 LubRanges<View0> x0ub(x0);
00098 LubRanges<View1> x1ub(x1);
00099 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u2(x0ub,x1ub);
00100 GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) );
00101 }
00102
00103 if (modified || Rel::testSetEventUB(me2) )
00104 {
00105 modified = false;
00106
00107 LubRanges<View2> x2ub1(x2);
00108 GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) );
00109 x0ubmod |= modified;
00110
00111
00112 bool modified2=false;
00113 LubRanges<View2> x2ub2(x2);
00114 GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) );
00115 x1ubmod |= modified2;
00116 modified |= modified2;
00117 }
00118
00119 } while (modified);
00120
00121 modified = false;
00122 do {
00123 bool modifiedOld = modified;
00124 modified = false;
00125
00126 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me0)
00127 || x0ubmod || modifiedOld)
00128 {
00129
00130 GlbRanges<View2> x2lb(x2);
00131 LubRanges<View0> x0ub(x0);
00132 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> >
00133 diff(x2lb, x0ub);
00134 GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) );
00135 }
00136
00137 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me1)
00138 || x1ubmod || modifiedOld)
00139 {
00140
00141 GlbRanges<View2> x2lb(x2);
00142 LubRanges<View1> x1ub(x1);
00143 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> >
00144 diff(x2lb, x1ub);
00145 GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) );
00146 }
00147
00148 if (Rel::testSetEventLB(me0,me1) || modified)
00149 {
00150
00151
00152 GlbRanges<View0> x0lb(x0);
00153 GlbRanges<View1> x1lb(x1);
00154 Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> >
00155 u1(x0lb,x1lb);
00156 GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) );
00157 }
00158
00159 } while(modified);
00160
00161 modified = false;
00162 {
00163
00164 ExecStatus ret = unionCard(home,modified, x0, x1, x2);
00165 GECODE_ES_CHECK(ret);
00166 }
00167
00168 if (x2.cardMax() == 0) {
00169 GECODE_ME_CHECK( x0.cardMax(home, 0) );
00170 GECODE_ME_CHECK( x1.cardMax(home, 0) );
00171 return home.ES_SUBSUMED(*this);
00172 }
00173
00174 if (x0.cardMax() == 0)
00175 GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
00176 if (x1.cardMax() == 0)
00177 GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
00178
00179 } while(modified);
00180
00181 if (shared(x0,x1,x2)) {
00182 return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00183 } else {
00184 if (x0ass && x1ass && x2ass)
00185 return home.ES_SUBSUMED(*this);
00186 if (x0ass != x0.assigned() ||
00187 x1ass != x1.assigned() ||
00188 x2ass != x2.assigned()) {
00189 return ES_NOFIX;
00190 } else {
00191 return ES_FIX;
00192 }
00193 }
00194 }
00195
00196
00197
00198
00199
00200
00201
00202 template<class View0, class View1>
00203 forceinline
00204 UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x, View1 y)
00205 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00206 shared = Gecode::shared(x) || viewarrayshared(x,y);
00207 }
00208
00209 template<class View0, class View1>
00210 forceinline
00211 UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x,
00212 const IntSet& z, View1 y)
00213 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00214 shared = Gecode::shared(x) || viewarrayshared(x,y);
00215 IntSetRanges rz(z);
00216 unionOfDets.includeI(home, rz);
00217 }
00218
00219 template<class View0, class View1>
00220 forceinline
00221 UnionN<View0,View1>::UnionN(Space& home, UnionN& p)
00222 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
00223 shared(p.shared) {
00224 unionOfDets.update(home,p.unionOfDets);
00225 }
00226
00227 template<class View0, class View1>
00228 Actor*
00229 UnionN<View0,View1>::copy(Space& home) {
00230 return new (home) UnionN<View0,View1>(home,*this);
00231 }
00232
00233 template<class View0, class View1>
00234 ExecStatus
00235 UnionN<View0,View1>::post(Home home, ViewArray<View0>& x, View1 y) {
00236 switch (x.size()) {
00237 case 0:
00238 GECODE_ME_CHECK(y.cardMax(home, 0));
00239 return ES_OK;
00240 case 1:
00241 return Rel::Eq<View0,View1>::post(home, x[0], y);
00242 case 2:
00243 return Union<View0,View0,View1>::post(home, x[0], x[1], y);
00244 default:
00245 (void) new (home) UnionN<View0,View1>(home,x,y);
00246 return ES_OK;
00247 }
00248 }
00249
00250 template<class View0, class View1>
00251 ExecStatus
00252 UnionN<View0,View1>::post(Home home, ViewArray<View0>& x,
00253 const IntSet& z, View1 y) {
00254 (void) new (home) UnionN<View0,View1>(home,x,z,y);
00255 return ES_OK;
00256 }
00257
00258 template<class View0, class View1>
00259 PropCost
00260 UnionN<View0,View1>::cost(const Space&, const ModEventDelta&) const {
00261 return PropCost::quadratic(PropCost::LO, x.size()+1);
00262 }
00263
00264 template<class View0, class View1>
00265 ExecStatus
00266 UnionN<View0,View1>::propagate(Space& home, const ModEventDelta& med) {
00267 ModEvent me0 = View0::me(med);
00268 ModEvent me1 = View1::me(med);
00269 bool ubevent = Rel::testSetEventUB(me0, me1);
00270 bool lbevent = Rel::testSetEventLB(me0, me1);
00271 bool anybevent = Rel::testSetEventAnyB(me0, me1);
00272 bool cardevent = Rel::testSetEventCard(me0, me1);
00273
00274 bool modified = false;
00275 bool oldModified = false;
00276
00277 do {
00278 do {
00279 oldModified = modified;
00280 modified = false;
00281 if (modified || oldModified || ubevent)
00282 GECODE_ES_CHECK(unionNXiUB(home, modified, x, y,unionOfDets));
00283 if (modified || oldModified || ubevent)
00284 GECODE_ES_CHECK(partitionNYUB(home, modified, x, y,unionOfDets));
00285 if (modified || oldModified || anybevent)
00286 GECODE_ES_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets));
00287 if (modified || oldModified || lbevent)
00288 GECODE_ES_CHECK(partitionNYLB(home, modified, x, y,unionOfDets));
00289 if (modified || oldModified || cardevent || ubevent) {
00290 GECODE_ES_CHECK(unionNCard(home, modified, x, y, unionOfDets));
00291 }
00292 } while (modified);
00293
00294 for(int i=0;i<x.size();i++) {
00295
00296 while (i<x.size() && x[i].assigned()) {
00297 GlbRanges<View0> det(x[i]);
00298 unionOfDets.includeI(home,det);
00299 x.move_lst(i);
00300 modified = true;
00301 }
00302 }
00303
00304 } while (modified);
00305
00306 if (x.size()==0) {
00307 BndSetRanges all1(unionOfDets);
00308 GECODE_ME_CHECK( y.intersectI(home,all1) );
00309 BndSetRanges all2(unionOfDets);
00310 GECODE_ME_CHECK( y.includeI(home,all2) );
00311 unionOfDets.dispose(home);
00312 return home.ES_SUBSUMED(*this);
00313 }
00314
00315 return shared ? ES_NOFIX : ES_FIX;
00316 }
00317
00318 }}}
00319
00320