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