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 ElementUnionConst<SView,RView>::
00045 ElementUnionConst(Home home, SView y0,
00046 SharedArray<IntSet>& iv0,
00047 RView y1)
00048 : Propagator(home), x0(y0), iv(iv0), x1(y1) {
00049 home.notice(*this,AP_DISPOSE);
00050 x0.subscribe(home,*this, PC_SET_ANY);
00051 x1.subscribe(home,*this, PC_SET_ANY);
00052 }
00053
00054 template<class SView, class RView>
00055 forceinline
00056 ElementUnionConst<SView,RView>::
00057 ElementUnionConst(Space& home, bool share,
00058 ElementUnionConst<SView,RView>& p)
00059 : Propagator(home,share,p) {
00060 x0.update(home,share,p.x0);
00061 x1.update(home,share,p.x1);
00062 iv.update(home,share,p.iv);
00063 }
00064
00065 template<class SView, class RView>
00066 PropCost
00067 ElementUnionConst<SView,RView>::cost(const Space&, const ModEventDelta&) const {
00068 return PropCost::linear(PropCost::HI, iv.size()+2);
00069 }
00070
00071 template<class SView, class RView>
00072 forceinline size_t
00073 ElementUnionConst<SView,RView>::dispose(Space& home) {
00074 home.ignore(*this,AP_DISPOSE);
00075 if (!home.failed()) {
00076 x0.cancel(home,*this, PC_SET_ANY);
00077 x1.cancel(home,*this, PC_SET_ANY);
00078 }
00079 iv.~SharedArray();
00080 (void) Propagator::dispose(home);
00081 return sizeof(*this);
00082 }
00083
00084 template<class SView, class RView>
00085 ExecStatus
00086 ElementUnionConst<SView,RView>::
00087 post(Home home, SView x0, SharedArray<IntSet>& xs,
00088 RView x1) {
00089 int n = xs.size();
00090
00091
00092 Iter::Ranges::Singleton s(0, n-1);
00093 GECODE_ME_CHECK(x1.intersectI(home,s));
00094 (void) new (home)
00095 ElementUnionConst<SView,RView>(home,x0,xs,x1);
00096 return ES_OK;
00097 }
00098
00099 template<class SView, class RView>
00100 Actor*
00101 ElementUnionConst<SView,RView>::copy(Space& home, bool share) {
00102 return new (home) ElementUnionConst<SView,RView>(home,share,*this);
00103 }
00104
00105 template<class SView, class RView>
00106 ExecStatus
00107 ElementUnionConst<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00108 Region r(home);
00109 int n = iv.size();
00110
00111 bool* stillSelected = r.alloc<bool>(n);
00112
00113 bool loopVar;
00114 do {
00115 loopVar = false;
00116 for (int i=n; i--;)
00117 stillSelected[i] = false;
00118
00119
00120
00121 LubRanges<RView> x1ub(x1);
00122 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub);
00123 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > >
00124 vx1ub(x1ubc);
00125
00126 GlbRanges<RView> x1lb(x1);
00127 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb);
00128 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > >
00129 vx1(x1lbc);
00130
00131
00132
00133
00134
00135 GLBndSet sofarBefore(home);
00136 LUBndSet selectedInter(home, IntSet (Limits::min,
00137 Limits::max));
00138 GLBndSet* before =
00139 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
00140
00141 int i = 0;
00142
00143 unsigned int maxCard = 0;
00144 unsigned int minCard = Limits::card;
00145
00146 while ( vx1ub() ) {
00147
00148 i = vx1ub.val();
00149 IntSetRanges candCardR(iv[i]);
00150 unsigned int candidateCard = Iter::Ranges::size(candCardR);
00151
00152 IntSetRanges candlb(iv[i]);
00153 LubRanges<SView> x0ub(x0);
00154 Iter::Ranges::Diff<IntSetRanges,
00155 LubRanges<SView> > diff(candlb, x0ub);
00156
00157 bool selectSingleInconsistent = false;
00158 if (x1.cardMax() <= 1) {
00159 GlbRanges<SView> x0lb(x0);
00160 IntSetRanges candub(iv[i]);
00161 Iter::Ranges::Diff<GlbRanges<SView>,
00162 IntSetRanges > diff2(x0lb, candub);
00163 selectSingleInconsistent = diff2() || candidateCard < x0.cardMin();
00164 }
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174 if (selectSingleInconsistent ||
00175 candidateCard > x0.cardMax() ||
00176 diff()) {
00177 ModEvent me = (x1.exclude(home,i));
00178 loopVar |= me_modified(me);
00179 GECODE_ME_CHECK(me);
00180 } else {
00181 stillSelected[i] = true;
00182
00183
00184 if (vx1() && vx1.val()==i) {
00185
00186
00187 IntSetRanges candlb(iv[i]);
00188 ModEvent me = x0.includeI(home,candlb);
00189 loopVar |= me_modified(me);
00190 GECODE_ME_CHECK(me);
00191 ++vx1;
00192 }
00193 new (&before[i]) GLBndSet(home);
00194 before[i].update(home,sofarBefore);
00195 IntSetRanges cub(iv[i]);
00196 sofarBefore.includeI(home,cub);
00197 IntSetRanges clb(iv[i]);
00198 selectedInter.intersectI(home,clb);
00199 maxCard = std::max(maxCard, candidateCard);
00200 minCard = std::min(minCard, candidateCard);
00201 }
00202
00203 ++vx1ub;
00204 }
00205
00206 if (x1.cardMax()==0) {
00207
00208 {
00209 GECODE_ME_CHECK(x0.cardMax(home,0));
00210 }
00211 for (int i=n; i--;)
00212 if (stillSelected[i])
00213 before[i].dispose(home);
00214 selectedInter.dispose(home);
00215 sofarBefore.dispose(home);
00216 return home.ES_SUBSUMED(*this);
00217 }
00218
00219 if (x1.cardMin() > 0) {
00220
00221
00222 BndSetRanges si(selectedInter);
00223 ModEvent me = x0.includeI(home, si);
00224 loopVar |= me_modified(me);
00225 GECODE_ME_CHECK(me);
00226 me = x0.cardMin(home, minCard);
00227 loopVar |= me_modified(me);
00228 GECODE_ME_CHECK(me);
00229 }
00230 selectedInter.dispose(home);
00231
00232 if (x1.cardMax() <= 1) {
00233 ModEvent me = x0.cardMax(home, maxCard);
00234 loopVar |= me_modified(me);
00235 GECODE_ME_CHECK(me);
00236 }
00237
00238 {
00239
00240 BndSetRanges sfB(sofarBefore);
00241 ModEvent me = x0.intersectI(home,sfB);
00242 loopVar |= me_modified(me);
00243 GECODE_ME_CHECK(me);
00244 }
00245
00246 sofarBefore.dispose(home);
00247
00248 GLBndSet sofarAfter(home);
00249
00250
00251
00252 for (int i=n; i--;) {
00253 if (!stillSelected[i])
00254 continue;
00255 BndSetRanges b(before[i]);
00256 BndSetRanges s(sofarAfter);
00257 GlbRanges<SView> x0lb(x0);
00258 Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s);
00259 Iter::Ranges::Diff<GlbRanges<SView>,
00260 Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter);
00261 if (diff()) {
00262 ModEvent me = (x1.include(home,i));
00263 loopVar |= me_modified(me);
00264 GECODE_ME_CHECK(me);
00265
00266
00267 IntSetRanges ivi(iv[i]);
00268 if (!Iter::Ranges::subset(diff, ivi))
00269 GECODE_ME_CHECK(ME_SET_FAILED);
00270 }
00271
00272 IntSetRanges iviub(iv[i]);
00273 sofarAfter.includeI(home,iviub);
00274 before[i].dispose(home);
00275 }
00276 sofarAfter.dispose(home);
00277
00278 } while (loopVar);
00279
00280 if (x0.assigned() || x1.assigned()) {
00281 return home.ES_SUBSUMED(*this);
00282 }
00283
00284 return ES_FIX;
00285 }
00286
00287 }}}
00288
00289