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 Select {
00041
00042 template <class SView, class RView>
00043 forceinline
00044 SelectIntersection<SView,RView>::
00045 SelectIntersection(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 SelectIntersection<SView,RView>::
00059 SelectIntersection(Space* home, bool share,
00060 SelectIntersection<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 SelectIntersection<SView,RView>::cost(ModEventDelta) const {
00071 return PC_LINEAR_HI;
00072 }
00073
00074 template <class SView, class RView>
00075 Support::Symbol
00076 SelectIntersection<SView,RView>::ati(void) {
00077 return Reflection::mangle<SView,RView>("Gecode::Set::Select::Intersection");
00078 }
00079
00080 template <class SView, class RView>
00081 Reflection::ActorSpec
00082 SelectIntersection<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 SelectIntersection<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) SelectIntersection(home, x0, iv, x1, universe);
00112 }
00113
00114 template <class SView, class RView>
00115 size_t
00116 SelectIntersection<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 SelectIntersection<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 SelectIntersection<SView,RView>(home,x0,xs,x1,universe);
00140 return ES_OK;
00141 }
00142
00143 template <class SView, class RView>
00144 Actor*
00145 SelectIntersection<SView,RView>::copy(Space* home, bool share) {
00146 return new (home) SelectIntersection<SView,RView>(home,share,*this);
00147 }
00148
00149 template <class SView, class RView>
00150 ExecStatus
00151 SelectIntersection<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 RangesCompl<LubRanges<SView> > candubc(candub);
00198 Iter::Ranges::Inter<GlbRanges<SView>,
00199 RangesCompl<LubRanges<SView> > > inter(x0lb, candubc);
00200
00201
00202
00203
00204
00205
00206 if (candidate.cardMax() < x0.cardMin() ||
00207 inter()) {
00208 ModEvent me = (x1.exclude(home,candidateInd));
00209 loopVar |= me_modified(me);
00210 GECODE_ME_CHECK(me);
00211
00212 iv[j].var.cancel(home,this, PC_SET_ANY);
00213 ++i;
00214 ++vx1ub;
00215 continue;
00216 } else {
00217
00218
00219 if (vx1() && vx1.val()==candidateInd) {
00220
00221 GlbRanges<SView> x0lb(x0);
00222 ModEvent me = candidate.includeI(home,x0lb);
00223 loopVar |= me_modified(me);
00224 GECODE_ME_CHECK(me);
00225
00226 LubRanges<SView> candub(candidate);
00227 me = x0.intersectI(home,candub);
00228 loopVar |= me_modified(me);
00229 GECODE_ME_CHECK(me);
00230 ++vx1;
00231 }
00232 new (&before[j]) LUBndSet(home);
00233 before[j].update(home,sofarBefore);
00234 GlbRanges<SView> clb(candidate);
00235 sofarBefore.intersectI(home,clb);
00236 }
00237
00238 ++vx1ub;
00239 ++i; ++j;
00240 }
00241
00242
00243
00244 for (int k=i; k<n; k++) {
00245 iv[k].var.cancel(home,this, PC_SET_ANY);
00246 }
00247 n = j;
00248 iv.size(n);
00249
00250 if (x1.cardMax()==0) {
00251
00252 {
00253 IntSetRanges uniI(universe);
00254 GECODE_ME_CHECK(x0.includeI(home,uniI));
00255 }
00256 {
00257 IntSetRanges uniI(universe);
00258 GECODE_ME_CHECK(x0.intersectI(home,uniI));
00259 }
00260 for (int i=n; i--;)
00261 before[i].dispose(home);
00262 return ES_SUBSUMED(this,home);
00263 }
00264
00265 {
00266
00267 BndSetRanges sfB(sofarBefore);
00268 ModEvent me = x0.includeI(home,sfB);
00269 loopVar |= me_modified(me);
00270 GECODE_ME_CHECK(me);
00271 }
00272
00273 sofarBefore.dispose(home);
00274
00275 LUBndSet sofarAfter(home, universe);
00276
00277
00278
00279 for (int i=n; i--;) {
00280 if (sofarAfter.size() == 0) break;
00281
00282
00283 BndSetRanges b(before[i]);
00284 BndSetRanges s(sofarAfter);
00285 LubRanges<SView> x0ub(x0);
00286 Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00287 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00288 BndSetRanges>, LubRanges<SView> > diff(inter, x0ub);
00289 if (diff()) {
00290 ModEvent me = (x1.include(home,iv[i].idx));
00291 loopVar |= me_modified(me);
00292 GECODE_ME_CHECK(me);
00293
00294
00295 me = iv[i].var.excludeI(home,diff);
00296 loopVar |= me_modified(me);
00297 GECODE_ME_CHECK(me);
00298 }
00299
00300 GlbRanges<SView> ivilb(iv[i].var);
00301 sofarAfter.intersectI(home,ivilb);
00302 before[i].dispose(home);
00303 }
00304 sofarAfter.dispose(home);
00305
00306 } while (loopVar);
00307
00308
00309 if (x1.assigned() && !x0.assigned()) {
00310 int ubsize = x1.lubSize();
00311 if (ubsize > 2) {
00312 assert(ubsize==n);
00313 ViewArray<SView> is(home,ubsize);
00314 for (int i=n; i--;)
00315 is[i]=iv[i].var;
00316 GECODE_REWRITE(this,(RelOp::IntersectionN<SView, SView>
00317 ::post(home,is,x0)));
00318 } else if (ubsize == 2) {
00319 assert(n==2);
00320 SView a = iv[0].var;
00321 SView b = iv[1].var;
00322 GECODE_REWRITE(this,(RelOp::Intersection<SView, SView, SView>
00323 ::post(home,a,b,x0)));
00324 } else if (ubsize == 1) {
00325 assert(n==1);
00326 GECODE_REWRITE(this,(Rel::Eq<SView,SView>::post(home,x0,iv[0].var)));
00327 } else {
00328 GECODE_ME_CHECK(x0.cardMax(home, 0));
00329 return ES_SUBSUMED(this,home);
00330 }
00331 }
00332
00333 bool allAssigned = true;
00334 for (int i=iv.size(); i--;) {
00335 if (!iv[i].var.assigned()) {
00336 allAssigned = false;
00337 break;
00338 }
00339 }
00340 if (x0.assigned() && x1.assigned() && allAssigned) {
00341 return ES_SUBSUMED(this,home);
00342 }
00343
00344 return ES_FIX;
00345 }
00346
00347 }}}
00348
00349