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