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 Element {
00041
00042 template <class SView, class RView>
00043 forceinline
00044 ElementIntersection<SView,RView>::
00045 ElementIntersection(Space* home, SView y0,
00046 IdxViewArray<SView>& iv0,
00047 RView y1,
00048 const IntSet& theUniverse)
00049 : Propagator(home), universe(theUniverse), x0(y0), iv(iv0), x1(y1) {
00050 force(home);
00051 x0.subscribe(home,this, PC_SET_ANY);
00052 x1.subscribe(home,this, PC_SET_ANY);
00053 iv.subscribe(home,this, PC_SET_ANY);
00054 }
00055
00056 template <class SView, class RView>
00057 forceinline
00058 ElementIntersection<SView,RView>::
00059 ElementIntersection(Space* home, bool share,
00060 ElementIntersection<SView,RView>& p)
00061 : Propagator(home,share,p) {
00062 x0.update(home,share,p.x0);
00063 x1.update(home,share,p.x1);
00064 iv.update(home,share,p.iv);
00065 universe.update(home,share,p.universe);
00066 }
00067
00068 template <class SView, class RView>
00069 PropCost
00070 ElementIntersection<SView,RView>::cost(ModEventDelta) const {
00071 return PC_LINEAR_HI;
00072 }
00073
00074 template <class SView, class RView>
00075 Support::Symbol
00076 ElementIntersection<SView,RView>::ati(void) {
00077 return Reflection::mangle<SView,RView>("Gecode::Set::Element::Intersection");
00078 }
00079
00080 template <class SView, class RView>
00081 Reflection::ActorSpec
00082 ElementIntersection<SView,RView>::spec(const Space* home,
00083 Reflection::VarMap& m) const {
00084 Reflection::ActorSpec s(ati());
00085 int count = 0;
00086 for (IntSetRanges ur(universe); ur(); ++ur)
00087 count++;
00088 Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00089 count = 0;
00090 for (IntSetRanges ur(universe); ur(); ++ur) {
00091 (*a)[count++] = ur.min();
00092 (*a)[count++] = ur.max();
00093 }
00094 return s << a
00095 << x0.spec(home, m)
00096 << iv.spec(home, m)
00097 << x1.spec(home, m);
00098 }
00099
00100 template <class SView, class RView>
00101 void
00102 ElementIntersection<SView,RView>::post(Space* home,
00103 Reflection::VarMap& vars,
00104 const Reflection::ActorSpec& spec) {
00105 spec.checkArity(4);
00106 Reflection::IntArrayArgRanges ur(spec[0]->toIntArray());
00107 IntSet universe(ur);
00108 SView x0(home, vars, spec[1]);
00109 IdxViewArray<SView> iv(home, vars, spec[2]);
00110 RView x1(home, vars, spec[3]);
00111 (void) new (home) ElementIntersection(home, x0, iv, x1, universe);
00112 }
00113
00114 template <class SView, class RView>
00115 size_t
00116 ElementIntersection<SView,RView>::dispose(Space* home) {
00117 unforce(home);
00118 if (!home->failed()) {
00119 x0.cancel(home,this, PC_SET_ANY);
00120 x1.cancel(home,this, PC_SET_ANY);
00121 iv.cancel(home,this,PC_SET_ANY);
00122 }
00123 universe.~IntSet();
00124 (void) Propagator::dispose(home);
00125 return sizeof(*this);
00126 }
00127
00128 template <class SView, class RView>
00129 ExecStatus
00130 ElementIntersection<SView,RView>::
00131 post(Space* home, SView x0, IdxViewArray<SView>& xs,
00132 RView x1, const IntSet& universe) {
00133 int n = xs.size();
00134
00135
00136 Iter::Ranges::Singleton s(0, n-1);
00137 GECODE_ME_CHECK(x1.intersectI(home,s));
00138 (void) new (home)
00139 ElementIntersection<SView,RView>(home,x0,xs,x1,universe);
00140 return ES_OK;
00141 }
00142
00143 template <class SView, class RView>
00144 Actor*
00145 ElementIntersection<SView,RView>::copy(Space* home, bool share) {
00146 return new (home) ElementIntersection<SView,RView>(home,share,*this);
00147 }
00148
00149 template <class SView, class RView>
00150 ExecStatus
00151 ElementIntersection<SView,RView>::propagate(Space* home, ModEventDelta) {
00152 int n = iv.size();
00153
00154 bool loopVar;
00155 do {
00156 loopVar = false;
00157
00158
00159
00160 LubRanges<RView> x1ub(x1);
00161 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00162 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00163 vx1ub(x1ubc);
00164
00165 GlbRanges<RView> x1lb(x1);
00166 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00167 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00168 vx1(x1lbc);
00169
00170
00171
00172
00173
00174
00175 LUBndSet sofarBefore(home,universe);
00176 GECODE_AUTOARRAY(LUBndSet, before, n);
00177
00178 int j = 0;
00179 int i = 0;
00180 while ( vx1ub() ) {
00181
00182
00183 if (iv[i].idx < vx1ub.val()) {
00184 iv[i].var.cancel(home,this, PC_SET_ANY);
00185 ++i;
00186 continue;
00187 }
00188 assert(iv[i].idx == vx1ub.val());
00189 iv[j] = iv[i];
00190
00191 SView candidate = iv[j].var;
00192 int candidateInd = iv[j].idx;
00193
00194
00195 GlbRanges<SView> x0lb(x0);
00196 LubRanges<SView> candub(candidate);
00197 Iter::Ranges::Diff<GlbRanges<SView>,LubRanges<SView> >
00198 inter(x0lb, candub);
00199
00200
00201
00202
00203
00204
00205 if (candidate.cardMax() < x0.cardMin() ||
00206 inter()) {
00207 ModEvent me = (x1.exclude(home,candidateInd));
00208 loopVar |= me_modified(me);
00209 GECODE_ME_CHECK(me);
00210
00211 iv[j].var.cancel(home,this, PC_SET_ANY);
00212 ++i;
00213 ++vx1ub;
00214 continue;
00215 } else {
00216
00217
00218 if (vx1() && vx1.val()==candidateInd) {
00219
00220 GlbRanges<SView> x0lb(x0);
00221 ModEvent me = candidate.includeI(home,x0lb);
00222 loopVar |= me_modified(me);
00223 GECODE_ME_CHECK(me);
00224
00225 LubRanges<SView> candub(candidate);
00226 me = x0.intersectI(home,candub);
00227 loopVar |= me_modified(me);
00228 GECODE_ME_CHECK(me);
00229 ++vx1;
00230 }
00231 new (&before[j]) LUBndSet(home);
00232 before[j].update(home,sofarBefore);
00233 GlbRanges<SView> clb(candidate);
00234 sofarBefore.intersectI(home,clb);
00235 }
00236
00237 ++vx1ub;
00238 ++i; ++j;
00239 }
00240
00241
00242
00243 for (int k=i; k<n; k++) {
00244 iv[k].var.cancel(home,this, PC_SET_ANY);
00245 }
00246 n = j;
00247 iv.size(n);
00248
00249 if (x1.cardMax()==0) {
00250
00251 {
00252 IntSetRanges uniI(universe);
00253 GECODE_ME_CHECK(x0.includeI(home,uniI));
00254 }
00255 {
00256 IntSetRanges uniI(universe);
00257 GECODE_ME_CHECK(x0.intersectI(home,uniI));
00258 }
00259 for (int i=n; i--;)
00260 before[i].dispose(home);
00261 return ES_SUBSUMED(this,home);
00262 }
00263
00264 {
00265
00266 BndSetRanges sfB(sofarBefore);
00267 ModEvent me = x0.includeI(home,sfB);
00268 loopVar |= me_modified(me);
00269 GECODE_ME_CHECK(me);
00270 }
00271
00272 sofarBefore.dispose(home);
00273
00274 LUBndSet sofarAfter(home, universe);
00275
00276
00277
00278 for (int i=n; i--;) {
00279 if (sofarAfter.size() == 0) break;
00280
00281
00282 BndSetRanges b(before[i]);
00283 BndSetRanges s(sofarAfter);
00284 LubRanges<SView> x0ub(x0);
00285 Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00286 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00287 BndSetRanges>, LubRanges<SView> > diff(inter, x0ub);
00288 if (diff()) {
00289 ModEvent me = (x1.include(home,iv[i].idx));
00290 loopVar |= me_modified(me);
00291 GECODE_ME_CHECK(me);
00292
00293
00294 me = iv[i].var.excludeI(home,diff);
00295 loopVar |= me_modified(me);
00296 GECODE_ME_CHECK(me);
00297 }
00298
00299 GlbRanges<SView> ivilb(iv[i].var);
00300 sofarAfter.intersectI(home,ivilb);
00301 before[i].dispose(home);
00302 }
00303 sofarAfter.dispose(home);
00304
00305 } while (loopVar);
00306
00307
00308 if (x1.assigned() && !x0.assigned()) {
00309 int ubsize = x1.lubSize();
00310 if (ubsize > 2) {
00311 assert(ubsize==n);
00312 ViewArray<SView> is(home,ubsize);
00313 for (int i=n; i--;)
00314 is[i]=iv[i].var;
00315 GECODE_REWRITE(this,(RelOp::IntersectionN<SView, SView>
00316 ::post(home,is,x0)));
00317 } else if (ubsize == 2) {
00318 assert(n==2);
00319 SView a = iv[0].var;
00320 SView b = iv[1].var;
00321 GECODE_REWRITE(this,(RelOp::Intersection<SView, SView, SView>
00322 ::post(home,a,b,x0)));
00323 } else if (ubsize == 1) {
00324 assert(n==1);
00325 GECODE_REWRITE(this,(Rel::Eq<SView,SView>::post(home,x0,iv[0].var)));
00326 } else {
00327 GECODE_ME_CHECK(x0.cardMax(home, 0));
00328 return ES_SUBSUMED(this,home);
00329 }
00330 }
00331
00332 bool allAssigned = true;
00333 for (int i=iv.size(); i--;) {
00334 if (!iv[i].var.assigned()) {
00335 allAssigned = false;
00336 break;
00337 }
00338 }
00339 if (x0.assigned() && x1.assigned() && allAssigned) {
00340 return ES_SUBSUMED(this,home);
00341 }
00342
00343 return ES_FIX;
00344 }
00345
00346 }}}
00347
00348