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