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