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(Space* 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(Space* 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 Support::Symbol
00079 Union<View0,View1,View2>::ati(void) {
00080 return Reflection::mangle<View0,View1,View2>("Gecode::Set::RelOp::Union");
00081 }
00082
00083 template <class View0, class View1, class View2>
00084 Reflection::ActorSpec
00085 Union<View0,View1,View2>::spec(const Space* home,
00086 Reflection::VarMap& m) const {
00087 return MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00088 View2,PC_SET_ANY>::spec(home, m, ati());
00089 }
00090
00091 template <class View0, class View1, class View2>
00092 void
00093 Union<View0,View1,View2>::post(Space* home,
00094 Reflection::VarMap& vars,
00095 const Reflection::ActorSpec& spec) {
00096 spec.checkArity(3);
00097 View0 x0(home, vars, spec[0]);
00098 View1 x1(home, vars, spec[1]);
00099 View2 x2(home, vars, spec[2]);
00100 (void) new (home) Union(home,x0,x1,x2);
00101 }
00102
00103 template <class View0, class View1, class View2>
00104 ExecStatus
00105 Union<View0,View1,View2>::propagate(Space* home, ModEventDelta med) {
00106
00107
00108
00109 bool x0ass = x0.assigned();
00110 bool x1ass = x1.assigned();
00111 bool x2ass = x2.assigned();
00112
00113 ModEvent me0 = View0::me(med);
00114 ModEvent me1 = View1::me(med);
00115 ModEvent me2 = View2::me(med);
00116
00117 bool x0ubmod = false;
00118 bool x1ubmod = false;
00119 bool modified = false;
00120
00121 do {
00122
00123 modified = false;
00124 do {
00125
00126 {
00127 LubRanges<View0> x0ub(x0);
00128 LubRanges<View1> x1ub(x1);
00129 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u2(x0ub,x1ub);
00130 GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) );
00131 }
00132
00133 if (modified || Rel::testSetEventUB(me2) )
00134 {
00135 modified = false;
00136
00137 LubRanges<View2> x2ub1(x2);
00138 GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) );
00139 x0ubmod |= modified;
00140
00141
00142 bool modified2=false;
00143 LubRanges<View2> x2ub2(x2);
00144 GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) );
00145 x1ubmod |= modified2;
00146 modified |= modified2;
00147 }
00148
00149 } while (modified);
00150
00151 modified = false;
00152 do {
00153 bool modifiedOld = modified;
00154 modified = false;
00155
00156 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me0)
00157 || x0ubmod || modifiedOld)
00158 {
00159
00160 GlbRanges<View2> x2lb(x2);
00161 LubRanges<View0> x0ub(x0);
00162 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> >
00163 diff(x2lb, x0ub);
00164 GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) );
00165 }
00166
00167 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me1)
00168 || x1ubmod || modifiedOld)
00169 {
00170
00171 GlbRanges<View2> x2lb(x2);
00172 LubRanges<View1> x1ub(x1);
00173 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> >
00174 diff(x2lb, x1ub);
00175 GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) );
00176 }
00177
00178 if (Rel::testSetEventLB(me0,me1) || modified)
00179 {
00180
00181
00182 GlbRanges<View0> x0lb(x0);
00183 GlbRanges<View1> x1lb(x1);
00184 Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> >
00185 u1(x0lb,x1lb);
00186 GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) );
00187 }
00188
00189 } while(modified);
00190
00191 modified = false;
00192 {
00193
00194 ExecStatus ret = unionCard(home,modified, x0, x1, x2);
00195 GECODE_ES_CHECK(ret);
00196 }
00197
00198 if (x2.cardMax() == 0) {
00199 GECODE_ME_CHECK( x0.cardMax(home, 0) );
00200 GECODE_ME_CHECK( x1.cardMax(home, 0) );
00201 return ES_SUBSUMED(this,home);
00202 }
00203
00204 if (x0.cardMax() == 0)
00205 GECODE_REWRITE(this,(Rel::Eq<View1,View2>::post(home,x1,x2)));
00206 if (x1.cardMax() == 0)
00207 GECODE_REWRITE(this,(Rel::Eq<View0,View2>::post(home,x0,x2)));
00208
00209 } while(modified);
00210
00211 if (shared(x0,x1,x2)) {
00212 return (x0ass && x1ass && x2ass) ? ES_SUBSUMED(this,home) : ES_NOFIX;
00213 } else {
00214 if (x0ass && x1ass && x2ass)
00215 return ES_SUBSUMED(this,home);
00216 if (x0ass != x0.assigned() ||
00217 x1ass != x1.assigned() ||
00218 x2ass != x2.assigned()) {
00219 return ES_NOFIX;
00220 } else {
00221 return ES_FIX;
00222 }
00223 }
00224 }
00225
00226
00227
00228
00229
00230
00231
00232 template <class View0, class View1>
00233 forceinline
00234 UnionN<View0,View1>::UnionN(Space* home, ViewArray<View0>& x, View1 y)
00235 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00236 shared = x.shared() || viewarrayshared(x,y);
00237 }
00238
00239 template <class View0, class View1>
00240 forceinline
00241 UnionN<View0,View1>::UnionN(Space* home, ViewArray<View0>& x,
00242 const IntSet& z, View1 y)
00243 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00244 shared = x.shared() || viewarrayshared(x,y);
00245 IntSetRanges rz(z);
00246 unionOfDets.includeI(home, rz);
00247 }
00248
00249 template <class View0, class View1>
00250 forceinline
00251 UnionN<View0,View1>::UnionN(Space* home, bool share, UnionN& p)
00252 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
00253 shared(p.shared) {
00254 unionOfDets.update(home,p.unionOfDets);
00255 }
00256
00257 template <class View0, class View1>
00258 Actor*
00259 UnionN<View0,View1>::copy(Space* home, bool share) {
00260 return new (home) UnionN<View0,View1>(home,share,*this);
00261 }
00262
00263 template <class View0, class View1>
00264 ExecStatus
00265 UnionN<View0,View1>::post(Space* home, ViewArray<View0>& x, View1 y) {
00266 switch (x.size()) {
00267 case 0:
00268 GECODE_ME_CHECK(y.cardMax(home, 0));
00269 return ES_OK;
00270 case 1:
00271 return Rel::Eq<View0,View1>::post(home, x[0], y);
00272 case 2:
00273 return Union<View0,View0,View1>::post(home, x[0], x[1], y);
00274 default:
00275 (void) new (home) UnionN<View0,View1>(home,x,y);
00276 return ES_OK;
00277 }
00278 }
00279
00280 template <class View0, class View1>
00281 ExecStatus
00282 UnionN<View0,View1>::post(Space* home, ViewArray<View0>& x,
00283 const IntSet& z, View1 y) {
00284 (void) new (home) UnionN<View0,View1>(home,x,z,y);
00285 return ES_OK;
00286 }
00287
00288 template <class View0, class View1>
00289 PropCost
00290 UnionN<View0,View1>::cost(ModEventDelta) const {
00291 return PC_QUADRATIC_LO;
00292 }
00293
00294 template <class View0, class View1>
00295 Support::Symbol
00296 UnionN<View0,View1>::ati(void) {
00297 return Reflection::mangle<View0,View1>("Gecode::Set::RelOp::UnionN");
00298 }
00299
00300 template <class View0, class View1>
00301 Reflection::ActorSpec
00302 UnionN<View0,View1>::spec(const Space* home,
00303 Reflection::VarMap& m) const {
00304 Reflection::ActorSpec s =
00305 MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>
00306 ::spec(home, m, ati());
00307 int count = 0;
00308 for (BndSetRanges uod(unionOfDets); uod(); ++uod)
00309 count++;
00310 Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00311 count = 0;
00312 for (BndSetRanges uod(unionOfDets); uod(); ++uod) {
00313 (*a)[count++] = uod.min();
00314 (*a)[count++] = uod.max();
00315 }
00316 return s << a;
00317 }
00318
00319 template <class View0, class View1>
00320 void
00321 UnionN<View0,View1>::post(Space* home,
00322 Reflection::VarMap& vars,
00323 const Reflection::ActorSpec& spec) {
00324 spec.checkArity(3);
00325 ViewArray<View0> x0(home, vars, spec[0]);
00326 View1 x1(home, vars, spec[1]);
00327 Reflection::IntArrayArgRanges zr(spec[2]->toIntArray());
00328 IntSet z(zr);
00329 (void) new (home) UnionN(home,x0,z,x1);
00330 }
00331
00332 template <class View0, class View1>
00333 ExecStatus
00334 UnionN<View0,View1>::propagate(Space* home, ModEventDelta med) {
00335 ModEvent me0 = View0::me(med);
00336 ModEvent me1 = View1::me(med);
00337 bool ubevent = Rel::testSetEventUB(me0, me1);
00338 bool lbevent = Rel::testSetEventLB(me0, me1);
00339 bool anybevent = Rel::testSetEventAnyB(me0, me1);
00340 bool cardevent = Rel::testSetEventCard(me0, me1);
00341
00342 bool modified = false;
00343 bool oldModified = false;
00344
00345 do {
00346 oldModified = modified;
00347 modified = false;
00348 if (modified || oldModified || ubevent)
00349 GECODE_ME_CHECK(unionNXiUB(home, modified, x, y,unionOfDets));
00350 if (modified || oldModified || ubevent)
00351 GECODE_ME_CHECK(partitionNYUB(home, modified, x, y,unionOfDets));
00352 if (modified || oldModified || anybevent)
00353 GECODE_ME_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets));
00354 if (modified || oldModified || lbevent)
00355 GECODE_ME_CHECK(partitionNYLB(home, modified, x, y,unionOfDets));
00356 if (modified || oldModified || cardevent || ubevent)
00357 GECODE_ME_CHECK(unionNCard(home, modified, x, y, unionOfDets));
00358 } while (modified);
00359
00360 for(int i=0;i<x.size();i++){
00361
00362 while (i<x.size() && x[i].assigned()) {
00363 GlbRanges<View0> det(x[i]);
00364 unionOfDets.includeI(home,det);
00365 x.move_lst(i);
00366 }
00367 }
00368
00369 if (x.size()==0) {
00370 BndSetRanges all1(unionOfDets);
00371 GECODE_ME_CHECK( y.intersectI(home,all1) );
00372 BndSetRanges all2(unionOfDets);
00373 GECODE_ME_CHECK( y.includeI(home,all2) );
00374 unionOfDets.dispose(home);
00375 return ES_SUBSUMED(this,home);
00376 }
00377
00378 return shared ? ES_NOFIX : ES_FIX;
00379 }
00380
00381 }}}
00382
00383