00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 namespace Gecode { namespace Set { namespace Select {
00025
00026 template <class SView, class RView>
00027 forceinline
00028 SelectIntersection<SView,RView>::
00029 SelectIntersection(Space* home, SView y0,
00030 IdxViewArray<SView>& iv0,
00031 RView y1,
00032 const IntSet& theUniverse)
00033 : Propagator(home, true), universe(theUniverse), x0(y0), iv(iv0), x1(y1) {
00034
00035 x0.subscribe(home,this, PC_SET_ANY);
00036 x1.subscribe(home,this, PC_SET_ANY);
00037 iv.subscribe(home,this, PC_SET_ANY);
00038 }
00039
00040 template <class SView, class RView>
00041 forceinline
00042 SelectIntersection<SView,RView>::
00043 SelectIntersection(Space* home, bool share,
00044 SelectIntersection<SView,RView>& p)
00045 : Propagator(home,share,p) {
00046 x0.update(home,share,p.x0);
00047 x1.update(home,share,p.x1);
00048 iv.update(home,share,p.iv);
00049 universe.update(share,p.universe);
00050 }
00051
00052 template <class SView, class RView>
00053 PropCost
00054 SelectIntersection<SView,RView>::cost(void) const {
00055 return PC_LINEAR_HI;
00056 }
00057
00058 template <class SView, class RView>
00059 SelectIntersection<SView,RView>::~SelectIntersection(void) {
00060 x0.cancel(this, PC_SET_ANY);
00061 x1.cancel(this, PC_SET_ANY);
00062 iv.cancel(this,PC_SET_ANY);
00063 }
00064
00065 template <class SView, class RView>
00066 ExecStatus
00067 SelectIntersection<SView,RView>::
00068 post(Space* home, SView x0, IdxViewArray<SView>& xs,
00069 RView x1, const IntSet& universe) {
00070 int n = xs.size();
00071
00072
00073 Iter::Ranges::Singleton s(0, n-1);
00074 GECODE_ME_CHECK(x1.intersectI(home,s));
00075 (void) new (home)
00076 SelectIntersection<SView,RView>(home,x0,xs,x1,universe);
00077 return ES_OK;
00078 }
00079
00080 template <class SView, class RView>
00081 Actor*
00082 SelectIntersection<SView,RView>::copy(Space* home, bool share) {
00083 return new (home) SelectIntersection<SView,RView>(home,share,*this);
00084 }
00085
00086 template <class SView, class RView>
00087 ExecStatus
00088 SelectIntersection<SView,RView>::propagate(Space* home) {
00089 int n = iv.size();
00090
00091 bool loopVar;
00092 do {
00093 loopVar = false;
00094
00095
00096
00097 LubRanges<RView> x1ub(x1);
00098 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00099 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00100 vx1ub(x1ubc);
00101
00102 GlbRanges<RView> x1lb(x1);
00103 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00104 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00105 vx1(x1lbc);
00106
00107
00108
00109
00110
00111
00112 LUBndSet sofarBefore(home,universe);
00113 GECODE_AUTOARRAY(LUBndSet, before, n);
00114
00115 int j = 0;
00116 int i = 0;
00117 while ( vx1ub() ) {
00118
00119
00120 if (iv[i].idx < vx1ub.val()) {
00121 iv[i].var.cancel(this, PC_SET_ANY);
00122 ++i;
00123 continue;
00124 }
00125 assert(iv[i].idx == vx1ub.val());
00126 iv[j] = iv[i];
00127
00128 SView candidate = iv[j].var;
00129 int candidateInd = iv[j].idx;
00130
00131
00132 GlbRanges<SView> x0lb(x0);
00133 LubRanges<SView> candub(candidate);
00134 RangesCompl<LubRanges<SView> > candubc(candub);
00135 Iter::Ranges::Inter<GlbRanges<SView>,
00136 RangesCompl<LubRanges<SView> > > inter(x0lb, candubc);
00137
00138
00139
00140
00141
00142
00143 if (candidate.cardMax() < x0.cardMin() ||
00144 inter()) {
00145 ModEvent me = (x1.exclude(home,candidateInd));
00146 loopVar |= me_modified(me);
00147 GECODE_ME_CHECK(me);
00148
00149 iv[j].var.cancel(this, PC_SET_ANY);
00150 ++i;
00151 ++vx1ub;
00152 continue;
00153 } else {
00154
00155
00156 if (vx1() && vx1.val()==candidateInd) {
00157
00158 GlbRanges<SView> x0lb(x0);
00159 ModEvent me = candidate.includeI(home,x0lb);
00160 loopVar |= me_modified(me);
00161 GECODE_ME_CHECK(me);
00162
00163 LubRanges<SView> candub(candidate);
00164 me = x0.intersectI(home,candub);
00165 loopVar |= me_modified(me);
00166 GECODE_ME_CHECK(me);
00167 ++vx1;
00168 }
00169 before[j].init(home);
00170 before[j].update(home,sofarBefore);
00171 GlbRanges<SView> clb(candidate);
00172 sofarBefore.intersectI(home,clb);
00173 }
00174
00175 ++vx1ub;
00176 ++i; ++j;
00177 }
00178
00179
00180
00181 for (int k=i; k<n; k++) {
00182 iv[k].var.cancel(this, PC_SET_ANY);
00183 }
00184 n = j;
00185 iv.size(n);
00186
00187 if (x1.cardMax()==0) {
00188
00189 {
00190 IntSetRanges uniI(universe);
00191 GECODE_ME_CHECK(x0.includeI(home,uniI));
00192 }
00193 {
00194 IntSetRanges uniI(universe);
00195 GECODE_ME_CHECK(x0.intersectI(home,uniI));
00196 }
00197 for (int i=n; i--;)
00198 before[i].dispose(home);
00199 return ES_SUBSUMED;
00200 }
00201
00202 {
00203
00204 BndSetRanges sfB(sofarBefore);
00205 ModEvent me = x0.includeI(home,sfB);
00206 loopVar |= me_modified(me);
00207 GECODE_ME_CHECK(me);
00208 }
00209
00210 sofarBefore.dispose(home);
00211
00212 LUBndSet sofarAfter(home, universe);
00213
00214
00215
00216 for (int i=n; i--;) {
00217 if (sofarAfter.size() == 0) break;
00218
00219
00220 BndSetRanges b(before[i]);
00221 BndSetRanges s(sofarAfter);
00222 LubRanges<SView> x0ub(x0);
00223 Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s);
00224 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00225 BndSetRanges>, LubRanges<SView> > diff(inter, x0ub);
00226 if (diff()) {
00227 ModEvent me = (x1.include(home,iv[i].idx));
00228 loopVar |= me_modified(me);
00229 GECODE_ME_CHECK(me);
00230
00231
00232 me = iv[i].var.excludeI(home,diff);
00233 loopVar |= me_modified(me);
00234 GECODE_ME_CHECK(me);
00235 }
00236
00237 GlbRanges<SView> ivilb(iv[i].var);
00238 sofarAfter.intersectI(home,ivilb);
00239 before[i].dispose(home);
00240 }
00241 sofarAfter.dispose(home);
00242
00243 } while(loopVar);
00244
00245
00246 if(x1.assigned() && !x0.assigned()) {
00247 int ubsize = x1.lubSize();
00248 if (ubsize > 2) {
00249 assert(ubsize==n);
00250 ViewArray<SView> is(home,ubsize);
00251 for (int i=n; i--;) {
00252 is[i] = iv[i].var;
00253 }
00254 GECODE_ES_CHECK((RelOp::IntersectionN<SView, SView>
00255 ::post(home,is,x0)));
00256 return ES_SUBSUMED;
00257
00258 } else if (ubsize == 2) {
00259 assert(n==2);
00260 SView a = iv[0].var;
00261 SView b = iv[1].var;
00262
00263 GECODE_ES_CHECK((RelOp::Intersection<SView, SView, SView>
00264 ::post(home,a,b,x0)));
00265 return ES_SUBSUMED;
00266 } else if (ubsize == 1) {
00267 assert(n==1);
00268 GECODE_ES_CHECK(
00269 (Rel::Eq<SView,SView>::post(home,x0,iv[0].var)));
00270 return ES_SUBSUMED;
00271 } else {
00272 GECODE_ME_CHECK(x0.exclude(home,Limits::Set::int_min,
00273 Limits::Set::int_max));
00274 return ES_SUBSUMED;
00275 }
00276 }
00277
00278 bool allAssigned = true;
00279 for (int i=iv.size(); i--;) {
00280 if (!iv[i].var.assigned()) {
00281 allAssigned = false;
00282 break;
00283 }
00284 }
00285 if (x0.assigned() && x1.assigned() && allAssigned) {
00286 return ES_SUBSUMED;
00287 }
00288
00289 return ES_FIX;
00290 }
00291
00292 }}}
00293
00294